1
$\begingroup$

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 $

$\endgroup$
  • 1
    $\begingroup$ I guess I'm a bit confused on how $n_0$ relates to $k$? It seems to me that you could have $n_0=3, \space k=1$ which would make $A = \{1,2,3 \}$. Then $A$ would have no integers greater than $n_0$ $\endgroup$ – graydad Jan 2 '15 at 21:20
  • $\begingroup$ Very sorry Someone Edited my post and moved the Statement around to make no sense at all i put it back to what it originally said. $\endgroup$ – Faust Jan 2 '15 at 21:34
  • $\begingroup$ Ah okay, no problem. And thanks for clearing up the $k+1$ thing for me. My next question is, why define $D$ in case $1$? Also, what is the hint from the similar problem? $\endgroup$ – graydad Jan 2 '15 at 21:36
  • $\begingroup$ Me defining D in Case 1 just makes it easy to prove that $A_1 \ cup B = $ natural numbers as $A_1 \ cup B $ says with words Exactly the same thing as the Set D $\endgroup$ – Faust Jan 2 '15 at 21:40
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I meant $m-1\geq n_0$ $\endgroup$ – Jorge Fernández Hidalgo Jan 2 '15 at 21:43
  • $\begingroup$ It shows all the elements greater than $n_0$ are in $A$, the proof is by contradiction. You assume it is not true, if you assume this the set I describe in the first paragraph is a non-empty subset of the natural numbers (The key here is that it is not empty because you can apply the well ordering principle, which is equivalent to induction).using the well ordering principle you find the least element and call it $m$, since $m-1$ is smaller than $m$ but greater than or equal to $n_0$ it is in $A$, but if $m-1$ is in $A$ so is $m$. Contradicting that $m$ is not in $A$. $\endgroup$ – Jorge Fernández Hidalgo Jan 2 '15 at 21:48
  • $\begingroup$ I have tried to make things clearer, please read again. $\endgroup$ – Jorge Fernández Hidalgo Jan 2 '15 at 22:16
  • $\begingroup$ Oh! Thank you for taking the time to re-write that I totally follow how it proves it for all values now. $\endgroup$ – Faust Jan 2 '15 at 22:21
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thank you that makes perfect sense. $\endgroup$ – Faust Jan 2 '15 at 21:59
1
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ One of the equivalent ways to rephrase induction is exactly what the OP wants to prove only with $n_0=1$, namely that if a subset $A$ of $\mathbb N$ contains $1$ and it satisfies that if $a\in A$ then $a+1\in A$ then $A=\mathbb N$ $\endgroup$ – Jorge Fernández Hidalgo Jan 2 '15 at 21:44
  • $\begingroup$ That certainly looks like an inductive argument. $\endgroup$ – MuchToLearn Jul 19 '18 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.