Can Infinity Be Bigger Than Infinity?

Yes, and it doesn't stop there. For any infinite set, there's always a strictly larger one. There is no "biggest infinity." Instead there's an endless tower of them, each infinitely larger than the one below.

Even stranger, one of the simplest questions about this tower, whether there's an infinity between the first two familiar ones, was proven in 1963 to be impossible to answer using the standard rules of mathematics.

Adding to Infinity Changes Nothing, but One Operation Changes Everything

Try to make infinity bigger by adding to it, and nothing happens. Add one element to a countably infinite set: still the same size. Double it: same size. Even take infinitely many copies of it: still the same size.

ℵ₀ + 1 = ℵ₀
ℵ₀ + ℵ₀ = ℵ₀
ℵ₀ × ℵ₀ = ℵ₀

So how can you ever get bigger? The answer is an operation that grows even finite sets explosively: taking all possible subsets.

Subsets Grow Fast

The power set of a set S, written P(S), is the set of all its subsets, including the empty set and S itself.

For S = {a, b, c}, there are 8 subsets:

{ }, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}

Each element is either in a subset or out of it, so a set with n elements has 2ⁿ subsets:

For finite sets, 2ⁿ is always bigger than n. Check powers of two with the logarithm table for base 2. The amazing part is that this stays true for infinite sets too.

Cantor's Theorem

In 1891, Georg Cantor proved that for any set S, finite or infinite, the power set P(S) is strictly larger than S.

The proof is short and clever. Suppose someone claims a pairing f that matches each element x of S with a subset f(x), covering every subset. Now define a troublemaking subset:

D = { x in S : x is NOT in f(x) }

D is a subset of S, so if the pairing covers every subset, some element d must be paired with it: f(d) = D. Now ask: is d in D?

• If d is in D, then by D's definition, d is not in f(d) = D. Contradiction.
• If d is not in D, then d is not in f(d), so by definition d is in D. Contradiction.

Either way, we get a contradiction. So no such pairing can exist, and P(S) is always bigger than S.

The self-referential trick resembles the liar paradox ("This sentence is false"). A closely related idea gave Bertrand Russell his famous paradox in 1901, and later helped inspire Kurt Gödel's incompleteness theorems.

The Endless Tower

Apply Cantor's theorem again and again:

ℕ  <  P(ℕ)  <  P(P(ℕ))  <  P(P(P(ℕ)))  <  …

Each step is a strictly bigger infinity. These sizes are written with the Hebrew letter beth:

• ℶ₀ = ℵ₀, the size of the whole numbers
• ℶ₁ = 2^ℵ₀, the size of P(ℕ), which equals the size of the real numbers
• ℶ₂ = 2^ℶ₁, the size of all subsets of the real numbers
• … and so on, forever

The fact that P(ℕ) matches the real numbers makes sense if you think in binary: a subset of ℕ is like an infinite string of 0s and 1s (is 1 in it? is 2?), and so is a binary decimal between 0 and 1. See how binary strings map to numbers with the binary to decimal converter.

The Unanswerable Question: The Continuum Hypothesis

Cantor proved the real numbers are bigger than the whole numbers. He then asked: is there any infinite set whose size is strictly between them?

He believed the answer was no. That guess is the continuum hypothesis:

There is no set with ℵ₀ < |S| < 2^ℵ₀

Cantor tried for years to prove it and couldn't. In 1900, David Hilbert put it first on his famous list of 23 problems for the new century.

An Insider Reference: Gödel and Cohen

The resolution came in two halves:

• In 1940, Kurt Gödel showed the continuum hypothesis can't be disproved from the standard axioms of set theory (ZFC), assuming those axioms are consistent.
• In 1963, Paul Cohen of Stanford invented a technique called forcing and showed it can't be proved either.

So the continuum hypothesis is independent of standard mathematics. You can add it as an axiom, or add its negation, and either way you get a consistent system (if ZFC itself is consistent). Cohen received the Fields Medal in 1966 for this work, still the only Fields Medal awarded for work in logic.

Two Concepts Worth Knowing

Power Set

The power set of S is the set of all subsets of S. For a finite set with n elements it has 2ⁿ elements, and Cantor's theorem guarantees it's always strictly larger than S, even when S is infinite.

Independence

A statement is independent of a set of axioms if the axioms can neither prove nor disprove it. Euclid's parallel postulate is independent of his other axioms, which is why non-Euclidean geometries exist.

Quick Answer: Is There an Infinity Bigger Than Infinity?

Yes. Cantor's theorem proves that the set of all subsets of any set is strictly larger than the set itself. Starting from the whole numbers, this gives an endless sequence of ever-larger infinities. There is no largest infinity, and whether any infinity lies between the whole numbers and the real numbers can't be decided from standard axioms.

Try Them Yourself

• Base-2 Logarithm Table: powers of two, the size of power sets
• Binary to Decimal Converter: subsets as binary strings
• Base 2 to Base 10 Table: list subsets of a small set in order
• Number Theory Formulas: properties of whole numbers
• What Is Infinity? And Why Are There Different Sizes of Infinity?: the diagonal argument
• Mastering Truth Tables: the logic behind proof by contradiction

List all 16 subsets of {a, b, c, d}, then write each one as a 4-digit binary number. You'll see exactly why a set with n elements has 2ⁿ subsets.