## Franklin's Notes

### Cardinality

Intuitively, cardinality is an attempt to formalize the notion of "sizes" of sets, allowing us to compare which of two sets is "bigger" or "contains more elements". Two sets $A$ and $B$ are said to have the same cardinality if there exists a bijection between them, and this relationship is denoted by $|A|=|B|$ or $\text{card}(A)=\text{card}(B)$. We say that the cardinality of $A$ is "less than or equal to" that of $B$, denoted $|A|\leq |B|$, if there exists an injective function $f:A\to B$ (in other words, if "a copy of $A$ can fit inside of $B$"). We say that the cardinality of $A$ is "strictly less than" that of $B$ if $|A|\leq |B|$ but $|A|\neq |B|$.

The cardinal numbers are an attempt to formalize and treat "sizes" of sets as independent objects. However, cardinalities do not behave the same way as numbers, so the usage of the symbol $\leq$ to refer to cardinality comparisons is sometimes misleading. Inequalities between cardinalities sometimes behave analogously to inequalities between numbers, more or less as we would expect, but there are cases in which they behave differently. Here is a list of some rules governing cardinal inequalities:

• Transitivity: if $|A|\leq |B|$ and $|B|\leq |C|$, then $|A|\leq |C|$. Additionally, if $|A|=|B|$ and $|B|=|C|$, then $|A|=|C|$. Note that if $f:A\to B$ and $g:B\to C$ are injections (bijections), then $g\circ f:A\to C$ is an injection (bijection).

• Cantor-Bernstein Theorem : if $|A|\leq |B|$ and $|B|\leq |A|$, then $|A|=|B|$. The proof of this is non-trivial.

• Trichotomy : assuming the Axiom of Choice , it is true that for any two sets $A$ and $B$, either $|A|>|B|$ or $|A|<|B|$ or else $|A|=|B|$.

• Cantor's Theorem : for any set $A$, $|A| < |2^A|$. That is, every set has strictly "more" subsets than it has elements.