Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Doesn't the statement "if T contains PA and T is (omega-) consistent, then T can neither prove Con(T) nor its negation." require that T be computable? –  Quinn Culver Oct 14 '11 at 13:18
    
Quinn, we are of course talking about recursively axiomatized theories, so yes T is "computable." –  Keshav Srinivasan Oct 15 '11 at 14:13
    
This is not about your question itself, but you should avoid editing the question too often for two reasons: (1) it bumps it up to the top of the question thread, which is not a desirable effect for a minor edit; (2) it will eventually become community-wiki. –  Thierry Zell Oct 18 '11 at 1:58

2 Answers 2

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.

share|improve this answer
    
All right, what if we replaced every occurrence of the word "consistent" in my original post with the phrase "sigma-1 sound", and we replaced Con(T) with Sig(T), a statement of arithmetic saying "T is sigma-1 sound." In that case what would be my error? –  Keshav Srinivasan Oct 10 '11 at 0:01
1  
Your error would be explained by doing the same replacements to my answer. $\hspace{1 in}$ –  Ricky Demer Oct 10 '11 at 1:11
    
Ricky, your answer was "You can't carry that out in PA because it could be that PA is consistent and proves ¬Con(PA)." But is it possible for PA to be sigma-1 sound and prove ¬Sig(PA)? –  Keshav Srinivasan Oct 10 '11 at 1:22
    
Yes. $\;$ (The only way I know to show that is from Godel's 2nd Thm.) $\;\;$ –  Ricky Demer Oct 10 '11 at 3:03
1  
@Keshav: No, it is $\Pi^0_2$ (and this is an optimal classification, as it is not contained in any consistent extension of PA by a set of $\Sigma^0_2$-sentences). By the way, the standard name of this statement is the uniform $\Sigma^0_1$-reflection principle, and it is denoted as $\mathrm{RFN}_T(\Sigma^0_1)$, $\mathrm{RFN}_{\Sigma^0_1}(T)$ or similar variations in the literature. –  Emil Jeřábek Oct 12 '11 at 10:10

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)".

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.