next up previous contents
Next: Substraction Up: The natural numbers Previous: Multiplication   Contents


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:

$\displaystyle 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{displaymath}\begin{cases}
 m \leq n \\ n \leq m
 \end{cases}
 \Longleftrightarrow\end{displaymath} \begin{displaymath}\begin{cases}
 \exists k_1 \in \mathbb{N}, \; n=m+k_1 \\ 
 \exists k_2 \in \mathbb{N}, \; m=n+k_2 
 \end{cases}\end{displaymath}    
    $\displaystyle \quad$ $\displaystyle 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{displaymath}\begin{cases}
 m \leq n \\  n \leq p
 \end{cases}
 \Longleftr...
...ion} \end{matrix}}{=}m+\underbrace{(k_1+k_2)}_{\in \mathbb{N}}.\end{displaymath}    

    Hence, $ m \leq p$.
$ \qedsymbol$

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

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

Proof. By definition, we have:

$\displaystyle 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,

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

Proof. By definition, we have:

$\displaystyle 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.

$\displaystyle 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.

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

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

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

by induction on $ n$. $ \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)$.


next up previous contents
Next: Substraction Up: The natural numbers Previous: Multiplication   Contents
root 2002-06-10