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

There is nothing fancy or special going on here at all. Here's the argument spelled out in more detail (this presentation is adapted from Lord Shark the Unknown's answer, but modified to more closely match the argument from your text).

Let $T(a)$ be the predicate $\forall b\in \Bbb N:(a=b\text{ or }a<b\text{ or }b>a)$. You seem to accept the given proof of $T(1)$.

Let us prove $T(a)\implies T(a')$. Assume $T(a)$. Write $U(b)$ for the statement "$a'=b$ or $a'<b$ or $b<a'$". Then $U(1)$ is true: $1<a'$.

Now suppose $U(b)$ holds; we will prove $U(b')$. Note first that by $T(a)$, we have $a=b$ or $a<b$ or $b>a$. If $a=b$ then $a'=b'$. If $a<b$ then $a'=a+1<b+1=b'$ by (14). If $a>b$ then $a'=a+1>b+1=b'$ by (14). Thus in all cases, $U(b')$ is true.

---

As your text mentions, the induction hypothesis $U(b)$ was not used at all in the proof of $U(b')$ (though the "outer" induction hypothesis $T(a)$ is used).

Answer 2

You are asking about the proof of trichotomy: $a=b$, $a<b$ or $b<a$ for all $a$, $b$, for all $a$, $b\in\Bbb N$.

Let $T(a)$ be the predicate $\forall b\in \Bbb N:(a=b\text{ or }a<b\text{ or }b>a)$. You seem to accept $T(1)$.

Let us prove $T(a)\implies T(a')$. Assume $T(a)$. Write $U(b)$ for the statement "$a'=b\text{ or }a'<b\text{ or }b<a'$". Then $U(1)$ is true: $1<a'$. Suppose $U(b)$ holds. Either $a'=b$, $a'<b$ or $b<a'$. In both the cases $a'=b$ and $a'<b$, it follows that $a'<b'$. The hard case is $b<a'$.

We need to prove that if $b<a'$, then either $a'=b'$ or $b'<a'$. By definition, $a'=b+c$ for some $c\in \Bbb N$. If $c=1$, then $a'=b'$. Otherwise, $c=d'$ for some $d$, and $a'=b+d'=(b+d)'=b'+d$, so that $b'<a'$.

This final assertion involves the formula $(b+d)'=b'+d$ which you may not accept yet. But this follows by induction on $d$: $(b+d)'=b'+d\implies b+d' =b'+d\implies (b+d')'=(b'+d)'=b'+d'$.

Answer 3

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.

Answer 4

As stated at page 100, the proof of trichotomy (15) is by induction.

It is a "nested" induction : an outer on $a$ that in turn needs induction on $b$ in both the base case ($a=1$) and in the inductive step.

We want to prove that :

$\forall b \ [a \ne b \to (a<b \lor b<a)]$, for every $a$.

Induction on $a$, using the formula : $Q(a) := \forall b \ [a \ne b \to (a<b \lor b<a)]$.

Base case : $a=1$.

Induction on $b$, using the formula : $P(b) := (1 \ne b \to (1<b \lor b<1))$.

When $b=1$, we use the tautology $p \to (\lnot p \to q)$ with $1=1$ (axiom for equality) to derive : $\lnot (1=1) \to (1<1 \lor 1<1)$. This is $P(1)$.

Now for $P(b')$. We know that $b′=b+1$. Using the definition of "<" ($a<b \text { iff } b=a+c$) we have that $1<b′$.

Thus, using the tautology : $p → (p ∨ q))$, we have : $1<b′ ∨ b′<1$ and then (by the tautology : $p→(q→p)$) : $1≠b′ → (1<b′ ∨ b′<1)$.

This amounts to having proved $P(b′)$ (without using the assumption $P(b)$).

Using again the previous tautology, we have $P(b) → P(b′)$.

Having proved $P(1)$ and "$P(b) → P(b′)$, for every $b$", we apply induction to conclude with $∀b P(b)$, i.e.

"for every $b$, if $1≠b$, then either $1<b$ or $b<1$".

And this is the conclusion of the first part of the induction on $a$, the base case $Q(1)$.

---

Now we have to complete the "outer" induction, i.e. we have to prove that :

assumed that "if $a≠b$, then either $a<b$ or $b<a$, for every $b$" we have to prove that "if $a′≠b$, then either $a′<b$ or $b<a′$, for every $b$".

The proof is again by induction on $b$.

The case for $b=1$ amounts to : "if $a′≠1$, then either $a′<1$ or $1<a′$.

It is simply the result that we have already proved (see : $\forall b P(b)$ above).

Now we have to prove the indcutive step :

assumed that "if $a′≠b$, then either $a′<b$ or $b<a′$", prove that "if $a′≠b'$, then either $a′<b'$ or $b'<a′$.

If $a' \ne b'$, then (Ax.III) $a \ne b$. Thus, by the induction hypotheses on $a$ : either $a<b$ or $b<a$.

Here we apply a "proof by cases" using (14).

Case 1) : $a < b$. Then $a+1 < b+1$ and thus $a' < b'$ and thus (using the tautology : $p \to (p \lor q)$) : $a' < b' \lor b' < a'$.

Case 2) : $b < a$. In the same way $b' < a'$ and thus $a' < b' \lor b' < a'$.

In both cases, we have that $a' < b' \lor b' < a'$ and thus :

if $a' \ne b'$, then either $a' < b'$ or $b' < a'$.

Thus, we have proved $Q(a')$ (without using $Q(a)$) and again we have $Q(a) \to Q(a')$.

---

---

Conclusion: we have proved $Q(1) := \forall b \ [1 \ne b \to (1<b \lor b<1)]$, and we have proved $Q(a) \to Q(a')$, for every $a$.

Thus we use (Ax.V) to conclude with $\forall a Q(a)$, i.e.:

$\forall a \ \forall b \ [a \ne b \to (a<b \lor b<a)]$.