Problem involving the set of natural number which contain n0

[Seydlitz]

Homework Statement

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

Homework Equations

Proof by induction methods

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

 

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

 

[Seydlitz]

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.

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,...\}$

 

[micromass]

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,...\}$

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.

 

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

 

[LCKurtz]

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,...\}$

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

 

[Seydlitz]

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

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

And so on.

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.

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

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

 

[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".

 

[Seydlitz]

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

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

 

[verty]

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

If φ is a unary predicate such that:

φ(0) is true, and
for every natural number n, if φ(n) is true, then φ(n+1) is true,

then φ(n) is true for every natural number n.

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.

 

[Seydlitz]

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.

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$

 

[LCKurtz]

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\}$$

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

 

[Seydlitz]

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

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?

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.

 

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

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\}$$

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

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?

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.

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

 

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

 

[LCKurtz]

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.

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.

 

[Seydlitz]

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.

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)
https://www.physicsforums.com/showthread.php?t=699717

Here's problem recommendation I asked for the chapter:
https://www.physicsforums.com/showthread.php?t=702527

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

 

[LCKurtz]

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)
https://www.physicsforums.com/showthread.php?t=699717

Here's problem recommendation I asked for the chapter:
https://www.physicsforums.com/showthread.php?t=702527

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

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.

 

[Seydlitz]

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.

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.