Proving $a\ne{b}\implies{a<b}\lor{b<a}$ for natural numbers beginning with 1 using Peano's Axioms without induction hypothesis

Question

Here, I am asking specifically about a proof which does not use an induction hypothesis, and which relies exclusively on Peano's axioms as stated herein. My interest is not in simply producing the results. I want the insight intended by these superlative mathematicians.

The following is from Fundamentals of Mathematics, Volume 1 Foundations of Mathematics: The Real Number System and Algebra; Edited by H. Behnke, F. Bachmann, K. Fladt, W. Suess and H. Kunle

I've used square brackets '[' and ']' to indicate where referenced text is copied in place.

The quoted text is part of the development of the theory of natural numbers. Their version of Peano's axioms begins with 1, not 0. I am able to follow the discussion up to the proof of rule (15).

If for the numbers $a,b$ there exists a number $c$ with $a+c=b,$ we write $a<b$ ($a$ is less than $b$), or alternatively $b>a$ ($b$ is greater than $a$). For the relation $<$ defined in this way we have the following theorems:

12. if $a<b,$ then $a\ne b$ (antireflexivity);

13. if $a<b$ and $b<c,$ then $a<c$ (transitivity);

14. if $a<b,$ then $\left(a+d\right)<\left(b+d\right)$ (monotonicity of addition);

15. if $a\ne b,$ then $a<b$ or $b<a.$

Rule (12), which states that $a+c\ne a$ for all $a,c,$ is proved by complete induction on $a,$ for we have $1+c\ne1$ by (1) [$a+1=a^{\prime}$],
(7) [$a+b=b+a$] and axiom IV [$a^{\prime}\ne1$ for every number $a$]; and if we had $a^{\prime}+c=a^{\prime},$ it would follow that $\left(a+c\right)^{\prime}=a^{\prime},$ and thus $a+c=a.$ For
the proof of (13), (14) we set $a+u=b,b+v=c$ and thus get

$c=\left(a+u\right)+v=a+\left(u+v\right),$

$b+d=\left(a+u\right)+d=a+\left(u+d\right)=\left(a+d\right)+u.$

Complete induction on $a$ is again used to prove (15), as follows.

The case $a=1$ is first dealt with by complete induction on $b:$
[footnote: In this case the induction hypothesis is not used at all, a fact which may make the proof somewhat harder to follow.]

$1=1;$

$1<1+b=b+1=b^{\prime}.$

Then from (15) (for all $b$) the same statement with $a^{\prime}$instead of $a$ (thus for all $b:$ $a^{\prime}<b$ or $a^{\prime}=b$ or
$b<a^{\prime}$) is derived by complete induction on $b:$

$1<a^{\prime};$

$a^{\prime}<b^{\prime}$ or $a^{\prime}=b^{\prime}$or $b^{\prime}<a^{\prime}$
by (15) and (14);

here again the induction hypothesis ($a^{\prime}<b$ or $a^{\prime}=b$ or $b<a^{\prime}$) is not used.

The version of Peano's axioms used in the text is:

• I. $1$ is a number.
• II. To every number $a$ there corresponds a unique number $a^{\prime},$
  called its successor.
• III. If $a^{\prime}=b^{\prime},$ then $a=b.$

• IV. $a^{\prime}\ne1$ for every number $a.$

• V. Let $A\left(x\right)$ be a proposition containing the variable
  $x.$ If $A\left(1\right)$ holds and if $A\left(n^{\prime}\right)$
  follows from $A\left(n\right)$ for every number $n,$ then $A\left(x\right)$
  holds for every number $x.$

I have tried very hard to figure out what the authors intended by their sketched proof of (15). The first part $1<b^\prime$ is obvious. But the second part

Then from (15) (for all $b$) the same statement with $a^{\prime}$instead of $a$ (thus for all $b:$ $a^{\prime}<b$ or $a^{\prime}=b$ or
$b<a^{\prime}$) is derived by complete induction on $b:$ $1<a^{\prime};$
$a^{\prime}<b^{\prime}$ or $a^{\prime}=b^{\prime}$ or $b^{\prime}<a^{\prime}$
by (15) and (14);

has me baffled. Every way I can come up with either requires an induction hypothesis, presupposes ordering, or appeals to something beyond the stated axioms (such as set theory, or comparing collections of vertical strokes on paper, etc.).

At the point in the development where this discussion appears the authors have introduced the principle of recursion which they use to define addition by $a+1=a^{\prime}$ and $a+b^{\prime}=\left(a+b\right)^{\prime}$. We also have, for addition, the three-term associative law, the two-term commutative law, and the cancellation law. Subtraction, and 0 are not yet available.

The proofs of the general associative law and the theorem of strong induction both rely on the ordering theorems and therefore cannot be used in the proof.

There is sufficient context to write
$$a=1+1+1,$$
$$a^{\prime}=1+1+1+1,$$
etc., without parentheses, assuming each $+1$ is appended to the right.

My best guess:

The best argument I can come up with is that every number except 1 is a successor, and is arrived at successively beginning with 1. This means that given $a^{\prime}$, one or more numbers are arrived at before arriving at $a^{\prime}$ in succession. Using what is available it is easily shown that those numbers are all less than $a^{\prime}$.

These are the two forms of recursion discussed prior to defining addition recursively. The second is not explicitly referred to in any of the subsequent discussion. Perhaps that is a hint that I should be applying it on my own.

The proof of this theorem is then given; followed by:

It seems reasonable that the more general principle can be used to form for each number a unique set containing that number and all the "previous" numbers. From this set of sets it is straight forward to establish the desired result.

Is this the kind of argument I should be using to prove this theorem?

Answer 1

Your problem is with the quote:

In this case the induction hypothesis is not used at all, a fact which may make the proof somewhat harder to follow.

This sentence isn't saying, "There is a proof of this statement that doesn't use the induction axiom of Peano." Indeed, there isn't such a thing. What this footnote was trying (and failing) to do was to avoid the confusion caused by the fact that the proof that $1$ is less than every other number is an induction proof whose induction step doesn't use the induction hypothesis. i.e. In order to show that $1<a'$, you don't need to use the assumption that $a=1$ or $1<a$.

(But it is still an induction proof. We are only allowed to write this proof because of the fifth Peano axiom. And it does take the standard form of an induction proof:

• Base Case: $1=1$, so either $1=1$ or $1<1$
• Induction Step: Assume that $a=1$ or $1<a$ (But we actually don't need this). Then $1<a'$. Therefore $a'=1$ or $1<a'$.

If you need to take some time to get your head around an induction proof whose induction step doesn't use the induction hypothesis, don't worry. It is a rather counter-intuitive idea that we'd need such proofs.

---

Here's a similar induction proof that might help demonstrate this idea. You might have at one point been taught that Weak Induction and Strong Induction are equivalent. This isn't quite true: ordinals larger than the natural numbers are sets which have strong induction but not weak induction. What is true is that Weak Induction is equivalent to (Strong Induction and Every Number is either $1$ or a Successor).

Therefore Every Number is either $1$ or a Successor is a property that's really key to the natural numbers. We should be able to prove it quickly using the Peano Axioms you've been given. Let's prove it by induction.

• Base Case: $1$ is $1$, so it is either $1$ or a successor.
• Induction Step: Assume that $a$ is either $1$ or a successor. (But again, we don't need to) Then $a'$ is a successor, because it's the successor of $a$. Therefore $a'$ is either $1$ or a successor.

By induction, every number is either $1$ or a successor. QED

Again, we didn't need the induction hypothesis in the induction step. But without the induction axiom, we wouldn't be able to prove this. If you play around with some of the other 'obvious' properties of the naturals, trying to prove them just from the five Peano Axioms, you might find more cases of this.