Understanding “Infinity” Mathematically: Cardinality, the Diagonal Argument, and Power Sets

The word “infinity” gets used often in everyday conversation and in mathematics, but it’s a very deep concept. The 19th-century mathematician Georg Cantor discovered that infinities too differ in size, and created the notion of “cardinality” as a tool for comparing them.

This article starts from the basic method of comparing infinities and organizes the main concepts around infinite cardinality: the diagonal argument, power sets, Cantor’s theorem, and the continuum hypothesis.

Conclusions

• The relative size of infinities is judged not by subtraction but by whether a “one-to-one correspondence (bijection)” can be constructed
• Counter to intuition, the natural numbers, the integers, and the rationals all have the same cardinality $\aleph_0$ (countable infinity)
• By Cantor’s diagonal argument, the reals have cardinality $2^{\aleph_0}$ (the cardinality of the continuum), strictly greater than that of the naturals
• The operation of forming a power set always produces a cardinality greater than the original set (Cantor’s theorem). Consequently there is no “largest infinity”
• The continuum hypothesis — “is there another cardinality between the naturals and the reals?” — is known to be undecidable from the current axiom system of set theory (ZFC) alone

Cardinality: A Way of Thinking for Comparing Infinities

For finite sets you can compare sizes by counting elements and subtracting. But the notion of “number of elements” can’t be applied to infinite sets as-is. So Cantor came up with the method of judging relative size by whether the elements of two sets can be paired up exhaustively and without duplication.

• If every element of one can be matched to elements of the other with nothing left over or missing, the two sets are said to have “the same cardinality”
• If no matter how hard you try you can’t finish pairing them and one side always has leftovers, that side is said to have the greater cardinality

This criterion — “can a one-to-one correspondence (bijection) be constructed?” — is the only yardstick for comparing infinities.

Counterintuitive Infinities of “the Same Cardinality”

Using one-to-one correspondence, a number of counterintuitive results emerge.

The Naturals and the Even Numbers Have the Same Cardinality

Comparing the set of natural numbers with the set of even numbers, the evens look like “only half” of the naturals. But with the correspondence below, the two pair up with nothing left over.

Each of the naturals 1, 2, 3, … corresponds to exactly one of the evens 2, 4, 6, …, so the naturals and the evens have the same cardinality. This cardinality, called “countable infinity,” is written $\aleph_0$ (aleph-zero).

The Naturals and the Rationals Have the Same Cardinality Too

The positive rationals can be written in the form “numerator / denominator,” so they can be laid out as an infinite grid with numerators down the side and denominators across the top.

This grid is packed densely with rationals; however narrow an interval you take, it contains infinitely many rationals. Compared with the naturals, which are just sparsely lined up as 1, 2, 3, …, the rationals clearly look more numerous.

Yet if you traverse this grid diagonally, starting from the groups where “numerator plus denominator” is smallest, you can rearrange all the rationals into a single line. Within a group of the same sum, order by smallest numerator, and skip values that have already appeared (such as 2/2 = 1/1, which reduces to the same thing).

flowchart LR
  a["1/1"] --> b["1/2"] --> c["2/1"] --> d["1/3"] --> e["2/2 (skipped)"] --> f["3/1"] --> g["1/4"] --> h["…"]

Assigning natural-number indices from the front of this rearranged list of rationals gives an exact correspondence, as follows.

Looking only at a finite range, the rationals are overwhelmingly more numerous than the naturals. But once you consider “counting all the way through to infinity,” the story changes. The procedure above assigns exactly one natural-number index to every rational, and conversely one rational to every natural-number index. Given that this one-to-one correspondence can be built, “more” and “fewer” in the finite case has no bearing on cardinality, and the cardinality of the rationals is the same $\aleph_0$ (countable infinity) as the naturals. The integers admit a similar rearrangement alternating positive and negative, so the naturals, the integers, and the rationals are all classified as the same countable infinity.

The Reals Are Strictly Larger: The Diagonal Argument

Not all infinities have the same cardinality. The set of reals has a cardinality strictly greater than that of the naturals. Cantor’s diagonal argument is what proved this.

The idea goes as follows.

1. Suppose the reals could all be indexed by natural numbers (that they are countable), and line up the reals between 0 and 1 in a list by their decimal expansions
2. Build a new decimal by changing, one at a time, the n-th decimal digit of the n-th real in the list
3. The new real built this way differs from the n-th real in the list at the n-th decimal place, so it exists nowhere in the list

In other words, even when you think you’ve built “a list of all the reals,” you can always construct a real that isn’t on it. This means the reals are not countable — that is, they have a cardinality strictly greater than the naturals. This cardinality of the reals is called the cardinality of the continuum, written $2^{\aleph_0}$.

Why Do Power Sets Raise Cardinality?

There’s a reason the cardinality of the continuum is written in the exponential form $2^{\aleph_0}$.

The collection of all subsets of a set $A$ is called the “power set,” written $\mathcal{P}(A)$. Constructing one subset is the same as deciding, for each element of $A$, whether to “include it or not.”

For example, the subset $\{a, c\}$ of $A = \{a, b, c\}$ corresponds to the following sequence of 0s and 1s (the characteristic function).

With $n$ elements, you repeat the binary “include / don’t include” choice $n$ times, so the total number of subsets is $2^n$. Applying this idea directly to infinite sets, the cardinality of the power set of a set with cardinality $\kappa$ is defined as $2^{\kappa}$. This is why the cardinality of the power set of the naturals’ cardinality $\aleph_0$ coincides with the reals’ cardinality $2^{\aleph_0}$.

Note that even if you take the base of the power set to be 3 or 10 instead of 2, the following equalities hold in the world of infinity, so it converges to the same cardinality of the continuum anyway.

Cantor’s Theorem: There Is No Largest Infinity

Cantor proved that for any set $A$, the cardinality of its power set $\mathcal{P}(A)$ is always greater than the cardinality of $A$ itself.

From this theorem, you can keep making cardinalities larger without bound, as follows.

1. The cardinality of the naturals $\aleph_0$
2. Its power set = the cardinality of the reals $2^{\aleph_0}$
3. Its power set = the cardinality of all functions on the reals $2^{2^{\aleph_0}}$
4. And so on; the operation of forming power sets can be continued infinitely

Even if you suppose a “largest infinite set $M$” exists, its power set $\mathcal{P}(M)$ would be larger than $M$, a contradiction. Therefore there is no greatest among all infinities. This is called Cantor’s paradox.

The Continuum Hypothesis

So far two cardinalities have appeared: countable infinity $\aleph_0$ and the cardinality of the continuum $2^{\aleph_0}$. Here a question arises.

• Between the cardinality of the naturals and the cardinality of the reals, does there exist a set with a cardinality different from both?

The claim that “there does not” is called the continuum hypothesis. This question leaves a great mystery in modern mathematics. Through the work of Gödel and Cohen, it has been shown that the continuum hypothesis can be proven neither true nor false from the current axiom system of set theory (ZFC) alone. That is, whether you add the continuum hypothesis as an axiom or add its negation as an axiom, either way you get a consistent mathematical system.

Summary

• Comparing the sizes of infinities uses the criterion “can a one-to-one correspondence be constructed?”
• The naturals, the integers, and the rationals all have the same cardinality $\aleph_0$ (countable infinity)
• By the diagonal argument, the reals have cardinality $2^{\aleph_0}$ (the cardinality of the continuum), strictly greater than the naturals
• Because forming a power set always raises cardinality, there is no largest infinity
• The continuum hypothesis, asking whether another cardinality lies between the naturals and the reals, is independent of the ZFC axiom system

References

• Cantor, G. “Über eine elementare Frage der Mannigfaltigkeitslehre”. Jahresbericht der Deutschen Mathematiker-Vereinigung, 1891 (the original paper on the diagonal argument)
• Cohen, P. J. “The Independence of the Continuum Hypothesis”. Proceedings of the National Academy of Sciences, 1963
• Gödel, K. “The Consistency of the Continuum Hypothesis”. Annals of Mathematics Studies, 1940