If $S\subseteq \mathbb{N}:\ N_0\in S $ and $n+1\in S$ whenever $n\in S,$ then $S$ contains all natural numbers s.t. $n\geq N_0$.

Question

If $S\subseteq \mathbb{N}:\ N_0\in S $, for some $N_0\in \mathbb{N}$ and $n+1\in S$ whenever $n\in S,$ then $S$ contains all natural numbers s.t. $n\geq N_0$.

Considering the set $C$ that consists of $S$ together with all natural numbers, less than $N_0$ will be nice, but I can't see how to use this in showing that $S$ contains all natural numbers. Any help or hint will be highly appreciated in this regard.

Thanks a lot!

Answer 1

Let $S \subseteq \mathbb{N}$ and $N_0 \in \mathbb{N}$ satisfy the properties you defines. Now, let $S^\ast = \{n \in \mathbb{N}:\ n < N_0\}$. We show that $T = S \cup S^\ast$ contains all natural numbers by induction:

• Base Case: As $1$ is the least natural number $1 \leq N_0$. So either $1 = N_0 \in S$ or $1 < N_0$ implying $1 \in S^\ast$. Either way, $1 \in T$.
• Inductive Step: Suppose $n \in T$. Then either $n \in S$ or $n \in S^\ast$. If the former is the case, then by a property of $S$ that you defined we get $n + 1 \in S$. Otherwise if $n \in S^\ast$, then $n < N_0$. But, $n + 1$ is least natural number strictly larger than $n$; so we must have $n + 1 \leq N_0$. Then either $n + 1 = N_0 \in S$ or $n + 1 < N_0$ implying $N_0 \in S^\ast$. Either way, $n + 1 \in T$.

So by induction, $T$ contains all natural numbers. Now, we come to the main part: we show using what we established that $S$ contains all natural numbers $n \geq N_0$: Well, certainly $n \in S \cup S^\ast$ as $T$ contains all natural numbers. But, since $n \geq N_0$, we have $n \not< N_0$; so $n \notin S^\ast$. Thus, $n \in S$.