Let $m \in \mathbb{N}$. Show that $\nexists n \in \mathbb{N}$ such that $m < n < s(m)$, where $s$ is the successor function.

Here's my proof using only the Peano Axioms I was introduced. I'd appreciate someone to check my work.

Let's prove it by contradiction. Suppose that $\exists n \in \mathbb{N}$ such that (1) $m < n$ and (2) $ n < s(m)$.

From the definition of order we have that:

(1) implies that $\exists c \in \mathbb{N} \setminus \{0\}$ such that $m + c = n$.

(2) imples that $\exists c' \in \mathbb{N} \setminus \{0\}$ such that $n + c' = s(m)$.

Therefore $$ \begin{align*} n + c' + c &= s(m) + c\\ &= s(m + c)\\ &= s(n)\\ \end{align*} $$

Since $c' \neq 0$ and $c \neq 0$, we know that $c' + c \neq 0$ and therefore $\exists k \in \mathbb{N}$ such that $s(k) = c' + c$. Hence:

$$ \begin{align*} n + s(k) &= s(n)\\ s(n + k) &= s(n) \rightarrow n + k = n \rightarrow k = 0 \end{align*} $$

Since we've concluded that $k=0$, we have that $s(k) = s(0) = 1 = c + c'$, where follows that $c$ or $c'$ needs to be equals to $0$, and that is a contradiction.

I also have one more question... After defining what a function is, can't we conclude that $s : \mathbb{N} \setminus \{0\} \rightarrow \mathbb{N}$ is actually $s(n) = n + 1$ ?

If so, using that the proof would've been more immediate...

Any kind of comments and critics are highly appreciated! Thank you!


1 Answer 1


Your proof doesn't work as it is, because from "$n+k = n$" you cannot get "$k = 0$" just like that. You need induction in order to prove this cancellation fact. Either that or you just use induction to directly prove the original desired theorem.

  • $\begingroup$ That ancellation fact was previously proved using induction. $\endgroup$
    – Bruno Reis
    Mar 31, 2019 at 12:30
  • $\begingroup$ @BrunoReis: Then that's fine, but you should have stated it, otherwise people like me will guess that you're cancelling without justification. It's a common mistake since many students don't stick strictly to the deductive rules and given axioms. =) $\endgroup$
    – user21820
    Mar 31, 2019 at 15:24

You must log in to answer this question.

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