A global pandemic, apocalyptic fires, and the possible descent of the US into violent anarchy three days from now can do strange things to the soul.<\/p>\n\n\n\n
Bertrand Russell—and if he’d done nothing else in his long life, I’d love him forever for it—once wrote that “in adolescence, I hated life and was continually on the verge of suicide, from which, however, I was restrained by the desire to know more mathematics.” This summer, unable to bear the bleakness of 2020, I obsessively read up on the celebrated proof of the unsolvability of the Continuum Hypothesis<\/a> (CH) from the standard foundation of mathematics, the Zermelo-Fraenkel axioms<\/a> of set theory. (In this post, I’ll typically refer to “ZFC,” which means Zermelo-Fraenkel plus the famous Axiom of Choice<\/a>.)<\/p>\n\n\n\n For those tuning in from home, the Continuum Hypothesis was formulated by Georg Cantor<\/a>, shortly after his epochal discovery that there are different orders of infinity: so for example, the infinity of real numbers (denoted C for continuum, or \\( 2^{\\aleph_0} \\)) is strictly greater than the infinity of integers (denoted \u21350<\/sub>, or “Aleph-zero”). CH is simply the statement that there’s no infinity intermediate<\/em> between \u21350<\/sub> and C: that anything greater than the first is at least the second. Cantor tried in vain for decades to prove or disprove CH; the quest is believed to have contributed to his mental breakdown. When David Hilbert presented his famous list<\/a> of 23 unsolved math problems in 1900, CH was at the very top.<\/p>\n\n\n\n Halfway between Hilbert’s speech and today, the question of CH was finally “answered,” with the solution earning the only Fields Medal<\/a> that’s ever been awarded for work in set theory and logic. But unlike with any previous yes-or-no question in the history of mathematics, the answer was that there provably is<\/em> no answer from the accepted axioms of set theory! You can either have intermediate infinities or not; neither possibility can create a contradiction. And if you do<\/em> have intermediate infinities, it’s up to you how many: 1, 5, 17, \u221e, etc.<\/p>\n\n\n\n The easier half, the consistency of CH with set theory, was proved by incompleteness dude Kurt G\u00f6del<\/a> in 1940; the harder half, the consistency of not(CH), by Paul Cohen<\/a> in 1963. Cohen’s work introduced the method of forcing<\/a>, which was so fruitful in proving set-theoretic questions unsolvable that it quickly took over the whole subject of set theory. Learning G\u00f6del and Cohen’s proofs had been a dream of mine since teenagerhood, but one I constantly put off.<\/p>\n\n\n\n This time around I started with Cohen’s retrospective essay<\/a>, as well as Timothy Chow’s Forcing for Dummies<\/a> and A Beginner’s Guide to Forcing<\/a>. I worked through Cohen’s own Set Theory and the Continuum Hypothesis<\/a>, and Ken Kunen’s Set Theory: An Introduction to Independence Proofs<\/a>, and Dana Scott’s 1967 paper<\/a> reformulating Cohen’s proof. I emailed questions to Timothy Chow, who was ridiculously generous with his time. When Tim and I couldn’t answer something, we tried Bob Solovay<\/a> (one of the world’s great set theorists, who later worked in computational complexity and quantum computing), or Andreas Blass<\/a> or Asaf Karagila<\/a>. At some point mathematician and friend-of-the-blog Greg Kuperberg<\/a> joined my quest for understanding. I thank all of them, but needless to say take sole responsibility for all the errors that surely remain in these posts.<\/p>\n\n\n\n On the one hand, the proof of the independence of CH would seem to stand with general relativity, the wheel, and the chocolate bar as a triumph of the human intellect. It represents a culmination of Cantor’s quest to know the basic rules of infinity—all the more amazing if the answer turns out to be that, in some sense, we can’t<\/em> know them.<\/p>\n\n\n\n On the other hand, perhaps no other scientific discovery of equally broad interest remains so sparsely popularized, not even (say) quantum field theory or the proof of Fermat’s Last Theorem. I found barely any attempts to explain how forcing works to non-set-theorists, let alone to non-mathematicians. One notable exception was Timothy Chow’s Beginner’s Guide to Forcing<\/a>, mentioned earlier—but Chow himself, near the beginning of his essay, calls forcing an “open exposition problem,” and admits that he hasn’t solved it. My modest goal, in this post and the following ones, is to make a further advance on the exposition problem.<\/p>\n\n\n\n OK, but why a doofus computer scientist like me? Why not, y’know, an actual expert? I won’t put forward my ignorance as a qualification, although I have<\/em> often found that the better I learn a topic, the more completely I forget what initially confused me, and so the less able I become to explain things to beginners.<\/p>\n\n\n\n Still, there is one<\/em> thing I know well that turns out to be intimately related to Cohen’s forcing method, and that made me feel like I had a small “in” for this subject. This is the construction of oracles<\/a> in computational complexity theory. In CS, we like to construct hypothetical universes where P=NP or P\u2260NP, or P\u2260BQP, or the polynomial hierarchy is infinite, etc. To do so, we, by fiat, insert a new function—an oracle<\/em>—into the universe of computational problems, carefully chosen to make the desired statement hold. Often the oracle needs to satisfy an infinite list of conditions, so we handle them one by one, taking care that when we satisfy a new condition we don’t invalidate the previous conditions.<\/p>\n\n\n\n All this, I kept reading, is profoundly<\/em> analogous to what the set theorists do when they create a mathematical universe where the Axiom of Choice is true but CH is false, or vice versa, or any of a thousand more exotic possibilities. They insert new sets into their models of set theory, sets that are carefully constructed to “force” infinite lists of conditions to hold. In fact, some of the exact same people—such as Solovay<\/a>—who helped pioneer forcing in the 1960s, later went on to pioneer oracles in computational complexity. We’ll say more about this connection in a future post.<\/p>\n\n\n\n How Could It Be?<\/strong><\/p>\n\n\n\n How do you study a well-defined math problem, and return the answer that, as far as the accepted axioms of math can say, there is<\/em> no answer? I mean: even supposing it’s true<\/em> that there’s no answer, how do you prove<\/em> such a thing?<\/p>\n\n\n\n Arguably, not even G\u00f6del’s Incompleteness Theorem<\/a> achieved such a feat. Recall, the Incompleteness Theorem says loosely that, for every formal system F that could possibly serve as a useful foundation for mathematics, there exist statements even of elementary arithmetic that are true but unprovable in F—and Con(F), a statement that encodes F’s own consistency, is an example of one. But the very statement that Con(F) is unprovable is equivalent to Con(F)’s being true<\/em> (since an inconsistent system could prove anything, including Con(F)). In other words, if the Incompleteness Theorem as applied to F holds any interest, then that’s only because F is, in fact<\/em>, consistent<\/em>; it’s just that resources beyond F are needed to prove this.<\/p>\n\n\n\n Yes, there’s a “self-hating theory,” F+Not(Con(F)), which believes in its own inconsistency. And yes, by G\u00f6del, this self-hating theory is consistent<\/em> if F itself is. This means that it has a model<\/strong>—involving “nonstandard integers,” formal artifacts that effectively promise a proof of F’s inconsistency without ever actually delivering it. We’ll have much, much<\/em> more to say about models later on, but for now, they’re just collections of objects, along with relationships between the objects, that satisfy all the axioms of a theory (thus, a model of the axioms of group theory is simply … any group!).<\/p>\n\n\n\n In any case, though, the self-hating theory F+Not(Con(F)) can’t be arithmetically sound<\/em>: I mean, just look at it! It’s either unsound because F is consistent, or else it’s unsound because F is inconsistent. In general, this is one of the most fundamental points in logic: consistency does not imply soundness<\/strong>. If I believe that the moon is made of cheese, that might be consistent<\/em> with all my other beliefs about the moon (for example, that Neil Armstrong ate delicious chunks of it), but that doesn’t mean my belief is true<\/em>. Like the classic conspiracy theorist, who thinks that any apparent evidence against their hypothesis was planted by George Soros or the CIA, I might simply believe a self-consistent collection of absurdities. Consistency is purely a syntactic condition—it just means that I can never prove both a statement and its opposite—but soundness goes further, asserting that whatever I can prove is actually the case, a relationship<\/em> between what’s inside my head and what’s outside it.<\/p>\n\n\n\n So again, assuming we had any business using F in the first place, the Incompleteness Theorem gives us two consistent<\/em> ways to extend F (by adding Con(F) or by adding Not(Con(F))), but only one sound<\/em> way (by adding Con(F)). But the independence of CH from the ZFC axioms of set theory is of a fundamentally different kind. It will give us models of ZFC+CH, and models of ZFC+Not(CH), that are both<\/em> at least somewhat plausible as “sketches of mathematical reality”—and that both even have defenders. The question of which is right, or whether it’s possible to decide at all, will be punted to the future: to the discovery (or not) of some intuitively compelling foundation for mathematics that, as G\u00f6del hoped, answers the question by going beyond ZFC.<\/p>\n\n\n\n Four Levels to Unpack<\/strong><\/p>\n\n\n\n While experts might consider this too obvious to spell out, G\u00f6del’s and Cohen’s analyses of CH aren’t so much about infinity, as they are about our ability to reason <\/em>about infinity using finite sequences of symbols. The game is about building self-contained mathematical universes to order—universes where all the accepted axioms about infinite sets hold true, and yet that, in some cases, seem to mock what those axioms were supposed to mean<\/em>, by containing vastly fewer objects than the mathematical universe was “meant” to have.<\/p>\n\n\n\n In understanding these proofs, the central hurdle, I think, is that there are at least four different “levels of description” that need to be kept in mind simultaneously.<\/p>\n\n\n\n At the first level, G\u00f6del’s and Cohen’s proofs, like all mathematical proofs, are finite sequences of symbols. Not only that, they’re proofs that can be formalized in elementary arithmetic (!). In other words, even though they’re about<\/em> the axioms of set theory, they don’t themselves require<\/em> those axioms. Again, this is possible because, at the end of the day, G\u00f6del’s and Cohen’s proofs won’t be talking about infinite sets, but “only” about finite sequences of symbols that make statements about infinite sets.<\/p>\n\n\n\n At the second level, the proofs are making an “unbounded” but perfectly clear claim. They’re claiming that, if someone showed you a proof of either CH or Not(CH), from the ZFC axioms of set theory, then no matter how long the proof or what its details, you could convert it into a proof that ZFC itself<\/em> was inconsistent. In symbols, they’re proving the “relative consistency statements”<\/p>\n\n\n\n Con(ZFC) \u21d2 Con(ZFC+CH), and they’re proving these as theorems of elementary arithmetic<\/em>. (Note that there’s no hope of proving Con(ZF+CH) or Con(ZFC+Not(CH)) outright<\/em> within ZFC, since by G\u00f6del, ZFC can’t even prove its own consistency.)<\/p>\n\n\n\n This translation is completely explicit; the independence proofs even yield algorithms<\/em> to convert proofs of inconsistencies in ZFC+CH or ZFC+Not(CH), supposing that they existed, into proofs of inconsistencies in ZFC itself.<\/p>\n\n\n\n Having said that, as Cohen himself often pointed out, thinking about the independence proofs in terms of algorithms to manipulate sequences of symbols is hopeless: to have any chance of understanding these proofs, let alone coming up with them, at some point you need to think about what the symbols refer<\/em> to.<\/p>\n\n\n\n This brings us to the third level: the symbols refer to models of set theory<\/em>, which could also be called “mathematical universes.” Crucially, we always can and often will take these models to be only countably<\/em> infinite: that is, to contain an infinity of sets, but “merely” \u21350<\/sub> of them, the infinity of integers or of finite strings, and no more.<\/p>\n\n\n\n The fourth level of description is from within the models themselves: each model imagines itself to have an uncountable<\/em> infinity of sets. As far as the model’s concerned, it comprises the entire mathematical universe, even though “looking in from outside,” we can see that that’s not true. In particular, each model of ZFC thinks<\/em> it has uncountably many sets, many themselves of uncountable cardinality, even if “from the outside” the model is countable.<\/p>\n\n\n\n Say what? The models are mistaken<\/em> about something as basic as their own size, about how many sets they have? Yes. The models will be like The Matrix<\/em> (the movie, not the mathematical object), or The Truman Show<\/em>. They’re self-contained little universes whose inhabitants can never discover that they’re living a lie—that they’re missing sets that we, from the outside, know to exist. The poor denizens of the Matrix will never even be able to learn that their universe—what <\/em>they mistakenly think of as the<\/em> universe—is secretly countable! And no Morpheus<\/a> will ever arrive to enlighten them, although—and this is crucial to Cohen’s proof in particular—the inhabitants will be able to reason more-or-less intelligibly about what would happen if a Morpheus did<\/em> arrive.<\/p>\n\n\n\n The L\u00f6wenheim-Skolem Theorem<\/a>, from the early 1920s, says that any<\/em> countable list of first-order axioms that has any model at all (i.e., that’s consistent), must have a model with at most countably many elements. And ZFC is a countable list of first-order axioms, so L\u00f6wenheim-Skolem applies to it—even though ZFC implies the existence of an uncountable infinity of sets! Before taking the plunge, we’ll need to not merely grudgingly accept but love and internalize this “paradox,”<\/a> because pretty much the entire proof of the independence of CH is built on top of it.<\/p>\n\n\n\n Incidentally, once we realize that it’s possible to build self-consistent yet “fake” mathematical universes, we can ask the question that, incredibly, the Matrix<\/em> movies never ask. Namely, how do we know that our own, larger universe isn’t similarly a lie? The answer is that we don’t! As an example—I hope you’re sitting down for this—even though Cantor proved that there are uncountably many real numbers, that only means there are uncountably many reals for us<\/em>. We can’t rule out the possibly that God, looking down on our universe, would see countably many reals.<\/p>\n\n\n\n Cantor’s Proof Revisited<\/strong><\/p>\n\n\n\n To back up: the whole story of CH starts, of course, with Cantor’s epochal discovery of the different orders of infinity, that for example, there are more subsets of positive integers (or equivalently real numbers, or equivalently infinite binary sequences) than there are positive integers. The devout Cantor thought his discovery illuminated the nature of God; it’s never been entirely obvious to me that he was wrong.<\/p>\n\n\n\n Recall how Cantor’s proof works: we suppose by contradiction that we have an enumeration of all infinite binary sequences: for example,<\/p>\n\n\n\n s(0) = 0<\/strong>0000000… We then produce a new infinite binary sequence that’s not on the list, by going down the diagonal and flipping each bit, which in the example above would produce 1011…<\/p>\n\n\n\n But look more carefully. What Cantor really shows is only that, within our mathematical universe<\/em>, there can’t be an enumeration of all the reals of our universe. For if there were, we could use it to define a new real that was in the universe but not in the enumeration. The proof doesn’t rule out the possibility that God<\/em> could enumerate the reals of our universe! It only shows that, if so, there would need to be additional, heavenly reals that were missing from even God’s enumeration (for example, the one produced by diagonalizing against that<\/em> enumeration).<\/p>\n\n\n\n Which reals could possibly be “missing” from our universe? Every real you can name—42, \u03c0, \u221ae, even uncomputable reals like Chaitin’s \u03a9<\/a>—has to be there, right? Yes, and there’s the rub: every real you can name<\/em>. Each name is a finite string of symbols, so whatever your naming system, you can only ever name countably many reals, leaving 100% of the reals nameless.<\/p>\n\n\n\n Or did you think of only the rationals<\/em> or algebraic numbers<\/em> as forming a countable dust of discrete points, with numbers like \u03c0 and e filling in the solid “continuum” between them? If so, then I hope you’re sitting down for this: every real number you’ve ever heard of<\/em> belongs to the countable dust! The entire concept of “the continuum” is only needed for reals that don’t have names and never will.<\/p>\n\n\n\n From \u21350<\/sub> Feet<\/strong><\/p>\n\n\n\n G\u00f6del and Cohen’s achievement was to show that, without creating any contradictions in set theory, we can adjust size of this elusive “continuum,” put more reals into it or fewer. How does one even start to begin to prove such a statement?<\/p>\n\n\n\n From a distance of \u21350<\/sub> feet, G\u00f6del proves the consistency of CH by building minimalist mathematical universes: one where “the only sets that exist, are the ones required<\/em> to exist by the ZFC axioms.” (These universes can, however, differ from each other in how “tall” they are: that is, in how many ordinals<\/a> they have, and hence how many sets overall. More about that in a future post!) G\u00f6del proves that, if<\/em> the axioms of set theory are consistent—that is, if they describe any universes at all—then they also describe these minimalist universes. He then proves that, in any of these minimalist universes, from the standpoint of someone within<\/em> that universe, there are exactly \u21351<\/sub> real numbers, and hence CH holds.<\/p>\n\n\n\n At an equally stratospheric level, Cohen proves the consistency of not(CH) by building … well, non<\/em>-minimalist mathematical universes! A simple way is to start with G\u00f6del’s minimalist universe—or rather, an even more minimalist universe than his, one that’s been cut down to have only countably many sets—and then to stick in a bunch of new real numbers<\/em> that weren’t in that universe before. We choose the new real numbers to ensure two things: first, we still have a model of ZFC, and second, that we make CH false. The details of how to do that will, of course, concern us later.<\/p>\n\n\n\n My Biggest Confusion<\/strong><\/p>\n\n\n\n In subsequent posts, I’ll say more about the character of the ZFC axioms and how one builds models of them to order. Just as a teaser, though, to conclude this post I’d like to clear up a fundamental misconception I had about this subject, from roughly the age of 16 until a couple months ago.<\/p>\n\n\n\n I thought: the way G\u00f6del proves the consistency of CH, must be by examining all the sets in his minimalist universe, and checking that each one has either at most \u21350<\/sub> elements or else at least C of them. Likewise, the way Cohen proves the consistency of not(CH), must be by “forcing in” some extra sets, which have more than \u21350<\/sub> elements but fewer than C elements.<\/p>\n\n\n\n Except, it turns out that’s not how it works. Firstly, to prove CH in his universe, G\u00f6del is not going to check each set to make sure it doesn’t have intermediate cardinality; instead, he’s simply going to count all the reals to make sure that there are only \u21351<\/sub> of them—where \u21351<\/sub><\/a> is the next infinite cardinality after \u21350<\/sub>. This will imply that C=\u21351<\/sub>, which is another way to state CH.<\/p>\n\n\n\n More importantly, to build a universe where CH is false, Cohen is going to start with a universe where C=\u21351<\/sub>, like G\u00f6del’s universe, and then add in more reals:<\/em> say, \u21352<\/sub> of them. The \u21351<\/sub> “original” reals will then supply our set of intermediate cardinality between the \u21350<\/sub> integers and the \u21352<\/sub> “new” reals.<\/p>\n\n\n\n Looking back, the core of my confusion was this. I had thought: I can visualize what \u21350<\/sub> means; that’s just the infinity of integers. I can also<\/em> visualize what \\( C=2^{\\aleph_0} \\) means; that’s the infinity of points on a line. Those, therefore, are the two bedrocks of clarity in this discussion. By contrast, I can’t<\/em> visualize a set of intermediate cardinality between \u21350<\/sub> and C. The intermediate infinity, being weird and ghostlike, is the one that shouldn’t exist unless we deliberately “force” it to.<\/p>\n\n\n\n Turns out I had things backwards. For starters, I can’t<\/em> visualize the uncountable infinity of real numbers. I might think<\/em> I’m visualizing the real line—it’s solid, it’s black, it’s got little points everywhere—but how can I be sure that I’m not merely visualizing the \u21350<\/sub> rationals, or (say) the computable or definable reals, which include all the ones that arise in ordinary math?<\/p>\n\n\n\n The continuum C is not at all<\/em> the bedrock of clarity that I’d thought it was. Unlike its junior partner \u21350<\/sub>, the continuum is adjustable, changeable—and we will<\/em> change it when we build different models of ZFC. What’s (relatively) more “fixed” in this game is something that I, like many non-experts, had always given short shrift to: Cantor’s sequence of Alephs \u21350<\/sub>, \u21351<\/sub>, \u21352<\/sub>, etc.<\/p>\n\n\n\n Cantor, who was a very great man, didn’t merely discover that C>\u21350<\/sub>; he also discovered that the infinite cardinalities form a well-ordered<\/a> sequence, with no infinite descending chains. Thus, after \u21350<\/sub>, there’s a next greater infinity that we call \u21351<\/sub>; after \u21351<\/sub> comes \u21352<\/sub>; after the entire infinite sequence \u21350<\/sub>,\u21351<\/sub>,\u21352<\/sub>,\u21353<\/sub>,… comes \u2135\u03c9<\/sub>; after \u2135\u03c9<\/sub> comes \u2135\u03c9+1<\/sub>; and so on. These infinities will always be there in any universe of set theory, and always in the same order.<\/p>\n\n\n\n
Con(ZFC) \u21d2 Con(ZFC+Not(CH)),<\/p>\n\n\n\n
s(1) = 01<\/strong>010101…
s(2) = 110<\/strong>01010….
s(3) = 1000<\/strong>0000….<\/p>\n\n\n\n