3
$\begingroup$

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!?

  • 0
    How is the negation relevant, especially since we are working in Peano Arithmetic?2011-03-09

4 Answers 4

7

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.

  • 0
    @Gabriel Nivasch: for the witness property, the theory only has to prove $A(t)$ under the assumption that the theory proves $(\exists x)A(x)$ first. For the scapegoat property, the theory has to prove $(\exists x)A(x) \to A(s_A)$ for *every* formula $A(x)$ and appropriate term $s_A$. Here is a concrete example. In the specific case of Heyting Arithmetic (HA) let $R(x)$ say that $x$ is a coded proof of $0=1$ in HA. Then HA cannot prove $(\exists x)R(x) \to R(t)$ for any closed term, and of course HA cannot prove $(\exists x)R(x)$, but HA does have the witness property.2017-05-25
4

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$.

  • 0
    I think this was the first post to answer the question, and I voted it up.2011-03-09
4

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.

1

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.

  • 0
    I don't think we know that PA is consistent.2011-03-09