4
$\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!

$\endgroup$
7
  • $\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, 2014 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, 2014 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$ Oct 19, 2014 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, 2014 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$ Oct 19, 2014 at 15:57

1 Answer 1

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

$\endgroup$
2
  • $\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$ Oct 19, 2014 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$ Oct 19, 2014 at 16:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .