Gödel's Incompleteness Theorem Explained: Correcting Misconceptions

[00:00:00]Many popularizers who use Gödel's incompleteness  theorem to make bold claims about fundamental limits of human knowledge have made a category  error. Neil deGrasse Tyson: "Gödel, he concluded that at some point in mathematics, you just have  to make something up!" Deepak Chopra: "Gödel's theorem shows the limitations of almost  every theory of reality. My favorite is consciousness." Veritasium: "There is a hole at  the bottom of math, a hole that means we will never know everything with certainty." Today  I'll cover misuses, why they're misuses, and I'll also talk about what Gödel's theorem actually  says because to state it in its catchy glib form misses the necessary rigor required to know its  domain of application. The TLDR is that Gödel's incompleteness theorem is about axiomatization,  not epistemology. Now there's an asterisk here, which I'll get to later. Epistemology is just  fancy technical jargon for what and how we can know. So, knowledge. "KNOWLEDGE." The gist of  Gödel is that someone can hand you any concrete, mechanically checkable theory, let's call it F,  and Gödel's machinery then spits out explicit arithmetic statements, maybe a busy beaver  statement, that F, your little machinery here, can neither prove nor disprove. Those sentences set a  hard ceiling for that particular proof verifier, even though you yourself can always zoom out, beef  up the axioms, and push the line further. See this excellent exposition here by Scott Aaronson on  that. As for these other more pop-sci videos, I used to believe these slogans as well. It's  difficult not to be seduced by the mysticism around Gödel's theorem. That changed for me,  personally, when I was at the University of Toronto. It was there that I took a course where  part of the final exam was to actually prove Gödel's first incompleteness theorem, assuming  only a specific model of arithmetic. Now, this was tricky because not only did you have to be acutely  clear in each line of reasoning, but you had to properly understand the assumptions. For instance,  what does it mean to be powerful enough to encode arithmetic? Power's not a math word in this  context. What are we, Thanos? What's arithmetic?

[00:02:12]What's a model? What's an interpretation? What's  a universe in model theory? What's the difference between syntax and semantics? Now, I bring this  up not because I'll be assuming you know these, but to emphasize that theorems are all based on  terribly tedious assumptions that one can't just gloss over. Gödel was a mathematical genius, one  of Einstein's closest friends in his later years.

[00:02:35]In 1931, Gödel blew apart Hilbert's program  in a single stroke. He severed mathematical truth from formal proof. He also fixed exact  limits on axiomatization. He also helped lay the bedrock for computability theory. And  he also guaranteed that these undecidable problems will exist forever. And that's all just  from one year. Add Gödel's completeness theorem, which yields the compactness principle. Also  the constructible universe, which proved the consistency of the generalized continuum  hypothesis with the axiom of choice. And then, of course, his rotating universe solution that  he gave to Einstein as a 70th birthday present, where there are time travel solutions in general  relativity. All of that is fantastic and can't be understated. Now, let's get back to that  one-liner. Gödel's incompleteness theorem is about axiomatization and not epistemology. Questions  in the field of epistemology are questions that deal with the nature and sources and limits of  knowledge. The nature of knowledge even includes defining what knowledge is. Now, this isn't  trivial. You can see the Gettier's problem and the recent deep dive with Jennifer Nagel. Link  will be in the description. On the other hand, Gödel's incompleteness theorems are regarding  what can be proven within a formal system. Now, every word here is important. First, notice that  there's a plural, and that's because there are two incompleteness theorems. The one that most people  talk about when they mention his incompleteness theorem is the first one. Actually, something you  should notice is that I keep saying Gödel. That's just my English pronunciation of his name. You're  stuck with it. Formal has a specific meaning, and within also has a specific meaning. The claims  of Gödel's theorems are of a different domain than the claims in epistemology. The confusion between  this has led to some wild misinterpretations, allowing pundits to import metaphysics through a  linguistic loophole. You know I'm a fan of rigor on this channel, so let's at least be slightly  more rigorous and clarify what Gödel actually proved. Any consistent recursive axiomatization  of arithmetic is incomplete. Again, each word here is important. If you have a formal system that's  consistent, so it doesn't prove contradictions, and it can be mechanically checked,  so that's the recursive axiomatization, then there will always be true statements  capable of being stated within that system, but that can't be proved within the system  itself. Neither can you prove its negation.

[00:05:02]Sounds profound. However, unless you already  think knowledge is a single fixed formal system, that we are trapped in Robinson arithmetic, say,  then it's difficult to see why this would have any implication on our general limitations, or lack  thereof, of knowledge. But why? Well, for one, we use multiple systems for knowledge generation.  Not just formal. We also use informal reasoning, like intuition. We also use empirical observation.  As an aside here, you may wonder, but Curt, wait, doesn't Penrose have something to say about this?  Doesn't he have an argument in this domain? Yes.

[00:05:38]And I've spoken to Penrose twice. I'll place links  in the description. And at another point on this channel, I'll cover where what I'm about to say  in this entire video either agrees with Penrose, diverges from him, or is independent  of him. Aside over. Now, furthermore, unlike what you may infer from Russell's 200-page  proof of 1 plus 1 equals 2, we don't actually use axioms to justify our knowledge. Instead, we use  our prior established mathematical knowledge to justify the fittedness of some axiomatic system.  So it's directly the opposite. Russell himself even remarked about this. In some sense, using  axioms to justify our knowledge would be like building scaffolding to support the ground. Sure,  it's impressive, but entirely unnecessary. Anyhow, even further, we didn't need Gödel to tell us  that there exists some facts about math that will forever be beyond our grasp. Why? Because  unless you're this metaverse-merging Zuckerberg, you have finite working memory. You have finite  processing speed. You even have a finite life. So you can't mentally compute some, say, 94,000-digit  addition problem, let alone something with googolplex digits, let alone some exam paper with  basic addition problems so large that it stretches beyond the boundaries of the observable universe.  You'd have no hope of comprehending it, let alone completing it. Now, let's get to some of these  misconceptions. Deepak: "Gödel's theorem shows the limitations of almost every theory of reality.  My favorite is consciousness-only monism." No, not exactly. Gödel shows only that formal,  recursively axiomatized systems of arithmetic leave some arithmetic truths unprovable. Nothing  in the proof even mentions consciousness, mind-matter dualism, non-dualism, or a purely  rational description. As Gregory Chaitin likes to say, truth outruns proof. But that's a fact inside  math. It's not carte blanche for metaphysics. It's important to be clear in one's presentations  of mathematical and physics material. Actually, I was scheduled to speak with Deepak in person on  this channel. But I told his people, respectfully, that I would have to question him on some spurious  uses of quantum physics if he was to bring that up. And then they cancelled the day before the  scheduled interview. Note that this wasn't Deepak cancelling, it was someone or some people on his  team. For all I know, Deepak has no idea about any of this. Neil deGrasse Tyson: "Can mathematics  be constructed as a completely self-consistent set of rules? And Gödel concluded, and it's  not just because he pulled it out of his ass, he can show that at some point in mathematics,  you just have to make something up." Now, this one is an odd one. It sounds like what Neil is  talking about is just axioms, which are what you assume to be true. But Gödel didn't show that you  have to have axioms. The necessity of axioms is a fundamental prerequisite for the kind of formal  deductive systems that Gödel was analyzing. So Neil deGrasse Tyson was accurately describing the  nature of axioms in some sense, although I would disagree with that we just make anything up. But  he mistakenly presents this as the core revelation of Gödel's incompleteness theorems. Also, as  we mentioned with Bertrand Russell, you aren't looking for arbitrary axioms, but rather your  axioms are justified by their consequences. I've heard Michio Kaku say that Gödel's theorem implies  that we'll never know a theory of everything in physics, but this is another misstep.  Incompleteness is about proof-theoretic closure, not about differential equations describing  nature. Philosopher Graham Oppie points out that Gödel places no a priori barrier on how  well equations can model empirical data. In other words, Gödel doesn't equal epistemology. The  theorem shows a technical fact about recursively axiomatized formal systems. It's silent on  what human beings or physicists can know by other means, such as intuition, experiments,  higher-order logics, new axioms, etc. Also, one shouldn't confuse proof with some capital-T truth.  Incompleteness is an internal mathematical gap, but it doesn't automatically license metaphysical  conclusions about consciousness, God, multiverses, etc. Physics isn't obviously a Gödel-style system.  A physical TOE may be stochastic, or continuous, or even algorithmically infinite. Gödel's diagonal  step needs none of these. Physics, after all, is science, not mathematics. We use mathematics  because it works, not because we think nature is mathematics. This, in my present deliberations,  is a correct statement. Physics is model-based and provisional. See my recent video about why  the so-called proofs that particles take all possible paths is faulty. Veritasium: "There is a  hole at the bottom of math, a hole that means we will never know everything with certainty." No,  not exactly, Derek. Gödel shows that no single recursively axiomatized system can prove all  arithmetic truths. Not that human beings, who can move between systems, by the way, will never know  everything for certain. I've heard a popularizer say that Gödel showed that mathematics collapses under  its own weight. Math didn't collapse. The Gödel's theorem only blocks a complete and consistent  single axiom set, not mathematical reasoning as a whole. By the way, a subtle and extremely  important point that many seem to miss is that these unprovable truths by Gödel, the ones that  Gödel guarantees via his sentences, they're not globally true. Now, why is that? It's because of  Gödel's completeness theorem, which is a different theorem. If a statement is true in all models,  then your system necessarily proves it. And this contradicts its unprovability. Therefore, any  undecidable statement is true in some models and false in others. It counts only as true relative  to a certain model, and it's usually the standard one. So these unprovable truths aren't some stash  of universal facts forever beyond reach. They're actually model dependent. Now, you may get the  impression that, well, these experts, they don't know what they're talking about. But that's not  the correct takeaway. These are extremely bright and precise people. What's funny is that I find  most physicists are quite humble and tentative when it comes to ontological or epistemological  claims behind closed doors. You can see this on this channel itself, this theories of everything  podcast that I have. This is something that I try to elicit because I treat this podcast  like office hours, as if I'm privately in a professor's office asking questions and I don't  care about the audience. And the professors, they notice that. They just speak to me with the  same level of technicality that they would behind closed doors. And the audience is just there like  a fly on the wall. It's difficult to do open door physics. But by the way, someone who does do  open door physics extremely well is Gabriel Karkassi. But, however, Gabriel is rare. And for  some reason, when something is framed as this is for a general audience, those popularizers go into  this orchidaceous popular science communication mode. They want to convey some voodoo to seduce  the audience. Someone said about my previous video about all possible paths. They said like, Curt,  come on. You're fighting a straw man because no physicist actually claims that particles literally  explore all possible paths. At Barf Manager, I'm sorry to disappoint you. Brian Cox: "And let  me use my language carefully. I was going to say it is 'as if.' Many physicists would say, 'no,  it does!' So the statement is that the electron explores both routes at the same time. At once,  let's say, on its route from the electron gun through the slits to the screen. Many physicists  now would say that that is a correct description of reality. The particle does." And this, by  the way, was on a large channel explaining physics to millions of people. I think that's  more harmful in the long run, since it leads to misconceptions that others have to dispel.  And then the popularizer of science who came in with those claims feels like they have to defend  themselves. And then so they do. And the audience just sees this conflict and combativeness. It  gives credence to those who want to dismiss science or scientists as not knowing what they're  talking about. Claiming, hey, it's all conjecture, etc. I think it's more fruitful from the get-go to  be honest about what we don't know and where our theories begin and end. It's more honest, at least  I think so, to spend the extra few minutes to say what you want to say more precisely with the  correct caveats. Now, I understand the alternative is to cajole the audience with showy quantum  pornography to continue to sell seats or get more views. But who cares? Who cares if that's at the  expense of adding more confusion? Or even worse, making the audience feel like they understood  something on a deep level when what was presented was superficial, with analogies that don't hold  up under just two levels of question-asking. I would imagine that acknowledging shortcomings or  those disasters openly enhances long-term trust by demonstrating a commitment to validity over  reputation. Now again, a refrain on this channel is to not wholesale by what anyone is saying,  not even me. You have to listen to the arguments and not be swayed by pomp and circumstance. One  always has to ask, what is the specific argument?

[00:15:09]Understand it. When critiquing something,  critique that. Not the person, not the person's affiliations, or lack thereof, or the animation,  or what have you. When critiquing, you think, what is the claim, and the argumentation for  that claim or the justification, and that's it.

[00:15:28]Getting back to incompleteness, our inability  to grasp most of the theorems of arithmetic or Robinson arithmetic has nothing to do with Gödel  and everything to do with our finite cognitive capacities. Even if we somehow overcame these  girdalian limitations, these mundane constraints would still prevent us from knowing many, if not  most, mathematical truths, like those high-digit span tests that we talked about earlier. Also,  think about this. You know that the Gödel sentence itself is true, despite being unprovable within  the system. How? Because you can step outside the formal system and use meta-reasoning. You are  not that single formal system. This fact alone dismantles the claim that Gödel's theorem imposes  fundamental epistemological limits. You should know, though, that you have this undecidable  truth, and you may think, okay, well, why can't I just append it to my axiom set for some given  fixed theory? That still doesn't erase the ceiling that Gödel set. It just relocates it. Because the  stronger theory that you've now formed carries its own incompleteness sentence, and that just goes  on ad infinitum. Chaitin says that rather than Gödel giving us limits, Gödel's freed us. Gregory  Chaitin, by the way, is the founder of algorithmic information theory, who basically pioneered  a whole new field of math when he was just a teenager after being inspired by Gödel. Gregory  Chaitin: "I view it as saying that mathematics is creative, and will always be creative. Gödel  incompleteness is really good news. It's not bad news. It's not a closed system. It's an open  system." Now, let's get back to that asterisk that I talked about earlier. It's that every computable  proof engine is an axiom system. So, so what, and what does that mean? Well, Gödel's theorem still  marks objective limits on what such an engine can certify. Now, the tie to epistemology does come  from our tie to relying on these external proof checkers for these undecidable theorems. The  Paris-Harrington theorem is another example, as it shows there exist statements that are  unprovable in piano arithmetic, or what have you, yet are actually proven using other mathematical  resources. Therefore, we have knowledge of these truths, despite them being unprovable in one  formal system. So, as Graham Oppie points out, when theologians compare our knowledge of  mathematics to our knowledge of God, claiming both are fundamentally linked by girdelian  restraints, they're making an elementary category error. Our mathematical knowledge isn't analogous  to our theological knowledge. And Gödel's theorem doesn't support any such analogy. Likewise,  when continental philosophers invoke Gödel to defend notions of radical indeterminacy or  undecidability of theories, they're misapplying a precisely defined mathematical result to  vaguely articulated philosophical positions. Now, someone asked me, but Curt, doesn't Gödel imply  that our knowledge is partial? And I'll just summarize this conversation, I'll put a link on  screen. I asked in response, what do you mean by partial? Do you mean finite, like some decidable  theory? And the conversation partner said, yes. And I then went on to explain that Gödel  relies on an infinite arithmetic. Otherwise, every theorem could be listed in full, because the  set would be finite, and membership then could be mechanically decided by a straightforward brute  force inspection. This person was then saying, okay, so then should we not use Gödel's theorem  as a simile for knowledge? And then my claim is that knowledge is quite slippery here. The point  is that the Gödel sentence is constructed using the assumption that the underlying formalism  contains the whole of elementary arithmetic, meaning you can always form numerals of unbounded  size, and prove addition and multiplication facts for each of them, etc. And that unboundedness is  the infinity that's baked into the proof. So if you impose a hard bound on numeral size, then the  whole incompleteness argument never even starts.

[00:19:30]Even if our minds were formal systems, no one is  consistent in their beliefs. Thus, Gödel's theorem wouldn't apply to your knowledge generation  anyhow, if you're basing your generation on some formal analogy with belief as axioms, since,  recall, one of the assumptions of Gödel's theorem was consistency to begin with. Now, it turns out,  axiomatization does not equal knowledge. To me, that's a huge takeaway from Gödel, although  you arguably could have concluded that from the Lohenheim-Skolem theorems a few years before.  I wrote a Substack post about this, and I'll place a link on screen and in the description. Note that  I worked on this video on and off for a few weeks writing the script, and I tried to simplify it,  but I decided it was better to be honest with you about the complexity and tell you the details,  along with signposts and references, for you to learn more, than to try to wow you with some  cursory response that may leave you saying, whoa, my mind is blown, but then a day later you're  left scratching your head like, wait, what did I actually learn? The overall lesson is that Gödel's  incompleteness theorem is an extremely specific theorem with extremely specific assumptions that  are quite thorny to untangle. Gödel sharpened vagueness by pinpointing concrete arithmetic  statements that no fixed, consistent, computable axiom set can nail down. The relationship  between formal systems and human cognition isn't straightforward, and while we aren't identical  to current formal systems, the extent to which human reasoning can be modeled computationally  is nowhere near settled. See the Church-Turing thesis applied to mind, for instance. To draw  epistemological consequences from Gödel requires teasing out each of these assumptions, and much  of the time, such as the quotations that I've cited before, when people say that Gödel showed  that there's some human limitation, you have to pause and decode, because the decoded version  is most often a resounding, no, not exactly.