Prove that order is antisymmetric. (for natural numbers)

Question

Prove that order is antisymmetric.(for natural numbers)i.e. If $ a \leq b$ and $b\leq a$ then $a=b$.
I do not want a proof based on set theory.
I am following the book Analysis 1 by Tao. It should be based on peano axioms.
I tried $ b=a+n$ where $n$ is a natural number then $ a+n \leq a$ but subtraction not yet defined (in the text that I am following). How should I proceed ?

Answer 1

Use the following strategy:

First, prove the general facts:

• Prove $a + (b + c) = (a + b) + c$ by induction on $a$
• Prove that $a + b = a$ implies $b = 0$ by induction on $a$ and the injectivity of successor.
• Prove that $a + b = 0$ implies $b = 0$ by induction on $a$ and the fact that 0 is not a successor.
• Prove that $a + 0 = a$ by induction on $a$.

Then, for our $a$ and $b$:

• Observe that $a \leq b$ and $b \leq a$ implies we have $c$ and $d$ such that $a + c = b$ and $b + d = a$.
• Conclude that $a = (a + c) + d$, and therefore $a = a + (c + d)$.
• Conclude that $c + d = 0$.
• Conclude that $d = 0$.
• Conclude that $b + 0 = a$.
• Conclude that $b = a$.

It's a mess, for sure, but I don't think you can do much better if you're really using Peano axioms from scratch.

Answer 2

Hint:

Prove $$a++\le a$$ gives a contradiction, they use induction to prove $a+n\le a$ gives a contradiction.

Answer 3

If you're allowed to rely on trichotomy you might as well suppose by way of contradiction that $a\ne b$. Since $a\leq b$ and $b\leq a$ it follows that $a<b$ and $b<a$, a contradiction to the forementioned trichotomy property.

Remarks.

• For this proof to be valid you'd sooner have $a\leq b$ defined as $a<b\oplus a=b$ where by $\oplus$ we mean an exclusive or
• To understand why we can conclude $a<b$ and $b<a$ from $a\leq b$ and $b\leq a$ take into account that $(p\oplus q)\wedge \sim q\implies p$ where $p$ and $q$ are propositions and $\oplus$ is an exclusive or.