Tao Analysis I - 2.2.4

Exercise 2.2.4

Justify the three statements marked (why?) in the proof of Proposition 2.2.13.

Let's follow the provided proof of Proposition 2.2.13 and fill in the gaps.

Proposition 2.2.13 (Trichotomy of order for natural numbers). Let $a$ and $b$ be natural numbers. Then exactly one of the following three statements is true: 

• $a < b$
• $a = b$
• $a > b$.

The proof is in two parts:

• Part 1 - showing that not more than one of the three statements can hold at the same time
• Part 2 - showing at least one of the three statements must be true
  

Although it feels unusual, proving both of these things is sufficient to show that only one of the three statements can be true.

 

Part 1

Let's work through the cases.

• If $a<b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a>b$.
• If $a>b$ then by definition 2.2.11, $a \neq b$. This leaves the possibility of $a<b$.
• If $a=b$ then by definition 2.2.11, $a \nless b$ and $a \ngtr b$.

We're left to explore the possibility of $a<b$ and $a>b$ both being true. Proposition 2.2.12(c) says that if $a \leq b$ and $a \geq b$, then $a=b$. Our strict inequalities are a special case, and so we are led to $a=b$. But this is a contradiction! So we conclude not more than one of the cases can be simultaneously true.

Part 2

The book uses induction to prove that at least one of the three statements must be true. It fixes $b$ and inducts on $a$. 

When $a=0$, then $0 \leq b$ for all $b$. We're asked why (1). This means either $0 = b$ or $0 < b$ (but not both). This is the induction base case $a=0$.

The inductive hypothesis is that for a given $a$, at least one of the three statements is true. We need to show that if this is true for $a$, then it is also true for $a++$.

• If $a>b$ then $a++ > b$. We're asked why (2).
• If $a=b$ then $a++ > b$. We're asked why (3).
• If $a<b$ then by Proposition 2.2.12(e) we have $a++ \leq b$.This means either $a++ = b$ or $a++ < b$ (but not both). 

This concludes the induction.

We now answer the why questions.

 

Why 1

When $a=0$, then $0 \leq b$ for all $b$. We're asked why. 

The variables $a$ and $b$ are independent of each other, so $a$ does not constrain $b$. 

By definition $b$ is a natural number so it can take values from $b=0$ upwards. This is why $0 \leq b$. $\square$

Some of the other solution sites answered this question by demonstrating why the inequality $0 \leq b$ holds for all natural numbers $b$. Definition 2.2.1 of addition states that $0 + m:=m$, so we have $0 + b = b$. This matches Definition 2.2.11 for order relations, where $b = 0 + b$ means $b \geq 0$, or equivalently $0 \leq b$.

Why 2

If $a>b$ then $a++ > b$. We're asked why.

Let's start with 

$$a>b$$

Proposition 2.2.12(d) that addition preserves order, give us

$$a++ > b++$$

Now $b++ = b + 1$, and $b++ \neq b$ (Axiom 2.4), so by Definition 2.2.11 of order relations gives us

$$b++ > b$$

Since order is transitive by Proposition 2.2.12(b), from

$$a++ > b++ > b$$

we finally have

$$a++ > b$$

 

Why 3

If $a=b$ then $a++ > b$. We're asked why.

Let's start with

$$a = b$$

and increment both sides

$$a++ = b++$$

which we can rewrite as

$$a++ = b + 1$$

This matches Definition 2.2.11 for order relations, giving us the desired

$$a++ > b$$

 

Note

In the last 2 answers we've used $n++ = n + 1$. Although trivially obvious, we might ask how we show it from the basic axioms and lemmas. 

It is a corollary of the following two lemmas

• Lemma 2.2.2 - For any natural number $n$, $n+0=n$.
• Lemma 2.2.3 - For any natural numbers $n$ and $m$, $n+(m++)=(n+m)++$.
  

Here we take $m=0$ so $n+(0++)=(n+0)++$ becomes the desired $n+1=n++$.