0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ – DanielWainfleet Feb 7 '19 at 22:09
  • 2
    $\begingroup$ 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. $\endgroup$ – Arturo Magidin Feb 7 '19 at 22:21
  • $\begingroup$ Also, perhaps see math.stackexchange.com/questions/16358/… $\endgroup$ – Arturo Magidin Feb 7 '19 at 22:42
2
$\begingroup$

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.

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