What is the point of induction?

[The Student]

No, {k,1} does NOT contain k+1!

Because S contains k= 1, it must contain k+1= 2.
Because S contains k= 2, it must contain k+1= 3.
Because S contains k= 3, it must contain k+1= 4.
etc.

Ohhhhhhh, I think I got it!!!, so, can k be any element in S that we choose? This whole time I thought that we couldn't pick what k could be, and that any k should work. Am I on the right track?

 

[HallsofIvy]

Well, the general direction! You have to prove that "if the statement is true for some number k, then it is true for k+1".

 

[The Student]

Well, the general direction! You have to prove that "if the statement is true for some number k, then it is true for k+1".

Am I right by saying that the only element that we can use for k is 1?

 

[tkhunny]

Ohhhhhhh, I think I got it!!!, so, can k be any element in S that we choose? This whole time I thought that we couldn't pick what k could be, and that any k should work. Am I on the right track?

Am I right by saying that the only element that we can use for k is 1?

Still no. You do not get to pick. "k" represents an arbitrary element known to be in S. So far, we have one example, but we don't care about that for the moment.

1) Suppose we happen to find an element in S. Call it "k". That's the point of calling it "k". It represents an arbitrary element, not a specific element you have chosen.
2) Having found "k", prove that "k+1" must also be in S.

Our goal is to prove something for ALL elements of an INFINITE set. It does not matter how many examples you find. That is not good enough.

 

[The Student]

Still no. You do not get to pick. "k" represents an arbitrary element known to be in S. So far, we have one example, but we don't care about that for the moment.

1) Suppose we happen to find an element in S. Call it "k". That's the point of calling it "k". It represents an arbitrary element, not a specific element you have chosen.
2) Having found "k", prove that "k+1" must also be in S.

Our goal is to prove something for ALL elements of an INFINITE set. It does not matter how many examples you find. That is not good enough.

What if instead of N we use M where M={1,2,3,4,5,6}

Then can I say:

If a subset S ⊂ M satisfies
(i) 1∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then S = M.

And now can I prove it this way?:

if k=1, then k+1=2 so now we know 2 is an element of S and
if k=1, then k+2=3 so now we know 3 is an element of S and
if k=1, then k+3=4 so now we know 4 is an element of S and
if k=1, then k+4=5 so now we know 5 is an element of S and
if k=1, then k+5=6 so now we know 6 is an element of S which completes the set of M.

So, can't we have always use 1 as an element of k?

 

[The Student]

No, {k,1} does NOT contain k+1!

Because S contains k= 1, it must contain k+1= 2.
Because S contains k= 2, it must contain k+1= 3.
Because S contains k= 3, it must contain k+1= 4.
etc.

Why does k need to keep changing? I don't understand how k+1=2 can then mean that k=2?

 

[The Student]

I think so, but I am not sure. Your sentence itself makes no sense as written.

S is a set of natural numbers or integers greater than or equal to the integer m. Each member of S has the additional property of P.

How do you know that S is not empty?

You do not initially. In the natural number case, you must FIRST PROVE that 1 has property P, which means that 1 is a member of S and S is not empty. In the integers greater than or equal to m case, you must FIRST PROVE that that m has property, which means that m is a member of S and S is not empty.

So am I correct by saying that we must prove 1 is a natural number, and by doing so we will know that 1 is an element of S?

Now consider ANY number k that is in S. That means that k has property P because it is in S. Furthermore, k is greater than or equal to 1 in the natural number case (because there is no natural number smaller than 1) or k is greater than or equal to m in the integer case (because S contains only integers greater than or equal to m).

How do you know that there is any such number k? Because you proved there was in step 1.

Where did we prove that k is a number?

Using only the facts that k has property P and that k is greater than or equal to 1 (or m), prove that (k + 1) has property P. If it does, then obviously (k + 1) is also in S. But then k + 2 is in S as is k + 3 so k + 4 is in S, etc.

But HollsofIvy a few posts earlier said that the k is what changes. Is he/she wrong?

The power of the proof by induction is that in two steps we prove something for an infinite number of cases.

Consider the proposition that all natural numbers are odd. We can prove that it is true for 1. But we cannot prove that it is true that the next higher number from an odd number is also odd. A proof by induction will not work for just any random property.

\(\displaystyle Let\ S\ be\ the\ set\ of\ all\ natural\ numbers\ n\ such\ that\ n \le n^2\)

\(\displaystyle 1 \le 1 = 1^2 \longrightarrow if\ n = 1, n \le n^2\).

So S is not empty and 1 belongs to S. Thus there is at least one natural number that belongs to S and that number is certainly greater than or equal to 1.

\(\displaystyle Let\ k\ be\ ANY\ element\ of S\)

\(\displaystyle So\ k\ is\ a\ natural\ number\ \ge 1\ and\ k \le k^2\)

We have not said anything about k + 1. We have certainly not assumed that (k + 1) is a member of S because k is.

\(\displaystyle (k + 1)^2 = k^2 + 2k + 1\)

\(\displaystyle 1 \le k \longrightarrow 2 \le 2k \longrightarrow 3 \le 2k + 1\ because\ k \in S\)

\(\displaystyle k \le k^2\ because\ k \in S\)

\(\displaystyle So\ k + 3 \le k^2 + 2k + 1\)

\(\displaystyle But\ k + 1 < k + 3\)

\(\displaystyle So\ k + 1 \le k^2 + 2k + 1\)

\(\displaystyle Or\ k + 1 \le (k + 1)^2\)

\(\displaystyle So\ S = the\ set\ of\ natural\ numbers\)

\(\displaystyle THUS, n \le n^2\ for\ every\ n\ that\ is\ a\ natural\ number\)

 

[tkhunny]

What if instead of N we use M where M={1,2,3,4,5,6}

Then can I say:

If a subset S ⊂ Msatisfies
(i) 1∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then S = M.

And now can I prove it this way?:

if k=1, then k+1=2 so now we know 2 is an element of S and
if k=1, then k+2=3 so now we know 3 is an element of S and
if k=1, then k+3=4 so now we know 4 is an element of S and
if k=1, then k+4=5 so now we know 5 is an element of S and
if k=1, then k+5=6 so now we know 6 is an element of S which completes the set of M.

So, can't we have always use 1 as an element of k?

Still no. Stop picking finite sets. You CANNOT prove with your finite set that if k is in S, then k+1 is in S, since it simply is not the case for k = 6. You thought you solved this problem by stating that the set was complete, but that is just smoke and mirrors.

Also, see what you attempted to do? You made each statement begin with k = 1. This is no good. Each possible value for 'k' must lead to the next successive value.

'k' is arbitrary. You MUST NOT pick it. It must work for ALL elements of S. If you show it for some finite set, you have done nothing. If you sit down and demonstrate it for the first 3 billion natural numbers, you still have only a finite set and the last will fail. 'k', being arbitrary, must represent EACH element in the infinite set.

 

[mmm4444bot]

Click HERE for additional examples and lessons on mathematical induction. (The third link has a simple example.)

Cheers ~ Mark :cool:

 

[The Student]

We do not have to prove that 1 is a natural number. We have to prove that 1 has the property P that we are asserting is true of every natural number. Because 1 is a natural number AND we have proved that 1 has property P, we have proved that 1 belongs to S.

The proposition that we are asserting is one that pertains to numbers. It does not pertain to colors. Dogginess is not less than or equal to the square of dogginess because squaring is a property of numbers. Remember that PKA told you that S is a subset of N (and I said that S is a subset of I). Dogs, flowers, angels, rocks, etc are not members of S. Just numbers of some defined type.

What we did prove is that S actually contains numbers and is not empty.

I hesitate to correct what Halls of Ivy said because he obviously knows much more math than I do but what he meant was this.

We PROVE that WHATEVER k we choose, k + 1 is in S. Obviously if k is a whole number or an integer, k + 1 is also a whole number or an integer. Where the meat of the proof lies is in showing that property P is true of k + 1 if it is true of k.

Now we could have chosen k as 1 (or m in my more general formulation) and if we had, 2 is ONE UP from 1 so 2 has property P.

So we could just as well have chosen 2 for k, and if we had 3 is ONE UP from 2 so 3 has property P.

But that means we could just as well have chosen 3 for k, and if we had 4 is ONE UP from 3 and so 4 has property 4. This goes on forever. No matter what k we choose there is another number one greater that is also in S and that we could have chosen.

So, is the whole point of mathematical induction to show that any set of natural numbers that one can pick out a variable from and add 1 to, tells us that the set must be all natural numbers?

 

[tkhunny]

Still no. This technique is not restricted to the Natural Numbers. Also, if your set is the Natural Numbers, you cannot pick a "variable" out of it. There are no variables in the set of natural numbers. Take a little more time to contemplate the meaning of "arbitrary". You REALLY wan't to pick one so that you can make a specific calculation. Stop it. By being "arbitrary", you are, in essence, picking ALL elements in your set simultaneously. The point of mathematical induction is to prove infinitely many premises in one single act.

If the elements in your infinite set can be described sequentially, this technique may be helpful in proving that some premise is true for all elements of the infinite set.

In the amazing rhetoric just observed, we started at 1 and moved one at a time, k ==> k+1. Indeed, this might be a proof for all natural numbers (Note: Some definitions include "0" with the Natural Numbers).

What if we start at 2 and move two at a time? k ==> k + 2? This might be a proof for all even natural numbers.

What if we start at sqrt(3) and prove sqrt(k) ==> sqrt(k+1)? This might be a proof for all primary square roots of natural numbers greater then 2.

"k", as it has been used, may not be a number at all. It could be just a sequence index of the elements of your infinite set.

Evaluation: You are holding on to finite, concrete thinking far too much. Let it go. At this point in your studies, you should be starting to think about the infinite and the abstract. Well, right after Sports Center, anyway.

 

[The Student]

If the elements in your infinite set can be described sequentially, this technique may be helpful in proving that some premise is true for all elements of the infinite set.

In the amazing rhetoric just observed, we started at 1 and moved one at a time, k ==> k+1. Indeed, this might be a proof for all natural numbers (Note: Some definitions include "0" with the Natural Numbers).

What if we start at 2 and move two at a time? k ==> k + 2? This might be a proof for all even natural numbers.

What if we start at sqrt(3) and prove sqrt(k) ==> sqrt(k+1)? This might be a proof for all primary square roots of natural numbers greater then 2.

Why do you say "might be"? Can't induction prove the propositions that you had wrote right above this sentence?

"k", as it has been used, may not be a number at all. It could be just a sequence index of the elements of your infinite set.

Evaluation: You are holding on to finite, concrete thinking far too much. Let it go. At this point in your studies, you should be starting to think about the infinite and the abstract.

 

[The Student]

No.

Let's forget the complication of sets of integers, which I brought up, and stick with proofs of induction for propositions concerning all the natural numbers.

The set of all natural numbers with the property that each exceeds 3 and is exceeded by 6 is {4, 5}. It contains only natural numbers, and it is possible to add 1 to each of them, but the number 5 + 1 = 6 is not in the set {4, 5}. And the set {4, 5} is not the set of all natural numbers.

The set of all natural numbers that are evenly divisible by 2 contains only natural numbers, and it is possible to add 1 to each of them, resulting in odd numbers, but the odd numbers are not in the set of even numbers. So the set of all even natural numbers is not the set of all natural numbers even though it is an infinite set containing only natural numbers.

In inductive proofs you are concerned with some property P that you want to prove is true of every natural number.

The set S that you are concerned with is initially defined as the set of all natural numbers with that property, not the set of all natural numbers. At the start, you have not proved that any natural number has property P. The set S could be empty, or finite, or infinite but not include all natural numbers.

So the first step in the proof is to prove that 1 has that property. That does two things. It shows that the set is not empty and that 1 is in the set.

The second step is to prove that, for any number k whatsoever in the set, k + 1 is in the set. (You know from the first step that the set S is not empty.) Of course k + 1 exists and is part of the set of natural numbers, but just being a natural number does not make k + 1 a member of set S. What do we know about k and k + 1? They are both natural numbers and so have all the properties previously proven to belong to all natural numbers, including the property that a natural number is is equal to or greater than 1. Furthermore, because k belongs to set S, it has property P. Now using that information about k and k + 1, prove that k + 1 also has property P and so is a member of the set S. In terms of the proof, nothing is demonstrated by adding 1 to k. We know you can add 1 to k, and that k + 1 is a natural number. You have to prove that k + 1 has property P.

If you prove that k + 1 has property P, then you can say that set S is identical to the set of natural numbers and P is a property of every natural number. I have given now two examples of how to do such a proof. mmm gave you a link that shows examples. The examples are not as simple as just adding 1 to k and saying it equals k + 1. At least my examples were in fact extremely simple ones.

I have not once heard you mention anything in your questions about the property P that defines the members of set S. Set S is not initially defined as the set of natural numbers. Set S is initially defined as the set of natural numbers that have property P. You are defining sets without reference to any defining property and so wandering in a fog. This whole induction process works only for properties that apply to all natural numbers.

I shall give you one more example and then I am going to bed.

PROVE: \(\displaystyle \displaystyle \left(\sum_{i = 1}^ni\right) = \dfrac{n(n + 1)}{2}\ for\ every\ natural\ number\ n.\)

\(\displaystyle Let\ S\ be\ the\ set\ of\ all\ natural\ numbers\ n\ such\ that\ \displaystyle \left(\sum_{i = 1}^ni\right) = \dfrac{n(n + 1)}{2}.\)

\(\displaystyle \displaystyle \left(\sum_{i=1}^1i\right) = 1 = \dfrac{2}{2} = \dfrac{1(1 + 1)}{2}.\)

\(\displaystyle So\ 1 \in S.\)

\(\displaystyle Consider\ an\ arbitrary\ number\ k \in S.\)

\(\displaystyle So\ \displaystyle \left(\sum_{i = 1}^ki\right) = \dfrac{k(k + 1)}{2}\).

\(\displaystyle \displaystyle \left(\sum_{i = 1}^{k+1}i\right) = \left(\sum_{i=1}^ki\right) + (k + 1) =\)

\(\displaystyle \dfrac{k(k + 1)}{2} + (k + 1) = \dfrac{k^2 + k}{2} + \dfrac{2k + 2}{2} = \dfrac{k^2 + 3k + 2}{2} = \dfrac{(k + 1)(k + 2)}{2} =\dfrac{(k + 1)[(k + 1) + 1]}{2}.\)

\(\displaystyle So\ k + 1 \in S.\)

\(\displaystyle So\ S\ is\ the\ set\ of\ all\ natural\ numbers.\)

\(\displaystyle THUS, \displaystyle \left(\sum_{i = 1}^ni\right) = \dfrac{n(n + 1)}{2}\ for\ every\ natural\ number\ n.\)

Edit: I just saw tkhunny's latest post. He is of course right that you can use induction for propositions that are not directly about natural numbers. I had mentioned earlier and given an example of a proposition that did not apply to all natural numbers. In my post above, I am not contradicting tkhunny. I was limiting myself to the case of propositions about all natural numbers. If you cannot grasp the concept of mathematical induction for propositions about the natural numbers, you are not going to grasp it for propositions that vary somewhat from that fundamental pattern.

So is k+1 in all natural numbers actually a given from the start? I thought we would have to prove that.

 

[The Student]

Still no. Stop picking finite sets. You CANNOT prove with your finite set that if k is in S, then k+1 is in S, since it simply is not the case for k = 6. You thought you solved this problem by stating that the set was complete, but that is just smoke and mirrors.

Also, see what you attempted to do? You made each statement begin with k = 1. This is no good. Each possible value for 'k' must lead to the next successive value.

'k' is arbitrary. You MUST NOT pick it. It must work for ALL elements of S. If you show it for some finite set, you have done nothing. If you sit down and demonstrate it for the first 3 billion natural numbers, you still have only a finite set and the last will fail. 'k', being arbitrary, must represent EACH element in the infinite set.

The reason I keep trying subsets of N is because my professor gave us this for our notes:

If a subset S ⊂ N satisfies
(i) 1 ∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then S = N.

So why does he start off by saying "subset" if it can only be an identical set?

 

[Deleted member 4993]

The reason I keep trying subsets of N is because my professor gave us this for our notes:

If a subset S ⊂ N satisfies
(i) 1 ∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then S = N.

So why does he start off by saying "subset" if it can only be an identical set?

Where did that restriction come from?

 

[The Student]

Where did that restriction come from?

Because if I put it this way:

If the subset S = {1,2,3,4,} of N (which still means S ⊂ N)
(i) 1∈ S,
(ii) k ∈ S ⇒ k + 1 ∈ S,
then S = N.

But this doesn't work because if k=4 then k+1 can't be an element of S.

So, I am starting to think that there is a basic symbol that I have a falseunderstanding about.

 

[pka]

So, I am starting to think that there is a basic symbol that I have a false understanding about.

Do you understand that every set is a subset of itself?

 

[The Student]

Do you understand that every set is a subset of itself?

Yes, but why wouldn't he have just called it an identical set if that is all it can be?

 

[The Student]

In terms of the formal logic and limiting ourselves to the natural numbers, we are dealing with TWO DIFFERENT sets, S and N, with N being the set of natural numbers.

Let's define the set of natural numbers N as {1, 2, 3 ....}.

\(\displaystyle For\ every\ k \in N, (k + 1) \in N.\). There is no need to prove that. It is part of the definition of natural numbers.

S is defined as follows:

\(\displaystyle Every\ member\ of\ S\ is\ a\ natural\ number\ with\ property\ P.\)

There is nothing in that definition that implies that S = N. There is nothing in that definition that says S has any members and so is not the empty set. If the defining property is "being less than 0," no natural number has that property and so no natural number is a member of S, which is in fact the empty set. If the property is being more than 2 but less than 6, then S = {3, 4, 5} and is finite and definitely not equal to N. Notice that 5 is in S but that 5 + 1 is not in S. If the property is "being evenly divisible by 3," then S = {3, 6, 9 ....}, which is an infinite set but S is not equal to N because there are many members of N that are not elements of S. In fact, if k is a member of S when being evenly divisible by 3 is the defining property, (k + 1) is not a member of S for any k in S. (k + 1) is NOT necessarily in S although it is necessarily in N.

This whole thing will make no sense from a set theory perspective unless you realize that S and N are different sets, that S is not NECESSARILY equal to N, and that consequently (k + 1) is not NECESSARILY a member of S although it is necessarily a member of N.

We have Peano's axiom (which, as PKA points out, can be shown to be a theorem from some more primitive axiom) saying:

\(\displaystyle IF\ (a)\ S\ is\ a\ subset\ of\ N, (b)\ 1 \in S, and\ (c)\ for\ any\ k \in S, (k + 1) \in S,\ THEN\ S = N\).

Notice that this axiom/theorem does not say that (k + 1) is a member of S. It is a conditional statement that says what happens when (k + 1) is a member of S, but makes no assertion that the condition is true.

Is there anything up to here that is unclear?

Yes, I really do think I understand everything up until here this time.

OK we seek to prove that P is true for all natural numbers. That is the same as PROVING that S = N. Do you see why?

Yes, I think it's because if we prove that 1 is a natural number with property P, and we already showed that if 1 is an element of S, and if k=1, then 1+1=2. So 2 also is now known to be an element of S. Then, if this is all true, then we now know that 2 is an element of S and that k is an element of S, then k can equal 2 and then we can show 2+1=3, and now 3 is known to be an element of S, etc.

One way to prove that S = N is with Peano.

PROVE that 1 has property P.

Would we do this by writing 1=1 which is the reflexive axiom of Peano?

Then PROVE that (k + 1) has property P starting from an ARBITRARY k in S. As tkhunny, this cannot be a calculation involving any specific number. It must be a general proof. You can use in your proof the facts that k and (k + 1) are both natural numbers and that k is a member of S and SO HAS PROPERTY P.

What would a proof look like to show that k and (k+1) are both natural numbers without choosing a number for k?

Once you have shown that (k + 1) is a natural number with property P, then (k + 1) is a member of S by the definition of S. But that means the conditions of the Peano postulate apply, so S = N. And that means every member of N has property P. In other words, every natural number has property P.

I have tried to avoid any appeal to intuitive understanding. Just try to think this through as a matter of logic on the assumption that the Peano postulate is true. Giving an intuitive justification for the Peano postulate is a different question.

Edit: You will notice that as I have defined S it is necessarily a subset of N.

 

[tkhunny]

Why do you say "might be"? Can't induction prove the propositions that you had wrote right above this sentence?

The fact that I gave you two examples explaining this, and this is all you question, is not encouraging.

Why are you in this class, anyway?