# Peano Arithmetic, proof

Show in PA:

$$\forall v_0\forall v_1 (v_0

Hello,

I have a question to this task, because I do not know, how to proof this. I give the definition of PA:

PA is the theory consisting of: ($$S$$ is the successor-function, therefore $$S(n)=n+1$$)

1. $$Sx\neq 0$$
2. $$Sx=Sy\rightarrow x=y$$
3. $$x
4. $$\neg(x<0)$$
5. $$x
6. $$x+0=x$$
7. $$x+Sy=S(x+y)$$
8. $$x\cdot 0=0$$
9. $$x\cdot Sy=x\cdot y+x$$

(The theory containing 1-9, is called $$Q$$, the Robinson Arithmetic)

1. If $$\varphi$$ is a formula ($$v$$ is free variable in $$\varphi$$), then PA contains:

$$(\varphi_0^v\wedge \forall v(\varphi\to \varphi^v_{sv}))\to\forall v \varphi$$

Now I tried to proof this, just using these 10 axioms. I think we have to use 10. at some point for sure, otherwise we could proof this in $$Q$$.

How can I start, when I do such proofs? I started like this:

$$v_0\rightarrow v_1$$ with 3.

$$v_0\rightarrow v_1\rightarrow v_0

Intuitively I could use 3. $$n$$-times until I get to the point, where $$v_1=S^n(v_2)$$. But there are some problems with that. The first is, that 3. does not help me to decide the equality, furthermore it does not give me the concrete existence of such a $$v_2$$, which holds $$v_0+v_2=v_1$$.

Thanks in advance for any tips and hints.

• You are trying to prove the definition of order. It depends how the book you are reading is building the characterization of Peano arithmethic. You want to prove that $y<x\iff x= (S\circ S)^n (y)$. To prove this kind of composition you must use induction.
– user173262
Commented Jun 11, 2016 at 18:54
• I gave our definition of "Peano arithmetic" above, or do I missunderstand you? What do mean by "building the characterization of Peano arithmetic"? To prove "$y<x\leftrightarrow x=(S\circ S)^n(y)$" by induction, does that work like the "normal" induction?. I start with n=0. $y<x\leftrightarrow y<S^0(x)=x$ (using 3.) Which already shows the start of the induction. Commented Jun 11, 2016 at 19:07
• Yes, normal induction.
– user173262
Commented Jun 11, 2016 at 19:18

Hint

By induction on $v$, using $\varphi(v) := (x < v \to ∃y \ (x + y = v))$.

i) Basis : for $v=0$, we have $\lnot (x < 0)$, by Ax.4.

Thus, using the tautology; $\lnot A \to (A \to B)$, we derive by modus ponens:

$(x < 0 \to ∃y \ (x + y = 0))$

i.e. $\varphi(0)$.

ii) Induction step : we assume that $\varphi(v)$ holds and we have to prove that $\varphi(Sv)$ holds also.

Assume: $x < Sv$; by Ax.3: $x < v \lor x = v$.

By cases (i.e. Disjunction elimination) :

• if $x < v$, then by Induction hypotheses: $∃y \ (x+y=v)$ and thus: $(x + Sy = Sv)$ by Ax.7;

• if $x = v$, then $x + 0 = v$, by Ax.6, and thus: $(x + S0 = Sv)$.

In both cases:

$∃y \ (x+y=Sv)$

and we conclude with: $x < Sv \to ∃y \ (x+y=Sv)$.

Thus, we have $\varphi(v) \to \varphi(Sv)$ and we apply Ax.10 (Induction) to conclude with: $\forall v \ \varphi(v)$, i.e.

$\forall v \ (x < v \to ∃y \ (x + y = v))$.

Then we apply Generalization (i.e. $\forall$-introduction) to get:

$\forall x \ \forall v \ (x < v \to ∃y \ (x + y = v))$.