# How does Godel use diagonalization to prove the 1st incompleteness theorem?

I'm looking for an intuitive explanation of this without too much jargon as I am new to set theory. I understand Cantor's diagonal proof as well as the basic idea of 'this statement cannot be proved false,' I'm just struggling to link the two together.

Cheers

• I would say they are two different things. Cantor considered the sequence whose nth member is the nth digit of the nth number in a sequence of number. Godel considered a particular n. – DanielWainfleet Feb 7 '19 at 22:09
• The idea of "diagonalization" is a bit more general then Cantor's diagonal argument. What they have in common is that you kind of have a bunch of things indexed by two positive integers, and one looks at those items indexed by pairs $(n,n)$. The "diagonalization" involved in Goedel's Theorem is the Diagonal Lemma. There is a bit of an analogy with Cantor, but you aren't really using Cantor's diagonal argument. – Arturo Magidin Feb 7 '19 at 22:21
• Also, perhaps see math.stackexchange.com/questions/16358/… – Arturo Magidin Feb 7 '19 at 22:42

Goedel provides a way of representing both mathematical formulas and finite sequences of mathematical formulas each as a single positive integer (by replacing each symbol with a number, and then using the numbers as exponents in the prime factorization).

If you can identify when a number corresponds to an axiom, and your "rules of inference" (valid logical arguments; such as Modus ponens, that allows you to deduce $$Q$$ if you have both $$P\to Q$$ and $$P$$) can be modeled by certain finite processes (you can have a computer do them), then there is a way of checking whether a given number corresponds to a formal proof, and so given two numbers, $$N$$ and $$M$$, you can check:

1. Is $$N$$ the number of a sequence of formulas?
2. If so, is the sequence of formulas a formal proof?
3. If so, is the last line of the proof the formula with number $$M$$?

If the answer to all three questions is 3, then you know that $$N$$ is the number of a proof for the formula with number $$M$$, and in particular that there is a proof for that formula.

Conversely, if you can prove a given formula $$F$$, then you can convert the proof into a number $$N$$, the formula into a number $$M$$, and then the number $$N$$ will be the number of a proof for the formula $$M$$.

This entire thing can be coded as a relationship between numbers. Just like you can say "$$n$$ is a multiple of $$m$$", or "$$k$$ is a power of $$q$$", or "$$p$$ is a prime", you can also say "$$N$$ is a proof for $$M$$." This is a statement that can be described purely in terms of the numerical properties of $$N$$ and $$M$$.

Goedel constructs a formula which essentially says: "There is no number $$N$$ which is a proof for the number you get by starting with the number $$k$$, and performing the following operations to it."

Now, this is itself a formula, so it has a number. It turns out that if you calculate the number of this formula, you get exactly the number you get by starting with the number $$k$$ and performing the operations described by the statement.

So even though the statement is, on its face, about number (it just says "There is no number $$N$$ which is in the relation of 'being a proof' for the number $$f(k)$$"), when you interpret the relationship 'being a proof' and you interpret the number $$f(k)$$, the statement is talking about itself.

One reason the process is sometimes called diagonalization is that you are essentially looking for a number $$k$$, corresponding to the value of the entire statement, which has $$k=f(k)$$ (so that the statement will "refer to itself"). That is, you are trying to find a number $$k$$ in the "diagonal" of the graph.