Ordering

We define a binary relation $\leq$ (=''less than or equal to'') in $\mathbb{N}$ in the following way:

Definition 6.1.27   For any two natural numbers $m$ and $n$, we have:

$$m \leq n \Longleftrightarrow \; \exists k \in \mathbb{N}, \; n=m+k.$$

The following theorem requires the belonging of 0 to the set $\mathbb{N}$ of natural numbers.

Theorem 6.1.28   The binary relation $\leq$ is an ordering on $\mathbb{N}$.

Proof. First we prove that $\leq$ is an ordering on $\mathbb{N}$.

1. (R) For any $m \in \mathbb{N}$, $m=m+0$ and $0 \in \mathbb{N}$, thus $m \leq m$.
2. (AS) Let $m$ and $n$ be two natural numbers such that $m \leq n$ and $n \leq m$. We have:

   $$\begin{cases} m \leq n \\ n \leq m \end{cases} \Longleftrightarrow \begin{cases} \exists k_1 \in \mathbb{N}, \; n=m+k_1 \\ \exists k_2 \in \mathbb{N}, \; m=n+k_2 \end{cases}$$

   $$\quad n+m=(m+k_1)+(n+k_2)\underset{\begin{matrix}\uparrow \\ \text{by c... ...\ \text{and associativity}\\ \text{of addition}\end{matrix}}{=}(n+m)+(k_1+k_2).$$

   
   
   Thus $k_1+k_2=0$ and by Proposition 1.16, $k_1=k_2=0$, i.e. $m=n$.
3. (T) Let $m$, $n$ and $p$ be three natural numbers such that $m \leq n$ and $n \leq p$. We have:

   $$\begin{cases} m \leq n \\ n \leq p \end{cases} \Longleftr... ...ion} \end{matrix}}{=}m+\underbrace{(k_1+k_2)}_{\in \mathbb{N}}.$$

   
   
   Hence, $m \leq p$.

$\qedsymbol$

Proposition 6.1.29   For any triple $(m,n,p)$ of natural numbers,

$$(m \leq n) \Longleftrightarrow (m+p \leq n+p).$$

Proof. By definition, we have:

$$m \leq n \Longleftrightarrow \; \exists k \in \mathbb{N}, \; n=m+k.$$

Thus we have $n+p=(m+k)+p=m+\underbrace{(k+p)}_{\in \mathbb{N}}$, i.e. $m+p \leq n+p$. $\qedsymbol$

Proposition 6.1.30   For any triple $(m,n,p)$ of natural numbers,

$$(m \leq n) \Longleftrightarrow (mp \leq np).$$

Proof. By definition, we have:

$$m \leq n \Longleftrightarrow \; \exists k \in \mathbb{N}, \; n=m+k.$$

Thus we have $np=(m+k)p=mp+\underbrace{kp}_{\in \mathbb{N}}$, i.e. $mp \leq np$. $\qedsymbol$

Now we define a ``not so new'' binary relation on $\mathbb{N}$: when $m$ and $n$ are two natural numbers, we denote $m<n$ if $m \leq n$    and $m neq n$, i.e.

$$m<n \Longleftrightarrow \; \exists k \in \mathbb{N}\setminus \{ 0 \}, n=m+k.$$

Obviously, this relation is not an ordering, because of a lack of reflexivity. Nevertheless it has useful properties; in particular it is transitive and verifies properties like Proposition 1.29 and Proposition 1.30.

Theorem 6.1.31   The relation $\leq$ is a total ordering in $\mathbb{N}$, i.e.

$$\forall m \in \mathbb{N}, \;\forall n \in \mathbb{N},\; n \leq m m \leq n.$$

Proof. What has to be proven is that the ordering is total; we will prove it in the following form:

$$\forall m \in \mathbb{N}, \;\forall n \in \mathbb{N},\; m<n m=n n<m.$$

by induction on $n$.

• Suppose that $n=0$:
  • If $m=0$, then $m=n$;
  • If $m \neq 0$, then $0<m$
  and we are done.
• Assume that $n$ and $m$ verify the theorem for any $m \in \mathbb{N}$; we shall now compare $n'$ and $m$.
  • Suppose that $m \leq n$, i.e. it exists $k \in \mathbb{N}$ such that $n=m+k$. Then we have: $n'=(m+k)'=m+k'$ and $m \leq n'$.
  • If $n <m$, it exists $r \in \mathbb{N}\setminus \{ 0 \}$ such that $m=n+r$. As $r \neq 0$, it exists a natural number $s$ such that $r=s'$ and we have:

    $$m=n+r=n+s'=n+(s+1)=n+(1+s)=(n+1)+s=n'+s.$$

    
    
    If $s=0$, then $m=n'$; otherwise, $n'<m$ and we are done.

$\qedsymbol$

The following result is easily proven by contrapositive arguments.

Proposition 6.1.32   Let $m$, $n$ and $p$ be three natural numbers. Then we have:

(i)

$mp<np \Longrightarrow (p \neq 0$    and $m<n)$.

(ii)

$mp \leq np \Longrightarrow ( p=o$    or $m \leq n)$.