Is my summary of induction accurate?

[The Student]

Here is what my notes show:

1) If a subset S ⊂ N satisfies

2) (i) 1∈ S,

3) (ii) k ∈ S ⇒ k + 1 ∈ S,

4) then S = N.

My interpretation:

Line 1 means that we will give S an element or elements that are also of N.
Line 2 means that we will give S the element 1.
Line 3 means that we are introducing a variable k that must be an element of S because we also gave the element k + 1 to S.
Line 4 is accurate for the following reasons. By claiming that S has the elements 1, k and k + 1, we can now test them and find out if indeed S = N. Now we can show that 1, k and k + 1 are elements of S. Because we showed that 1 and k are both elements of S, then k can equal 1. If k can equal 1, then k + 1 can equal 2. And because k + 1 is also an element of S, then so is 2. It follows that because 2 now is an element of S and so is k, then k can now equal 2. Now that we know k can equal 2, then it is true that k + 1 can equal 3; therefore, 3 can now be an element of S and so on. We can deduce that S = N with the original statement.

If something doesn't seem right, please let me know.

 

[HallsofIvy]

That's a rather rough summary but, overall, accurate.

 

[daon2]

Here is a very informative post on induction, and will introduce you to "strong" or "complete" induction as well.

http://math.stackexchange.com/quest...ond-principle-of-finite-induction/14987#14987

 

[The Student]

Hello Again

Ready to try again, I see. That's good. Congratulations.

Mathematical induction is a matter of proof. We do not GIVE anything. We must PROVE everything.

Your notes are correct but deceptive. Lines 1, 2, and 3 form a conditional statement. Furthermore line 1 is VERY abstract.

Let's start with its being conditional. If A is true, then B is true. To prove B true from that conditional, I must prove A is true.
If I am a mother, then I am a woman is a true statement, but it does not make me a woman. In fact I am a father and so a man. See why I disagree with your word "give." Conditionals do not give us anything without strings attached.

Ohhhh, I didn't realize that the whole thing is one statement. I should have noticed that, but I think a few months ago I was just too frustrated and focused on other questions that I had. So is it basically saying if ... and ... and ... only if ... then ... ?

Now for the abstract part. Notice that S is not defined. Your formula is completely general. It is some set. What is in that set? This little formula does not tell you.

So to USE this little formula, you must first define a set. The definition must involve some property or attribute that involves natural numbers. That is, it can't be a set of cars or cats or caps or cams. It has to be defined in terms of natural numbers.

What if the property is not true of any number? That is OK in terms of defining the set because the empty set is considered a set that belongs to every set.

Oh, so is it not that we are giving S these properties, but rather we are testing to see if it has them? Do they exist in S whether or not we test them?

If we are going to use set theory and this formula to PROVE things, we have to say something like

\(\displaystyle \mathbb S = the\ set\ of\ all\ natural\ numbers\ that\ have\ property\ P\),

Just so I can be clear on what property p means, why doesn't a natural number automatically already have property p by definition of being a natural number? In other words, don't all natural numbers have property p?

where P is something that you are saying is true about numbers.

If you do not get this, we are stuck so let me know if anything so far is vague.

Now once you have defined the set, you must prove that 1 is in the set. How do you do that? Well, you PROVE that 1 has property P, whatever you have defined that to be.

Having proved that, we have done what is usually the easy part, but we have at least proved that the set is not empty and contains 1.

Now for the tricky part, we assume that there is at least one number in the set (which we know is true because we have shown 1 to be in the set) and we choose an arbitrary one of those numbers. That number does have property P because it is in the set. (That is in a sense given, but only because we have already proved that there is at least one number in the set, namely 1.) Now we PROVE that no matter what number we chose from the set, the next number in order has property P and THEREFORE is in the set.

Then we have satisfied the conditions and can say that S = N, which is the same as saying that every natural number has property P.

I think I understand this part.

 

[The Student]

I'll be back tomorrow to finish responding. For now, I just want to clarify a few things in the sentence above.

It is the not the set S that has the property we are interested in, but the elements of S that have the property.

To use an analogy, a library that consists solely of history books is not itself a history book. You must distinguish between the set and the elements in the set.

For example, the set of all natural numbers is not a natrual number.

The set of all teen-aged girls is not a teen-aged girl.

Think of the set as a bag, and the elements as what is inside the bag.

OK Got that?

To use the axiom you gave, we must define S as the set of all those natural numbers that have property P. (I know, you asked about the property. Tomorrow, I'll get to that. For right now, just think of a property as being a true statment about something, in this case one or more natural numbers.) There are three possibilities. No natural numbers have property P, some natural numbers, but not all, have property P, or all natural numbers have property P. In all three cases, however, the set S is defined because the set without any elements, the "empty set," is considered a legitimate set. So in the language of set theory the set S, once defined as those natural numbers with property P, exists even if no numbers have property P.

Now if you can prove that 1 is an element of S, you will have also shown that S is not empty, thereby eliminating that possibility. 1 is obviously a natural number so to prove that 1 is an element of S, you must prove that 1 has property P. At that point, you have satisfied one of the conditions. It is, however, still not clear whether some or all natural numbers have property P. But it is clear that AT LEAST some natural numbers have property P.

This all may seem quite abstract BECAUSE it is. At the end, we are going to go through an explicit example to try to make it concrete.

If any of this is obscure, just tell me where. In the meantime, good night. I'll have further responses to your last post tomorrow.

I actually feel like it is all sinking in - what a difference a nice break from it makes.

 

[The Student]

To recapitulate:

\(\displaystyle IF\ [1]\ \mathbb S \in \mathbb N,\ and\ [2]\ 1 \in \mathbb S,\ and\ [3]\ k \in \mathbb S \implies (k + 1) \in \mathbb S,\ THEN\ \mathbb S = \mathbb N.\)

The above is an axiom stated in the language of set theory. Standing by itself it proves NOTHING because it is a conditional statement. It proves something only if we define a property P of natural numbers, PROVE that 1 has property P, and then PROVE a conditional within the conditional, namely IF k is a natural number with property P, THEN the next natural number in line also has property P. This is fairly abstract, and we shall use at least one example to make it concrete, but let's stay abstract for a few more minutes.

A set is a collection of items; it is not the same as the items. The set of bears is not a bear. The set of natural numbers is not a natural number. A set may have no items in it; the set with no items in it is called the empty set. So the set of pink unicorns can be defined, but it has no items in it and so is equal to the empty set. One of the definitions in set theory is subset. X is a subset of set Y MEANS X is a set that contains no items that are not in Y. Notice what this definition does: it makes Y a subset of itself, and it makes the empty set a subset of Y. The empty set contains no items so it contains no items that are not contained in Y. This is a little mind-bending to be sure, but it just follows from the definitions. The empty set is a subset of every set. In particular, the empty set is a subset of the set of natural numbers.

Consequently, when we define S as the subset of natural numbers with property P, we have not proven or even claimed that ANY natural number has property P. If no natural number has property P, then S is the empty set, which is a subset of N by definition. So the first defining step in a proof by induction does not prove a thing. (In fact, it is usually not even considered a step because it is so trivial.)

OK I think that recapitulates fully. Please feel free to question me on anything where I have failed to be clear or where you want even the tiniest bit of clarification.

On to properties. A property is something that we say is true. Living in water is a property of living fish. Truth and property are (close to) synonyms. In math, we want to assume the absolute minimum of properties. What is assumed may be wrong; it is not proved but taken on faith. It is prudent that we make as small as possible what we take on faith and so may be wrong about. Consequently, when we define natural numbers, we ascribe to them a minimum of properties. All the rest of the properties (and there are an infinite number of them) are not assumed, but must be proven. To put this a different way: if we just assume that everything we suspect is true about natural numbers IS true, how much confidence would you have in anything that relied on mathematics such as a bridge or an elevator. Make sense?

OK we are going to start with an easy example, one that is in all the books. But I do not want you to look at any books. I want you to do this as much as possible on your own, right here, using the tutors wherever you get stuck. And we are going to do it in steps.

PROVE: \(\displaystyle \text{For every natural number n, } \displaystyle \sum_{i=1}^ni = (1 + ...\ n) = \dfrac{n(n+1)}{2} = n(n + 1) / 2.\)

Now can you do the step (so trivial it is usually not even counted) of writing in English a sentence that defines the set S that we are going to work with.

If S is a subset of all natural numbers, and 1 is of this set, and (if k is also of this set, then k + 1 is of S too), then S is the same set as the natural numbers.


So I get the feeling that induction does at least 2 major things in general:
1) It defines a set S to equal N.
2) It uses a method of logic \(\displaystyle IF\ [1]\ \mathbb S \in \mathbb N,\ and\ [2]\ 1 \in \mathbb S,\ and\ [3]\ k \in \mathbb S \implies (k + 1) \in \mathbb S,\ THEN\ \mathbb S = \mathbb N\) that must be applied to certain formulas and/or equations to show that they are true.

 

[daon2]

Perhaps to get you thinking about what is really going on, consider this: The only things special about N being used in induction is the fact that there is a "starting point" and that every element has a unique successor. That is, there is a unique element in N, coming after 5, and that is 5+1=6. And in general k+1 is the successor to k. There is only one element which is not a successor: 1, it is where the base case is proved.

So you can also do induction on any set which possesses that quality. For example: let M={-2,-4,-6,...}. Define the successor of k in M to be (k-2), then it follows every element has a unique successor. You can prove that a statement P is true for every element of M by:

1) Let S be the subset of M for which P(m) is true.

2) Show -2 belongs to S.

3) Show that k belongs to S implies (k-2) belongs to S. [i.e. an element belonging to S implies its successor does also, whatever the successor may be]

Conclude: S=M, so P(m) is true for all m in M.

Compare this to the statement for "standard induction."

Now, this is an odd example, but one that is used more frequently is: Show a statement P(n) for every n bigger than some integer k (in your case, k=1). Then the successor is the same as in the standard definition, and the base case is n=k (instead of n=1). For example: for all n>= 4, n! > 2^n.

Note that it is also possible to induct on the set of rationals (and any countable set). Though the choice of successor has to be made intelligently, and this will probably almost never work nicely.

 

[The Student]

Perhaps to get you thinking about what is really going on, consider this: The only things special about N being used in induction is the fact that there is a "starting point" and that every element has a unique successor. That is, there is a unique element in N, coming after 5, and that is 5+1=6. And in general k+1 is the successor to k. There is only one element which is not a successor: 1, it is where the base case is proved.

So you can also do induction on any set which possesses that quality. For example: let M={-2,-4,-6,...}. Define the successor of k in M to be (k-2), then it follows every element has a unique successor. You can prove that a statement P is true for every element of M by:

1) Let S be the subset of M for which P(m) is true.

2) Show -2 belongs to S.

3) Show that k belongs to S implies (k-2) belongs to S. [i.e. an element belonging to S implies its successor does also, whatever the successor may be]

Is what I emboldened above allowed to be automatically assumed because we are talking about a set with an infinite number of elements? Or is there a more rigorous reason why it is true?

 

[The Student]

So I get the feeling that induction does at least 2 major things in general:
1) It defines a set S to equal N.

NO. This is where I think you are having your major stumbling block. It DEFINES S as a subset of N. It specifically does not define S as equal to N. Because the empty set is one of the subsets of N, defining S as a subset does not entail assuming that any number is in S. Of course, it is also true that N is a subset of itself. So the definition of S as a subset leaves open several possibilities: (1) no natural number has the property that defines members of S, (2) a finite number of members have that property, (3) an infinite number of natural numbers, but NOT all natural numbers. have that property, or (4) all natural numbers have that property. In short, the definition of S does not constitute the proof. What constitutes the proof are showing (I) that 1 is a member of S by showing that 1 has the property, and (II) that (k + 1) is a member of S by showing that
(k + 1) has the property if k has the property.

I don't think that I explained what I meant well enough here. I meant that the final outcome from using induction to prove something finishes with a new understanding of the set that we introduced which is set S in our examples. I get this notion from the result that shows N = S at the end of the statement that we use. Also, it seems like this part is built into induction to show how S can be other infinite sets other than N. Of course the two sets named S would be different sets. One would be N, and the other could be a set like the set that daon2 was talking about.

 

[The Student]

daon is absolutely correct that induction can be applied outside the natural numbers, and my second example will demonstrate a very simple case, but all such cases involve a one-to-one correspondence with the natural numbers.

I wish you had tried to define the subset S (or more precisely, define the members of the subset S) for the concrete example I posed in my prior post. I think getting concrete may help you get firm in your own mind what we mean. I am going to give you some examples of defining S. Then please answer my question in the previous post.

Example of a subset S of N that has no members.

\(\displaystyle \mathbb S = \{x\ such\ that\ x \in \mathbb N\ and\ x < (x - 1)\}.\)

Obviously, no number is less than one less than itself, but S is a perfectly good subset of N, namely the empty set.

Example of a subset S of N that has a finite number of members.

\(\displaystyle \mathbb S = \{x\ such\ that\ x \in \mathbb N\ and\ x < 6\}.\)

Notice that this subset fails the second condition of mathematical induction: 5 is in S but 5 + 1 is not.

Example of a subset of N that has an infinite number of members but not all the natural numbers.

\(\displaystyle \mathbb S = \{x\ such\ that\ x \in \mathbb N\ and\ x > 3\}.\)

Notice that this subset fails the first condition of mathematical induction: 1 is not in S.

Another example of a subset S of N that has an infinite number of members but not all natural numbers

\(\displaystyle \mathbb S = \{x\ such\ that\ x \in \mathbb N\ and\ x = 2y - 1,\ where\ y \in \mathbb N\}.\)

This subset contains all the odd natural numbers and so includes 1, but NO k + 1 is a member of S if k is a member of S because one more than an odd number is an even number. This subset massively fails the second condition of induction.

An example of a subset S of N that includes all the natural numbers and so is equal to N.

\(\displaystyle \mathbb S = \{x\ such\ that\ x \in \mathbb N\ and\ (x + 1)^2 = x^2 + 2x + 1\}.\)

I hope you can now see that defining S as a subset of N does not necessarily define S as N.

Please now try to define S for the example I gave in my previous post, and we shall proceed. Of course, as always, you may also ask questions if I have been unclear.

I really did try to define S as best I could. I will try again.

The set that we are going to be working with is a subset N that we will call S. If that holds, and 1 is an element of S, and if k is an element of S, then k + 1 is too, then S = N.

This definition of S seems exactly like the last one that I did. But this is where I am at in my head when defining S.

 

[daon2]

[/I]Is what I emboldened above allowed to be automatically assumed because we are talking about a set with an infinite number of elements? Or is there a more rigorous reason why it is true?

For the natural numbers N, the way it is constructed: every element has a unique successor, and every element except for 1 is a successor.

For the general case, you need the same property, and you should probably prove that, in the case of the set M I defined, every element of M has a unique successor, and every element except for -2 is a successor.

Here's some more examples:

The set of non-negative odd integers: 1 is the unique element with no successor, and the successor of any element k is k+2.

The set of all polynomials of the form Pn(x)=x^n (n>=0). Define the successor of Pn(x) to be x*Pn(x) = x^(n+1). Then the polynomial P0(x) = 1 is the unique element with no successor. (If you have taken Linear Algebra, this is called the standard basis of the vector space of polynomials over some field. It is infinite dimensional).

The set of prime numbers, ordered by the usual ordering. The successor of the Kth prime number will be the (K+1)th prime number. (Using this to prove things about the set of primes will probably be difficult, but it is still valid).

 

[The Student]

OK Yes. We end up if we are successful in our proof showing that S = N. But we do not assume that identity at the beginning.

There are a number of ways to formalize proofs by induction. I have stuck with the one that your notes have specified, which is to show that S = N. My planned second example will show you how to go beyond the natural numbers in practice while formally sticking with what is in your notes.

In most of the cases that I am aware of, you may show that S = some other infinite set by showing that the other infinite set can be placed into one-to-one correspondence with the natural numbers and has a starting point. Daon knows more advanced math than I do so my explanation may need to be refined.

The point that I was trying to get at in my last post is that, in the form in which induction is being presented in your notes, we INITIALLY define S in terms of some property of its members that are natural numbers. We have not assumed that S = N or any other set other than what we have just defined.

Ok, I feel comfortable with this part now except for the little bit left over in my last post to you. I think I know enough about this topic to get me through my first year course. My professor says that the course doesn't have very much of it in it. In fact, I looked through the entire year of notes that he has on the university's website, and properties don't even get mentioned. Of course I know that they will in the coming honors math courses that I hopefully will be taking. Class starts in 2 weeks - yikes!!!

 

[The Student]

Student

I believe it is VERY VERY hard to get this as a purely abstract idea. Working concrete examples will, I believe, make it easier.

Two posts ago, I suggested as an example a specific theorem that I'd like to let you prove with me looking over your shoulder. To start, I'd like you to define S for that example. I gave several examples of such definitions in my previous post. Try to define S for THAT specific concrete theorem. Then we can proceed with the example.

Here is what is theorem that we want to prove in this example \(\displaystyle For any x \in \mathbb N, (1 +\ ...\ n) = n(n + 11)/2.\)

This is a standard example that you can look up, but let's try to do it on your own OK? First step define S.

Oops, I thought that there was really just one way to define S. But I am still confused about the English sentence that you want me to use to define S for the case of \(\displaystyle \text{For every natural number n, } \displaystyle \sum_{i=1}^ni = (1 + ...\ n) = \dfrac{n(n+1)}{2} = n(n + 1) / 2.\). I don't know how defining S, using an English sentence, would change with this equation. I thought as long as we show that S = N, we could apply the elements of S to the equation to see if it works?

 

[daon2]

Look, defining S is automatic (and implied), so much so that mathematicians rarely do it in their proofs. Here is how you define S:

Let S be the subset of all natural numbers n such that <insert statement involving n you want to prove> is true.

 

[The Student]

Think of the formula that was in your notes as a VERY general template that we use to form proofs.

For each proof, we have to define an appropriate S and then prove that THAT version of S = N.

Then for THAT S we have to PROVE that 1 is a member of it as the "first" step in the proof.

I gave I think five examples two or three posts ago. What you are doing is you are defining S as the set that contains all the numbers for which what you are trying to prove (the presumed property) is true. So to prove this theorem we define S as

\(\displaystyle S = \{x\ such\ that\ x \in \mathbb N\ and\ (1 +\ ...\ x) = x(x + 1)/2\}.\)

The definition of S depends on what we are trying to prove (the presumed property).

Now prove that 1 belongs to S.

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

 

[The Student]

Perfect. Congratulations.

Usually the first part of the proof is just about this simple.

Notice what you have done. You have now PROVED that S is NOT the empty set because it has AT LEAST one member. Moreover, 1 is a member of S. If S did not contain 1, it certainly could NOT be true that S = N because 1 is a natural number. You have not yet proved that S has more than one member, namely 1, so you certainly have not YET proved that S = N, but you know it is not a hopeless quest.

Furthermore, you now have a logical basis to consider an arbitrary member of k in S. It is important to rememebr that k must stand for ANY member of S. It may be 1, or it may not. So far we do not know how many members S has; it could be 1 or it could be infinite. So k is just any old member, not necessarily a specific one.

Because k is in S, it is a natural number. So (k + 1) is automatically a natural number too.

Furthermore, BECAUSE k is a member of S it is true that \(\displaystyle \displaystyle \sum_{i=1}^ki = \dfrac{k(k + 1)}{2}.\)

Now for the last step in the proof, PROVE:

\(\displaystyle PROVE:\ \displaystyle \sum_{i = 1}^{k + 1}i = \dfrac{(k+1)[(k + 1) + 1]}{2}, GIVEN\ \sum_{i=1}^ki = \dfrac{k(k + 1)}{2}, \)

Once you have that done, let's do one more to make sure you absolutely have it locked. If you can't prove it, we shall work on it together.

I shall be tied up tomorrow morning so I shall not be able to respond until sometime after noon tomorrow.

I spent a lot of time going over examples like these in the notes of the course that I will be taking, so I do know the answers to these questions and how they came to be. When I try to do it as if I am doing it through my own intuition and not the fact that I know the answer and how to get it, I come up with
\(\displaystyle \ \displaystyle \sum_{i = 1}^{k + 1}i = \dfrac{k(k + 1)}{2} \) + (k + 1) = ((k + 1)(k + 2))/2. Of course the last part is not identical to the answer that you show. So, how can I make (k + 2) = ((k + 1) + 1)? Doesn't bedmas say that I must add what is inside the brackets before adding what is outside? Or does one of the axioms for addition allow us to bypass the bedmas rule?

 

[HallsofIvy]

The associative law says that (a+b)+ c= a+ (b+ c).

 

[The Student]

The associative law says that (a+b)+ c= a+ (b+ c).

Oh cool, thanks

 

[The Student]

Are you up for one more? Please let me know if you want to quit.

If this next example is in your notes, I'll find a different one. But this one is easy and shows what daon was discussing earlier about being able to use induction for problems that, TECHNICALLY, are not about the entire set of natural numbers.

\(\displaystyle PROVE:\ For\ every\ y \in \mathbb N\ and\ y > 4, 4y + 1 < y^2.\)

WOW You cannot prove this for y = 1 because it is then false.

\(\displaystyle 4 * 1 + 1 = 5 \ne 1 = 1^2.\)

Do you see a way to define S to get around that difficulty?

No we don't have this one, so I will give it a try.

If S ⊂ N, and y = 4 + n, and n ∈ N, then S = {N > 4}

This is just a shot in the dark.

 

[The Student]

Are you up for one more? Please let me know if you want to quit.

If this next example is in your notes, I'll find a different one. But this one is easy and shows what daon was discussing earlier about being able to use induction for problems that, TECHNICALLY, are not about the entire set of natural numbers.

\(\displaystyle PROVE:\ For\ every\ y \in \mathbb N\ and\ y > 4, 4y + 1 < y^2.\)

WOW You cannot prove this for y = 1 because it is then false.

\(\displaystyle 4 * 1 + 1 = 5 \ne 1 = 1^2.\)

Do you see a way to define S to get around that difficulty?

I am still fuzzy on defining S in different situations. In my mind, I still only see one way to define S for proofs using induction that use N. I never did understand what I was doing wrong a few posts ago when you wanted me to define S for the sumation equation.

I have to go until tomorrow evening. I will get back into this then.