# How to prove a non-provable statement? That is weird…

a) there are mathematical statements, eg. formulated in Peano, which are known to be true but not provable. If not provable, how do we "prove" they are true? Is it not fishy? (I think Gödel does not address this exactly in this form. He says there is something which is true, but he does not say that we can know it is true.)

b) Suppose I add to Peano all those statements which can be known to be true theoretically. Will I have a statement then, which can be known to be true but not provable? I think Gödel does not address this exactly in this form. He says there will be something which is true, but he does not say that we can know it is true.

• You prove that they are true arguing in a stronger system than Peano Arithmetic. For example, Goodstein's theorem is proved by associating to each number in a Goodstein sequence an ordinal below $\epsilon_0$ (and arguing that there is no infinite decreasing sequence of ordinals). By contrast, Peano arithmetic cannot prove that an ordered set of type $\epsilon_0$ is well-ordered. – Andrés E. Caicedo Jan 9 '18 at 21:38
• Gödel's incompleteness theorems say, roughly, that in any given model of a sufficiently powerful theory, there is a statement which is true of that model but which cannot be proved to be true using only the tools available within the model. You should find and learn a precise statement of this. – Patrick Stevens Jan 9 '18 at 21:40
• logicmatters.net/igt/godel-without-tears is a good read, by the way. – Patrick Stevens Jan 9 '18 at 21:42
• To expand on Andrés E. Caicedo statement and to rephrase your first statement to make it clearer. "There are mathematical statements that are expressible in Peano arithmetic that are not provable with respect to the Peano axioms but for which we can prove in the metalogic (typically ZFC) hold in all models of Peano arithmetic." There are multiple different logical systems involved here. – Derek Elkins left SE Jan 9 '18 at 21:44
• en.wikipedia.org/wiki/True_arithmetic – PyRulez Jan 10 '18 at 0:28

The statements of Gödel's theorems are about (for simplicity) a certain formal theory, namely $PA$, known as Peano's arithmetic (actually they're more general but I'll stick to that). This theory contains axioms, such as $\forall x \forall y, x\times s(y) = x\times y + x$ and many others.

Now there is also a formal system that allows one to deduce theorems from these axioms; one such theorem would be $\forall x \forall y, x\times y = y\times x$.

There are also sentences $\phi$ that can be expressed in this language that cannot be proved or refuted in this theory. This is somewhat to be expected, indeed if I have no axioms for instance, then clearly I can't prove much beyond logical tautologies (although it's not so easy to see what one can prove without axioms, but that's another question), so we can expect that with too few axioms, some things are left undecided (why should we have found all the right axioms ?)

However we also have a "model" for these axioms, that is in a sense a universe in which these are true. Such a "universe" is $\mathbb{N}$. In this universe all axioms in $PA$ are true, and therefore all theorems of $PA$ are true as well. However, a statement $\phi$ that cannot be proved or refuted in $PA$ has a truth value in $\mathbb{N}$ : it is either true or false (which is not to be mistaken with "either provable or refutable"). The sentences that are true in $\mathbb{N}$ are sometimes called statements of "true arithmetic".

Since we work in a much more powerful theory than $PA$ (namely ZF) we can prove things about $\mathbb{N}$ that go beyond the theorems of $PA$. Obviously what we prove can't contradict the theorems of $PA$, but we can prove things that $PA$ can't. In particular it is not surprising that we can decide sentences that $PA$ can't: Gödel's first incompleteness theorem says that this is the case; there is a statement $\phi$ that is part of true arithmetic (it is true in $\mathbb{N}$, and for vulgarization purposes one may say it is true) but it is not provable from $PA$. In short, there are true but unprovable sentences.

Now if you add to Peano all statements of true arithmetic you obtain... true arithmetic ! Since the Peano axioms are true in $\mathbb{N}$, they are part of true arithmetic, so true arithmetic + $PA$ = true arithmetic. However, as each sentence is either true or false in $\mathbb{N}$, it means that this new theory (sometimes written $Th(\mathbb{N})$ for "theory of $\mathbb{N}$") decides every statement: every statement is provable or refutable from this, so there will be no more "true but unprovable statements".

This seems to contradict Gödel's theorem, but actually it doesn't since $Th(\mathbb{N})$ doesn't satisfy the hypotheses of this theorem, indeed it is not recursively axiomatizable, which means there is no algorithm that can decide whether a given sentence $\phi$ is an axiom. So it's a pretty "lousy" theory in the sense that we can't use it, contrary to $PA$. Gödel's theorem doesn't say that any theory about the integers has true but unprovable statements, it says that any such usable theory has true but unprovable statements.

Hope this makes things clearer

• "it is not surprising that we can decide sentences that PA can't" Hindsight truly is 20-20... (And that's not a critique, mind you. Somewhere on MSE I've made a very similar remark.) – Stefan Mesken Jan 9 '18 at 21:55
• In "a statement ... has a truth value in $\mathbb N$", how are you using the word "truth"? Are you saying that every well formed statement in PA is decidable in ZF? – stewbasic Jan 9 '18 at 22:06
• Possibly a silly question about the answer: is there more than one universe, in the sense you're using the term? If so, are there universes $\mathbb{N}_1$ and $\mathbb{N}_2$ such that some statement $\phi$ (unprovable from PA) is true in $\mathbb{N}_1$ but false in $\mathbb{N}_2$? (And going further, is it known whether such a pair of universes could be found for every PA-unprovable statement $\phi$?) – David Z Jan 10 '18 at 2:46
• @DavidZ: You can come to the Logic chat-room for in-depth discussion. But briefly, every independent (not just unprovable) sentence over PA is true in some model of PA and false in another model of PA. This is an immediate consequence of the semantic-completeness theorem for first-order logic, which is a basic result in mathematical logic that can be proven in very weak foundational systems such as ACA. Furthermore, you may be interested in this post. – user21820 Jan 10 '18 at 4:14
• Simply to point out one thing : @SteveJessop, you mentioned that if ZF proves its own inconsistency, then it's inconsistent; however that's (unfortunately) not true; as the example of ZF + $\neg$Cons(ZF) shows. If ZF is consistent, this is a consistent theory and it proves its own inconsistency. So it's not really "whichever of the two it is". It's just that we expect ZF to have "standard models" and then if ZF proves its own inconsistency, that's bad news (but from the point of view of a weak metatheory...). – Maxime Ramzi Jan 10 '18 at 6:57

Intuitively: consider the statement

''this statement is not provable in the theory $T$''.

This statement is true if it is not provable in $T$.

Godel has formally proved that such a statement can be expressed, and it and its negation are not provable, in any theory that contains Peano arithmetics.

And adding the statement as a new axiom gives a new theory in wich we can define a new not provable statement of the same kind.

• "Godel has formally proved". Is he stepping out of Peano? That is cheating. – Dave Jan 11 '18 at 18:08

There are two points here:

1. In the context of arithmetic, the term "true" means "true in the structure $$\Bbb N$$. So when Gödel's theorem states that there is a "true statement which is not provable", it means "true in the natural numbers" and not provable from $$\sf PA$$, or whatever relevant axiomatic system we're talking about.

But truth, even in the natural numbers, might depend on your meta-theory. This is a fickle question, since the choice of meta-theory depends a lot on the mathematician. But I guess most people would agree that since $$\sf PA$$ is consistent, the statement "$$\sf PA$$ is consistent" (which can be formulated as the non-existence of a solution for a Diophantine equation, for concreteness) is true, but it is not provable.

2. The incompleteness theorem does not state "every sufficiently complicated system is incomplete". Rather it states that "every sufficiently complicated system which can be recognized by a computer is incomplete". If we add all the true statements, then we get a complete theory, but this theory is no longer recognizable by a computer. Namely, we cannot write an algorithm to tell us whether a certain statement is an axiom of our theory or not.

This is bad, because the fact we can use a computer to verify our axioms means that we can use a computer to verify our proofs. And so the incompleteness theorem tells us that if we want to forego the incompleteness, we can no longer use machinated proof verification. And since humans tends to make mistakes, well, that's not ideal.

In any case, you prove things with a stronger theory. The statement $$x\cdot y=y\cdot x$$ is not provable from just the axioms of the group. After all, not every group is Abelian. But you can prove this once you add it as an axiom, or add a stronger axiom like $$x\cdot x=1$$.

• ''$\mathsf{PA}$ is consistent'' would be the nonexistence of a solution, rather. – Andrés E. Caicedo Jan 10 '18 at 14:43
• Right. I usually think about the two things in backwards directions... :) – Asaf Karagila Jan 10 '18 at 14:44

For each sentence $\phi$ in the Peano's arithmetic you have $\mathbb{N}\models\phi$ or $\mathbb{N}\models\neg\phi$ but not both, i.e. you have that $\phi$ or $\neg\phi$ is true in $\mathbb{N}$.

Gödel's second incompleteness theorem says that there exists a sentence $\phi$ such that neither $\phi$ nor $\neg\phi$ is provable in Peano's arithmetic. However one of them is true (in the structure $\mathbb N$).

• You mean "neither $\phi$ nor $\neg \phi$ are provable in Peano arithmetic". – Stefan Mesken Jan 9 '18 at 21:47
• @StefanMesken yes I mean this. I apologize for my bad english – Gödel Jan 9 '18 at 21:50
• No worries -- happens to me all the time. – Stefan Mesken Jan 9 '18 at 22:02