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!


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 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 at 15:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.