Two sets $A, B$ have the same cardinality $|A| = |B|$ iff there exists a bijection $A \to B$. Cardinalities form a linearly ordered hierarchy (under AC).

Examples:

• $|\mathbb N| = \aleph_0$ — countably infinite.
• $|\mathbb Z| = |\mathbb Q| = \aleph_0$ — listable.
• $|\mathbb R| = 2^{\aleph_0} = \mathfrak c$ — uncountable.

Cantor's diagonal argument: suppose $\mathbb R \cap [0,1]$ were countable. List the reals as $r_1, r_2, \ldots$ with decimal expansions. Construct $r^*$ by taking the $n$-th decimal of $r_n$ and flipping it. Then $r^*$ differs from every $r_n$ — contradiction. So $\mathbb R$ is uncountable.

For any set $A$, $|A| < |2^A|$ (the power set is strictly larger). Iterating gives an infinite tower $\aleph_0 < 2^{\aleph_0} < 2^{2^{\aleph_0}} < \cdots$. The continuum hypothesis: is there a cardinality strictly between $\aleph_0$ and $2^{\aleph_0}$? Gödel + Cohen showed it is independent of ZFC.

Interactive: Cantor's diagonal