2
$\begingroup$

I'm a middle school student that is missing some parts to understand Gödel's incompleteness theorem. We have a statement "a" such that "a" says that "statement b cannot be proved from the axioms." Now it is time for assuming that the statement is false to reach the contradiction. My question is: which statement are we assuming false, is it "a" or "b"? or is "a" the same as "b"? and how to complete the proof from this point? Can you apply these steps to the statement "x=y" as an example? Sorry for the naive question but I haven't studied set theory or logic yet and I want to understand this theorem.

$\endgroup$
5
  • 2
    $\begingroup$ Veritasium recently came out with a video that as far as I can tell explained the basic intuition pretty well. $\endgroup$
    – Arthur
    May 30, 2021 at 21:10
  • $\begingroup$ I watched it and also watched Numberphile's video but the language is unclear between the two choices. Anyways thanks for your help. $\endgroup$
    – Helana
    May 30, 2021 at 21:14
  • 2
    $\begingroup$ I strongly endorse Veritasium's video. $\endgroup$
    – Asaf Karagila
    May 30, 2021 at 21:19
  • 1
    $\begingroup$ If you read through the puzzle "machines that talk about themselves" starting on page 193 of this book and its solution on page 201, you'll find a non-technical argument that captures the essence of Godel's proof. $\endgroup$
    – saulspatz
    May 30, 2021 at 21:21
  • 1
    $\begingroup$ Here's my two-penn'orth on this: you can't understand the incompleteness theorem without understanding some elementary mathematical logic. The sense in which one statement can refer to another or to itself is uselessly vague until you understand enough mathematical logic to see how syntax can be encoded in arithmetic and understand what that means. I find popularisations like those of Smullyan amusing but unhelpful. $\endgroup$
    – Rob Arthan
    Jun 2, 2021 at 23:30

1 Answer 1

6
$\begingroup$

I strongly recommend this expository article by Rosser. It's what I learned from initially.


In fact, what we need is a "somewhat self-referential" sentence. Specifically, working in an "appropriate" axiom system $T$ (let's ignore the details here for the moment), we want a sentence $\varphi$ with the following property:

$(*)\quad$ $T$ proves "$\varphi$ iff [$\varphi$ is not $T$-provable]."

That is, in a sense $\varphi$ says "I am $T$-unprovable." So we're not just considering some random sentence, or some $a$ and $b$ which are unrelated to each other.

In the interest of completeness (hehe), let me say that - for the purposes of this answer - "$T$ is appropriate" means something along the lines of "$T$ is reasonably simple, sufficiently strong, and doesn't prove anything false." (Actually it turns out that if we look at "For every $T$-proof of $\varphi$ there is a shorter $T$-disproof of $\varphi$" we can weaken our hypotheses on $T$ - this was observed by Rosser after Godel's original argument - but I think this isn't worth focusing on at first.)


Now let me say a little bit about how we use $(*)$, which I hope will demystify things a little bit.

If we can find such a $\varphi$, then we can argue roughly as follows:

If $T$ proves $\varphi$ then $T$ can verify its own prove of $\varphi$ and so prove "$T$ does prove $\varphi$" - combining this with $(*)$ above, we get a contradiction in $T$. On the other hand, if $T$ disproves $\varphi$ then - via $(*)$ again - we get that $T$ proves "$T$ proves $\varphi$," and so $T$ is incorrect since it doesn't prove $\varphi$ (well if it does, it's inconsistent, hence obviously incorrect) but thinks that it does. So - under the assumption that $T$ is "appropriate," whatever that means - $T$ can neither prove nor disprove $\varphi$.


There are of course several subtleties here, going all the way back to $(*)$ itself. The big ones in my opinion are:

  • Why can $T$ talk about $T$-provability?

  • Even given $T$'s ability to talk about $T$-provability, why should a sentence with property $(*)$ exist? That is, why is self-reference possible?

Each of these is nontrivial (to put it mildly); interestingly, while the second bulletpoint is in my opinion far more mysterious, it's also significantly easier to prove (it's an instance of the diagonal lemma, the proof of which is extremely short if very slippery).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.