# Aftermath of the incompletness theorem proof

This is somewhat of a minor point about the incompletness theorem, but I'm always a little unsure:

So one proves that there is a formula which is unprovable in the theory of consideration. Okay, at this point one is done.

Then, as that unproven sentence contains the claim that this (the unprovable-ness) would happen, one is in some sense justified to say "So the statement really is true, but still, it's unprovable within the theory". Now here is my problem: I'm very unsure in which sense this notion of truth which somewhat comes from outside the theory is sensible. There is a note on that point on the wikipedia page but I don't really comprehend it.

The word "true" is used disquotationally here: the Gödel sentence is true in this sense because it "asserts its own unprovability and it is indeed unprovable" (Smoryński 1977 p. 825; also see Franzén 2005 pp. 28–33). It is also possible to read "GT is true" in the formal sense that primitive recursive arithmetic proves the implication Con(T)→GT, where Con(T) is a canonical sentence asserting the consistency of T (Smoryński 1977 p. 840, Kikuchi and Tanaka 1994 p. 403)

So I can see that if one is technically aware that one is now talking in a meta language, that one has introduced a new "true". But then again (a) if one reflects on the fact that one draws such technicals conclusions outside of the initial freamework, then it seems to me one should really introduce another meta-meta-language. And (b) isn't it really just a little ambiguous to say "Gödels incompleteness theorems says that there are true statements, which can't be proven within a certain strong theory"?

I'd be thankful if someone could elaborate on that.

-
In this context (Peano arithmetic, natural numbers, ...) it is common to use the word "true" to mean "holds in the standard model of natural numbers". In other words, claiming Gödel sentence is true is just claiming that it holds in the standard model. – boumol Jul 24 '12 at 8:30
see Carl's answer below, I think it explains the issue quite nicely. – Kaveh Aug 4 '12 at 10:05
See math.stackexchange.com/a/1334753/21820 for a very brief sketch of the true issues lying at the bottom of the meta-mess. The short answer to your question is that indeed there is no way you can truly define truth, unless you want to rely on the (entire) real world as what is true. Even then, it is not a formal definition but a intuitive notion. One may use ZF to prove the incompleteness theorem for PA. ZF, being strictly stronger than PA, proves the consistency of PA, but ZF itself is a first-order theory and we can use ZF to prove that this formalized ZF is incomplete. – user21820 Aug 16 '15 at 14:43

There might be a bit of a chicken-and-egg happening here. For the common proofs of Gödel's Incompleteness Theorem, we put special priority on the structure $( \mathbb{N} , 0, S, + , \cdot , \mathrm{exp} )$ of elementary arithmetic. If something is true in this structure, then we often refer to that statement as true.

Peano Arithmetic is one attempt to axiomatize all truths of this structure. In more modern terms, it was perhaps hoped that the statement $$\mathbb{N} \models \phi \;\Leftrightarrow\; \text{PA} \vdash \phi$$ would have been true (or true). Gödel's Theorem tells us that this is impossible, and, more, that any attempt to "nicely" axiomatize truth in $\mathbb{N}$ is doomed to fail, by being either inconsistent, or incomplete.

As the structure $\mathbb{N}$ "exists" outside of the formal system PA (and "existed" well before this system was devised), we can argue about truth within the structure $\mathbb{N}$ using methods outside the formal system PA. In fact, there are several truths about $\mathbb{N}$ that we know cannot be proved within PA (e.g., Goodstein's Theorem and a certain strengthening of the finite Ramsey's Theorem). As long as there is no real controversy about these extra-PA methods used, the truth of these results is similarly uncontroversial. It is by using such methods outside of PA that we argue that if PA is consistent, then $G_{\text{PA}}$ is true (in $\mathbb{N}$).

While perhaps a bit ambiguous, this consequence of Gödel's Theorem could be restated (somewhat awkwardly) as "Given any "nice" consistent axiom system capable of expressing elementary arithmetic, there are number-theoretic statements which are true in $\mathbb{N}$ that cannot be proved within that system."

-
Regarding "As the structure $\mathbb{N}$ "exists" outside of the formal system PA...", what are the theories (which make us say that certain number theoretic relations are true), so that we can compare it with PA? Appearently these are not PA-like, otherwise we could state some formulas but could never get to know if they are true (in some theory). E.g. you say "there are several truths ... for example the Goodstein's Theorem". Which is the framework where it is shown that it can is true in that framework? – NikolajK Jul 24 '12 at 9:32
If you want to be a formalist, the theoretical framework to talk about these structures would be set theory, i.e., ZFC. But this is besides the point. We "know" what the natural numbers are. And we can define when a sentence holds in $\mathbb N$. There are two sides to mathematical logic: syntax and semantics. Proving things in a given theory is syntax, whether or not a sentence holds in a structure such as $\mathbb N$ is semantics. Both are connected by the completeness theorem. – Stefan Geschke Jul 24 '12 at 11:16
The Wikipedia quote already has an answer to the question about framework. The system PRA, which is much weaker than PA, is able to prove that Con($T$) implies the Gödel sentence for $T$. Thus, because we assume Con($T$) is true in the hypotheses of the incompleteness theorem, and because normal mathematical methods include everything in PRA and more, we can conclude that the Gödel sentence is true as well. It may help to notice we are not proving the sentence's truth ab initio, we have already made some assumptions in the hypotheses, and other conclusions follow from these hypotheses. – Carl Mummert Jul 24 '12 at 11:37
I personally think that doing math purely formalistically, deriving theorems from axioms using formal proofs, is pretty dull. I certainly believe that the natural numbers exist and using the inductive definition mentioned before, I can define in a reasonable way when a sentence holds in $\mathbb N$, or in other structures. – Stefan Geschke Jul 24 '12 at 12:17
@StefanGeschke: This is maybe similar to the statement "If the universe had never produced conscious life (=if the universe couldn't reflect on itself), then I don't think the notion of an existence of the universe has any meaning". Thankfully, this kind of problems don't hinder us from doing math ;) – NikolajK Jul 24 '12 at 12:51

This is an extension of a comment below Arthur Fischer's answer. For concreteness we will work with the theory PA but in principle any sufficiently strong theory would act the same.

Working in PA, or even in the weaker theory PRA, we can formally prove the implication $$\text{Con}(PA) \to G_{PA}$$ where $G_{PA}$ is the Gödel sentence of PA. This leads to two conclusions:

1. Because we know from the first incompleteness theorem that $G_{PA}$ is not provable in PA, and because $\text{Con}(PA) \to G_{PA}$ is provable in PA, $\text{Con}(PA)$ must not be provable in PA. This is the standard way to prove the second incompleteness theorem.

2. If we were working in a setting where we had already assumed $\text{Con}(PA)$, and we have access to the normal resources of PRA, then we can prove $G_{PA}$. In particular, when we are proving the incompleteness theorems we are working in normal mathematics, which includes much more than just PRA, and we assume $\text{Con}(PA)$ when we are proving that theorem. Under that assumption we can prove $G_{PA}$ in normal mathematics. Thus the Gödel sentence is "true" in exactly the same sense that $\text{Con}(PA)$ is true when we assume it as a hypothesis to prove the incompleteness theorem.

The key point in the second bullet is that we don't prove $G_{PA}$ starting with nothing. We prove $G_{PA}$ starting with the knowledge or assumption that $\text{Con}(PA)$ holds. If we did not assume the truth of $\text{Con}(PA)$, or have a separate proof of $\text{Con}(PA)$, the argument in that bullet would be useless. But once we do assume $\text{Con}(PA)$ is true, it only takes a very weak theory (PRA) to deduce that $G_{PA}$ is also true under that assumption.

-

The incompleteness theorem, in its usual form, talks about the natural numbers $\mathbb N$ together with some relations such as $\leq$, constants such as $0$ and $1$ and operations $+$ and $\cdot$. To simplify matters, we are ready to add another operation, exponentiation $n^m$. There is an inductive definition of when a sentence $\varphi$ in the appropriate language is true in $\mathbb N$. This inductive definition over the complexity of $\varphi$ is just what you would expect:

For example, if $\varphi(x_1,\dots,x_n)$ is a formula and we already know, given natural numbers $m_1,\dots,m_n$, whether $\varphi(m_1,\dots,m_n)$ holds in $\mathbb N$, then $\exists x_1\varphi(x_1,\dots,x_n)$ holds for $m_2,\dots,m_n$ in place of $x_2,\dots,x_n$ if there is some $m\in\mathbb N$ such that $\varphi(m,m_2,\dots,m_n)$.

A simpler example, the formula $x\leq y$ holds for $m$ and $n$ in place of $x$ and $y$ if we actually have $m\leq n$ in $\mathbb N$.

Now we use Gödel's technique to construct a sentence $\varphi$ that intuitively says "I am not provable". This is actually highly non-trivial, but we just assume it can be done. If $\varphi$ were provable, we could prove a statement that is wrong in $\mathbb N$. (Because if $\varphi$ were true, we could not prove it.) But we assume that from our axioms we can only prove true statements in $\mathbb N$. So $\varphi$ is actually unprovable and thus true in $\mathbb N$ in the sense discussed above.

The really technical part of this argument is to show that we can talk about provability in the language of $\mathbb N$. For me the most impressive part of Gödel's argument is that there is a sentence that basically says "I am not provable". This is the so-called fixed point lemma.

-
The sentence I have to fight here is the second paragraph. My problem is that you state "given natural numbers $m_1,\dots,m_n$, whether $\varphi(m_1,\dots,m_n)$ holds in $\mathbb N$" (you say it holds) and then in the very same sentence you require "if there is some $m\in\mathbb N$ such that $\varphi(m,m_2,\dots,m_n)$." Maybe, you mean the first part as a statement not in the same framework as the second one. Also, I've seen that $\exists x\varphi(x,y,...)$ structur in the Bourbaki outline of the prove. Are the unprovable sentences always of this "there exists something for that" structure? – NikolajK Jul 24 '12 at 9:37
I am sorry, the existential quantifier was just chosen as the most interesting example. The other cases are formulas without any logical connectives (called atomic formulas) and formulas of the form $\varphi\wedge\psi$ and $\neg\varphi$. G&ouml;del sentences usually start with a universal quantifier. But a universal quantifier – Stefan Geschke Jul 24 '12 at 10:58
can be expressed by negation and an existential quantifier. Anyhow, both my statements are in the same framework. I assume we know for which natural numbers $\varphi(m_1,dots,m_n)$ holds (is true in $\mathbb N$) and then define for which numbers $\exists x\varphi(x,m_2,\dots,m_n)$ holds. – Stefan Geschke Jul 24 '12 at 11:10
Maybe this clears things up: You say "Now we use Gödel's technique to construct a sentence $\varphi$" and you used the symbol $\varphi$ also to denote the statement in the second paragraph about the natural numbers (so let's for clarity call the number-sentence from the second paragraph $\phi$ in the following). In the incompleteness theorem, is the "I am not provable"-sentence (let's call it $\Phi$) the sentence $\phi$ (which is true in $\mathbb{N}$) or is $\phi$ only involved in the proof of $\Phi$? – NikolajK Jul 24 '12 at 12:02
I find this all very confusing. First I am talking about when a general sentence holds in $\mathbb N$. Then I specialize to a certain G&ouml;del sentence $\varphi$. For this specific sentence we define whether or not it holds in $\mathbb N$ just as before. By the specific nature of the sentence, we know that it holds iff it is not provable. – Stefan Geschke Jul 24 '12 at 12:10