# 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:

1. No intersect: |A ∪ B| = |A| + |B|
2. overlap (inclusion-exclusion principle): |A ∪ B| = |A| + |B| − |A ∩ B|

1. |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.