First Order Logic Peano arithmetic Proof

191 Views Asked by At

I'm trying to prove:

$\forall x\forall y((x=y)\longrightarrow(x\not<y)$

I tried starting off with

$u=v, u+s(z) = v\vdash u = v$

$u=v, u+s(z) = v\vdash u+s(z) = v$

. . .

$u=v, u+s(z) = v\vdash s(z) = 0$

and try to get a contradiction (since $s(z) \not = 0$, is a theorem), but I'm having a lot of difficulty proving that $s(z) = 0$.

Any help would be greatly appreciated.

1

There are 1 best solutions below

2
On

Use the following lemma: $$\forall a,b,u:\, u+a=u+b\to a=b$$ This can be proved by induction on $u$, provided we already know $s(x+y)=s(x)+y\,$ (which is another lemma if the axiom is stated in the other argument).

The base case $u=0$ is immediate.
Now suppose $s(u)+a=s(u)+b$. Then using the above statement, we have $s(u+a)=s(u+b)$. Then injectivity of $s$ implies $u+a=u+b$ which implies $a=b$ by induction hypothesis.