1
$\begingroup$

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 ?

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

3 Answers 3

1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

Hint:

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

$\endgroup$
0
$\begingroup$

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.
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .