2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Quinn Culver
    Commented Oct 14, 2011 at 13:18
  • $\begingroup$ Quinn, we are of course talking about recursively axiomatized theories, so yes T is "computable." $\endgroup$
    – Keshav Srinivasan
    Commented Oct 15, 2011 at 14:13

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
12
  • $\begingroup$ 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? $\endgroup$
    – Keshav Srinivasan
    Commented Oct 10, 2011 at 0:01
  • 1
    $\begingroup$ Your error would be explained by doing the same replacements to my answer. $\hspace{1 in}$ $\endgroup$
    – user5810
    Commented Oct 10, 2011 at 1:11
  • $\begingroup$ 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)? $\endgroup$
    – Keshav Srinivasan
    Commented Oct 10, 2011 at 1:22
  • $\begingroup$ Yes. $\;$ (The only way I know to show that is from Godel's 2nd Thm.) $\;\;$ $\endgroup$
    – user5810
    Commented Oct 10, 2011 at 3:03
  • 1
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Commented Oct 12, 2011 at 10:10
3
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .