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 $
Best Answer
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.)