Set
definition: A set is an unordered collection of objects
{1, 2, 3} and {1, 2, 3, 2} are same set
{57} != 57
- nothing in set: ∅
- can contain objects of more than one type
- the empty set is a subset of any set
Cardinality
the number of (different) objects in a set
symbol by: |A|
Size:
- No intersect: |A ∪ B| = |A| + |B|
overlap (inclusion-exclusion principle): |A ∪ B| = |A| + |B| − |A ∩ B|
- |A ∪ B ∪ C| = |A| + |B| + |C| − |B ∩ C| − |A ∩ B| − |A ∩ C| + |A ∩ B ∩ C|
Subset
If every element of A is also in B, we say A is subset of B
Symbol by: A ⊆ B
Proper subset: A is a subset to B but not equals to B: A ⊂ B
- reverse ⊇
Tuple
- order of values in a tuple matters and duplicate elements don’t magically collapse
(1, 2, 2, 3) != (1, 2, 3)
(1, 2, 2, 3) != (2, 2, 1, 3)
- tuple must contain at least two elements
(x) should be write as x
- can contain objects of more than one type
Operation
Intersection: set containing all objects that are in both A and B
$$ A ∩ B $$
- if no set have no intersection, then, the two sets are disjoint
Union: set containing all objects that are in one (or both) of sets
$$ M ∪ P $$
Difference: The set difference of A contains all the objects that are in A but not in B
$$ A - B $$
Complement: contains all objects that aren’t in A
$$ \overline A $$
- Universal set: represent by
U, contains all the objects of the sort(s) you are discussing
if our universe U is all integers, and A contains all the multiples of 3, then the complement of A is all the integers whose remainder mod 3 is either 1 or 2.
- De 'Morgan Law:
$$ \overline{A\cup B}=\overline{A}\cap\overline{B} $$
Cartesian product: contains all ordered pairs (x, y) where x is in A and y is in B
$$ A × B = {(x, y) | x ∈ A \quad\textrm{and}\quad y ∈ B} $$
For example, if A = {a, b} and B = {1, 2}, then
$$ A × B = {(a, 1),(a, 2),(b, 1),(b, 2)} $$
$$ B × A = {(1, a),(2, a),(1, b),(2, b)} $$
- order matters for Cartesian products
- for two set A, B, suppose|A| = n and |B| = q, so |A × B| = nq
Proof
proof subset:
Let sets A and B be defined as above.
Let x be an element of A.
[missing details]
So x is an element of B.
Since x was arbitrarily chosen,
we’ve shown that any element of A is also an element of B. So A is a subset of B.
proof abstract:
For any sets A, B, and C, if A × B ⊆ A × C and A 6= ∅, then B ⊆ C.
Suppose that A, B, and C are sets and suppose that A × B ⊆ A × C and A 6= ∅. We need to show that B ⊆ C.
So let’s choose some x ∈ B. Since A 6= ∅, we can choose an element t from A.
Then (t, x) ∈ A × B by the definition of Cartesian product. Since (t, x) ∈ A × B and A × B ⊆ A × C, we must have that (t, x) ∈ A × C (by the definition of subset).
But then (again by the definition of Cartesian product) x ∈ C. So we’ve shown that if x ∈ B, then x ∈ C. So B ⊆ C, which is what we needed to show.
proof contrapositive:
For any sets A and B, if (A − B) ∪ (B − A) = A ∪ B then A ∩ B = ∅
Proof: Let’s prove the contrapositive. That is, we’ll prove that if A ∩ B != ∅, then (A − B) ∪ (B − A) 6= A ∪ B.
So, let A and B be sets and suppose that A ∩ B != ∅.
Since A ∩ B != ∅, we can choose an element from A ∩ B. Let’s call it x.
Since x is in A ∩ B, x is in both A and B. So x is in A ∪ B. However, since x is in B, x is not in A−B.
Similarly, since x is in A, x is not in B −A. So x is not a member of (A−B)∪(B −A).
This means that (A − B) ∪ (B − A) and A ∪ B cannot be equal, because x is in the second set but not in the first.
