When $n=1$ the equality holds; otherwise, by Problem $3.6, n=m^{*}=m+1$, for some $m \in \mathbb{N}$, and the inequality holds.

Let $m$ be any element of $\mathbb{N}$ and construct the subsets $N_{1}={m}, N_{2}={x: x \in \mathbb{N}, xm} .$ We are to show that $\left{N_{1}, N_{2}, N_{3}\right}$ is a partition of $\mathbb{N}$ relative to ${=,<,>}$.
(1) Suppose $m=1$; then $N_{1}={1}, N_{2}=\emptyset$ (Problem 3.9) and $N_{3}={x: x \in \mathbb{N}, x>1}$. Clearly $N_{1} \cup N_{2} \cup N_{3}=\mathbb{N}$. Thus, to complete the proof for this case, there remains only to check that $N_{1} \cap N_{2}=N_{1} \cap N_{3}=N_{2} \cap N_{3}=\emptyset .$
(2) Suppose $m \neq 1$. Since $1 \in N_{2}$, it follows that $1 \in N_{1} \cup N_{2} \cup N_{3}$. Now select any $n \neq 1 \in N_{1} \cup N_{2} \cup N_{3}$. There are three cases to be considered:
(i) $n \in N_{1}$. Here, $n=m$ and so $n^{} \in N_{3}$. (ii) $n \in N_{2}$ so that $n+p=m$ for some $p \in \mathbb{N}$. If $p=1$, then $n^{}=m \in N_{1}$; if $p \neq 1$ so that $p=1+q$ for some $q \in \mathbb{N}$, then $n^{}+q=m$ and so $n^{} \in N_{2}$.
(iii) $n \in N_{3}$. Here $n^{}>n>m$ and so $n^{} \in N_{3}$.
Thus, for every $n \in \mathbb{N}, n \in N_{1} \cup N_{2} \cup N_{3}$ implies $n^{*} \in N_{1} \cup N_{2} \cup N_{3}$. Since $1 \in N_{1} \cup N_{2} \cup N_{3}$ we conclude that $\mathbb{N}=N_{1} \cup N_{2} \cup N_{3}$.

Now $m \notin N_{2}$, since $m \nless m$; hence $N_{1} \cap N_{2}=\emptyset$. Similarly, $m \ngtr m$ and so $N_{1} \cap N_{3}=\emptyset$. Suppose $p \in N_{2} \cap N_{3}$ for some $p \in \mathbb{N}$. Then $pm$, or, what is the same, $p<m$ and $m<p$. Since $<$ is transitive, we have $p<p$, a contradiction. Thus, we must conclude that $N_{2} \cap N_{3}=\emptyset$ and the proof is now complete for this case.

Since $mn$. If $m=n$, then $m+p=n+p$; if $m>n$, then $m+p>n+p$ (Theorem II’). Since these contradict the hypothesis, we conclude that $m<n$.