Peano Arithmetic, proof

Question

Show in PA:

$\forall v_0\forall v_1 (v_0<v_1\rightarrow \exists v_2\quad v_0+v_2=v_1)$

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<Sy\leftrightarrow (x<y\vee x=y)$
4. $\neg(x<0)$
5. $x<y\vee x=y\vee y<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)

10. 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<S(v_1)$

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.

Answer 1

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