I have read the Proof sketch for Gödel's first incompleteness theorem on Wikipedia and do some contemplation about it. Then I was wondering about the self-referential step of the proof.

The proof begins with the assumption that every symbol/statement in the arithmetic language can be encoded into a unique natural number (Gödel's number). Then assume that between any two natural number, x and y, there are relations R called provability; that is, if x is the code of some statements, then y is the code of the concatenation between statements encoded in x and a statement proved by them, denoting as x R y.

Let G(F(z)) be the Gödel's number of any formula F(z), then define an additional relation between two number, q(n, G(F(z))), that corresponds to the statement "n is not the Gödel number of a proof of F(G(F(z)))". And then define new function, P(x) = ∀y q(y, x).

In the self-referential step, We can plug the Gödel's number of any formula into P(x), say P(G(F(x))), and then we obtain the form P(G(F(x))) = ∀y q(y, G(F(x))) ("there is no proof of F(G(F(x)))"). Then, because P(x) is a formula, plug it into itself, P(G(P(x))) = ∀y q(y, G(P(x))) ("there is no proof of P(G(P(x)))"). It says that there is no proof for itself!

I was wondering that is it necessary to do something like that in the self-referential step?. Why not doing something simpler like: define q(y, x) as "y is not a Gödel's number of proof of a statement coded by x" and then take P(x) = ∀y q(y, G(P(x))) and show that it contradicts itself? Does it violate some principle about logic or arithmetic?

  • $\begingroup$ $x$ in $P(x)$ is a variable: and "empty place" to be filled. $G(P(x))$ into $P(G(P(x)))$ is a numeral: a "name" for a number. This means that $P(G(P(x)))$ is a sentence (an assertion that is either TRUE or FALSE) while $P(x)$ is an open formula: an expression whose truth-value is undefined: it depends on thenvalue assigned as argument to $x$. $\endgroup$ – Mauro ALLEGRANZA Mar 27 '18 at 7:20
  • $\begingroup$ If P(x) has an empty place (hole) in it, why can it be translated into numeral G(P(x)) despite having a hole? $\endgroup$ – armamoyl Mar 27 '18 at 7:40
  • 1
    $\begingroup$ See Gödel's Incompleteness Theorem: Arithmetization of Syntax: $\varphi$ is a formula and its Gödel's number, denoted $\ulcorner \varphi \urcorner$, is a "name" for the formula. The "name" is encoded with numbers. The formula $\varphi(x)$ is an open formula with a free occurrence of variable $x$; its "name" $\ulcorner \varphi(x) \urcorner$ is again a "name" for it and it is again a number with no "holes". $\endgroup$ – Mauro ALLEGRANZA Mar 27 '18 at 8:22
  • $\begingroup$ Maybe the proof sketch on Wikipedia is oversimplified so I miss some important concepts. Thanks for a good article. $\endgroup$ – armamoyl Mar 27 '18 at 9:03
  • 1
    $\begingroup$ NO: the encoding as well as the self-referential aspect are used to prove the theorem but there are other ways. See e.g. Paris–Harrington theorem as well as Goodstein's theorem. $\endgroup$ – Mauro ALLEGRANZA Mar 27 '18 at 17:49

Your Answer

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

Browse other questions tagged or ask your own question.