Cantor’s Infinity — cantor.plnt.earth

Abstract

Cantor proved that no set can be put in bijection with its power set and that the real numbers are uncountable. This page presents the diagonal method, the power-set theorem, the Cantor–Bernstein–Schröder (CBS) theorem, and the link to the Well-Ordering Theorem (via AC).

1. Power-Set Theorem
2. Uncountability of ℝ
3. Cantor–Bernstein–Schröder
4. Well-Ordering Thread
References

1. Power-Set Theorem

Cantor’s Theorem. For every set A, there is no surjection A → 𝒫(A). Hence |A| < |𝒫(A)|.

Proof. Assume f: A → 𝒫(A) is surjective. Let B = {x ∈ A : x ∉ f(x)}. For b with f(b)=B, if b ∈ B then b ∉ f(b)=B; if b ∉ B then b ∈ f(b)=B. Contradiction. ∎

2. Uncountability of ℝ

Theorem. |ℝ| = |𝒫(ℕ)| > |ℕ|.

Sketch. List binary expansions; flip the n-th digit of the n-th row to form a new sequence; it differs from every listed one at position n. ∎

Figure — Cantor’s diagonal on a toy 5×5 grid.

3. Cantor–Bernstein–Schröder

CBS. If there are injections f: A → B and g: B → A, then |A| = |B| (there is a bijection).

Sketch. Decompose into chains under f and g; pair elements along chains to build a bijection. ∎

4. Well-Ordering Thread

Cantor conjectured that every set can be well-ordered; Zermelo proved it using the Axiom of Choice (AC). In ZFC this is equivalent to AC. No explicit well-order of ℝ is known in ZFC.

See the Axiom of Choice page for equivalences (Zorn’s Lemma, Tychonoff) and consequences (Banach–Tarski).

References