Question about Godel's 2nd Theorem - MathOverflow

Question about Godel's 2nd Theorem

2011-10-09T22:34:19Z

Let Con(PA) be the sentence of arithmetic which translates as "Peano Arithmetic is consistent." Then according to Godel's 2nd incompleteness theorem, assuming PA is consistent then PA can neither prove Con(PA) nor its negation. And in fact, if T contains PA and T is (omega-) consistent, then T can neither prove Con(T) nor its negation. In particular, if PA+Con(PA) is consistent then PA+Con(PA) can neither prove Con(PA+Con(PA)) nor its negation.

But consider the following piece of reasoning: if PA is consistent, then Con(PA) is true, so PA+Con(PA) is consistent, so Con(PA+Con(PA)) is true. My question is, why can't this reasoning by formalized in PA, so that within PA you can prove Con(PA) implies Con(PA+Con(PA))? If you could prove that, then since you can obviously prove Con(PA) within PA+Con(PA), you would be able to prove Con(PA+Con(PA)) within PA+Con(PA), which is a contradiction. So where am I going wrong?

We can even talk about this in terms of model theory. There are nonstandard models of PA in which Con(PA) does not hold: basically, you have infinitely large natural numbers, and infinitely long proofs of a contradiction in PA. This does not mean that PA is inconsistent, because there are no proofs of finite length of this contradiction. So are there also nonstandard models of PA+Con(PA) in which Con(PA+Con(PA)) does not hold? (That's a rhetorical question; clearly there must be, but what do they look like?)

Any help would be greatly appreciated.

Thank You in Advance.

Answer by Ricky Demer for Question about Godel's 2nd Theorem

2011-10-09T23:09:48Z

You can't carry that out in PA because it could be that PA is consistent and proves $\lnot$Con(PA).
(in which case PA is not $\omega$-consistent)

The best description of a model "of PA+Con(PA) in which Con(PA+Con(PA)) does not hold" would be
"Take the standard model of PA, then 'insert' a nonstandard natural coding a proof of $\lnot$Con(PA)".

Answer by Andreas Blass for Question about Godel's 2nd Theorem

2011-10-09T23:40:32Z

Here's a somewhat more detailed version of Ricky Demer's answer.

In the first sentence of your piece of reasoning, you say "if PA is consistent, then Con(PA) is true, so PA+Con(PA) is consistent". The most natural justification for the step from "PA consistent and Con(PA) true" to "PA+Con(PA) consistent" presupposes that PA is true. After all, a consistent but false theory could become inconsistent when some true statement is added to it. So formalizing your argument would require proving that PA is true; that can't be done in PA --- in fact, "PA is true" can't even be expressed in the language of PA.

A more subtle justification for the step to "PA+Con(PA) is consistent" would use not the truth of PA but the weaker statement that all $\Sigma^0_1$ sentences provable in PA are true. That can be expressed in the language of PA, but alas it's not provable in PA. So the argument still can't be formalized in PA.