Proof of Properties of the Order on the Natural Numbers

Throughout we use the numbered claims of Arithmetic of Addition on the Natural Numbers and the defining property of $<$ from the definition of the order: $m<n$ means that $n=m+k$ for some $k\in\mathbb{N}$. Every appeal to induction means an application of Principle of Induction for the Natural Numbers.

Claim 1. The relation $m\le m$ holds because $m=m$, and $m<n$ implies $m\le n$, both directly from the definition. For transitivity of $<$, suppose $n=m+k$ and $p=n+l$ with $k,l\in\mathbb{N}$. Then, by claim 3 of Arithmetic of Addition on the Natural Numbers,

$$p=(m+k)+l=m+(k+l),$$

and $k+l\in\mathbb{N}$, so $m<p$. For transitivity of $\le$, suppose $m\le n$ and $n\le p$. If $m=n$ or $n=p$ the conclusion is immediate; otherwise $m<n$ and $n<p$, so $m<p$ and hence $m\le p$.

Claim 2. If $m<m$ then $m=m+k$ for some $k\in\mathbb{N}$, contradicting claim 8 of Arithmetic of Addition on the Natural Numbers. If both $m<n$ and $n<m$ held, then $m<m$ by Claim 1, which is impossible. Finally, suppose $m\le n$ and $n\le m$ and $m\ne n$. Then $m<n$ and $n<m$, which we have just excluded; hence $m=n$.

Claim 3. We first record that $m<S(m)$ for every $m$: indeed $S(m)=m+1$ by claim 1 of Arithmetic of Addition on the Natural Numbers, so the definition applies with $k=1$.

We prove by induction on $n$ the statement $T(n)$: for every $m\in\mathbb{N}$, at least one of $m<n$, $m=n$, $n<m$ holds.

$T(1)$: let $m\in\mathbb{N}$. If $m=1$ we are done. Otherwise $m=S(j)$ for some $j\in\mathbb{N}$ by claim 6 of Arithmetic of Addition on the Natural Numbers, and $S(j)=j+1=1+j$ by claims 1 and 4 of that lemma; hence $m=1+j$ and $1<m$.

$T(n)\Rightarrow T(S(n))$: let $m\in\mathbb{N}$ and apply $T(n)$. If $m<n$, then $m<S(n)$ by $n<S(n)$ and Claim 1. If $m=n$, then $m<S(m)=S(n)$. If $n<m$, write $m=n+k$ with $k\in\mathbb{N}$. When $k=1$ we get $m=n+1=S(n)$. When $k\ne 1$, claim 6 of Arithmetic of Addition on the Natural Numbers gives $k=S(j)=j+1$ for some $j\in\mathbb{N}$, so by claims 3, 4 and 1 of that lemma

$$m=n+(j+1)=(n+1)+j=S(n)+j,$$

hence $S(n)<m$. This proves $T(S(n))$.

By induction $T(n)$ holds for all $n$, so at least one of the three alternatives holds. At most one holds: $m<n$ and $n<m$ are incompatible by Claim 2, and $m=n$ together with $m<n$ or with $n<m$ would give $m<m$, which is impossible by Claim 2.

Claim 4. Induct on $m$. For $m=1$ we have $1\le 1$ by Claim 1. Assume $1\le m$. Since $m<S(m)$, as recorded in the proof of Claim 3, we get $m\le S(m)$, and transitivity of $\le$ from Claim 1 gives $1\le S(m)$.

Claim 5. That $m<S(m)$ was recorded in the proof of Claim 3. Now suppose $k\le S(m)$ and $k\ne S(m)$; then $k<S(m)$, so $S(m)=k+b$ for some $b\in\mathbb{N}$. By Claim 3 applied to $k$ and $m$, one of $k<m$, $k=m$, $m<k$ holds; in the first two cases $k\le m$ and we are done. Suppose $m<k$, say $k=m+a$ with $a\in\mathbb{N}$. Then, using claim 3 of Arithmetic of Addition on the Natural Numbers,

$$S(m)=k+b=(m+a)+b=m+(a+b),$$

while $S(m)=m+1$ by claim 1 of that lemma. Hence $m+(a+b)=m+1$, and applying claim 4 of that lemma to both sides gives $(a+b)+m=1+m$, so $a+b=1$ by claim 5 of that lemma. This contradicts claim 7 of that lemma. Therefore $m<k$ is impossible and $k\le m$.

Claim 6. The relation $m<m+j$ is the definition with $k=j$. Next suppose $j\le t$. If $j=t$ then $m+j=m+t$. Otherwise $t=j+k$ with $k\in\mathbb{N}$, and claim 3 of Arithmetic of Addition on the Natural Numbers gives

$$m+t=m+(j+k)=(m+j)+k,$$

so $m+j<m+t$. In both cases $m+j\le m+t$. Finally suppose $m\le n$. If $m=n$ then $S(m)=S(n)$. Otherwise $n=m+k$ with $k\in\mathbb{N}$, and by claims 1, 3 and 4 of Arithmetic of Addition on the Natural Numbers

$$S(n)=n+1=(m+k)+1=(m+1)+k=S(m)+k,$$

so $S(m)<S(n)$. In both cases $S(m)\le S(n)$.

Claim 7. Existence of $k$ with $y=m+k$ is the definition of $m<y$. For uniqueness, suppose $y=m+k=m+k'$ with $k,k'\in\mathbb{N}$. By claim 4 of Arithmetic of Addition on the Natural Numbers this gives $k+m=k'+m$, and claim 5 of that lemma gives $k=k'$.