Discrete Math: Sets, Venn Diagrams & Functions

A \cup B : in A or B (or both) A \cap B : in both A and B A - B : in A but not B A^c : in the universe but not in A

Subset: every element of A is in B (A may equal B). Proper subset: A is a subset of B and A ≠ B.

The set of all subsets of A , including \varnothing and A . If |A| = n , then |\mathcal{P}(A)| = 2^n .

16

No. \varnothing has no elements; \{\varnothing\} has one element (the empty set). The empty set is a subset of every set.

|A \cup B| = |A| + |B| - |A \cap B|

|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|

45

(A \cup B)^c = A^c \cap B^c (A \cap B)^c = A^c \cup B^c

All ordered pairs (a, b) with a \in A , b \in B . |A \times B| = |A| \cdot |B| .

Sets with no elements in common: A \cap B = \varnothing

A \,\triangle\, B = (A - B) \cup (B - A) : elements in exactly one of the two sets

\mathbb{N} naturals, \mathbb{Z} integers, \mathbb{Q} rationals, \mathbb{R} reals, \mathbb{C} complex numbers

\mathbb{Z} and \mathbb{Q} are countably infinite. \mathbb{R} is uncountable (Cantor's diagonal argument).

Injective (one-to-one): different inputs give different outputs. Surjective (onto): every element of the codomain is hit. Bijective: both, so the function has an inverse.