# Ordering on Natural Numbers is Compatible with Addition

Jump to navigation
Jump to search

## Theorem

Let $m, n, k \in \N$ where $\N$ is the set of natural numbers.

Then:

- $m < n \iff m + k < n + k$

### Corollary

Let $a, b, c, d \in \N$ where $\N$ is the set of natural numbers.

Then:

- $a > b, c > d \implies a + c > b + d$

## Proof

Proof by induction:

For all $k \in \N$, let $\map P k$ be the proposition:

- $m < n \iff m + k < n + k$

$\map P 0$ is true, as this just says $m + 0 = m < n = n + 0$.

This is our basis for the induction.

### Induction Hypothesis

Now we need to show that, if $\map P j$ is true, where $j \ge 0$, then it logically follows that $\map P {j^+}$ is true.

So this is our induction hypothesis:

- $m < n \iff m + j < n + j$

Then we need to show:

- $m < n \iff m + j^+ < n + j^+$

### Induction Step

This is our induction step:

Let $m < n$.

Then:

\(\displaystyle m\) | \(<\) | \(\displaystyle n\) | |||||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle m\) | \(\subsetneq\) | \(\displaystyle n\) | Element of Finite Ordinal iff Subset | |||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle m^+\) | \(\subset\) | \(\displaystyle n\) | Definition of Successor Set | |||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle m^+\) | \(\subsetneq\) | \(\displaystyle n^+\) | Definition of Successor Set | |||||||||

\((1):\quad\) | \(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle m^+\) | \(<\) | \(\displaystyle n^+\) | Element of Finite Ordinal iff Subset |

This gives:

\(\displaystyle m + j\) | \(<\) | \(\displaystyle n + j\) | |||||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle \paren {m + j}^+\) | \(<\) | \(\displaystyle \paren {n + j}^+\) | from $(1)$ above | |||||||||

\(\displaystyle \leadstoandfrom \ \ \) | \(\displaystyle m + j^+\) | \(<\) | \(\displaystyle n + j^+\) | Definition of Addition in Minimal Infinite Successor Set |

So $\map P j \implies \map P {j^+}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

- $\forall m, n, k \in \N: m < n \iff m + k < n + k$

$\blacksquare$

## Sources

- 1951: Nathan Jacobson:
*Lectures in Abstract Algebra: I. Basic Concepts*... (previous) ... (next): Introduction $\S 4$: The natural numbers - 1960: Paul R. Halmos:
*Naive Set Theory*... (previous) ... (next): $\S 13$: Arithmetic - 1972: A.G. Howson:
*A Handbook of Terms used in Algebra and Analysis*... (previous) ... (next): $\S 4$: Number systems $\text{I}$: Peano's Axioms