5 sets Flashcards
how to express a set in roster notation?
{x1, x2, …}
how to express a set in set-builder notation?
{x ∈ U : P(x)} or {x ∈ U | P(x)}, where P(x) is a predicate over U
e.g. {x ∈ Z : x is even}
how to express a set in replacement notation?
{t(x) : x ∈ A} or {t(x) | x ∈ A}, where t(x) is a term in variable x
e.g. {x+1 : x ∈ Z}
what is the difference between being a subset and being a proper subset?
subset: A ⊆ B if ∀z (z ∈ A ⇒ z ∈ B)
proper subset: if A ⊆ B and A ≠ B
what is the power set P(A)?
set of all subsets of A
what is the cardinality of a set?
cardinality refers to size and is the number of elements in a set; denoted by |A|
singletons: sets of size 1
what is the cardinality of a power set of a finite set |P(A)|?
theorem 5.2.4:
if A is a finite set, the cardinality of its power set is |P(A)| = 2^|A|
what is an ordered pair?
expression in the form of (x, y)
what is the cartesian product of 2 sets?
when A and B are sets, the cartesian product or A x B (A cross B) is {(x, y) : x ∈ A and y ∈ B}
e.g. {a, b} × {1, 2, 3} = {(a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3)}
keep in mind the cardinality of the product ie
|{a, b} × {1, 2, 3}| = 6 = 2 × 3 = |{a, b}| × |{1, 2, 3}|
what is an ordered n-tuple?
expression in the form of (x1, x2, … , xn)
what is the cartesian product of n number of sets?
let A1, A2, …, An be sets. their cartesian product (A1 x A2 x … An) is {(x1, x2 ,…, xn) : x1 ∈ A1 and x2 ∈ A2 and … and xn ∈ An}
if A is a set, then A^n = A x A x … x A (n many As)
e.g. {0, 1} × {0, 1} × {x , y } = {(0, 0, x ), (0, 0, y ), (0, 1, x ), (0, 1, y ), (1, 0, x ), (1, 0, y ), (1, 1, x ), (1, 1, y)}
what are the boolean operations of sets?
union: A ∪ B = {x : x ∈ A or x ∈ B}
intersection: A ∩ B = {x : x ∈ A and x ∈ B}
complement: A \ B = {x : x ∈ A and x ̸∈ B} (read as A – B)
the complement of set B in universal set U is B (B with a line on top of it) or B^c and is defined by B line = U \ B
what does it mean for 2 sets to be disjoint?
A ∩ B = ∅
what does it mean for sets to be pairwise disjoint or mutually disjoint?
sets A1, A2, . . . , An are pairwise disjoint or mutually disjoint if Ai ∩ Aj = ∅ for all distinct i, j ∈ {1, 2, …, n}
how do you find the cardinality of disjoint sets?
theorem 5.3.12
|A ∪ B| = |A| + |B|
|A1 ∪ A2 ∪ ··· ∪ An|= |A1| + |A2| + ··· + |An|
theorem 5.3.13 (inclusion-exclusion principle)
for all finite sets A, B, |A ∪ B| = |A| + |B| − |A ∩ B|
as disjoint sets A ∩ B = ∅, it ends up being the sum of cardinalities
