Galileo's Paradox

Was Galileo wrong? Not exactly. He was reasoning correctly from a premise that everyone shared: that "greater" and "equal" must obey Euclid's common notion. Given that premise, the only consistent conclusion is that infinite quantities are not comparable, which is what he said. What Cantor eventually did was reject the premise, not repair Galileo's logic.

The medieval anticipation. Galileo was not the first to notice the phenomenon. Proclus, in the fifth century, observed that a diameter bisects a circle, so there must be twice as many semicircles as diameters — while every diameter yields exactly two semicircles and every semicircle has exactly one diameter. The mathematician Thābit ibn Qurra in the ninth century is credited by modern historians with accepting one-to-one correspondence between an infinite set and a proper part of it. Fourteenth-century scholastics including Gregory of Rimini discussed the same structure in theological settings. What Galileo added was a clean arithmetical example and a published, unembarrassed statement of the conflict.

Bolzano's near miss. Bernard Bolzano's Paradoxien des Unendlichen, published posthumously in 1851, examined exactly this family of examples and introduced much of the vocabulary. But Bolzano refused the final step. He saw the one-to-one correspondence between infinite sets and their parts and concluded that correspondence therefore cannot be the criterion of equal size. He kept Euclid and gave up pairing. Cantor, twenty years later, made the opposite choice, and that single decision is the difference between a curiosity and a theory.

What was actually given up. It is worth being precise about the cost. Cantor's move does not make Euclid's common notion false; it restricts it. For finite sets, proper containment still implies strictly smaller. For infinite sets, containment implies "no larger" but not "smaller". Everything else about counting survives. This is a small price, and it was still fought over ferociously — Leopold Kronecker, Cantor's former teacher, regarded the whole enterprise as illegitimate and worked to block its publication and its author's career.

Is any of it about the real world? Galileo's paradox concerns abstract collections. Whether an actually infinite collection of things can exist is a separate question, argued from Aristotle onwards and still argued today. Those who deny it often point to precisely this kind of result as evidence that an actual infinity of objects would behave absurdly. Those who accept it reply that "absurd" here only means "unlike the finite", which was never in dispute. The mathematics settles what infinite sets are like; it does not settle whether any exist outside mathematics.

Antiquity and the Middle Ages. Aristotle's distinction between the potential infinite (a process that never ends) and the actual infinite (a completed endless totality) framed the whole debate, and his rejection of the actual infinite was the orthodox position for two thousand years. Proclus, Thābit ibn Qurra, Robert Grosseteste and Gregory of Rimini each noticed pieces of the correspondence phenomenon, generally as a difficulty rather than a tool.

1638. Galileo published Discorsi e dimostrazioni matematiche, intorno à due nuove scienze in Leiden, the manuscript having been carried out of Italy while he was under house arrest after the 1633 trial. In the First Day, Salviati leads Simplicio through the argument: there are more numbers than squares, since most numbers are not squares; and there are as many squares as numbers, since every number has one root and every root one square. Salviati's conclusion is that "the attributes 'equal', 'greater', and 'less' are not applicable to infinite, but only to finite, quantities."

1851. Bolzano's Paradoxien des Unendlichen appeared three years after his death, cataloguing such correspondences in detail and declining to draw Cantor's conclusion.

1872–1874. Cantor, in correspondence with Dedekind, took the pairing criterion seriously as a definition, proved that the algebraic numbers can be listed, and proved that the reals cannot.

1888. Dedekind published Was sind und was sollen die Zahlen?, defining an infinite set as one similar to a proper part of itself. Galileo's embarrassment became a definition — arguably the cleanest example in mathematics of a paradox promoted to a foundation.

This is the paradox that decided what "how many" would mean.

Before it was resolved, size was a single notion tied to containment. After, size became cardinality: a property determined by matching, that behaves as expected for finite collections and quite differently for infinite ones. Every later statement about infinity — that the rationals are countable, that the reals are not, that there is no largest infinity — is stated in that language, and could not have been stated in Euclid's.

Three concrete consequences:

A usable definition of "infinite". Dedekind's criterion is intrinsic. It does not appeal to counting or to any prior notion of number. Given a set and a function, you can check it.

Countability as a working tool. The observation that a proper part can be listed off against the whole numbers is what makes it routine to enumerate the rationals, the algebraic numbers, the finite strings over an alphabet, and the computer programs. Each of those enumerations is Galileo's pairing applied to a harder set.

Permission to have more than one infinity. Galileo's response — that infinite quantities have no sizes — closes the subject. Cantor's response opens it. The entire transfinite hierarchy exists because one of the two available reactions to this puzzle was chosen over the other.

Computer science runs on the pairing. The set of all programs is infinite, and it can be listed: order them by length, then alphabetically. Gödel numbering is the same manoeuvre for logical formulas. Both work because an infinite set being "sparse" inside a bigger one is no obstacle to enumerating it.

That enumeration then does destructive work. The programs are countable; the functions from whole numbers to whole numbers are not. So there are functions no program computes — most of them, in fact. That argument is only two steps long, and its first step is Galileo's.

Data structures. Lazy infinite lists in functional languages, iterators that never terminate, and generators that dovetail several infinite streams together are all implementations of "an infinite collection can be re-indexed without loss".

Hashing and re-indexing. Every time a program maps an unbounded key space into an index and back without collisions, it is relying on the fact that a sparse infinite set and a dense one can be put in exact correspondence.

Let $\mathbb{N} = {1, 2, 3, \dots}$ and let $S = {n^2 : n \in \mathbb{N}}$ be the perfect squares.

The bijection. Define $f: \mathbb{N} \to S$ by $f(n) = n^2$. It is injective, since $m^2 = n^2$ with $m, n > 0$ forces $m = n$; and surjective onto $S$ by the definition of $S$. Hence

$$|\mathbb{N}| = |S| = \aleph_0$$

while $S \subsetneq \mathbb{N}$ properly, since $2 \notin S$.

The other intuition, made precise. The counting function for $S$ is $$|S \cap [1, N]| = \lfloor \sqrt{N} \rfloor$$ so the natural density of the squares is

$$d(S) = \lim_{N \to \infty} \frac{\lfloor \sqrt{N}\rfloor}{N} = 0$$

The even numbers $E$ satisfy $|E \cap [1,N]| = \lfloor N/2 \rfloor$, giving $d(E) = 1/2$, and by the prime number theorem the primes $P$ satisfy $|P \cap [1,N]| \sim N/\ln N$, giving $d(P) = 0$. All three sets have cardinality $\aleph_0$. Cardinality and density are independent invariants; the paradox is the collision of two questions sharing the word "more".

Dedekind's definition. A set $A$ is Dedekind-infinite if there exists an injection $f: A \to A$ that is not surjective — equivalently, if $A$ is in bijection with a proper subset of itself. Galileo's example shows $\mathbb{N}$ is Dedekind-infinite via $n \mapsto n^2$, or more simply $n \mapsto n+1$.

Every Dedekind-infinite set is infinite. The converse — that every infinite set is Dedekind-infinite — requires a weak form of the axiom of choice (countable choice suffices) and is not provable in ZF alone. In models of ZF without choice there can exist infinite sets that admit no such injection. So the definition Galileo's paradox suggests is slightly stronger than plain infinitude, a subtlety invisible from 1638.

The general principle. For any infinite cardinal $\kappa$ and any injection $g$ from a set into itself, the same absorption holds. In cardinal arithmetic this appears as

$$\aleph_0 + 1 = \aleph_0, \qquad \aleph_0 + \aleph_0 = \aleph_0, \qquad \aleph_0 \cdot \aleph_0 = \aleph_0$$

and more generally $\kappa + \lambda = \kappa \cdot \lambda = \max(\kappa, \lambda)$ for infinite cardinals, a theorem which itself depends on the axiom of choice. Note that subtraction and division are simply not defined: from $\aleph_0 + 1 = \aleph_0 + 0$ you may not cancel.

The limit of the method. Squaring is a bijection $\mathbb{N} \to S$. No function $\mathbb{N} \to \mathbb{R}$ is surjective, which is Cantor's theorem. The proof of that requires a genuinely new idea — the diagonal — and it is the point at which Galileo's puzzle stops being a curiosity about sparse subsets and becomes a theory of sizes.