Set Theory Flashcards
Intersection of A and B
A n B = {x=u | x in A ^ x in B}
Union of A and B
A U B = {x=u | x in A v x in B}
Difference of A minus B
A - B = {x=u | x in A ^ x not in B}
Symmetric difference of A and B
A delta B = {x=u | x in A exclusive v x in B}
Complement of A in U
A bar = {x=u | x not in A}
Set
An unordered list of objects called elements. An element cannot appear twice in a set.
Cardinality
|A|, The number of elements in A
Finite set
A set is finite if we can label them 1, 2, … , n
Subset A of set B
A set comprised only of elements of B.
A sub\eq = Vx in u [x in A -> x in B]
Proper subset A of set B
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)]
Equal sets A and B
IFF A sub\eq B and B sub\eq A
Family of sets
A set whose elements themselves are sets in u.
Power set of A
P(A), is the set of all subsets of A
|P(A)|, Cardinality of Power set of A
2^(|A|)
Cartesian Product of A and B
A x B = {(a,b) | a in A ^ b in B}.
These elements (a,b) are called ordered pairs.
|A x B|, Cardinality of Cartesian Product of
A and B
|A|*|B|
Disjoint sets A and B
A n B = empty set.
They have no elements in common
Partition F of A, where F contains subsets of A excluding the empty set.
1) F is pairwise disjoint (We didn’t put anything twice)
2) UF = A (We didn’t miss any)
One-to-One (Injective)
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.
Onto (Subjective)
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.
Bijection
A function is a bijection if it is both one-to-one and onto, or if it has an inverse
Prove inverse, f(x)^-1
f(f(x))^-1 = x and f(f(x)^-1) = x
Composition gof, where f: A -> B, g: B -> C
gof: A -> C via (a,c) in gof IFF Eb in B[(a,b) in f ^ (b,c) in g]
Composition properties
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
Cardinality redefinition
Set A has cardinality n IFF E bijection f: {1, 2, … n} -> A
Countability
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
Direct Proof
p -> q
Contrapositive (Indirect) Proof
notq -> notp
Converse
q -> p
Inverse
notp -> notq
Even integer
Ek in Z[n = 2k]
Odd integer
Ek in Z[n = 2k + 1]
Same parity
both numbers are even or boh numbers are odd
Rational number
Ep in Z,Eq in Z[x = p/q ^ q not/eq 0]
d|n, “d divides n”
Ek in Z[n = dk ^ d not/eq 0]
P is Prime
P>1 ^ Vm in Z,Vn in Z[P = mn -> m=1 v n=1]
P is composite
P>1 ^ Em in Z,En in Z[P = mn ^ 1<m,n<P]
UF, where F is a family of sets
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}
nF, where F is a family of sets
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}
Empty Set
The empty set is a subset of all sets
