Prove that if a set A of natural numbers contains $n_0$ and whenever A contains k it also contains k+1.

Question

Prove that if a set A of natural numbers contains $n_0$ and that whenever A contains k it also contains k+1.

Prove that A contains all natural numbers $ \geq n_0 $

This is rather similar to a question already on this site but its not quite the same and the only answer to that question is incomplete.

So if someone could tell me if this proof is OK i would appreciate it.

I could not for the life of me figure out how to turn this into an induction proof i think it may be possible to use strong induction on how i set this up to prove it or prove it by induction in a different way but i couldn't figure it out for the life of me even with the hint from the similar problem.

Case 1) In Case 1 set A=D but in D we shall define $n_0 =1 $

Now since $ 1 \in D $ and k+1 is $\in D$ we know that $D= \mathbb{N}$

technically this is the only part of the proof that relies on induction and i couldn't even figure out how to prove that since $ 1 \in D$ that $ D= \mathbb{N}$

Case2) now we know that $n_0 > 1$ so i will define a set $A_1$ such that $ a\in A_1 \forall a \in A$ such that $a \geq n_0$ and a set B where $ 1\in B$ and $(k+1) \in B$ whenever $(k+1) < n_0$

Since $ A_1 \cup B = D $ Where D is the set from Case 1 and that this is true $\forall n_0 \in \mathbb{N} $ thus we know that $A_1 = \mathbb{N} - B$ Which by definition defines $A_1$ as the set of natural numbers $ \geq n_0$ lastly since $ A_1 \subset A$ ( as A could contain numbers smaller than $n_0$ ) We know that A contains all natural numbers $ \geq n_0 $

Answer 1

Suppose that not every element larger than $n_0$ is in $A$, consider the set of numbers larger than $n_0$ that do not belong to $A$ and call this set $B$,this set is not empty, apply the well ordering principle to find the least element of this set, call it $m$.

Since $m>n_0$ we conclude $m-1\geq n_0$ since $m$ was the minimum element of $B$ we conclude $m$ is not in $B$, combining this with $m-1\geq n_0$ we obtain that $m-1\in A$. since $m-1$ is in $A$ we arrive at the conclusion that $m$ is in $A$, a contradiction because if $m$ is in $A$ $m$ is not in $B$, but $m$ is the minimum element in $B$, so $m$ is in $B$.

The contradiction comes from assuming there is an element larger than $n_0$ that is not in $A$ (which is the same as saying $B$ is not empty.)

Answer 2

I don't think you need induction at all for this. Let $A$ be a set of natural numbers such that $n_0 \in A$ and for all $k \in A$ then $k+1 \in A$. By assumption, $n_0+1 \in A$, which means $n_0+2 \in A$ which means $\dots$ Hence $A$ contains all natural numbers greater than or equal to $n_0$.

Answer 3

Your proof seems circular. You conclude in case 1 that $D=N$, however, that seems to require the statement you are trying to prove.

Different way: Let $B=\{ n \in N \mid n\geq n_0 and n\notin A \}$. Now suppose that the statement is not true. Then, since $B$ is a subset of $N$, $B$ must contain a smallest element, $x$, which by definition is not in $A$. $x\neq n_0$, since $n_0\in A$. Since $x-1$ is smaller than $x$, it must not be in $B$ and therefore it must be in $A$. However, by definition, this implies that $(x-1)+1=x$ belongs to $A$. Contradiction

This means that $B=\emptyset$ and therefore that $A$ contains all natural $n$ for which $n\geq n_0$.