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

Question

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

I don't know where I could go with an induction argument. I was thinking of proving that if $s\in (n,n+1)$, where $s$ is a natural number, then $s-n$ is a natural number which lies in $(0,1)$, which is impossible as all natural numbers are bounded below by $1$.

However, this assumes that natural numbers are closed under addition. Also, this does not use induction.

Any pointers for this question?

Answer 1

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

Answer 2

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.

Answer 3

Am I missing actual puzzle in the question when I say the following: First step in induction is to show that it holds for $n_{0}$ and in this case it is obvious that it hold for $n_{1}=1$ the second step is to assume the hypothesis at hand holds for $n_{k}$ and the last step is to use second step to show it must hold for $n_{k+1}$. So assume it does not hold for $k+1$ then there exists a natural number $s\in(k+1,k+2) $ then this gives the desired contradiction since $s-1\in(k,k+1) $ means $n_{k}$ does not hold. Then $(0,1)$ does not contain any natural number can be stated separately.

Hope i am not stealing anybody's time by missing the point.

Answer 4

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

Answer 5

You must know the following:

$\mathbb{Z}$ is a "well-ordered" ordered ring. Here, well-ordered means that every non-empty subset bounded by below has minimum.

Whatever definition you are using, you must fall in the above fact.

From that, we prove the following:

Proposition: There is no natural number $x$ such that $0 < x <1$.

Proof: Take the set $A:=\{n \in \mathbb{Z} \mid 0< n<1\}$. Supposing it is not empty, we would have a bounded by below non-empty subset. Therefore, it has a minimum $m$. But $0 < m² <m<1$, a contradiction with the fact that $m$ is the minimum of $A$.

The induction is as others (and also you) pointed out.

I could avoid talking about integers, and stay on $\mathbb{N}$. But the notation for concisely saying the properties that $\mathbb{N}$ should satisfy as an algebraic structure would be too cumbersome, I think. (Maybe not... defining something such as an "ordered monoid" but with two operations etc etc.)