Gödel's incompleteness theorem proof: What exactly are our assumptions?

Question

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.

Answer 1

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