Question about Godel's 2nd Theorem - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-19T01:17:43Z http://mathoverflow.net/feeds/question/77628 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/77628/question-about-godels-2nd-theorem Question about Godel's 2nd Theorem Keshav Srinivasan 2011-10-09T22:34:19Z 2011-10-18T01:20:05Z <p>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.</p> <p>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?</p> <p>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?)</p> <p>Any help would be greatly appreciated.</p> <p>Thank You in Advance.</p> http://mathoverflow.net/questions/77628/question-about-godels-2nd-theorem/77630#77630 Answer by Ricky Demer for Question about Godel's 2nd Theorem Ricky Demer 2011-10-09T23:09:48Z 2011-10-09T23:09:48Z <p>You can't carry that out in PA because it could be that PA is consistent and proves $\lnot$Con(PA). <br> (in which case PA is not $\omega$-consistent)</p> <p>The best description of a model "of PA+Con(PA) in which Con(PA+Con(PA)) does not hold" would be <br> "Take the standard model of PA, then 'insert' a nonstandard natural coding a proof of $\lnot$Con(PA)".</p> http://mathoverflow.net/questions/77628/question-about-godels-2nd-theorem/77633#77633 Answer by Andreas Blass for Question about Godel's 2nd Theorem Andreas Blass 2011-10-09T23:40:32Z 2011-10-09T23:40:32Z <p>Here's a somewhat more detailed version of Ricky Demer's answer.</p> <p>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. </p> <p>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 <code>$\Sigma^0_1$</code> 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.</p>