Use an induction argument to prove that for any natural number $n$, the interval $(n,n+1)$ does not contain any natural number.

1. Every natural number except $0$ is the successor of a natural number. The proof is by induction: the statement is vacuously true for $0$; and if it holds for $n$, it holds for $n+1$.

2. Every natural number is $\ge 0$. Again, by induction: true for $0$, and if $n\ge 0$, then $n+1\ge 0+1 > 0$.

Now suppose $q$ is a natural number strictly between $0$ and $1$. Since $q$ is not zero, it is the successor of some natural number $q'$ (by 1.) that is $\ge 0$ (by 2.). But $q'\ge 0$ implies that $q=q'+1\ge 0+1=1$, which contradicts the assumption that $q<1$. Therefore there is no natural number between $0$ and $1$.

Finally,

3. For any natural number $n$, there is no natural number between $n$ and $n+1$. We've just proven the base case ($n=0$). And if there were a natural number $q$ between $n+1$ and $n+2$, then it would be the successor of some $q'$ (by 1.), and that $q'$ would have to lie between $n$ and $n+1$, because if $q'\le n$ then $q=q'+1\le n+1$, and if $q'\ge n+1$ then $q=q'+1\ge n+2$. Therefore, if the statement holds for $n$, it holds for $n+1$.

Hint:

If there is no $a\in \mathbb{N}$ in $(n,n+1)$ then consider $(n+1, n+2)$. If there where a natural number, $b$, in $(n+1, n+2)$ there would be a natural number in $(n,n+1)$ since $b-1$ is also a natural number, but this is false by hypothesis.

Assumptions $(\forall n \in \mathbb N)(\exists k \in \mathbb N)$:

• (1) $k \ne n $
• (2) $k \ne n+1 $
• (3) $\exists y \in \mathbb N ~:~ n + y = k $
• (4) $\exists z \in \mathbb N ~:~ k + z = n + 1 $

Some lemmas to borrow (would have to be inductively established using peano axioms and definition of $+$):

• (5) Addition is commutative/associative
• (6) Addition is injective : $a + x = b + x \implies a = b$
• (7) Every natural number is either $0$ or it has a natural number predecessor
• (8) Zero has no predecessor

Your task is to prove that the above is inconsistent.

Starting with (3) and (4):

$$(\exists y \in \mathbb N ~:~ n + y = k )\land (\exists z \in \mathbb N ~:~ k + z = n + 1 )$$ $$(\exists y \in \mathbb N ~:~ n + y + 1 = k + 1) \land (\exists z \in \mathbb N ~:~ k + z = n + 1 )$$

Apply (5)

$$(\exists y \in \mathbb N ~:~ n + 1 + y = k + 1) \land (\exists z \in \mathbb N ~:~ k + z = n + 1 )$$ $$\exists y,z \in \mathbb N ~:~ (n + 1 + y = k + 1 \land k + z = n + 1 )$$ $$\exists y,z \in \mathbb N ~:~ (k + z + y = k + 1)$$

Apply (5)

$$\exists y,z \in \mathbb N ~:~ (z + y + k = 1 + k)$$

Apply (6)

$$\exists y,z \in \mathbb N ~:~ (z + y = 1)$$

Now the problem is reduced to establishing that (over natural numbers) $z + y = 1 \implies z = 0 \lor y = 0$ . Assume for the sake of contradiction that $z \ne 0$ and $y \ne 0$, then by (7)

$$p(z) + 1 + p(y) + 1 = 1$$ $$p(z) + p(y) + 1 = 0$$

Which contradicts (8). So $z = 0$ or $y = 0$. However the first contradictions (2) and the second contradicts (1).