2
$\begingroup$

I would like to ask a question about Gödel's Incompleteness Theorems which I've had in the back of my head for some time. Since I'm a student working in a completely different area of maths (my usual pastime is cutting and pasting manifolds), my understanding of these results is nontechnical (I first learned about them before I started studying maths at university, by reading Nagel and Newman's excellent book).

I realize there are other questions on this topic, but I'd like to be a bit more specific in my question, and I wasn't able to google up anything that addressed what I'm about to ask.

As I understand it, the First Incompleteness Theorem is proven by producing a sentence, $G$ (which in English reads: "This sentence is not provable in the system."), that is neither provable nor refutable in the system in question. Nevertheless, $G$ is true, which means it satisfies the inductive definition of truth (right?). Here's what I don't understand:

  1. Why does the sentence $G$ satisfy the inductive definition of truth? Is this because it is the negation of a false statement? If so, why is $\neg G$ false? Is this because it causes a contradiction, and sentences that lead to a contradiction in the system are false by definition?

  2. Why doesn't the fact that $G$ is true (i.e. the list of steps reducing the truth of $G$ to the truth to atomic sentences (axioms?)) constitute a proof of $G$?

  3. By Gödel's Completeness Theorem, there are formal systems in which $G$ is false, as argued here. How can this not cause a contradiction ($G$ can't both be provable and not be!). [What makes these systems different from those in which $G$ is true, and why is it often stated that $G$ is true, when in fact there are cases in which it isn't? Edit: answered here]

I hope I have managed to make myself clear. Thanks for any clarification!

|cite|improve this question
$\endgroup$
  • $\begingroup$ I actually wrote a few long answers about "true" in the context of arithmetic, which is what you are essentially asking. On this very site, no need to travel as far as MathOverflow. $\endgroup$ – Asaf Karagila♦ Oct 19 '14 at 15:24
  • 1
    $\begingroup$ Okay, I remembered wrong. The long answers are about other unprovable things and whether or not they can be said to be "true". But I did write at least one relevant answers, this one, and while I'm sure there were others, I can't seem to find them right now. :-) $\endgroup$ – Asaf Karagila♦ Oct 19 '14 at 15:30
  • $\begingroup$ @Asaf Thanks, I had missed that answer of yours (though I had seen this one). So that clarifies the last question of 3. $\endgroup$ – Emilio Ferrucci Oct 19 '14 at 15:43
  • $\begingroup$ If you read closely the answer I linked to, you might find that it answers all three questions. $\endgroup$ – Asaf Karagila♦ Oct 19 '14 at 15:50
  • $\begingroup$ Are you referring to the part where you say that truth depends on the model and not the axioms? I still don't see the connection to the first two questions, and the first part of 3. Am I getting the definition of "truth" right in my post? $\endgroup$ – Emilio Ferrucci Oct 19 '14 at 15:57
1
$\begingroup$

About 1., Gödel's First Incompleteness Theorem is a ingenious exercise of "coding" formal properties and relations regarding a theory $F$ with "a certain amount" of arithmetic inside $F$ itself.

This exercise ends with the definition of the so-called provability predicate $Prov_F(x)$ which holds of $a$ iff there is a proof in $F$ of the formula $A$ with "code" $a$.

To complete the proof, [it is used] the negated provability predicate $¬Prov_F(x)$: this gives a sentence $G_F$ such that

$⊢_F G_F \leftrightarrow ¬Prov_F(\ulcorner G_F \urcorner)$ [where $\ulcorner x \urcorner$ is the "code" of formula $x$].

Thus, it can be shown, even inside $F$, that $G_F$ is true if and only if it is not provable in $F$.

Thus, "reading" the above proof, we can "know of" the truth of $G_F$ (provided that $F$ is consistent) simply because $G_F$ is not provable in $F$ and $G_F$ is equivalent to the formula $¬Prov_F(\ulcorner G_F \urcorner)$.

About 2. :

Why doesn't the fact that $G$ is true constitute a proof of $G$ ?

Because a proof in $F$ of $G_F$ is a precise formal objcet and G's Incompleteness Th shows that such a proof in $F$ cannot exists.

Thus, the conclusion of G's Incompleteness Th is twofold :

  • there is a formula $G_F$ of $F$ which is "intuitively" true but not provable in $F$ [not "absolutely" un-provable]

  • the system $F$ is unable to prove all true sentences expressible in it.

For 3. :

By Gödel's Completeness Theorem, there are formal systems in which G is false. How can this not cause a contradiction ?

NO; by G's Completeness Th there are models of $F$ in which $G_F$ is false.

G's Completeness Th, prove that a formula provable in a theory $T$ must be true in all models of $T$.

Thus assuming that $\mathbb N$ is a model of our theory $F$ containing "a certain amount" of arithmetic, we have that all theorems of $F$ (i.e. formulae provable from $F$'s axioms) must be true in all models of $F$.

But $G_F$ is not provable from $F$'s axioms; thus, it must be not true in some model of $F$.

The proof of G's Incompleteness Th give us the insight that $G_F$ is true in $\mathbb N$; thus, it must be false in some model of $F$ different from $\mathbb N$, i.e. in some non-standard model of arithmetic.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thanks a lot for your lengthy answer. So is the notion of truth (when referring to a certain sentence) only an intuitive one (as you say in your answer of 2.), and not a precise one (as the recursive definition which I linked)? Also, what I was asking in 3. was why one of these non-standard models do not have a contradiction ($G$ provable and not provable). I apologize for using the wrong terminology (e.g. system as opposed to model). $\endgroup$ – Emilio Ferrucci Oct 19 '14 at 15:52
  • $\begingroup$ @EmilioFerrucci - regarding truth, the notion of truth of $G_F$ is the "intuitive one, but there is als the Tarski's one (the recursivly defined). About 3, all the models (standard and not) are relative to the same set of axioms; thus $G_F$ is not provable form the axioms ... fullstop. But it happens that some sentence is true in one model ($G_F$ is true in $\mathbb N$ and false in other models) and false in other; due to G's Completeness Th they are not provable from the axioms, i.e. they are not logical consequence of the axioms. $\endgroup$ – Mauro ALLEGRANZA Oct 19 '14 at 16:03

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.