Ordering Natural Numbers

Less Than

We're now prepared to define the usual order relations on natural numbers, starting with "less than". We might call these additive order relations, since they are defined in terms of $plus$ .

We define a relation $<$ on $N$ (pronounced less than) as follows. Given $a, b \in N$ , we say $a < b$ if there exists $c \in N$ such that $plus (a, next (c)) = b$ .

Showing that $a < b$ is straightforward enough; we just have to exhibit a specific $c$ such that $plus (a, next (c)) = b$ . Showing that $a ≮ b$ is different, though, because we have to show that no such $c$ exists. This will usually come down to showing that such an equation leads to something we know is absurd, like $0 = next (m)$ .

For all $m \in N$ we have the following.

$0 < next (m)$ .
$next (m) ≮ 0$ .

To see (1), note that $plus (0, next (m)) = next (m)$ as needed.

To see (2), suppose to the contrary we have $c \in N$ with $plus (next (m), c) = 0$ . But then $\begin{array}{rcl} next (plus (m, c)) \\ = & plus (next (m), c) \\ = & 0, \end{array}$ which is absurd.

No natural number is less than itself.

If $a \in N$ , then $a ≮ a$ .

Relations satisfying this property are called antireflexive.

Suppose we have $a < a$ . That is, that for some $c \in N$ we have $plus (a, next (c)) = a$ . Note than that $\begin{array}{rcl} plus (a, 0) \\ = & a \\ = & plus (a, next (c)) . \end{array}$ Since $plus$ is cancellative, we have $0 = next (c)$ ; however this is absurd. So we have $a ≮ a$ .

Two natural numbers cannot be simultaneously less than each other.

If $a, b \in N$ such that $a < b$ , then $b ≮ a$ .

Relations satisfying this property are called asymmetric.

Suppose $a < b$ ; then we have $m \in N$ such that $plus (a, next (m)) = b$ . Now suppose we also have $b < a$ , with $n \in N$ such that $p l u s (b, next (n)) = a$ . Now $\begin{array}{rcl} = & plus (a, plus (next (m), next (n))) \\ = & plus ((plus (a, next (m)), next (n)) \\ = & plus (b, next (n)) \\ = & a . \end{array}$ As we've shown, then $plus (next (m), next (n)) = 0 .$ But now we have $\begin{array}{rcl} 0 \\ = & plus (next (m), next (n)) \\ = & plus (plus (m, next (n)), next (n)) \\ = & next (plus (plus (m, next (n)), n)), \end{array}$ which is absurd. So $b ≮ a$ .

We can collapse chains of less-than relationships.

Let $a, b, c \in N$ . If $a < b$ and $b < c$ , then $a < c$ .

Relations satisfying this property are called transitive.

Suppose $a < b$ and $b < c$ . Then we have $m, n \in N$ such that $plus (a, next (m)) = b$ and $plus (b, next (n)) = c .$ Note that $\begin{array}{rcl} plus (a, next (plus (m, next (n)))) \\ = & plus (a, plus (next (m), next (m))) \\ = & plus (plus (a, next (m)), next (n)) \\ = & plus (b, next (n)) \\ = & c, \end{array}$ so that $a < c$ .

Less than is compatible with $next$ , $plus$ , and $times$ (almost).

Let $a, b, c \in N$ . Then the following are equivalent.

$a < b$
$next (a) < next (b)$ .
$plus (a, c) < plus (b, c)$ .
$times (a, next (c)) < times (b, next (c))$ .

First we show that (1) implies (2). Suppose $a < b$ ; then there exists $c \in N$ such that $plus (a, next (c)) = b$ . But then we have $\begin{array}{rcl} plus (next (a), next (c)) \\ = & next (plus (a, next (c))) \\ = & next (b), \end{array}$ so that $next (a) < next (b)$ .

To see (2) implies (1), suppose we have $c$ such that $plus (next (a), next (c) = next (b)$ . Then $\begin{array}{rcl} next (plus (a, next (c))) \\ = & plus (next (a), next (c)) \\ = & next (b); \end{array}$ since $next$ is injective, we have $plus (a, next (c)) = b$ and thus $a < b$ as needed.

Next we show that (1) implies (3). To that end suppose $a < b$ ; then there exists $m \in N$ such that $plus (a, next (m)) = b$ . Now $\begin{array}{rcl} plus (plus (a, c), next (m)) \\ = & plus (a, plus (c, next (m))) \\ = & plus (a, plus (next (m), c)) \\ = & plus (plus (a, next (m)), c) \\ = & plus (b, c) \end{array}$ so that $plus (a, c) < plus (b, c)$ .

Next we show that (3) implies (1). To that end suppose $plus (a, c) < plus (b, c)$ ; then there exists $m \in N$ such that $plus (plus (a, c), next (m)) = plus (b, c) .$ Now $\begin{array}{rcl} plus (plus (a, next (m)), c) \\ = & plus (a, plus (next (m), c)) \\ = & plus (a, plus (c, next (m))) \\ = & plus (plus (a, c), next (m)) \\ = & plus (b, c) . \end{array}$ Since $plus$ is cancellative, we have $plus (a, next (m)) = b$ , so that $a < b$ as needed.

Now we show that (1) implies (4). To that end, suppose $a < b$ ; then there exists $m \in N$ such that $plus (a, next (m)) = b$ . Now $\begin{array}{rcl} times (b, next (c)) \\ = & times (plus (a, next (m)), next (c)) \\ = & plus (times (a, next (c)), times (next (m), next (c))) \\ = & plus (times (a, next (c)), \\ plus (times (m, next (c)), next (c))) \\ = & plus (times (a, next (c)), \\ next (plus (times (m, next (c)), c))), \end{array}$ and so $times (a, next (c)) < times (b, next (c))$ .

Next we show that (4) implies (1), proceeding by induction on $a$ . For the base case $a = 0$ , we consider two possibilities for $b$ . If $b = 0$ , then we have $\begin{array}{rcl} times (a, next (c)) \\ = & times (0, next (c)) \\ = & times (b, next (c)), \end{array}$ so that $times (a, next (c)) ≮ times (b, next (c))$ . Then (4) is false, so the implication (4) implies (1) holds vacuously. If $b = next (m)$ for some $m$ , then we have $\begin{array}{rcl} times (a, next (c)) \\ = & times (0, next (c)) \\ = & 0 \\ < & next (plus (times (m, next (c)), c)) \\ = & plus (times (m, next (c)), next (c)) \\ = & times (next (m), next (c)) \\ = & times (b, next (c)) \end{array}$ and $a = 0 < next (m) = b,$ so (4) implies (1) holds.

For the inductive step, suppose we have $a \in N$ such that for all $b$ and $c$ , if $times (a, next (c)) < times (b, next (c))$ then $a < b$ . We wish now to show that this statement also holds for $next (a)$ . To that end we consider two possibilities for $b$ .

If $b = 0$ , we have $\begin{array}{rcl} times (next (a), next (c)) \\ = & plus (times (a, next (c)), next (c)) \\ = & next (plus (times (a, next (c)), c)) \\ ≮ & 0 \\ = & times (0, next (c)) \\ = & times (b, next (c)); \end{array}$ So (4) does not hold for $b = 0$ , and thus (4) implies (1) holds vacuously in this case.

Suppose instead we have $b = next (m)$ for some $m \in N$ , and suppose further that $times (next (a), next (c)) < times (b, next (c)) .$ Now $\begin{array}{rcl} = & plus (times (a, next (c)), next (c)) \\ = & times (next (a), next (c)) \\ < & times (b, next (c)) \\ = & times (next (m), next (c)) \\ = & plus (times (m, next (c)), next (c)) . \end{array}$ We've already shown that (3) implies (1) over all natural numbers, so this implies $times (a, next (c)) < times (m, next (c)) .$ By the induction hypothesis on $a$ , we have $a < m$ , and because (1) implies (2) over all natural numbers, we have $next (a) < next (m) = b$ as needed. So (4) implies (1) for all $b$ and $c$ for all $a$ by induction, and so (4) implies (1) over all natural numbers as needed.

...Or Equal To

It's typical to generalize $<$ just a bit to make it reflexive.

We define a relation $\leq$ on $N$ as follows: $a \leq b$ if either $a < b$ or $a = b$ .

Less than or equal to satisfies most of the properties less than does (or very nearly so).

The following are equivalent for all $a, b, c \in N$ .

$a \leq b$ .
There exists $m \in N$ such that $plus (a, m) = b$ .
$next (a) \leq next (b)$ .
$plus (a, c) \leq plus (b, c)$ .
$times (a, next (c)) \leq times (b, next (c))$ .

First we show that (1) implies (2). If $a \leq b$ , either $a = b$ or $a < b$ . If $a = b$ , then $plus (a, 0) = plus (b, 0) = b .$ If $a < b$ , then by definition there is a $c$ with $plus (a, next (c)) = b$ . So (1) implies (2).

Now we show that (2) implies (1). Suppose we have $m \in N$ with $plus (a, m) = b$ . There are two possibilities for $m$ . If $m = 0$ , then $\begin{array}{rcl} a \\ = & plus (a, 0) \\ = & plus (a, m) \\ = & b, \end{array}$ so $a \leq b$ . If $m = next (n)$ , then $plus (a, next (n)) = b$ , so $a < b$ and thus $a \leq b$ . So (2) implies (1).

Now we show (1) implies (3). If $a \leq b$ , then either $a = b$ or $a < b$ . In the first case we have $next (a) = next (b)$ , and in the second case, as we've shown, $next (a) < next (b)$ . In either case $next (a) \leq next (b)$ as needed.

(3) implies (1) is shown similarly. If $next (a) \leq next (b)$ , then either $next (a) = next (b)$ or $next (a) < next (b)$ . In the first case we have $a = b$ because $next$ is injective, and in the second case we've shown that $a < b$ . In either case $a \leq b$ as needed.

Now we show (1) implies (4). If $a \leq b$ then either $a = b$ or $a < b$ . If $a = b$ , we have $plus (a, c) = plus (b, c)$ , and if $a < b$ , we've shown that $plus (a, c) < plus (b, c)$ . In either case, $plus (a, c) \leq plus (b, c)$ .

(4) implies (1) is shown similarly. If $plus (a, c) \leq plus (b, c)$ then either $plus (a, c) = plus (b, c)$ or $plus (a, c) < plus (b, c)$ . In the first case, because $plus$ is cancellative we have $a = b$ . In the second case, we've shown that $a < b$ . In either case we have $a \leq b$ as needed.

Next we show (1) implies (5). If $a \leq b$ , then either $a = b$ or $a < b$ . If $a = b$ we have $times (a, next (c)) = times (b, next (c)) .$ If $a < b$ , then as we've shown we have $times (a, next (c)) < times (b, next (c)) .$ In either case we have $times (a, next (c)) \leq times (b, next (c)) .$

Finally we show (5) implies (1). If $times (a, next (c)) \leq times (a, next (b)),$ then either $times (a, next (c)) = times (b, next (c))$ or $times (a, next (c)) < times (b, next (c)) .$ In the first case we have $a = b$ because $times$ is (almost) cancellative, and in the second case we've shown that $a < b$ . In either case $a \leq b$ .

As expected, $\leq$ is reflexive, antisymmetric, and transitive.

The following hold for all $a, b, c \in N$ .

$a \leq a$ .
If $a \leq b$ and $b \leq a$ , then $a = b$ .
If $a \leq b$ and $b \leq c$ , then $a \leq c$ .

If $a \in N$ then $a = a$ , so $a \leq a$ by definition.

Suppose $a \leq b$ and $b \leq a$ . Then there exist $m, n \in N$ such that $plus (a, m) = b$ and $plus (b, n) = a$ . Now $\begin{array}{rcl} plus (a, plus (m, n)) \\ = & plus (plus (a, m), n) \\ = & plus (b, n) \\ = & a; \end{array}$ so we have $plus (m, n) = 0$ , and then $m = n = 0$ . So $a = plus (b, m) = plus (b, 0) = b$ as claimed.

Now suppose $a \leq b$ and $b \leq c$ ; then there are $m, n \in N$ with $plus (a, m) = b$ and $plus (b, n) = c$ . Then $\begin{array}{rcl} plus (a, plus (m, n)) \\ = & plus (plus (a, m), n) \\ = & plus (b, n) \\ = & c, \end{array}$ so $a \leq c$ .

We can also solve some inequalities.

If $m \in N$ such that $m \leq 0$ , then $m = 0$ .

Suppose $m \leq 0$ . There are two possibilities for $m$ ; either $m = 0$ or $m = next (n)$ for some $n$ . We've shown that $next (n) ≮ 0$ , and also that $0 ≮ 0$ ; in either case we have $m ≮ 0$ . So it must be that $m = 0$ .

We can split a $\leq$ inequality with a $next$ into an $=$ part and a $<$ part with no $next$ ; this is handy for induction proofs.

Let $k, n \in N$ . If $k \leq next (n)$ , then either $k \leq n$ or $k = next (n)$ .

Suppose $k \leq next (n)$ ; then we have $m$ such that $plus (k, m) = next (n)$ . There are two possibilities for $m$ . If $m = 0$ , then $k = plus (k, 0) = plus (k, m) = next (n) .$ Suppose instead that $m = next (u)$ for some $u$ . Then $\begin{array}{rcl} next (n) \\ = & plus (k, m) \\ = & plus (k, next (u)) \\ = & next (plus (k, u)) . \end{array}$ Since $next$ is injective, we have $plus (k, u) = n$ , and so $k \leq n$ as needed.

We can state this in a slightly different way.

For all $a, b \in N$ , if $a < next (b)$ then $a \leq b$ .

Greater Than

It's convenient to name the inverses of $<$ and $\leq$ .

We define a relation $>$ on $N$ (pronounced greater than) as follows. Given $a, b \in N$ , $a > b$ means the same as $a < b$ .

Similarly we define $\geq$ such that $a \geq b$ means the same as $b \leq a$ .

$>$ has analogous properties to those of $<$ whose proofs are all trivial.

For all $a, b, c \in N$ we have the following.

$next (a) > 0$ .
$0 ≯ next (a)$ .
$a ≯ a$ .
If $a > b$ , then $b ≯ a$ .
If $a > b$ and $b > c$ , then $a > c$ .

$>$ interacts with $next$ , $plus$ , and $times$ .

For all $a, b, c \in N$ , the following are equivalent.

$a > b$ .
$next (a) > next (b)$ .
$plus (a, c) > plus (b, c)$ .
$times (a, next (c)) > times (b, next (c))$ .

Likewise $\geq$ .

For all $a, b, c \in N$ we have the following.

$a \geq a$ .
If $a \geq b$ and $b \geq a$ , then $a = b$ .
If $a \geq b$ and $b \geq c$ , then $a \geq c$ .

And $\geq$ interacts with $next$ , $plus$ , and $times$ .

For all $a, b, c \in N$ , the following are equivalent.

$a \geq b$ .
There exists $m \in N$ such that $plus (b, m) = a$ .
$next (a) \geq next (b)$ .
$plus (a, c) \geq plus (b, c)$ .
$times (a, next (c)) \geq times (b, next (c))$ .

The additive order relations are handy for lots of reasons. A particularly good one is the following result, which gives a proof template for doing case analysis on $N$ .

Let $a, b \in N$ . Then one and only one of the following holds.

$a < b$
$a = b$
$a > b$

We call this the trichotomy property of the natural numbers.

First we show the "one" part; that any two natural numbers satisfy at least one of these relations. We proceed by induction on $a$ . For the base case $a = 0$ , note that there are two possibilities for $b$ . If $b = 0$ , then we have $a = 0 = b .$ If $b = next (m)$ for some $m$ , then we've shown that $a = 0 < next (m) = b,$ so that $a < b$ .

For the inductive step, suppose the claim holds for all $b$ for some $a$ , and consider $next (a)$ . Let $b \in N$ . By the inductive hypothesis we have three possibilities.

If $a < b$ , we have $plus (a, next (c)) = b$ for some $c$ . Thus $plus (next (a), c) = b .$ There are two possibilities for $c$ ; if $c = 0$ , then we have $next (a) = b$ as needed, and if $c = next (d)$ for some $d$ then $next (a) < b$ as needed.

If $a = b$ , we have $\begin{array}{rcl} plus (b, next (0)) \\ = & plus (a, next (0)) \\ = & next (plus (a, 0)) \\ = & next (a), \end{array}$ so $b < next (a)$ .

If $a > b$ , we have $plus (b, next (c)) = a$ for some $c$ . Now $\begin{array}{rcl} next (a) \\ = & next (plus (b, next (c))) \\ = & plus (b, next (next (c))), \end{array}$ so that $b < next (a)$ .

In all cases, either $next (a) < b$ , $next (a) = b$ , or $next (a) > b$ , as needed. By induction the claim holds for all $a, b \in N$ .

We still need to check the "only one" part of this claim. If $a = b$ , we've shown we cannot also have $a < b$ , and similarly cannot have $a > b$ . If $a < b$ , then (by definition) $b > a$ and we cannot also have $a > b$ .

And so at least one of $a < b$ , $a = b$ , or $a > b$ holds, but also at most one holds.

The order relations also allow us to express an alternative form of the induction principle. Recall that with ordinary induction, a property holds for all natural numbers if it holds for $0$ and also for $next (n)$ when it holds for $n$ . It turns out we can "weaken" the inductive hypothesis a bit to all $k$ such that $k \leq n$ . This form of induction is not actually stronger in deductive power than normal induction, but it is sometimes easier to use, and we call it strong induction to distinguish it from normal induction.

Let $A$ be a set and suppose we have a function $f : N \to A$ . Suppose now that we have a subset $B \subseteq A$ satisfying the following:

$f (0) \in B$ .
If $n \in N$ and $f (k) \in B$ for all $k \leq n$ , then $f (next (n)) \in B$ .

Then we have $f (n) \in B$ for all $n \in N$ . When using this theorem we say we are proceeding by strong induction; (1) is called the base case and (2) is called the inductive step.

Let $B$ be such a subset. We define an auxiliary subset $T \subseteq N$ as follows: $T = {n ∣ if k \leq n then f (k) \in B for all k} .$ We first will show that $T = N$ by induction.

For the base case, consider $n = 0$ . If $k \leq 0$ , then $k = 0$ . We have $f (k) = f (0) \in B$ by definition, and thus $0 \in T$ as needed.

For the inductive step, suppose we have $n \in T$ . Now suppose $k \leq next (n)$ . We need to show that $f (k) \in B$ . There are two possibilities: either $k \leq n$ or $k = next (n)$ . Suppose first that $k \leq n$ ; since $n \in T$ , we have $f (k) \in B$ . Now suppose $k = next (n)$ . Again we have $n \in T$ , and note that the condition for membership in $T$ is precisely the hypothesis of (2). So we have $f (next (n)) \in B$ . In either case we have $f (k) \in B$ , and so $next (n) \in T$ . By induction we thus have $T = N$ .

Finally we can show that $f (n) \in B$ for all $n$ . To this end let $n \in N$ . We have $n \in T$ , and in particular, since $n \leq n$ , we have $f (n) \in B$ . Since $n$ was arbitrary the theorem is proved.

The most common variant of strong induction is that having $A = N$ and $f = id$ .

Suppose we have a subset $B \subseteq N$ satisfying the following properties.

$0 \in B$ .
For all $n \in N$ , if $k \in B$ whenever $k \leq n$ , then $next (n) \in B$ .

Then $B = N$ .

Strong induction also has an analogous "measure" variety.

Let $f : A \to N$ be a function. Suppose we have $B \subseteq A$ satisfying the following.

$f (a) = 0$ implies $a \in B$ for all $a \in A$ .
For all $n \in N$ , if $f (a) = k$ and $k \leq n$ imply $a \in B$ for all $k \in N$ and $a \in A$ , then $f (a) = next (n)$ implies $a \in B$ for all $a \in A$ .

Then we have $B = A$ . When using this theorem we say we are proceeding by strong induction on $f$ ; (1) is called the base case, and (2) the inductive step.

Let $B$ be such a subset. We define an auxiliary subset $T \subseteq N$ by $T = {n ∣ if f (a) = n then a \in B for all a \in A} .$ We first will show that $T = N$ by strong induction.

For the base case $n = 0$ , note that for all $a \in A$ , if $f (a) = 0$ then $a \in b$ by (1). So we have $0 \in T$ .

For the inductive step, let $n \in N$ and suppose we have $k \in T$ for all $k \leq n$ . We want to show that $next (n) \in T$ . First note the following: if $a \in A$ and $k \leq n$ , since $k \in T$ , we have that if $f (a) = k$ then $a \in B$ . This is precisely the hypothesis of (2). And so, whenever $f (a) = next (n)$ , we have $a \in B$ . Thus $next (n) \in T$ , and by induction we have $T = N$ .

Finally, let $a \in A$ . Now $f (a) \in N \subseteq T$ , so we have $a \in B$ . Thus $B = A$ as claimed.

We can also show that there are no natural numbers between $m$ and $next (m)$ for any $m$ .

Let $m \in N$ . There does not exist $n \in N$ such that $m < n$ and $n < next (m)$ .

Suppose we have $m < n$ and $n < next (m)$ . Then we have $u, v \in N$ such that $plus (m, next (u)) = n$ and $plus (n, next (v)) = next (m)$ . Now $\begin{array}{rcl} next (m) \\ = & plus (n, next (v)) \\ = & plus (plus (m, next (u)), next (v)) \\ = & next (plus (plus (m, next (u)), v)) \\ = & next (plus (m, plus (next (u), v))) \\ = & next (plus (m, next (plus (u, v)))) . \end{array}$ Since $next$ is injective, $m = plus (m, next (plus (u, v)))$ , and so $next (plus (u, v)) = 0$ , which is absurd. So no such $m$ exists.

The following utility theorem tells us something about gaps between multiples of a nonzero number.

Suppose $a_{1}, a_{2}, b, k \in N$ such that the following hold.

$times (a_{1}, next (b)) = plus (times (a_{2}, next (b)), k)$ .
$k < next (b)$ .

Then $k = 0$ .

For bookkeeping purposes, let $A \subseteq N \times N$ be the set of all pairs $(a_{1}, a_{2})$ such that conditions (1) and (2) simultaneously imply $k = 0$ for all $b, k \in N$ . We need to show that if $(a_{1}, a_{2}) \in N \times N$ then $(a_{1}, a_{2}) \in A$ ; we will show this by induction first on $a_{1}$ and then on $a_{2}$ .

For the base case, we need to show that $(0, a_{2}) \in A$ for all $a_{2}$ . To this end, suppose we have $b$ and $k$ such that $a_{1} = 0$ , $a_{2}$ , $b$ , and $k$ satisfy (1) and (2). Now $\begin{array}{rcl} 0 \\ = & times (0, next (b)) \\ = & times (a_{1}, next (b)) \\ = & plus (times (a_{2}, next (b)), k) . \end{array}$ As we've shown, we must have $k = 0$ . Thus we have $(0, a_{2}) \in A$ for all $a_{2}$ .

For the inductive step, suppose we have $a_{1}$ such that $(a_{1}, a_{2}) \in A$ for all $a_{2}$ . We need to show that $(next (a_{1}), a_{2}) \in A$ for all $a_{2}$ , and will proceed by considering two possibilities for $a_{2}$ .

First suppose $a_{2} = 0$ , and suppose we have $b$ and $k$ such that $next (a_{1})$ , $a_{2} = 0$ , $b$ , and $k$ satisfy (1) and (2). Now $\begin{array}{rcl} plus (times (a_{1}, next (b)), next (b)) \\ = & times (next (a_{1}), next (b)) \\ = & plus (times (a_{2}, next (b)), k) \\ = & plus (times (0, next (b)), k) \\ = & plus (0, k) \\ = & k . \end{array}$ In particular, $next (b) \leq k$ ; but by the trichotomy property this is absurd since $k < next (b)$ . So (1) and (2) cannot hold simultaneously for $a_{2} = 0$ , and thus $(next (a_{1}), a_{2}) \in A$ vacuously.

Now suppose we have $a_{2} = next (m)$ for some $m$ . We need to show that $(next (a_{1}), a_{2}) \in A$ . To this end, suppose we have $b$ and $k$ such that $next (a_{1})$ , $a_{2} = next (m)$ , $b$ , and $k$ satisfy (1) and (2). Specifically, we have $\begin{array}{rcl} times (next (a_{1}), next (b)) \\ = & plus (times (a_{2}, next (b)), k) \\ = & plus (times (next (m), next (b)), k) . \end{array}$ Now we have $\begin{array}{rcl} plus (times (a_{1}, next (b)), next (b)) \\ = & times (next (a_{1}), next (b)) \\ = & plus (times (a_{2}, next (b)), k) \\ = & plus (times (next (m), next (b)), k) \\ = & plus (plus (times (m, next (b)), next (b)), k) \\ = & plus (times (m, next (b)), plus (next (b), k)) \\ = & plus (times (m, next (b)), plus (k, next (b))) \\ = & plus (plus (times (m, next (b)), k), next (b)), \end{array}$ and because $plus$ is cancellative, we have $times (a_{1}, next (b)) = plus (times (m, next (b)), k) .$ Because we also have $k < next (b)$ and $(a_{1}, m) \in A$ by the inductive hypothesis, $k = 0$ . So $(next (a_{1}), a_{2}) \in A$ .

So we have $(next (a_{1}), a_{2}) \in A$ for all $a_{2}$ . By induction, $A = N \times N$ as claimed.