Georg Cantor

Georg Cantor

Mathematician · 1845–1918 · Born in Saint Petersburg; academic career in Germany

Compare infinite sets by functions

Cantor made the size of an infinite set a subject of precise mathematics. The central operation is a bijection: a function that pairs every element of one set with exactly one element of another, leaving nothing unmatched. His work on countability, uncountability, cardinal numbers and ordinal numbers helped establish set theory as a mathematical field.

This achievement did not arise from nothing. Dedekind, Bolzano and other nineteenth-century mathematicians investigated infinite collections and mathematical foundations. Later axiomatizations also required contributions beyond Cantor's. The historical development is better understood through the problems and proofs than through a chain assigning every later theorem to one founder. Early set theory.

A research path through analysis

Cantor was born on 3 March 1845 and died in Halle on 6 January 1918. He studied in Berlin, completed his doctorate in 1867, and began working at Halle in 1869. Questions about the uniqueness of trigonometric-series representations led him to investigate exceptional sets of points. His 1874 paper established the countability of algebraic numbers and the uncountability of the reals. The familiar diagonal argument appeared later, in his 1891 paper. The two proofs should not be conflated. Biographical chronology.

His work encountered both criticism and support. Accounts that attribute his recurrent illness to a single opponent turn historical complexity into an unsupported clinical explanation. The revised lesson does not diagnose him retrospectively or repeat hostile quotations without their documentary setting. Mathematical arguments remain assessable independently of such narratives.

Countability is not density

Take natural numbers to include 0. The map n ↦ 2n is a bijection from the naturals to the even naturals. It is injective because 2m = 2n implies m = n. It is surjective onto the even naturals because every even natural has the form 2n. A proper subset can therefore have the same infinite cardinality as its parent.

The rationals are also countable. Arrange positive fractions p/q in a grid indexed by positive integers p and q. Visit diagonals of increasing p + q. Every positive fraction appears after finitely many diagonals; suppress duplicates such as 1/2 and 2/4, and then interleave zero and negative values. Density, which says that an interval contains rational numbers, is a different property from countability, which asks whether a sequence can reach every element.

This is an original explanatory enumeration, not a historical claim about which grid Cantor drew. It illustrates what an existence proof of a listing must establish: coverage, and a treatment of duplicates if a bijection is required.

Worked mechanism: diagonalization without decimal ambiguity

Let B be the set of all infinite sequences whose entries are 0 or 1. Suppose someone claims a list s₀, s₁, s₂, ... contains every sequence in B. Define a new sequence d by

d(n) = 1 − sₙ(n).

A finite prefix might look like this:

Listed sequence	Position 0	Position 1	Position 2	Position 3
s₀	0	0	1	1
s₁	1	1	1	0
s₂	0	1	0	1
s₃	1	0	0	1
d	1	0	1	0

The displayed four bits do not determine the entire sequence; the rule determines every position. For any proposed index k, d differs from sₖ at position k. Therefore d is absent from the list. Since the argument works for any proposed list, B is uncountable. This follows the mechanism in Cantor's 1891 paper, using modern notation. Primary text in translation.

Using sequences avoids the ambiguity of decimal representations such as 0.4999... = 0.5000.... If presenting a direct decimal proof, one can choose every new digit from {1,2}, choosing 2 when the corresponding listed diagonal digit is 1 and 1 otherwise. The constructed number cannot end in repeating nines, and a digit disagreement cannot be concealed by that representation ambiguity.

The power-set theorem

The same pattern works for an arbitrary set S. Suppose f maps S into its power set P(S), the set of all subsets of S. Define

D = {x ∈ S : x ∉ f(x)}.

If f were surjective, some d ∈ S would satisfy f(d) = D. But then d ∈ D exactly when d ∉ f(d), which is d ∉ D. This contradiction shows that no such surjection exists. Since x ↦ {x} injects S into P(S), the power set has strictly greater cardinality. This is a statement about sets and functions, not a procedure for physically storing every subset.

What this says about programs

Finite strings over a finite alphabet can be listed by length and then lexicographically. Programs written in a fixed finite notation form a subset of these strings, so there are at most countably many programs. Languages over that alphabet are subsets of the countable set of finite strings. The power-set theorem makes the collection of languages uncountable. Therefore some languages have no deciding program.

This counting argument establishes existence. It does not identify a particular undecidable language or prove the halting problem undecidable by itself. A named undecidability result needs its own proof, often a diagonal construction or a reduction. Nor does uncountability imply that every real-number question is computationally difficult: many particular numbers and operations have effective descriptions.

Ordinals, cardinals and the continuum hypothesis

Cardinals compare sizes. Ordinals describe well-order types. The orders ω and ω + 1 have the same cardinality, but ω + 1 has a greatest element and ω does not. An arbitrary bijection need not preserve order. Likewise, a bijection between a line and a square need not preserve continuity or dimension.

The continuum hypothesis states that there is no cardinal strictly between the naturals and the reals. Assuming ZFC is consistent, Gödel's work shows that CH cannot be refuted in ZFC, and Cohen's work shows that it cannot be proved there. These are relative results, not an unconditional proof that ZFC is consistent or that the question has no meaning under stronger assumptions. The independence result.

Exercises

1. Give an explicit bijection from the natural numbers, including 0, to the integers. Explain why merely saying “alternate signs” is insufficient without specifying how zero is handled.
2. Apply the power-set construction to S = {a,b,c} with f(a) = {a,b}, f(b) = {c}, f(c) = ∅. Compute D and prove it is not one of the three outputs.
3. A colleague concludes from countability of programs that the halting problem is undecidable and that every real number is uncomputable. Diagnose both errors, then state exactly what the cardinality argument proves.

Compare your reasoning with the worked solutions

1. A complete integer listing

Set f(0) = 0, f(2k−1) = k and f(2k) = −k for k ≥ 1. The sequence is 0, 1, −1, 2, −2, .... Every positive integer k occurs at 2k−1, every negative integer −k at 2k, and zero only at zero. These formulas prove coverage and uniqueness rather than relying on an informal pattern.

2. Build the missing subset

The element a is in f(a), so it is excluded from D. The element b is not in f(b) = {c}, so it belongs to D. The element c is not in f(c), so it also belongs. Thus D = {b,c}. It differs from f(a) at a, from f(b) at b, and from f(c) at c. The missing set is forced by the construction, even though the original function already produces three different subsets.

3. Existence is weaker than identification

Counting proves that the programs cannot cover all languages, but it has not singled out the halting language. That requires an argument connecting hypothetical halting decisions to a contradiction. Similarly, only countably many reals can have finite effective descriptions of a specified kind, but familiar reals such as 0 and 1/2 are computable. The correct conclusion is that uncountably many reals are not computable, not that none are. These distinctions prevent a powerful proof technique from being used as a universal slogan.