Peano Axiom Proofs: Proving $a < b$, if and only if $a + + \leq b$

Question

As for where I am getting my Peano Axioms, its from Terrance Tao's Analysis I text (math.unm.edu/~crisp/courses/math401/tao.pdf).

I am unsure whether my proof is correct for proving the forward implication. Here is the work I have done so far:

Assure $a<b$. Suppose for the sake of contradiction we have that $a + 1 \not\leq b$. In that case $a+1 > b$. From the definition of $<$ we have that $a \leq b$ and $a \neq b$. From the definition of $a \leq b$ we get that $b = a +d$ for some positive $d$. Also from the definition of $<$, we get that $b \leq a +1$ and $a +1 \neq b$. From the definition of $a \leq b$ we get that $a + 1 = b + f$ for some positive $f$. We now have that $a + 1 = a + d + f$. By cancellation law we have that $1 = d+ f$. Since $d$ and $f$ were both positive we now have a contradiction. Thus $a+1 \leq b$.

We didn't prove $1 = d+ f$ is a contradiction for positive numbers, so I am feeling hesitant towards this proof. Please suggest some ideas!

Answer 1

You're doing well so far! Now, since $f$ is positive and $1=d+f,$ this means that $d\le 1,$ but $d\ne 1.$ Do you see why? But that means $d<1,$ contradicting positivity of $d.$

Also, I think you mistyped your title.

---

Added: It's worth noting that the Peano Axioms aren't always formulated in the same way, so it would be helpful to know which version you're dealing with. Also, since you've apparently encountered the notion of addition and inequality (not typically part of the Peano Axioms), it would help to know what you've proved about those so far. It may well be that there's a more straightforward way to proceed, but we'll be hard-pressed to say for sure what it is, unless you can give us more information. Even the approach I suggested above may need to be altered, depending on what you know about positive numbers.

Answer 2

To prove the direct implication, we need to prove $$a<b\text{ implies }a\!+\!\!+\le b.$$

Following your reasoning, for contradiction we state that $a\!+\!\!+>b$. Thus $a<b<a\!+\!\!+$ what is imposible because between a natural number an its sucessor cannot be another natural number.

Now, we have some precisions:

By definition, we have $a<b$ iff $a\le b$ and $a\ne b$.

By definiton, we have $a\le b$ iff $b=a+m$ for some natural number $m$. (Not for a positive $m$ because the equality couldn't be unreachable.)

From here, we need to prove that $a<b$ iff $b=a+d$ for some positive $d$.

Also, we can prove there is a natural number $b$ such that $b\!+\!\!+=a$ whenever $a$ is positive.

Using this facts, from $a<b$, there is a positive $d$ such that $b=a+d$. And so $b=a+(n\!+\!\!+)$ where $n$ is a natural number. By addition properties, we have $b=a+(n\!+\!\!+)=(a+n)\!+\!\!+=(a\!+\!\!+)+n$. Finally by definition of order, $a\!+\!\!+\le b$ as we desired.

Answer 3

Remember that with this kond of material you have to strictly keep to the axioms ... and use whatever theorems al ready have been proven ... but you cannot treat this like a 'normal' exercise about numbers, where you can just use the 'usual' properties that you have known about numbers since elementary school

For example: you start your proof with: suppose $a +1 \not \le b$ ... then $a+1>b$. Yes, this is certainly true for the natural numbers, but the whole point of doing what you're doing now is to prove all of those kinds of properties, and this articular property you have not yet proven ... you would basically need Trichotomy ... which Tao only brings up after the proposition you have to prove now. So, you can't make the inference that you make here.

Instead, stick to the definitions and axioms. I'll show you how to go from $a<b$ to $a++\le b$ ... I'll leave going the other way to you, once you see how to do something like this:

OK, so suppose $a<b$. By definition of $<$ that means $a \le b$ and $a \not = b$. Now, by definition of $\le$, $a \le b$ means that there is some number $c$ such that $a+c=b$. Now, if you suppose that $c=0$, then that means that $a+0=b$, and since by Lemma 2.2.2 you have that $a+0=a$, we thus get that $a=b$, which contradicts $a \not = b$. So, $c \not = 0$. By Lemma 2.2.10 (you're past this one, so you can use it), that means that there is some $d$ such that $d++=c$. So, we have that $a +d++=b$. By Lemma 2.2.3, we have $a+d++=(a+d)++$, and thus we have $(a+d)++=b$. By definition 2.2.1 we have $(a++ )+d=(a+d)++$, and thus we have $(a++)+d=b$. By definition of $\le$ that means $a++ \le b$

Do you see how every little step is justified by the definitions or Lemma's you already have? Try to do the same thing when going the other way. Good luck!