0
$\begingroup$

Gödel first incompleteness theorem states that certain formal systems cannot be both consistent and complete at the same time. One could think this is easy to prove, by giving an example of a self-referential statement, for instance: "I am not provable". But the original proof is much more complicated:

It was proved by constructing a statement that indirectly referred to itself as 'This statement cannot be proved' - to be more precise, it says: 'The $i$-th proposition is not provable'.

By looking just at this sentence, it certainly isn't self-referential, but if we look at how all the propositions were numbered, we can see that $i$ is the number of the above proposition, so the self reference is not direct. Is it what makes the theorem so important and the reason why the proof is so complicated - the fact that statements containing no direct self-reference whatsoever might still refer to themselves indirectly?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Isnt the statement of the theorem itself important ? $\endgroup$ – Rene Schipperus Oct 10 '16 at 16:55
  • 3
    $\begingroup$ There was no obvious way to create a self-referential statement in the language of the integers - the language only allows one to refer directly to integers, but not to any other kind of object. The content of Gödel's proof is A) there is a way to encode statements and proofs about number theory as integers, and B) this encoding enables one to create a self-referential statement. $\endgroup$ – Dustan Levenstein Oct 10 '16 at 16:55
3
$\begingroup$

Self-reference has a problem, if you want to think about it in terms of "I am not provable" sort of approach. A well-formed formula cannot refer to itself. Moreover, a formula cannot refer to the meta-theory (which is where proofs exist).

What Gödel did was two things:

  1. Internalize the meta-theory into the natural numbers via coding, and show that this internalization is very robust.

  2. Showed that there is a sentence with Gödel number $n$, whose content is exactly "the sentence coded by $n$ is not provable".

The importance is in both points. They allow us both (limited) access to the meta-theory and the proofs; as well circumvent the problem of being a well-formed formula while still referring to itself. And while the importance of the incompleteness theorem is mainly in the fact that it shows there is no reasonable way to have a finitary proof-verification process to mathematics, and also prove or disprove every sentence; the proof itself is also important because it gives us the internalization of the meta-theory into the natural numbers.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Why can't we add Godel's sentence to the list of axioms of the system? Wouldn't that make the system both complete and consistent? $\endgroup$ – user4205580 Oct 10 '16 at 17:10
  • $\begingroup$ No. Just like with Cantor's diagonal argument, adding the new real to the countable list will not make the real numbers countable all of a sudden. You'll just be able to produce a new sentence which is not provable. Gödel's result is about every recursively axiomatizable system. So you will have to repeat this process quite a long time before you escape being recursively axiomatizable, and at that point you won't have an algorithm for verifying if something is a proof from your axioms, so it won't be very useful anyway. $\endgroup$ – Asaf Karagila♦ Oct 10 '16 at 17:12
  • $\begingroup$ Alright. Umm, and how to construct a new self referential Godel sentence if one already exists on the list of axioms? $\endgroup$ – user4205580 Oct 10 '16 at 19:39
  • 1
    $\begingroup$ @user4205580 The Godel sentence for a theory $T$ says (roughly) "There is no proof or disproof, in $T$, of this sentence." Change $T$, and you change the Godel sentence. E.g. the Godel sentence of $T+G(T)$ ($G(T)=$the Godel sentence of $T$) is "There is no proof or disproof, from $T+G(T)$, of this sentence." This is a genuinely different sentence, even if the differences are somewhat technical. $\endgroup$ – Noah Schweber Oct 10 '16 at 22:09
0
$\begingroup$

Let the $n$th formula be $F_n(x)$

Godel then takes the formula

$$G(y)\equiv \text{the formula $F_y(y)$ is unprovable}.$$

Now say that $m$ is such that $F_m(x)=G(x)$ then the self referential formula is $$G(m).$$ Basically you are inputing the formulas own Godel number.

|cite|improve this answer
$\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.