Huck Finn and the gaslighting of America

November 23rd, 2020

For the past month, I’ve been reading The Adventures of Huckleberry Finn to my 7-year-old daughter Lily. Is she too young for it? Is there a danger that she’ll slip up and say the n-word in school? I guess so, maybe. But I found it worthwhile just for the understanding that lit up her face when she realized what it meant that Huck would help Jim escape slavery even though Huck really, genuinely believed that he’d burn in hell for it.

Huck Finn has been one of my favorite books since I was just slightly older than Lily. It’s the greatest statement by one of history’s greatest writers about human stupidity and gullibility and evil and greed, but also about the power of seeing what’s right in front of your nose to counteract those forces. (It’s also a go-to source for details of 19th-century river navigation.) It rocks.

The other day, after we finished a chapter, I asked Lily whether she thought that injustice against Black people in America ended with the abolition of slavery. No, she replied. I asked: how much longer did it continue for? She said she didn’t know. So I said: if I told you that once, people in charge of an American election tried to throw away millions of votes that came from places where Black people lived—supposedly because some numbers didn’t exactly add up, except they didn’t care about similar numbers not adding up in places where White people lived—how long ago would she guess that happened? 100 years ago? 50 years? She didn’t know. So I showed her the news from the last hour.

These past few weeks, my comment queue has filled with missives, most of which I’ve declined to publish, about the giant conspiracy involving George Soros and Venezuela and dead people, which fabricated the overwhelmingly Democratic votes from overwhelmingly Democratic cities like Philadelphia and Milwaukee and Detroit (though for some reason, they weren’t quite as overwhelmingly Democratic as in other recent elections), while for some reason declining to help Democrats in downballot races. Always, these commenters confidently insist, I’m the Pravda-reading brainwashed dupe, I’m the unreasonable one, if I don’t accept this.

This is the literal meaning of “gaslighting”: the intentional construction of an alternate reality so insistently as to make the sane doubt their sanity. It occurred to me: Huck Finn could be read as an extended fable about gaslighting. The Grangerfords make their deadly feud with the Shepherdsons seem normal and natural. The fraudulent King and Duke make Huck salute them as royalty. Tom convinces Huck that the former’s harebrained schemes for freeing Jim are just the way it’s done, and Huck is an idiot for preferring the simplistic approach of just freeing him. And of course, the entire culture gaslights Huck that good is evil and evil is good. Huck doesn’t fight the gaslighting as hard as we’d like him to, but he develops as a character to the extent he does.

Today, the Confederacy—which, as we’ve learned the past five years, never died, and is as alive and angry now as it was in Twain’s time—is trying to win by gaslighting what it couldn’t win at Antietam and Gettysburg and Vicksburg. It’s betting that if it just insists, adamantly enough, that someone who lost an election by hundreds of thousands of votes spread across multiple states actually won the election, then it can bend the universe to its will.

Glued to the news, listening to Giuliani and McEnany and so on, reading the Trump campaign’s legal briefs, I keep asking myself one question: do they actually believe this shit? Some of the only insight I got about that question came from a long piece by Curtis Yarvin a.k.a. Mencius Moldbug, who’s been called one of the leading thinkers of neoreaction and who sometimes responds to this blog. Esoterically, Yarvin says that he actually prefers a Biden victory, but only because Trump has proven himself unworthy by submitting himself to nerdy electoral rules rather than simply seizing power. (If that’s not quite what Yarvin meant—well, I’m about as competent to render his irony-soaked meanings in plain language as I’d be to render Heidegger or Judith Butler!)

As for whether the election was “fraudulent,” here’s Yarvin’s key passage:

The fundamental purpose of a democratic election is to test the strength of the sides in a civil conflict, without anyone actually getting hurt. The majority wins because the strongest side would win … But this guess is much better if it actually measures humans who are both willing and able to walk down the street and show up. Anyone who cannot show up at the booth is unlikely to show up for the civil war. This is one of many reasons that an in-person election is a more accurate election. (If voters could be qualified by physique, it would be even more accurate) … My sense is that in many urban communities, voting by proxy in some sense is the norm. The people whose names are on the ballots really exist; and almost all of them actually did support China Joe. Or at least, preferred him. The extent to which they perform any tangible political action, including physically going to the booth, is very low; so is their engagement with the political system. They do not watch much CNN. The demand for records of their engagement is very high, because each such datum cancels out some huge, heavily-armed redneck with a bass boat. This is why, in the data, these cities look politics-obsessed, but photos of the polling places look empty. Most votes from these communities are in some sense “organized” … Whether or not such a design constitutes “fraud” is the judge’s de gustibus.

Did you catch that? Somehow, Yarvin manages to insinuate that votes for Biden are plausibly fraudulent and plausibly shouldn’t count—at least if they were cast by mail, in “many urban communities” (which ones?), during a pandemic—even as Yarvin glaincingly acknowledges that the votes in question actually exist and are actually associated with Biden-preferring legal voters. This is gaslighting in pure, abstract form, unalloyed with the laughable claims about Hugo Chávez or Dominion Voting Systems.

What I find terrifying about gaslighting is that it’s so effective. In response to this post, I’ll again get long, erudite comments making the case that up is down, turkeys are mammals, and Trump won in a landslide. And simply to read and understand those comments, some part of me will need to entertain the idea that they might be right. Much like with Bigfoot theories, this will be purely a function of the effort the writers put in, not of any merit to the thesis.

And there’s a second thing I find terrifying about gaslighting. Namely: it turns me into an ally of the SneerClubbers. Like them, I feel barely any space left for rational discussion or argument. Like them, I find it difficult to think of an appropriate response to Trumpian conspiracy theorists except to ridicule them, shame them as racists, and try to mute their influence. Notably, public shaming (“[t]he Trump stain, the stain of racism that you, William Hartmann and Monica Palmer, have covered yourself in, is going to follow you throughout history”) seems to have actually worked last week to get the Wayne County Board of Canvassers to back down and certify the votes from Detroit. So why not try more of it?

Of course, even if I agree with the wokeists that there’s a line beyond which rational discussion can’t reach, I radically disagree with them about the line’s whereabouts. Here, for example, I try to draw mine generously enough to include any Republicans willing to stand up, however feebly, against the Trump cult, whereas the wokeists draw their line so narrowly as to exclude most Democrats (!).

There’s a more fundamental difference as well: the wokeists define their worldview in opposition to the patriarchy, the white male power structure, or whatever else is preventing utopia. I, taking inspiration from Huck, define my moral worldview in opposition to gaslighting itself, whatever its source, and in favor of acknowledging obvious realities (especially realities about any harm we might be causing others). Thus, it’s not just that I see no tension between opposing the excesses of the woke and opposing Trump’s attempted putsch—rather, it’s that my opposition to both comes from exactly the same source. It’s a source that, at least in me, often runs dry of courage, but I’ve found Huck Finn to be helpful in replenishing it, and for that I’m grateful.

Endnote: There are, of course, many actual security problems with the way we vote in the US, and there are computer scientists who’ve studied those problems for decades, rather than suddenly getting selectively interested in November 2020. If you’re interested, see this letter (“Scientists say no credible evidence of computer fraud in the 2020 election outcome, but policymakers must work with experts to improve confidence”), which was signed by 59 of the leading figures in computer security, including Ron Rivest, Bruce Schneier, Hovav Shacham, Dan Wallach, Ed Felten, David Dill, and my childhood best friend Alex Halderman.

Update: I just noticed this Twitter thread by friend-of-the-blog Sean Carroll, which says a lot of what I was trying to say here.

Annual post: Come join UT Austin’s Quantum Information Center!

November 18th, 2020

Hook ’em Hadamards!

If you’re a prospective PhD student: Apply here for the CS department (the deadline this year is December 15th), here for the physics department (the deadline is December 1st), or here for the ECE department (the deadline is 15th). GREs are not required this year because of covid. If you apply to CS and specify that you want to work with me, I’ll be sure to see your application. If you apply to physics or ECE, I won’t see your application, but once you arrive, I can sometimes supervise or co-supervise PhD students in other departments (or, of course, serve on their committees). In any case, everyone in the UT community is extremely welcome at our quantum information group meetings (which are now on Zoom, naturally, but depending on vaccine distribution, hopefully won’t be by the time you arrive!). Emailing me won’t make a difference. Admissions are very competitive, so apply broadly to maximize your chances.

If you’re a prospective postdoctoral fellow: By January 1, 2021, please email me a cover letter, your CV, and two or three of your best papers (links or attachments). Please also ask two recommenders to email me their letters by January 1. While my own work tends toward computational complexity, I’m open to all parts of theoretical quantum computing and information.

If you’re a prospective faculty member: Yes, faculty searches are still happening despite covid! Go here to apply for an opening in the CS department (which, in quantum computing, currently includes me and MIP*=RE superstar John Wright), or here to apply to the physics department (which, in quantum computing, currently includes Drew Potter, along with a world-class condensed matter group).

The Complexity Zoo needs a new home

November 12th, 2020

Update (Nov. 14): I now have a deluge of serious hosting offers—thank you so much, everyone! No need for more.


Since I’m now feeling better that the first authoritarian coup attempt in US history will probably sort itself out OK, here’s a real problem:

Nearly a score years ago, I created the Complexity Zoo, a procrastination project turned encyclopedia of complexity classes. Nearly half a score years ago, the Zoo moved to my former employer, the Institute for Quantum Computing in Waterloo, Canada, which graciously hosted it ever since. Alas, IQC has decided that it can no longer do so. The reason is new regulations in Ontario about the accessibility of websites, which the Zoo might be out of compliance with. My students and I were willing to look into what was needed—like, does the polynomial hierarchy need ramps between its levels or something? The best would be if we heard from actual blind or other disabled complexity enthusiasts about how we could improve their experience, rather than trying to parse bureaucratese from the Ontario government. But IQC informed us that in any case, they can’t deal with the potential liability and their decision is final. I thank them for hosting the Zoo for eight years.

Now I’m looking for a volunteer for a new host. The Zoo runs on the MediaWiki platform, which doesn’t work with my own hosting provider (Bluehost) but is apparently easy to set up if you, unlike me, are the kind of person who can do such things. The IQC folks kindly offered to help with the transfer; I and my students can help as well. It’s a small site with modest traffic. The main things I need are just assurances that you can host the site for a long time (“forever” or thereabouts), and that you or someone else in your organization will be reachable if the site goes down or if there are other problems. I own the complexityzoo.com domain and can redirect from there.

In return, you’ll get the immense prestige of hosting such a storied resource for theoretical computer science … plus free publicity for your cause or organization on Shtetl-Optimized, and the eternal gratitude of thousands of my readers.

Of course, if you’re into complexity theory, and you want to update or improve the Zoo while you’re at it, then so much the awesomer! It could use some updates, badly. But you don’t even need to know P from NP.

If you’re interested, leave a comment or shoot me an email. Thanks!!

Unrelated Announcement: I’ll once again be doing an Ask-Me-Anything session at the Q2B (“Quantum to Business”) conference, December 8-10. Other speakers include Umesh Vazirani, John Preskill, Jennifer Ouellette, Eric Schmidt, and many others. Since the conference will of course be virtual this year, registration is a lot cheaper than in previous years. Check it out! (Full disclosure: Q2B is organized by QC Ware, Inc., for which I’m a scientific advisor.)

On defeating a sociopath

November 9th, 2020

There are people who really, genuinely, believe, as far as you can dig down, that winning is everything—that however many lies they told, allies they betrayed, innocent lives they harmed, etc. etc., it was all justified by the fact that they won and their enemies lost. Faced with such sociopaths, people like me typically feel an irresistible compulsion to counterargue: to make the sociopath realize that winning is not everything, that truth and honor are terminal values as well; to subject the sociopath to the standards by which the rest of us are judged; to find the conscience that the sociopath buried even from himself and drag it out into the light. Let me know if you can think of any case in human history where such efforts succeeded, because I’m having difficulty doing so.

Clearly, in the vast majority of cases if not in all, the only counterargument that a sociopath will ever understand is losing. And yet not just any kind of losing suffices. For victims, there’s an enormous temptation to turn the sociopath’s underhanded tools against him, to win with the same deceit and naked power that the sociopath so gleefully inflicted on others. And yet, if that’s what it takes to beat him, then you have to imagine the sociopath deriving a certain perverse satisfaction from it.

Think of the movie villain who, as the panting hero stands over him with his lightsaber, taunts “Yes … yes … destroy me! Do it now! Feel the hate and the rage flow through you!” What happens next, of course, is that the hero angrily decides to give the villain one more chance, the ungrateful villain lunges to stab the hero in the back or something, and only then does the villain die—either by a self-inflicted accident, or else killed by the hero in immediate self-defense. Either way, the hero walks away with victory and honor.

In practice, it’s a tall order to arrange all of that. This explains why sociopaths are so hard to defeat, and why I feel so bleak and depressed whenever I see one flaunting his power. But, you know, the great upside of pessimism is that it doesn’t take much to beat your expectations! Whenever a single sociopath is cleanly and honorably defeated, or even just rendered irrelevant—no matter that the sociopath’s friends and allies are still in power, no matter that they’ll be back to fight another day, etc. etc.—it’s a genuine occasion for rejoicing.

Anyway, that pretty much sums up my thoughts regarding Arthur Chu. In other news, hooray about the election!

Five Thoughts

November 7th, 2020

(1) A friend commented that Biden’s victory becomes more impressive after you contemplate the enthusiasm gap: Trump’s base believed that Trump was sent by God, whereas Biden’s base believed that Biden probably wasn’t a terrible human being. I replied that what we call the “Enlightenment” was precisely this, the switch from cowering before leaders who were sent by God to demanding leaders who probably aren’t terrible human beings.

(2) I would love for Twitter to deactivate Trump’s account—not for any ideological reason, simply for Trump’s hundreds of past violations of Twitter’s Terms of Service, and for there no longer being a compelling public interest in what Trump has to say that would override all his Terms of Service violations.

(3) When Biden appeared last night, and then again tonight, it wasn’t merely that he came across like a President-Elect of the US, but rather that he came across like a President-Elect of the US who’s filling a vacant position. Until Biden starts, there won’t be a president of the US; there will only continue to be the president of those who voted for him.

(4) Now that Trump has gone this far in shattering all the norms of succession, part of me wants to see him go the rest of the way … to being physically dragged out of the Oval Office by Secret Service agents on January 20, in pathetic and humiliating footage that would define how future generations remembered him.

(5) I had an idea for something that could make a permanent contribution to protecting liberal democracy in the US, and that anti-Trump forces could implement unilaterally for a few tens of millions of dollars—no need to win another election. The idea is to build a Donald J. Trump Historical Museum in Washington, DC. But, you see, this museum would effectively be the opposite of a presidential library. It would be designed by professional historians; they might solicit cooperation from former members of Trump’s inner circle, but would never depend on it. It would, in fact, be a museum that teenage students might tend to be taken to on the same DC field trips that also brought them to the Vietnam Memorial and the United States Holocaust Memorial Museum (USHMM). Obviously, the new museum would be different from those bleak places; it would (thankfully) have a little less tragedy and more farce … and that’s precisely the role that the new museum would fill. To show the kids on the field trips that it’s not always unmitigated horribleness, that here was a case where we Americans took a gigantic stumble backwards, seeming to want to recreate the first few rooms in the USHMM exhibition, the one where the macho-talking clown thrills Germany by being serious rather than literal. But then, here in the US, we successfully stopped it before it got to the later rooms. Sure, the victory wasn’t as decisive as we would’ve liked, it came at a great cost, but it was victory nonetheless. A 244-year-old experiment in self-governance is back in operation.

On the removal of a hideous growth

November 6th, 2020

The title of this post is not an allegory.

At 10am this morning, I had a previously-scheduled appointment with an oral surgeon to remove a large, hideous, occasionally painful growth on the inside of my lower lip. (I’d delayed getting it looked at for several months because of covid, but I no longer could.)

So right now I’m laying in bed at home, with gauze on my lips, dazed, hopped up on painkillers. I regret that things ever got to the point where this was needed. I believe, intellectually, that the surgeon executed about as competently as anyone could ask. But I still wish, if we’re being honest, that there hadn’t been quite this much pain in the surgery or in the recovery from it.

Again intellectually, I know that there’s still lots more pain in the days ahead. I’m not sure that whatever it was won’t just quickly grow back. And yet, I couldn’t be feeling more joy through my whole body with every one of these words that I write. At last I can honestly tell myself: the growth is gone.

A Drawing for Singularity Eve

November 2nd, 2020

Lily, my 7-year-old, asked me to share the above on my blog. She says it depicts the US Army luring Trump out of the White House with a hamburger, in order to lock the front door once he’s out—what she proposes should happen if Trump refuses to acknowledge a loss.

If you haven’t yet voted, especially if you live in a contested state, please do so tomorrow. Best wishes to us all!

Update (Nov. 3): Even if it comes 4-5 years late, this 8-minute podcast by Sam Harris gives perhaps the sharpest solution ever articulated to the mystery of how tens of millions of Americans could enthusiastically support an obvious fraud, liar, incompetent, and threat to civilization. Briefly, it’s not despite his immense failings but because of them—because by flaunting his failings he absolves his supporters for their own, even while the other side serves those same supporters relentless moral condemnation and scorn. I think I had known this—I even said something similar as the tagline of this blog (“The Far Right is destroying the world, and the Far Left thinks it’s my fault!”). But Sam Harris expresses it as only he can. If this analysis is right—and I feel virtually certain it is—then it bodes well that Biden, unlike Hillary Clinton, isn’t seen as especially sanctimonious or judgmental. Biden’s own gaffes and failings probably help him.

The Complete Idiot’s Guide to the Independence of the Continuum Hypothesis: Part 1 of <=Aleph_0

October 31st, 2020

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.

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 (CH) from the standard foundation of mathematics, the Zermelo-Fraenkel axioms of set theory. (In this post, I’ll typically refer to “ZFC,” which means Zermelo-Fraenkel plus the famous Axiom of Choice.)

For those tuning in from home, the Continuum Hypothesis was formulated by Georg Cantor, 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 ℵ0, or “Aleph-zero”). CH is simply the statement that there’s no infinity intermediate between ℵ0 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 of 23 unsolved math problems in 1900, CH was at the very top.

Halfway between Hilbert’s speech and today, the question of CH was finally “answered,” with the solution earning the only Fields Medal 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 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 have intermediate infinities, it’s up to you how many: 1, 5, 17, ∞, etc.

The easier half, the consistency of CH with set theory, was proved by incompleteness dude Kurt Gödel in 1940; the harder half, the consistency of not(CH), by Paul Cohen in 1963. Cohen’s work introduced the method of forcing, which was so fruitful in proving set-theoretic questions unsolvable that it quickly took over the whole subject of set theory. Learning Gödel and Cohen’s proofs had been a dream of mine since teenagerhood, but one I constantly put off.

This time around I started with Cohen’s retrospective essay, as well as Timothy Chow’s Forcing for Dummies and A Beginner’s Guide to Forcing. I worked through Cohen’s own Set Theory and the Continuum Hypothesis, and Ken Kunen’s Set Theory: An Introduction to Independence Proofs, and Dana Scott’s 1967 paper 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 (one of the world’s great set theorists, who later worked in computational complexity and quantum computing), or Andreas Blass or Asaf Karagila. At some point mathematician and friend-of-the-blog Greg Kuperberg 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.

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 know them.

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, 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.

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 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.

Still, there is one 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 in computational complexity theory. In CS, we like to construct hypothetical universes where P=NP or P≠NP, or P≠BQP, or the polynomial hierarchy is infinite, etc. To do so, we, by fiat, insert a new function—an oracle—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.

All this, I kept reading, is profoundly 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—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.

How Could It Be?

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 no answer? I mean: even supposing it’s true that there’s no answer, how do you prove such a thing?

Arguably, not even Gödel’s Incompleteness Theorem 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 (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, consistent; it’s just that resources beyond F are needed to prove this.

Yes, there’s a “self-hating theory,” F+Not(Con(F)), which believes in its own inconsistency. And yes, by Gödel, this self-hating theory is consistent if F itself is. This means that it has a model—involving “nonstandard integers,” formal artifacts that effectively promise a proof of F’s inconsistency without ever actually delivering it. We’ll have much, much 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!).

In any case, though, the self-hating theory F+Not(Con(F)) can’t be arithmetically sound: 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. If I believe that the moon is made of cheese, that might be consistent 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. 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 between what’s inside my head and what’s outside it.

So again, assuming we had any business using F in the first place, the Incompleteness Theorem gives us two consistent ways to extend F (by adding Con(F) or by adding Not(Con(F))), but only one sound 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 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ödel hoped, answers the question by going beyond ZFC.

Four Levels to Unpack

While experts might consider this too obvious to spell out, Gödel’s and Cohen’s analyses of CH aren’t so much about infinity, as they are about our ability to reason 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, by containing vastly fewer objects than the mathematical universe was “meant” to have.

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.

At the first level, Gödel’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 the axioms of set theory, they don’t themselves require those axioms. Again, this is possible because, at the end of the day, Gödel’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.

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 was inconsistent. In symbols, they’re proving the “relative consistency statements”

Con(ZFC) ⇒ Con(ZFC+CH),
Con(ZFC) ⇒ Con(ZFC+Not(CH)),

and they’re proving these as theorems of elementary arithmetic. (Note that there’s no hope of proving Con(ZF+CH) or Con(ZFC+Not(CH)) outright within ZFC, since by Gödel, ZFC can’t even prove its own consistency.)

This translation is completely explicit; the independence proofs even yield algorithms to convert proofs of inconsistencies in ZFC+CH or ZFC+Not(CH), supposing that they existed, into proofs of inconsistencies in ZFC itself.

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 to.

This brings us to the third level: the symbols refer to models of set theory, which could also be called “mathematical universes.” Crucially, we always can and often will take these models to be only countably infinite: that is, to contain an infinity of sets, but “merely” ℵ0 of them, the infinity of integers or of finite strings, and no more.

The fourth level of description is from within the models themselves: each model imagines itself to have an uncountable 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 it has uncountably many sets, many themselves of uncountable cardinality, even if “from the outside” the model is countable.

Say what? The models are mistaken about something as basic as their own size, about how many sets they have? Yes. The models will be like The Matrix (the movie, not the mathematical object), or The Truman Show. 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 they mistakenly think of as the universe—is secretly countable! And no Morpheus 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 arrive.

The Löwenheim-Skolem Theorem, from the early 1920s, says that any 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öwenheim-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,” because pretty much the entire proof of the independence of CH is built on top of it.

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 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. We can’t rule out the possibly that God, looking down on our universe, would see countably many reals.

Cantor’s Proof Revisited

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.

Recall how Cantor’s proof works: we suppose by contradiction that we have an enumeration of all infinite binary sequences: for example,

s(0) = 00000000…
s(1) = 01010101…
s(2) = 11001010….
s(3) = 10000000….

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…

But look more carefully. What Cantor really shows is only that, within our mathematical universe, 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 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 enumeration).

Which reals could possibly be “missing” from our universe? Every real you can name—42, π, √e, even uncomputable reals like Chaitin’s Ω—has to be there, right? Yes, and there’s the rub: every real you can name. 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.

Or did you think of only the rationals or algebraic numbers as forming a countable dust of discrete points, with numbers like π 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 belongs to the countable dust! The entire concept of “the continuum” is only needed for reals that don’t have names and never will.

From ℵ0 Feet

Gödel 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?

From a distance of ℵ0 feet, Gödel proves the consistency of CH by building minimalist mathematical universes: one where “the only sets that exist, are the ones required 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 they have, and hence how many sets overall. More about that in a future post!) Gödel proves that, if 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 that universe, there are exactly ℵ1 real numbers, and hence CH holds.

At an equally stratospheric level, Cohen proves the consistency of not(CH) by building … well, non-minimalist mathematical universes! A simple way is to start with Gödel’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 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.

My Biggest Confusion

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.

I thought: the way Gödel 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 ℵ0 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 ℵ0 elements but fewer than C elements.

Except, it turns out that’s not how it works. Firstly, to prove CH in his universe, Gödel 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 ℵ1 of them—where 1 is the next infinite cardinality after ℵ0. This will imply that C=ℵ1, which is another way to state CH.

More importantly, to build a universe where CH is false, Cohen is going to start with a universe where C=ℵ1, like Gödel’s universe, and then add in more reals: say, ℵ2 of them. The ℵ1 “original” reals will then supply our set of intermediate cardinality between the ℵ0 integers and the ℵ2 “new” reals.

Looking back, the core of my confusion was this. I had thought: I can visualize what ℵ0 means; that’s just the infinity of integers. I can also 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 visualize a set of intermediate cardinality between ℵ0 and C. The intermediate infinity, being weird and ghostlike, is the one that shouldn’t exist unless we deliberately “force” it to.

Turns out I had things backwards. For starters, I can’t visualize the uncountable infinity of real numbers. I might think 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 ℵ0 rationals, or (say) the computable or definable reals, which include all the ones that arise in ordinary math?

The continuum C is not at all the bedrock of clarity that I’d thought it was. Unlike its junior partner ℵ0, the continuum is adjustable, changeable—and we will 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 ℵ0, ℵ1, ℵ2, etc.

Cantor, who was a very great man, didn’t merely discover that C>ℵ0; he also discovered that the infinite cardinalities form a well-ordered sequence, with no infinite descending chains. Thus, after ℵ0, there’s a next greater infinity that we call ℵ1; after ℵ1 comes ℵ2; after the entire infinite sequence ℵ0,ℵ1,ℵ2,ℵ3,… comes ℵω; after ℵω comes ℵω+1; and so on. These infinities will always be there in any universe of set theory, and always in the same order.

Our job, as engineers of the mathematical universe, will include pegging the continuum C to one of the Alephs. If we stick in a bare minimum of reals, we’ll get C=ℵ1, if we stick in more we can get C=ℵ2 or C=ℵ3, etc. We can’t make C equal to ℵ0—that’s Cantor’s Theorem—and we also can’t make C equal to ℵω, by an important theorem of König that we’ll discuss later (yes, this is an umlaut-heavy field). But it will turn out that we can make C equal to just about any other Aleph: in particular, to any infinity other than ℵ0 that’s not the supremum of a countable list of smaller infinities.

In some sense, this is the whole journey that we need to undertake in this subject: from seeing the cardinality of the continuum as a metaphysical mystery, which we might contemplate by staring really hard at a black line on white paper, to seeing the cardinality of the continuum as an engineering problem.

Stay tuned! Next installment coming after the civilizational Singularity in three days, assuming there’s still power and Internet and food and so forth.

Oh, and happy Halloween. Ghostly sets of intermediate cardinality … spoooooky!

Vote in person if you can

October 13th, 2020
Image may contain: 1 person, eyeglasses and closeup

[If you’re not American, or you’re American but a masochist who enjoys the current nightmare, this post won’t be relevant to you—sorry!]

Until recently, this blog had a tagline that included “HOLD THE NOVEMBER US ELECTION BY MAIL.” So I thought I should warn readers that circumstances have changed in ways that have important practical implications over the next few weeks. It’s no longer that we don’t know whether Trump and Pence will acknowledge a likely loss—rather, it’s that we know they won’t. They were repeatedly asked; we all heard their answers.

That means that the best case, the ideal scenario, is already without precedent in the country’s 240-year history. It’s a president who never congratulates the winner, who refuses to meet him or coordinate a transfer of power, who skips the inauguration, and who’s basically dragged from the White House on January 20, screaming to his supporters (and continuing to scream until his dying breath) that the election was faked.

As I said, that banana-republic outcome is now the best case. But it’s also plausible that Trump simply declares himself the winner on election night, because the mail-in votes, urban votes, yet-to-be-counted votes, or any other votes that trend the wrong way are fake; social media and the Murdoch press amplify this fantasy; Trump calls on Republican-controlled state legislatures to set aside the “rigged” results and appoint their own slates of electors; the legislatures dutifully comply; and the Supreme Court A-OKs it all. If you think none of that could happen, read this Atlantic article from a few weeks ago, carefully to the end, and be more terrified than you’ve ever been in your life. And don’t pretend that you know what would happen next.

I know, I know, I’m mentally ill, it’s Trump Derangement Syndrome, I see Nazis behind every corner just because they killed most of my relatives, a little global pandemic here and economic collapse there and riots and apocalyptic fires and resurgent fascism and I act as though it’s the whole world coming to an end. A few months from now, after everything has gone swimmingly, this post will still be here and you can come back and tell me how crazy I was. I accept that risk.

For now, though, the best chance to avert a catastrophe is for Trump not merely to lose, but lose in a landslide that’s already clear by election night. Which means: as Michelle Obama advised already in August, put on your mask, brave the virus, and vote in person if you can—especially if you live in a state that’s in play, and that won’t start tallying mail-in ballots till after election day. If your state allows it, and if early votes will be counted by election night (check this!), vote early, when the lines are shorter. That’s what Dana and I did this morning; Texas going blue on election night would be one dramatic way to foreclose shenanigans. If you can’t vote in person, or if your state counts mail-in ballots earlier, then vote by mail or drop-box, but do it now, so you have a chance to fix any problems well before Election Day. (Note that, even in normal circumstances—which these aren’t—a substantial fraction of all mail-in ballots get rejected because of trivial errors.) I welcome other tips in the comments, from the many readers more immersed in this stuff than I am.

And if this post helped spur you in any way, please say so in the comments. It will improve my mood, thereby helping me finish my next post, which will be on the Continuum Hypothesis.

Update: It’s always fascinating to check my comments and see the missives from parallel universes, where Trump is a normal candidate who one might decide to vote for based on normal criteria, rather than what he himself has announced he is: a knife to the entire system that underlies such decisions. For a view from this universe, see (e.g.) today’s Nature editorial.

Another Update: If it allays anyone’s fears, I was pleasantly surprised by the level of pandemic preparedness when Dana and I went to vote. It was in a huge, cavernous gym on the UT campus, the lines were very short, masks and 6ft distancing were strictly enforced, and finger-coverings and hand sanitizer were offered to everyone.

Unrelated Update (10/16): For those who are interested, here’s a new podcast with me and Matt Asher, where we talk about the use of quantum mechanics (especially Bell inequality violations) to generate certified random numbers.

My second podcast with Lex Fridman

October 12th, 2020

Here it is—enjoy! (I strongly recommend listening at 2x speed.)

We recorded it a month ago—outdoors (for obvious covid reasons), on a covered balcony in Austin, as it drizzled all around us. Topics included:

  • Whether the universe is a simulation
  • Eugene Goostman, GPT-3, the Turing Test, and consciousness
  • Why I disagree with Integrated Information Theory
  • Why I disagree with Penrose’s ideas about physics and the mind
  • Intro to complexity theory, including P, NP, PSPACE, BQP, and SZK
  • The US’s catastrophic failure on covid
  • The importance of the election
  • My objections to cancel culture
  • The role of love in my life (!)

Thanks so much to Lex for his characteristically probing questions, apologies as always for my verbal tics, and here’s our first podcast for those who missed that one.