There are different sizes of infinity

We say that two sets are the 'same size' if their elements can be paired up one-to-one. This definition applies to infinite as well as finite sets. For example, consider the set N of 'natural numbers' {0, 1, 2, ...}. It's infinite, of course. It has the same size as the set of even natural numbers {0, 2, 4 ...} because, for example, you can match n with 2n. This may be counterintuitive.

Anyway, it's easy to show (see YouTube) that N also has the same size as the set of positive rational numbers (numbers of the form A/B, where A and B are natural numbers). Or the set of all finite sequences of letters. They're all the same size, and this is the smallest infinite size.

But there are bigger infinite sets. For example, consider the set C of all 'real' numbers - not just rationals - between 0 and 1. It's easy to show (using something called the 'diagonal argument'; see YouTube) that there's no one-to-one matching between C and N. Any matching misses some of the elements of C. Hence C is bigger than N. (BTW, C stands for 'continuum' - it's a continuous range of numbers).

The Continuum Hypothesis

The continuum hypothesis (CH) states that there are no sets bigger than N and smaller than C. CH was formulated by Georg Cantor around 1880.

CH seems pretty straightforward, kind of like saying that there are no integers between 0 and 1. It should be easy to prove or disprove, right?

Wrong. No one was able to prove or disprove it, and in 1900 David Hilbert put it first on his famous list of 23 open problems.

Amazingly, it turns out that CH can be neither proved nor disproved from the current axioms of mathematics. The two parts of this assertion were proved by Kurt Godel (in 1940) and Paul Cohen (in 1963). For his part of the proof, Cohen invented a general-purpose technique called "forcing". When I retire, I vow to learn about forcing, starting by reading Forcing for Dummies.

Updated, Apr 2023: I retired last year and I still don't understand forcing.

In other words, unless a new axiom comes along - some obvious fact that has somehow eluded mathematicians to date - we can never know if CH is true or false. This is analogous to the Heisenberg Uncertainty Principle, which proves (from the principles of quantum mechanics) that we can't measure both the position and momentum of a particle. It imposes a hard upper bound on what we puny humans can know.

The Generalized Continuum Hypothesis

You're probably wondering if there are sets even bigger than C. The answer is yes.

Given a set X, the 'power set of X' (denoted P(X)) is the set of all subsets of X. For example, if

X = {a,b,c}

then

P(X) = {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}.

It's easy to show (using a variant of the 'diagonal argument' mentioned above) that if X is any set (finite or infinite), P(X) is larger than X.

In particular, P(C) is larger than C. And P(P(C)) is larger than P(C), and so on. Given any set, there's always a larger one; there is no largest set.

As an aside: P(N) has the same size as C. This is easy to see. Every number in C can be written in binary; e.g. 0.1001011100011... We can think of this as corresponding to the set of natural numbers i for which there's a one in position i. This is in fact a one-to-one correspondence between P(N) and C.

Anyway, the 'Generalized Continuum Hypothesis' (GCH) says that, for any infinite set X, there are no sets larger than X and smaller than P(X). GCH is also independent of the axioms of mathematics.

Philosophy

Independently of whether we can prove CH, does it really have a unique truth value? Is there an unique abstract universe of sets in which there either is or isn't something intermediate in size between the integers and reals? This is the realm of the Philosophy of Mathematics. "Platonism" is the belief that there is a unique such universe; others believe, for example, that there is a 'multiverse' of them. CH might be true in some and false in others.

What's the word on the street about CH?

Paul Cohen thought that CH was obviously false. His argument (paraphrased): there are incremental ways of expanding infinite sets: e.g. taking their product (the set of all pairs). The power-set function (which produces the reals from the integers) is not incremental - it's something different and much cruder. There must be an incremental way to make a set bigger than the integers (but smaller than the reals). Note: I don't buy this at all - see below.

Hugh Woodin (a mathematician at UC Berkeley) has some results supporting the idea (but not proving) that CH is false. See here and here. (Warning: no one understands these papers).

Here's a video of a talk by Hugh Woodin.

Update (Apr 2023): Woodin has changed his mind, and believes that CH is true. He talks about this in summary and in more detail. I understand very little of either.

Me personally? I'm an unabashed Platonist, and I lean towards thinking that CH is true, period. All the incremental ways of making bigger sets that we know of (limits, products, etc.) can't make the integers into something bigger. I think it's likely that there are no other incremental ways, and that power-set is the only way to make an infinite set bigger.