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