Set Theory

Question 1

Intersection of A and B

Answer 1

A n B = {x=u | x in A ^ x in B}

Question 2

Union of A and B

Answer 2

A U B = {x=u | x in A v x in B}

Question 3

Difference of A minus B

Answer 3

A - B = {x=u | x in A ^ x not in B}

Question 4

Symmetric difference of A and B

Answer 4

A delta B = {x=u | x in A exclusive v x in B}

Question 5

Complement of A in U

Answer 5

A bar = {x=u | x not in A}

Question 6

Set

Answer 6

An unordered list of objects called elements. An element cannot appear twice in a set.

Question 7

Cardinality

Answer 7

|A|, The number of elements in A

Question 8

Finite set

Answer 8

A set is finite if we can label them 1, 2, … , n

Question 9

Subset A of set B

Answer 9

A set comprised only of elements of B.
A sub\eq = Vx in u [x in A -> x in B]

Question 10

Proper subset A of set B

Answer 10

A subset that of B, where B has elements that are not also in A.
A sub = Vx in u [x in A -> x in B ^ Ey in (B - A)]

Question 11

Equal sets A and B

Answer 11

IFF A sub\eq B and B sub\eq A

Question 12

Family of sets

Answer 12

A set whose elements themselves are sets in u.

Question 13

Power set of A

Answer 13

P(A), is the set of all subsets of A

Question 14

|P(A)|, Cardinality of Power set of A

Answer 14

2^(|A|)

Question 15

Cartesian Product of A and B

Answer 15

A x B = {(a,b) | a in A ^ b in B}.
These elements (a,b) are called ordered pairs.

Question 16

|A x B|, Cardinality of Cartesian Product of
A and B

Answer 16

|A|*|B|

Question 17

Disjoint sets A and B

Answer 17

A n B = empty set.
They have no elements in common

Question 18

Partition F of A, where F contains subsets of A excluding the empty set.

Answer 18

1) F is pairwise disjoint (We didn’t put anything twice)
2) UF = A (We didn’t miss any)

Question 19

One-to-One (Injective)

Answer 19

Vx1 in X1,Vx2 in X2[f(x1) = f(x2) -> x1 = x2],
If the two outputs are the same, then the two inputs must be the same.

Question 20

Onto (Subjective)

Answer 20

Vy in Y,Ex in X[f(x) = y],
For every pair in the co-domain, there exists something in the domain that points to it.

Question 21

Bijection

Answer 21

A function is a bijection if it is both one-to-one and onto, or if it has an inverse

Question 22

Prove inverse, f(x)^-1

Answer 22

f(f(x))^-1 = x and f(f(x)^-1) = x

Question 23

Composition gof, where f: A -> B, g: B -> C

Answer 23

gof: A -> C via (a,c) in gof IFF Eb in B[(a,b) in f ^ (b,c) in g]

Question 24

Composition properties

Answer 24

1) If f,g are both one-to-one, then so is gof
2) if f,g are both onto, then so is gof
3) if f,g are bijections, then gof is a bijection

Question 25

Cardinality redefinition

Answer 25

Set A has cardinality n IFF E bijection f: {1, 2, … n} -> A

Question 26

Countability

Answer 26

Set A is countable IFF E bijection f: N -> A (countably infinite).
Note: Z is countable, N x N is countable, Q is countable, R is NOT countable

Question 27

Direct Proof

Answer 27

p -> q

Question 28

Contrapositive (Indirect) Proof

Answer 28

notq -> notp

Question 29

Converse

Answer 29

q -> p

Question 30

Inverse

Answer 30

notp -> notq

Question 31

Even integer

Answer 31

Ek in Z[n = 2k]

Question 32

Odd integer

Answer 32

Ek in Z[n = 2k + 1]

Question 33

Same parity

Answer 33

both numbers are even or boh numbers are odd

Question 34

Rational number

Answer 34

Ep in Z,Eq in Z[x = p/q ^ q not/eq 0]

Question 35

d|n, “d divides n”

Answer 35

Ek in Z[n = dk ^ d not/eq 0]

Question 36

P is Prime

Answer 36

P>1 ^ Vm in Z,Vn in Z[P = mn -> m=1 v n=1]

Question 37

P is composite

Answer 37

P>1 ^ Em in Z,En in Z[P = mn ^ 1<m,n<P]

Question 38

UF, where F is a family of sets

Answer 38

The set of elements that appear in at least one set in F.
ex,
F = {{1},{1,2},{1,2,3,4}}
UF = {1,2,3,4}

Question 39

nF, where F is a family of sets

Answer 39

The set of elements that appear in ALL sets in F.
ex,
F = {{1},{1,2},{1,2,3,4}}
nF = {1}
Note: If there is not an element that appears in every set of F, then nF = {empty set}

Question 40

Empty Set

Answer 40

The empty set is a subset of all sets