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

Answer 6

Firstly, recall that $$ m \leq n \stackrel{\text{df}}{\iff} (m,n \in \textbf{N}) ~ \text{and} ~ (\exists k \in \textbf{N})(n = m + k) $$ and $$ m < n \stackrel{\text{df}}{\iff} (m \leq n) ~ \text{and} ~ (m \neq n). $$ It is easy to prove that $ \leq $ is a reflexive and transitive relation on $ \textbf{N} $. To establish its anti-symmetry, we need a lemma.

Lemma. If $ n \in \textbf{N} \setminus \{ 0 \} $, then there exists an $ m \in \textbf{N} $ such that $ n = m + 1 $.

Proof. Let $$ A = \{ n : \textbf{N} \mid (n = 0) ~ \text{or} ~ (\exists m \in \textbf{N})(n = m + 1) \}. $$ Clearly, $ 0 \in A $, and if $ n \in A $, then $ n + 1 \in A $ also, because there exists an $ m \in \textbf{N} $ such that $ n + 1 = m + 1 $. Therefore, by the Principle of Induction, $ A = \textbf{N} $, which yields the lemma. $ \qquad \square $

Theorem. $ \leq $ is an anti-symmetric relation on $ \textbf{N} $.

Proof. Let $ m,n \in \textbf{N} $, and suppose that $ m \leq n $ and $ n \leq m $. Then there exist $ k,l \in \textbf{N} $ such that $$ n = m + k \qquad \text{and} \qquad m = n + l. $$ Consequently, $$ n = m + k = (n + l) + k = n + (l + k). $$ By the Cancellation Law for $ + $, we find that $ l + k = 0 $. If $ k = 0 $, then $ l = l + k = 0 $. If $ k \neq 0 $, then the lemma says that there exists a $ j \in \textbf{N} $ such that $ k = j + 1 $, so $$ 0 = l + k = l + (j + 1) = (l + j) + 1. $$ This is a contradiction because $ 0 $ is not a successor. Therefore, $ k = 0 = l $, which yields $ m = n $. $ \qquad \square $

Proposition. Let $ m \in \textbf{N} $. Then there does not exist an $ n \in \textbf{N} $ such that $ m < n < m + 1 $.

Proof. Assume the contrary, i.e., there exists an $ n \in \textbf{N} $ such that $ m < n < m + 1 $. Then there exists a $ k \in \textbf{N} $ such that $ n = m + k $. As $ m \neq n $, we have $ k \neq 0 $. By the lemma, there exists a $ j \in \textbf{N} $ such that $ k = j + 1 $, so $$ m + 1 \leq (m + 1) + j = m + (1 + j) = m + (j + 1) = m + k = n. $$ We thus have $ n < m + 1 \leq n $. As $ \leq $ is an anti-symmetric relation on $ \textbf{N} $, we obtain $ n = m + 1 $, contradicting $ n < m + 1 $. $ \qquad \square $