Functions and cardinality

This shows there is no single "biggest infinity" — from any set, however large, you can always build a strictly larger one just by taking its power set. It is the theorem that makes an infinite hierarchy of infinities unavoidable, and its diagonal-argument proof technique is the direct ancestor of the arguments used to show some problems are uncomputable.

Suppose, for contradiction, that there is a surjection $f : A \to \mathcal{P}(A)$; we will derive a contradiction, which shows no such surjection can exist.

Define the "diagonal" set $D = \{x \in A : x \notin f(x)\}$: it collects every element of $A$ that is not a member of its own image under $f$. Since $D$ is a subset of $A$, it is an element of $\mathcal{P}(A)$.

Because $f$ is assumed surjective, there must be some $a_0 \in A$ with $f(a_0) = D$. Now ask the deciding question: is $a_0 \in D$?

If $a_0 \in D$, then by the definition of $D$, $a_0 \notin f(a_0)$; but $f(a_0) = D$, so this says $a_0 \notin D$ — a contradiction. If instead $a_0 \notin D$, then by the definition of $D$ (which excludes exactly the elements with $a_0 \in f(a_0)$), this forces $a_0 \in f(a_0) = D$ — again a contradiction.

Either way we reach a contradiction, so no surjection $f : A \to \mathcal{P}(A)$ can exist. Combined with the injection $x \mapsto \{x\}$ from $A$ into $\mathcal{P}(A)$, this gives exactly $|A| < |\mathcal{P}(A)|$.

Comparing cardinalities via injections only (each set fits inside the other) already forces the sets to have exactly the same size, just as with finite sets. This lets us prove $|A|=|B|$ by building two easy one-directional embeddings instead of one hard direct bijection — this is exactly how the examples below show intervals like $[0,1]$ and $(0,1)$ have the same cardinality.

Let $f : A \to B$ and $g : B \to A$ be the two given injections. The idea is to trace, for each element, the chain of ancestors obtained by repeatedly undoing $f$ and $g$, and to build the final bijection piece by piece depending on where each chain "starts".

For $a \in A$, define its backward chain $a, g^{-1}(a), f^{-1}(g^{-1}(a)), \ldots$, continuing as long as the needed inverse is defined, and symmetrically for $b \in B$. Every element's chain either goes back forever, or stops at an element of $A$ with no $g$-preimage, or stops at an element of $B$ with no $f$-preimage. This partitions $A$ into three parts $A_A$ (chain stops in $A$), $A_B$ (chain stops in $B$), $A_\infty$ (chain never stops), and likewise partitions $B$ into $B_A, B_B, B_\infty$.

On chains that stop in $A$ or never stop, $f$ itself already gives a bijection from that part of $A$ onto the corresponding part of $B$ (since these elements were reached by injections and nothing "runs out" on the $B$ side first). On chains that stop in $B$, it is $g$ that gives a bijection from the corresponding part of $B$ back onto that part of $A$, so its inverse $g^{-1}$ gives a bijection from that part of $A$ onto that part of $B$.

Define $h : A \to B$ by $h(a) = f(a)$ if $a \in A_A \cup A_\infty$, and $h(a) = g^{-1}(a)$ if $a \in A_B$. Since the three pieces are disjoint and each piece maps bijectively onto its matching piece of $B$ ($f$ onto $B_A \cup B_\infty$, $g^{-1}$ onto $B_B$), the combined map $h$ is a bijection from all of $A$ onto all of $B$, proving $|A|=|B|$.