Sets, Relations, Functions, and Cardinality

Question 1

What are “sets?”

Answer 1

Sets is a mathematical notion

Considered by some to be the foundation of all mathematics: “All mathematics is (just) set theory”

Things with elements have certain properties:

x is an element of the set A

x ∈ A

• Uordered collection of objects
• Not “boxes” - some have infinite sets, and sets that contain themselves

Question 2

What is an extensional presentation of a set?

Answer 2

List the elements

eg. {1, 2, 3}

Question 3

What is an intensional presentation of a set?

Answer 3

Given a set A, and a property P,

{x ∈ A | P(x)} is “the set of all elements of A that satisfies P

Ex:

• {x ∈ ℕ | x < 10}
• {x ∈ ℕ | x is prime}
• {x ∈ ℕ | Ǝy ∈ IN : x = 2y}

Russell’s Paradox: S = {x | x ∉ x}. Is S ∈ S?

Question 4

Sets for “x is an element of the set A”

Answer 4

x ∈ A

Question 5

How do you write that “A is a subset of B:”

Answer 5

A⊆B <=>_df ∀x : (x ∈ A) → (x ∈ B)

A set A is a subset of another set B if all elements of the set A are elements of the set B. In other words, the set A is contained inside the set B. The subset relationship is denoted as A⊆B.

For example, if A is the set {♢,♡,♣,♠} and B is the set {♢,△,♡,♣,♠}, then A⊆B but B⊄A.

Since B contains elements not in A, we can say that A is a proper subset of B. Or if I1 is the interval [0,2] and I2 is the interval [0,1], then I2⊂I1.

Question 6

How do you write that “All elements in A are also in B:”

Answer 6

A = B <=>_df (A ⊆ B) ∧ (B ⊆ A)

Question 7

How do you write “A is a proper subset of B:”

Answer 7

A ⊂ B <=>df (A ⊂ B) ∧ (A ≠ B)

A proper subset of a set A is a subset of A that is not equal to A. In other words, if B is a proper subset of A, then all elements of B are in A but A contains at least one element that is not in B.

For example, if A={1,3,5} then B={1,5} is a proper subset of AA. The set C={1,3,5} is a subset of AA, but it is not a proper subset of AA since C=A. The set D={1,4} is not even a subset of A, since 4 is not an element of A.

Question 8

How to indicate that something is an empty set:

Answer 8

∅, {}

P(a, b) = {∅, {∅}, {a}, {b}, {a, ∅}, {b,∅}, {a, b}, {a, b, ∅}}

Question 9

What is an intersection?

Answer 9

A⋂B

Contains all and only the elements of both A and B

Question 10

What is a union?

Answer 10

A⋃B

Contains all and only the elements of A, or B, or both

Question 11

What is a complement of set A?

Answer 11

Denoted A¯:

Contains all those elements of the universe of discourse that are not in A

Question 12

What is a powerset (of A)?

Answer 12

P(A), “powerset of A,” the set of all the subsets of A

• Defined in terms of sets

Question 13

What is an ordered pair / n-tuple?

Answer 13

A collection with n elements where the order matters

< a, b >, < a, a, b >

• Rather than introducing ordered pairs as another primitive notion, we can define them as sets:

< a, b > <=>_df {{a}, {a, b}}

*a first to illustrate the order

Question 14

What is the cross product?

Answer 14

A x B, “cross product or Cartesian product of A and B,” the set of all ordered pairs < a,b > consisting of the elements a ∈ A and b ∈ B

A x B <=>df { < x, y > | x ∈ A and y ∈ B}

Show that < a, b > = < c, d > iff a = c and b = d

Question 15

Formula to determine the number of formations in the powerset of A with n elements?

Answer 15

2ⁿ

Question 16

What are the elements of a relation?

What is a relation?

Answer 16

What are the elements of a relation? Ordered pairs!

What is a relation? A relation is a set of ordered pairs

Question 17

How many relations are there between two sets *A* with *n* elements, and *B* with
m elements (where *n,m* ∈ *IN* )?

Answer 17

2^{(n x m)}

Question 18

What are the writing convention, domain, and range for < a, b> ∈ R?

Answer 18

R(a, b) or aRb

• Domain: R: { a | there is some b, such that < a, b> ∈ R }
• Range R: { b | there is some a, such that < a, b> ∈ R }

Question 19

What is the layman’s definition of a function?

Answer 19

Rules that connect inputs to outputs

Question 20

What is the definition of a function in the set-theoretic view?

Answer 20

A function f : A -> B from A (domain) to B (range) [⊆ codomain] is a binary relation R_f on A and B, such that:

(1) The relation is single-valued

• Every element in the domain is paired with just one element in the range

(2) The domain of R_f is A (except partial functions)

• Write f(a) = b rather than Rf(a, b)

Question 21

What is an injective (one-one) function?

Answer 21

If for each y in the range of f there is only one x,

such that f(x) = y or (< x, y> ∈ f)

If a, a’ ∈ A and a ≠ a’ then f(a) ≠ f(a’)

• Assume f(a) = f(a’)
• Show: a = a’

Question 22

What is a surjective (onto) function?

Answer 22

If the range of f is equal to the codomain

range = codomain

Question 23

What is the difference between the range and codomain?

Answer 23

The codomain is the set of all possible values which can come out as a result but the range is the set of values which actually comes out.

Question 24

What is a bijective (one-to-one correspondence) function?

Answer 24

Injective and surjective

Composition: For f : A -> B and g : B -> C, f * g : A -> C**, such that g* f(a) = g(f(a))

Inverse function: f * f^-1 = id

Question 25

What is a powerset of the set {87, Ø, tree}

Answer 25

P{87, Ø, tree} = {Ø, {Ø}, {87}, {tree}, {Ø, 87}, {Ø, tree}, {Ø, 87, tree}, {87, tree}}