# Prove that order is antisymmetric. (for natural numbers)

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 ?

• I dont have a clear idea but try to show that $S(n)\le n$ is a contradiction. Commented Jun 19, 2016 at 6:31
• May I ask, how do you define orders $\le$ on $\omega$? I'm not familiar with Tao's books Commented Jun 19, 2016 at 7:24

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.

## Hint:

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

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 and $$b, a contradiction to the forementioned trichotomy property.

Remarks.

• For this proof to be valid you'd sooner have $$a\leq b$$ defined as $$a where by $$\oplus$$ we mean an exclusive or
• To understand why we can conclude $$a and $$b 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.