[Math] Proof that between two natural numbers there is no natural number

induction

I have to prove that between two natural numbers $n$ and $n+1$ there does not exist a natural number by using induction. Any hints? Edit: What would the best way to define $s(n)$?

Best Answer

I don't know what axioms you are working with (e.g. Peano axioms?), or what other results (lemma's) you are allowed to work with, but let's assume you use $s(x)$ for $x + 1$, and assume you have all of the following (either as an axiom, or as a Lemma):

  1. Nothing is smaller than $0$

  2. $0$ is the only number smaller than $s(0)$

  3. Any non-zero number is the successor of some number

  4. If $s(x) < s(y)$, then $x < y$

Then you should be able to prove your desired result using induction. Try that. If you still can't figure it out, let me know.

Edit:

... just noticed your edit about how to define $s(x)$ ... and I also realize that my second lemma above is of course just the base case for your inductive proof, so you're probably thinking "but that is what I need to prove! So I can't assume that. So how do I prove it?"

OK, the standard Peano Axioms (that basically define $s(x)$) are:

  1. $\forall x \: \neg s(x)=0 $

  2. $\forall x \forall y \: s(x) = s(y) \rightarrow x = y$

  3. $\forall x \: x + 0 = x$

  4. $\forall x \forall y \: x + s(y) = s(x + y)$

You can define $x < y$ by adding as a definitional axiom $\forall x \forall y \: (x < y \leftrightarrow \exists z \: y = x + s(z))$

And the inductive scheme says that if $P(0)$ and $\forall x \: P(x) \rightarrow P(s(x))$ then $\forall x \: P(x)$

From these axioms and inductive scheme, you can prove all of the 4 lemma's above, and using that (and induction again), you can prove your desired result.

Related Question