deducibility from peano axioms

Question

I have to solve the following problem: Using $\exists$ Introduction prove that PA$\vdash x\leq y \wedge y\leq z \longrightarrow x\leq z$: I used that if $x\leq y$ then $\ \exists \ r\ x+r=y$ and in the same way $\exists t \ y +t=z$, but in logic term I don't know how to use these equalities and the Peano's axioms to get the result.

Answer 1

Well, you know that $x+r=y$ that $y+t=z,$ so, if we know that addition is associative, then it follows that $x+(r+t)=(x+r)+t=y+t=z.$ Since $r+t\in\Bbb N$ for any $r,t\in\Bbb N,$ then putting $s=r+t,$ we have shown that there exists $s$ such that $x+s=z,$ and so $x\le z$ by definition of the relation "$\le$."

All that we need to do, then, is show that addition is, in fact, associative, so that the above reasoning completes the proof of your result.

Claim: $\forall k,m,n\in\Bbb N,$ we have $(k+m)+n=k+(m+n).$

Proof Outline: Take any $k,m\in\Bbb N.$ We proceed by induction on $n,$ with the $n=0$ case being clear by two applications of property (vi) from your comment below. Suppose, then, that $$(k+m)+n=k+(m+n)$$ for some $n\in\Bbb N.$ It follows, then, with two applications of property (vii) from your comment below, that $$(k+m)+S(n)=k+\bigl(m+S(n)\bigr),$$ so by induction, the Claim holds. $\Box$

Answer 2

See Wikipedia Peano Axioms.

The point of this answer is to show that you can define an ordering of the natural numbers before you define addition.

Proposition 1: If $n$ is any number except $0$, there exist an $m$ such that

$n = S(m)$

Moreover, if the successor of both $m$ and $m^{'}$ is equal to $n$, then $m = m^{'}$.

Proof: Exercise

---

Definitions:

The Decrement mapping $D$

$ n \mapsto D(n)$

sends any nonzero number $n$ to $m$, where $S(m) = n$.

We also define $1$ to be $S(0)$. Note that $D(1) = 0$

Note for any nonzero $n$ we have the 'keep decrementing unless you can't' number expressions:

(1) $D(n)$, $D(D(n))$, $D(D(D(n)))$, ...

It is understood that this list might terminate since you can't apply $D$ to $0$.

---

Proposition 2: If $n$ is any nonzero number, the decrementing terms (1) ends in the number $0$.

Proof: It is true for $n$ = 1.

Assume it is true for $n$, and consider $S(n)$. But $D(S(n)) = n$, so that for $S(n)$, compared to the terms for $n$, you simply get a new starting term.

QED

These logical expressions,

$m \ne n \;\; iff \;\; D(m) \ne D(n)$

are true provided both $m$ and $n$ are nonzero. By repeatedly applying Proposition 2 you will find that either $m$ or $n$ gets decremented to $0$ first.

Definition: If $m$ and $n$ are two distinct nonzero numbers, we say that $m$ is less than $n$, written $m \lt n$. if $m$ is decremented to zero before $n$.

We define the relation $\le$ in the obvious fashion and agree that for all natural numbers $n$, $\;0 \le n$.

Proposition 3: $x\leq y \wedge y\leq z \longrightarrow x\leq z$

Proof: Assume $x, y, z$ are three distinct nonzero numbers.

$x\leq y \wedge y\leq z \longrightarrow x\leq z$

IF AND ONLY IF

$D(x)\leq D(y) \wedge D(y)\leq D(z) \longrightarrow D(x)\leq D(z)$

As before, you see that $x$ is decremented to zero before both $y$ and $z$, so that $x \le z$.

We leave it to the reader to finish the proof.