$\begingroup$Is my proof correct?
The trichotomy of order for natural numbers states: Let $a,b$ be natural numbers. Then exactly one of the following statements is true:
I. $a < b$
II. $a = b$
III. $a > b$
Proof:
If $a < b$ then by definition $a \neq b$. If $a > b$ then $a \neq b$ by definition as well. Therefore it is not possible to have I and II be true at the same time, nor II and III be true at the same time, nor I, II, and III be true at the same time.
If $a < b$ and $a > b$ then it means we can write $a = b + m$ and $b = a + n$ for natural numbers $n,m$ where $a \neq b$. By substitution, $a = a + n + m$, which by cancellation law is $0 = n + m$. This also means $n = m = 0$, suggesting that $a = b$, a contradiction. Therefore it is not possible for I and III to be true at the same time.
Now we will show that at least one of I, II, or III is true via induction on $a$.
Base case: Let $a=0$. If $b=0$, then $a=b$, statement II, is true. If $b \neq 0$, then statement I is true, $0 < b$, since we can write $0 + m = m = b$ where $0 \neq b$.
Inductive step: Suppose either $a < b$, $a = b$, or $a > b$ is true. We need to show that $S(a) < b$, $S(a) = b$, or $S(a) > b$ is true.
If $a > b$, then $S(a) > b$ is true, since $a = b + m$ where $a \neq b$, so we also have $S(a) = S(b + m) = b + S(m)$ which satisfies the definition for $S(a) > b$ as long as $S(a) \neq b$. And $S(a) \neq b$ is true, since if it weren't, we'd have $b = b + S(m)$ or $0 = S(m)$ by additive identity and cancellation law, and $0$ is not a successor of any natural number.
If $a = b$, then $S(a) > b$ is true. This is because if $a = b$ then $S(a) = S(b) = S(b + 0) = b + S(0)$ which satisfies the definition for $S(a) > b$ as long as $S(a) \neq b$. And $S(a) \neq b$ is still true, since if it weren't, we'd have $b = b + S(0)$ or $0 = S(0)$ by additive identity and cancellation law, and $0$ is not a successor of any natural number.
If $a < b$, then either $S(a) < b$ or $S(a) = b$ is true. We can write $b = a + m$ for some $m$ where $a \neq b$ (so $m \neq 0$). Suppose $m=S(0)$. Then $b = a + S(0) = S(a + 0) = S(a)$. If $m \neq S(0)$, then $S(a) \neq b$, so it suffices to show that $b = S(a) + k$ for some $k$. If we let $S(k) = m$ (which is valid since we have $m \neq 0$), then $b = a + S(k) = S(a + k) = S(a) + k$ holds.
This closes the induction.
$\endgroup$1 Reset to default
