Exercise 2.2.4 (Trichotomy of order for natural numbers)

Proof.

Recall that $m++=m+1$ (see p26).

Our proof will consist of $2$ parts.

1.

We show the uniqueness first, i.e, we show that no more than $1$ of the above statements can be true at the same time. Suppose for the sake of contradiction that two statements can hold at the same time. This results in three possible cases:

• Case $1$: $a=b$ and $a<b$ hold at the same time.
  Since $a<b,$ by Proposition 2.2.12, we have $b=a+m,$ where $m$ is some positive natural number. Since $b=a$, we have, by the cancellation law, $m=0$ - a contradiction.
• Case $2$: $a=b$ and $a>b$ hold at the same time.
  This follows by the same line of reasoning as in the previous case.
• Case $3$: $a<b$ and $a>b$ hold at the same time.
  Since if $a<b,$ $a\le b$ is true by Definition 2.2.1, and similarly, if $a>b,$ $a\ge b$ is true by Definition 2.2.1. Therefore, using Proposition 2.2.12 (c), we have $a=b.$ This stands in contradiction to the previous cases. Thus, $a<b$ and $a>b$ can not hold at the same time.

2.

Now we show that at least one of the statements is true. We induct on $a$. Let’s look at the base case $a=0.$ We have $0\le b,$ because $b=0+b$ by Definition 2.2.1. If $b$ is not positive, we have $a=b=0$ by definition; otherwise, $a<b$. Now we suppose inductively that trichotomy law is true for some natural number $a.$ We now prove $P(a++),$ which is
"at least one of the statements $a++>b$ or $a++<b$ or $a++=b$ is true."
By the induction hypothesis, one of the following three cases holds.

(a)

$a=b$. Then, by Proposition 2.2.12 (f), $a+1>b$. In other words, $a++>b$.

(b)

$a>b.$ Since $a>b,$ we have $$a=b+m,\text{ where }m\text{ is positive.}$$

By the reverse version of the cancellation law, the following statement is true:

$$a+1=(b+m)+1,$$

which is the same as,

$$a++=b+(m+1).$$

Since $m+1$ is positive, by Proposition 2.2.12, we obtain

$$a++>b.$$

(c)

$a<b.$ By Proposition 2.2.12 (e), we have: $$a<b⟹a++\le b$$

By the definition of the ordering of the natural numbers, we have

$$a++=b+m,\text{ for some natural number }m\text{.}$$

If $m$ is not positive, we have $a++=b$. If $m$ is positive, we have by by Proposition 2.2.12 (f) that $a++>b.$ Thus either $a++=b$ or $a++<b$, and in either case we are done.

Thus, we’ve proven that at least one of the statements $a++>b$ or $a++<b$ or $a++=b$ is true, which closes the induction.