Measuring Infinity

Can one endless collection be larger than another? The question sounds impossible to test. We cannot finish counting either collection. Yet a comparison becomes possible once we stop asking for a final count and ask whether the elements can be matched.

That change in method lies at the beginning of modern set theory. It also brings a harder question into view: when are we entitled to treat an infinite collection as a completed mathematical object?

Infinity as a process—and as an object

In Book III of the Physics, Aristotle distinguished an infinite process from an infinite whole. We can always choose another natural number after the one just named. At every stage we have named only finitely many, yet there is no prescribed final stage. This is the intuition behind potential infinity. Actual infinity treats an infinite totality, such as the set of all natural numbers, as an object available for mathematical discussion.

The distinction is useful, though it should not be turned into a simple history of mathematics “overcoming” an ancient mistake. Mathematicians have used infinite processes and infinite objects in different ways. The challenge is to specify what claims about either kind of infinity mean and what justifies them.

Galileo encountered that challenge in Two New Sciences. The positive integers include numbers that are not perfect squares. Squares therefore seem to form a smaller part of the whole. Yet every positive integer $n$ has exactly one square $n^2$, and every positive square appears this way:

$$1\longleftrightarrow 1,\qquad 2\longleftrightarrow 4,\qquad 3\longleftrightarrow 9,\qquad \ldots$$

Galileo saw the pairing. He concluded that the familiar comparisons “equal,” “greater,” and “less” should not be applied to infinite multitudes in the ordinary way. The observation survived. A later generation would give it a different mathematical interpretation.

Bernard Bolzano also examined completed infinite collections in his posthumously published Paradoxes of the Infinite (1851). He recognized that an infinite collection can be paired with a proper part of itself. He did not simply treat such a pairing as a definition of equal size: his account continued to give weight to the idea that a whole exceeds its part. The disagreement reminds us that a correspondence is a fact about two collections, while the decision to call them equally numerous is part of a theory of size.

Nineteenth-century analysts developed more precise language for limits and continuity. That work allowed many arguments in calculus to proceed without treating an infinitesimal as an undefined tiny number. It did not remove every infinite totality from mathematics. In the same period, Georg Cantor's investigations of trigonometric series led him toward questions about sets of points and the comparison of infinite collections. A new account of size began to take shape.

Comparing without counting

One-to-one correspondence

Suppose $f:A\to B$ assigns an element of $B$ to each element of $A$.

• The function is injective if distinct elements of $A$ always receive distinct images.
• It is surjective if every element of $B$ is the image of at least one element of $A$.
• It is bijective if both conditions hold. Then each element on either side has exactly one partner on the other.

We call $A$ and $B$ equinumerous when a bijection exists between them. Their common size, or cardinality, is expressed by $|A|=|B|$. The definition works for finite sets and continues to make sense when counting to a last element is impossible.

Let $\mathbb N=\{1,2,3,\ldots\}$ and let $S=\{1,4,9,\ldots\}$ be the positive perfect squares. The map

$$f:\mathbb N\to S,\qquad f(n)=n^2$$

is a bijection. In the cardinal sense, $|\mathbb N|=|S|$, even though $S$ is a proper subset of $\mathbb N$. Galileo's puzzle becomes a defining feature of infinite cardinality: a whole can have the same cardinality as one of its proper parts.

The cardinality of $\mathbb N$ is written $\aleph_0$ (“aleph-null”). A set in bijection with $\mathbb N$ is countably infinite. Some books use “countable” to include finite sets as well, so we will say “at most countable” when we mean either finite or countably infinite.

A hotel with no last room

Hilbert's hotel gives the same idea a physical disguise. Imagine rooms numbered $1,2,3,\ldots$, with a guest in every room. One new guest arrives. Move the guest in room $n$ to room $n+1$. Every old guest still has a room, and room $1$ becomes available. This is the pairing behind

$$\aleph_0+1=\aleph_0.$$

If countably many new guests arrive, move the old guest in room $n$ to room $2n$. The even-numbered rooms hold the original guests. Put new guest $k$ in room $2k-1$. The hotel now accommodates two countably infinite groups:

$$\aleph_0+\aleph_0=\aleph_0.$$

These are statements about cardinal addition, not about adding ordinary finite numbers. They show why “more elements have been added” does not by itself tell us the cardinality of the result.

Binary choices and a larger infinity

The power set

If $A$ is a set, its power set $\mathcal P(A)$ consists of every subset of $A$. For $A=\{a,b\}$, the power set is

$$\mathcal P(A)=\{\varnothing,\{a\},\{b\},\{a,b\}\}.$$

A set with $n$ elements has $2^n$ subsets. Each element offers two choices: include it or leave it out. The same idea describes an infinite subset. Every $T\subseteq\mathbb N$ has a characteristic sequence $(t_1,t_2,\ldots)$, where $t_n=1$ when $n\in T$ and $t_n=0$ otherwise. Thus subsets of $\mathbb N$ correspond exactly to infinite binary sequences:

$$\mathcal P(\mathbb N)\ \cong\ \{0,1\}^{\mathbb N}.$$

The cardinality of this collection is written $2^{\aleph_0}$. The exponent here is a cardinal. The notation records the number of functions from $\mathbb N$ to a two-element set.

A list that cannot be complete

Could the binary sequences be listed as $s_1,s_2,s_3,\ldots$? Suppose that they could, and write the digit in position $n$ of $s_i$ as $b_{i,n}$:

$$\begin{aligned} s_1&=(b_{1,1},b_{1,2},b_{1,3},\ldots),\\ s_2&=(b_{2,1},b_{2,2},b_{2,3},\ldots),\\ s_3&=(b_{3,1},b_{3,2},b_{3,3},\ldots),\\ &\ \vdots \end{aligned}$$

Now construct another binary sequence $c=(c_1,c_2,\ldots)$ by reversing the diagonal digit in each row:

$$c_n=1-b_{n,n}.$$

The sequence $c$ differs from $s_1$ in its first digit, from $s_2$ in its second digit, and from $s_n$ at position $n$. It is a binary sequence, yet it cannot be anywhere on the proposed complete list. Every such list misses at least one sequence.

This modern binary-sequence presentation captures the argument Cantor published in 1891. It proves that $\mathcal P(\mathbb N)$ is uncountable:

$$\aleph_0<2^{\aleph_0}.$$

We have found a larger infinite cardinal. The next result shows that the construction works for every set, including ones already far larger than $\mathbb N$.

No largest cardinal

Cantor's theorem

Theorem. For every set $A$, the power set $\mathcal P(A)$ has strictly greater cardinality than $A$:

$$|A|<|\mathcal P(A)|.$$

First, $A$ is no larger than $\mathcal P(A)$. The map $a\mapsto\{a\}$ sends each element of $A$ to a different singleton subset, so it is injective.

To show that the two sets cannot have the same cardinality, suppose there were a surjection $f:A\to\mathcal P(A)$. Each $a\in A$ would be assigned a subset $f(a)$ of $A$. Ask whether $a$ belongs to its assigned subset, and collect the elements for which the answer is no:

$$B=\{a\in A\mid a\notin f(a)\}.$$

Because $B\subseteq A$, it belongs to $\mathcal P(A)$. Surjectivity would therefore give some $b\in A$ with $f(b)=B$. But then

$$b\in B \quad\Longleftrightarrow\quad b\notin f(b) \quad\Longleftrightarrow\quad b\notin B.$$

That is impossible. No surjection from $A$ onto $\mathcal P(A)$ exists. Combined with the singleton injection, this proves the theorem.

We can repeat the construction: starting with any set, take its power set, then the power set of that set, and so on. There is no largest cardinality among sets.

Why this construction is safe

The set $B$ is defined by selecting elements from an already given set $A$. Modern axiomatic set theory permits this kind of restricted selection. The contradiction comes from assuming that $f$ reaches every subset of $A$, not from the existence of $B$.

This distinction matters. Cantor's proof exposes a limit on mappings between sets. It does not license the claim that every property, however unrestricted, determines a set of all objects satisfying it. The latter idea leads toward Russell's paradox and the question taken up in the next article: when does a description actually define a set?

Sources

The historical account draws on these texts. Mathematical notation and explanations above are modern.

• Aristotle, Physics, Book III, on potential infinity.
• Galileo, Dialogues Concerning Two New Sciences, First Day, on integers and squares.
• Bolzano, Paradoxien des Unendlichen (1851).
• Cantor, “Über eine elementare Frage der Mannigfaltigkeitslehre” (1891).