Problem involving the set of natural number which contain n0

1. Jul 22, 2013

Seydlitz

1. The problem statement, all variables and given/known data
I'm still not confident enough to answer this.

Prove that if a set $A$ of natural numbers contains $n_{0}$ and contains $k + 1$ whenever it contains $k$, then $A$ contains all natural numbers $> n_{0}$.

2. Relevant equations
Proof by induction methods

3. The attempt at a solution
I'm mirroring the similar method in page.23 of Spivak's calculus book.

Suppose $A$ has $n_{0}$, let B be a set of all $l$ such that, $n_{0}+l$ is in $A$. Then $1$ is in $B$, so does $l+1$ assuming $l$ is in $B$. This show that $B$ is a set of all natural numbers, and it is in fact also contained in $A$. So there exist all natural number which is larger than $n_{0}$.

Practically it should work like this right?

$A=\{1,2,3,4,5,6,7...n\}$
Say $n_{0}$ is = $4$. Then there exist also in $A$ all integers which is larger than $4$.

When I say let B a a set of all $l$ such that, $n_{0}+l$ is in $A$. Then $B$ looks like this. $B=\{1,2,3,4,5,6,7,8..l\}$ so that in $A=\{1...5, 6, 7, 8, 9, 10, 11, 12, 13...n_{0}+l\}$

Though my question is, why we need to create set $B$ in this case, to prove what set $A$ contains. Is it related somehow to set theory, where if you want to show two sets are equal, you have to make show that they are the subset of each other? Can you guys please enlighten me on this point.

(This is like magic, by just writing the opening post, I think I understand better here than few minutes ago...)

2. Jul 23, 2013

LCKurtz

I think the idea here is to show you can start induction at other natural numbers than 1. So you want to relate the set $\{n_0, n_0+1, n_0+2,...\}$ to $\{1,2,3,...\}$. So you want $n_0$ to correspond to $1$. I would try letting$$B = \{n:\text{There is }m\in A\text{ such that }n = m+1-n_0\}$$Now start by showing $1\in B$ because $n_0\in A$, and so on.

3. Jul 23, 2013

Seydlitz

Ok I get the idea of corresponding $1$ in set $B$ to $n_{0}$ in A, though I'm a bit confused with this set definition. $n = m+1-n_0$

Say for example $A=\{2,3,4,5,6,7,8,9,...\}$ with $n_0=2$
Then B should be according to the definition the set $B$ seems to become, $B=\{0, 0, 0,...\}$

Last edited: Jul 23, 2013
4. Jul 23, 2013

micromass

I don't see how you got that.
We have that $1\in B$, because for $m=2$ we have $m\in A$ and $1 = m +1 - n_0 = 2 + 1 - 2$.
We have that $2\in B$, because for $m=3$, we have $m\in A$ and $2 = m+1-n_0$.
We have that $3\in B$, because for $m=4$, we have $m\in A$ and $3 = m+1-n_0$.

And so on.

5. Jul 23, 2013

verty

Being a fan of logic, I suggest the following approach. Run the induction on all the natural numbers but change P(x) so that $\forall x P(x)$ implies the result you want. That is, find a P(x) that works.

I won't help with finding P(x).

Last edited: Jul 23, 2013
6. Jul 23, 2013

LCKurtz

You get the elements of $B$ by taking the elements of $A$, subtracting $n_0$ (which is $2$ in your example) from them, and adding $1$.

7. Jul 23, 2013

Seydlitz

Ok I seems to get it. So this is how the story goes: The question wants us to understand like you said that it's possible to start induction with a number other than 1 right?

So we can imagine having this set $A$ which starts at $n_0$ and which has the property that there exist $k+1$ for every $k$, which means the set continues on forever. But we have to prove this fact if it's really true or not.

To prove it, we use the standard induction principle. That is, we start from 1, and we pair set $A$ with this set $B$, and do induction on $B$. If we manage to show that $B$ is a set of all integers, then consequently, $A$ is also comprised of integers larger than n_0.

What is this P(x) you're referring to, a simple 'function' or just statement?

8. Jul 23, 2013

HallsofIvy

Your original problem was about x being in some set A, so you can take P(x) to the statement "x is in A".

9. Jul 23, 2013

Seydlitz

I'm sorry I don't quite get yet what you, and verty means by this. P(x) is some sort of statement, isn't it? Like for all $x$, $x+1$ is in $A$. In this case the $P(x)$ is "$x+1$ in in $A$".

So just to finish what I've started here's the complete proof:

$$A = \{n_a:\text{There is }k\in \mathbb{N}\text{ such that }n_a = n_0+k\}$$
$$B = \{n_b:\text{There is }m\in A\text{ such that }n_b = m+1-n_0\}$$
$$1 \in B \text{ because } n_0 \in A$$
$$n_b+1 \in B \text{ because } n_0+k \in A$$

So $B$ contains all natural number and $A$ contains all natural number which is larger than $>n_0$.

10. Jul 23, 2013

verty

I can't sleep, so let me respond to this. The induction axiom says this:

What I called P(x), this calls φ(n). And our numbers start from 1, which is fine. The point is, this is how induction works, it proves a property true of all the natural numbers. You just need to find the correct property.

11. Jul 23, 2013

Seydlitz

Ok, is this a correct property then?

If $n_0>k$ then $n_0+1>k+1$, and so inside the set we have all natural numbers larger than $n_0$

12. Jul 24, 2013

LCKurtz

No. You can't start like that because that is essentially what you are trying to prove. What you are given about $A$ is:$$\text {1. There is a natural number }n_0 \in A$$ $$\text {2. If a natural number } x \in A \text{ then }x+1 \in A$$

13. Jul 24, 2013

Seydlitz

Ok I see, is this first statement alright then?
$$A = \{n_a:\text{There is }x\in \mathbb{N}\text{ such that }n_a = x\text{ and } n_0\in A\}$$

By the way, I'd like to know how is my proof and understanding to the question, is this working if the notation is alright?

Last edited: Jul 24, 2013
14. Jul 24, 2013

LCKurtz

No. That isn't alright. You have to start with what I just said: $A$ is a set with the following two properties:$$\text {1. There is a natural number }n_0 \in A$$ $$\text {2. If a natural number } x \in A \text{ then }x+1 \in A$$

Yes, that is the general idea of what you need to do. You show $B$ contains all the natural numbers, then use that to show $A$ contains all the natural numbers greater than or equal to $n_0$.

15. Jul 25, 2013

Seydlitz

Ok I'll try again.

$$B = \{n_b:\text{There is }m\in A\text{ such that }n_b = m+1-n_0\}$$
$$1 \in B \text{ because } n_0 \in A$$
$$n_b+1 \in B \text{ because } m+1 \in A$$
We assume there is $l$ in $B$ and $m$ in $A$, and that
$$l+1 \in B \text { because } m+1 \in A$$

This suggest $B$ is comprised of all natural number.
And we can conclude set $A$ contains all natural number $\geq n_0.$

Hopefully this is convincing enough.

16. Jul 25, 2013

LCKurtz

It convinces me that you have the general idea. But it is not a properly written argument. Is this a problem for which you want to hand in a proof in a class? I don't know how to help you learn how to write the argument without literally showing you how. If it isn't homework you are going to hand in I could do that, otherwise I'm afraid you will have to let your teacher correct your argument.

17. Jul 25, 2013

Seydlitz

It's not an homework assignment as I've currently not in any school. I've just graduated from high-school several months ago and I'll be starting my university next year. These are my previous threads I make before showing I intended to learn proof. (I've to add that most of my threads in PF are dedicated to beginner proofing question)

Here's problem recommendation I asked for the chapter:

I don't know what else to add to convince you further, and I won't insist either if you are not convinced.

Last edited: Jul 25, 2013
18. Jul 25, 2013

LCKurtz

OK, thanks for that information. One problem with these forums is we often don't know whether we are communicating with a student taking a university advanced calculus course or someone like yourself. I think it will be pretty difficult to learn how to write up a proof before you actually take such a course with a teacher. Anyway, for what it's worth, I will show you how I would expect a proper proof of that problem to look.

Problem: Given a set $A$ of natural numbers with the properties$$\text {1. There is a natural number }n_0 \in A$$ $$\text {2. If a natural number } x \in A \text{ then }x+1 \in A$$show that $A$ contains all natural numbers greater than or equal $n_0$.

Proof: Let $B=\{n-n_0+1: n\in A\}$. Since $n_0\in A$ then $n_0-n_0+1 = 1\in B$.

Now suppose a natural number $m\in B$. Then there exists $n\in A$ such that $m= n -n_0 + 1$. By the property 2 of $A$ we know $n+1 \in A$. Therefore $(n+1)-n_0 + 1 = m+1\in B$. At this point we have shown $1\in B$ and if $m\in B$ then $m+1 \in B$. Therefore, by the induction property, $B = \mathbb{N}$.

It remains to show that if $n\ge n_0$ then $n \in A$. If $n \ge n_0$ then $n-n_0 + 1 \ge 1$, so $n-n_0 + 1 \in B$. Therefore $n\in A$ by the definition of $B$. This shows that $\{n:n\ge n_0\}\subset A$.

The point is that statements that seem obvious need to be carefully shown in a proof. You don't just declare that they are true. Hopefully, this is of some help to you.

19. Jul 25, 2013

Seydlitz

Thank you for your understanding. I just want to self-study at this free time so that later on I can understand the material better. I'm just quite worried, that at large universities I'll hopefully be attending, it'll be difficult to have some sort of one-on-one time with the instructors or teachers, and in that case I might need to study myself.

I'm relieved to see I don't go too ashtray with my proof, yours is certainly very rigorous, and does include something which I assume is obvious, and that you will know it anyway without me saying it. I take it that isn't true with doing proof. I think I don't have the experience yet to decide which are important, and how to best organize the statements, and then chaining it to the definition to achieve the desired conclusion. Like I never think the need to show that n is really $n \geq n_0$ in details.