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.


1 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.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .