Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

How to show that the Peano Arithmetic theory is not scapegoat?

Note:

  • Peano Arithmetic is a consistent theory.

  • A theory T is scapegoat if for every formula $A$ with only one free variable there exist a closed term $s$ such that $T$ proves: $$(\exists x \; (\neg A(x)) )\Rightarrow \neg A(s)$$

("$\neg$" means "not"). I think we can start by assuming that the theory is scapegoat then we get a contradiction, but how!?

share|improve this question
1  
@Sandra: Is it supposed to be $(\exists x\neg A(x))\Rightarrow (\forall x\neg A(x))$, or $\exists x(\neg A(x)\Rightarrow \neg A(x))$? The latter seems a bit silly, so I suspect it's the former... –  Arturo Magidin Mar 9 '11 at 3:02
    
Thanks, I fixed it. –  user7986 Mar 9 '11 at 3:09
    
Perhaps you meant for the closed term s to appear in the specified theorem of T? As in "not A(s)"? –  hardmath Mar 9 '11 at 3:13
    
@ Answer#1: What about the theory itself?? –  user7986 Mar 9 '11 at 3:24
    
@ Answer#2: I didn't get the idea! Could you be more clear! –  user7986 Mar 9 '11 at 4:07

4 Answers 4

A theory $T$ is said to have the witness property if for every formula $A(x)$, if $T$ proves $(\exists x) A(x)$ then there is a term $t$ such that $T$ proves $A(t)$. The witness property is one of the criteria that are used to tell, qualitatively, whether a theory is constructive.

The definition of being a scapegoat theory is stronger than this: it requires the implication $(\exists x)A(x) \Rightarrow A(t)$ to be provable in the theory. In particular, every scapegoat theory has the witness property.

Fact: PA does not have the witness property.

To prove this, use the same sentence $A(x)$ that Apostolos gave, which says "if there is any coded proof of 0=1 then $x$ is a code for such a proof". PA proves $(\exists x)A(x)$. However, there is no single term $t$ such that PA can prove "if there is any coded proof of 0=1 then $t$ is such a code". In models where there is such a code, it will never be represented by a term.

share|improve this answer

Let $P(x)$ be the formula "if PA is inconsistent, then $x$ is the Gödel number of a proof of $0=1$". Then PA proves $\exists x P(x)$, but (assuming PA is consistent) it does not prove $P(s)$ for any closed term $s$.

share|improve this answer
    
I think this was the first post to answer the question, and I voted it up. –  Carl Mummert Mar 9 '11 at 14:21

Seeing this semantically: Gödel's incompleteness theorems say that there is a model $\mathcal{M}$ of PA that thinks that PA is inconsistent. If $A(x)$ is the formula that says "$x$ is a proof of a contradiction in PA" then that model satisfies $\exists x A(x)$. Now, the closed terms of the language represent the standard natural numbers. Thus, since it's assumed that PA is consistent there doesn't exist a closed term $s$ of the language of PA such that $A(s)$ is true in $\mathcal{M}$. This means that $(\exists x A(x))\to A(s)$ is also false in $\mathcal{M}$ for every term. Since it's false, PA doesn't prove it (due to soundness). Thus PA is not a scapegoat theory.

Seeing this syntactically: Assume that $A(x)$ is defined as above. Then if for any closed term $s$ the sentence $(\exists x A(x))\to A(s)$ was provable in PA, PA would prove $A(s)\lor(\lnot(\exists x A(x))$. At the same time since PA is assumed consistent it of course proves $\lnot A(s)$ (this is because finding out if a sequence of formulas constitutes a proof is a decidable problem). The consequence is that PA proves $\lnot(\exists x A(x))$ which states the consistency of PA, which is impossible because of the second incompleteness theorem.

share|improve this answer

We know that Peano Arithmetic is a consistent theory. So it has a consistent extension $K'$ such that $K'$ is a scapegoat theory and contains denumerably many closed terms.

share|improve this answer
    
I don't think we know that PA is consistent. –  Mitch Mar 9 '11 at 14:48

Your Answer

 
discard

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