# True but unprovable?

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!

• 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. – Asaf Karagila Oct 19 '14 at 15:24
• 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. :-) – Asaf Karagila Oct 19 '14 at 15:30
• @Asaf Thanks, I had missed that answer of yours (though I had seen this one). So that clarifies the last question of 3. – Emilio Ferrucci Oct 19 '14 at 15:43
• If you read closely the answer I linked to, you might find that it answers all three questions. – Asaf Karagila Oct 19 '14 at 15:50
• 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? – Emilio Ferrucci Oct 19 '14 at 15:57

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

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.

• 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). – Emilio Ferrucci Oct 19 '14 at 15:52
• @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. – Mauro ALLEGRANZA Oct 19 '14 at 16:03