Prove trichotomy law of addition in $\mathbb{N}$ (Peano Axioms).

Question

I need help in my proof trichotomy law of addition in $\mathbb{N}$ (Peano Axioms). I have already proved that addition is associative and commutative. Also I proved the cancellation law and some useful lemmas. Now I'm having trouble proving the following proposition:

Let $m,n \in \mathbb{N}$. Then, exactly one of the following statements is true:

1. $m=n$
2. There is a natural number $p \neq 0$ such that $ m = n + p$.
3. There is a natural number $q \neq 0 $ such that $n = m + q$.

My try

First, I proved that two of this statements can not occur at the same time.

If $1), 2)$ are true, then $m=m+p$ and by cancellation law, $p=0$, contradiction. This is analogous for $1),3)$. Then, assume $2),3)$. Then, $m = m + q + p$, and by cancellation law, $ 0 = q + p \implies q=p=0$, a contradiction (I proved this last statement previously). Then, no more than 1 statement can be true.

Now, I need to prove that at least $1$ of the statements is true to finish the proof, but I don't know how to proceed. I know that this is a basic/classic question but I did not found any post about this in MSE. If such post exist, please let me know and sorry for reposting.

Any hints are appreciated.

Answer 1

We will first prove that for all $n, m$, either $\exists p (n + p = m)$ or $\exists p (m + p = m)$. We proceed by induction on $m$.

Base case $m = 0$: then we have $m + n = 0 + n = n + 0 = n$.

Inductive case $m = S(k)$: we split into three sub-cases based on the inductive hypothesis and the fact that every number is either a successor or zero.

Subcase $k + p = n$ where $p = S(p')$: then we have $n = k + S(p') = S(k + p') = S(p' + k) = p' + S(k) = p' + m = m + p'$.

Subcase $k + p = n$ where $p = 0$: then $k + 0 = k = n$. Then $m = S(k) = S(n)$. Then $m = S(n + 0) = n + S(0)$.

Subcase $n + p = k$: then $n + S(p) = S(n + p) = m$.

Thus, we have proven that for every $n$, $m$, either $\exists p (n + p = m)$ or $\exists p (m + p = n)$.

We now wish to prove that for every $n, m$, we have at least one of $n = m$, $\exists p (n + S(p) = m)$, and $\exists p (m + S(p) = n)$.

Now suppose WLOG that $\exists p (n + p = m)$. We split into two cases. Firstly, suppose that $p = 0$. Then we have $n = m$. Secondly, suppose that we can write $p = S(p')$. Then we have $n + S(p') = m$. The case $\exists p (m + p = n)$ is similar.

Clearly, this suffices to show that at least one of the options in your trichotomy holds.