Class Notes (835,384)
United States (324,104)
Philosophy (46)
2250 (23)

N07MathematicalInduction - Mathematical Induction.pdf

9 Pages
Unlock Document

James Hildebrand

During this course, I have made claims that are not obviously true. I h ave simply asked you to take these claims for granted. I have said that: – the semantic rules guarantee that every compound sentence of SL has exactly one of the two truth values, T or F. (We know that, by definition, a truth value assignment must assign exactly one of T or F to every atomic sentence of SL, but why should it have to follow that every compound sentence must also be assigned exactly one of T or F?) – falsity is infectious in iterated conjunctions: If any conjunct in an iterated conjunction is false, the whole conjunction is false. – truth is infectious in iterated disjunctions: If any disjunct in an iterated disjunction is true, the whole disjunction is true. – the tree method is sound: If the tree for Γ closes, Γ will always be t-f inconsistent. – the tree method is complete: If Γ is t-f inconsistent, the tree for Γ will always close. I will also, in coming classes, make further claims of a like nature: – SD is sound: If Γ yields P in SD, then Γ t-f entails P. – SD is complete: If Γ t-f entails P then there is a way to derive P from Γ in SD. – the rules of replacement of SD+ are legitimate because sentences of SL are extensional in SD: If P and Q are equivalent in SD and some sentence, R, contains one or more occurrences of P among its components, then [R] (Q//P) (that is, the sentence that results of replacing one or more of the occurrences of P in R with occurrences of Q) is equivalent in SD to R. How do we know that there are no exceptions to these claims? We cannot go through all the sentences, sets, and arguments of SL and verify that there are no exceptions, because there are infinitely many of them. We might try to prove the claims by reductio ad absurdum (that is, by showing that if you suppose that they are false you get caught in a contradiction), but it is not obvious how to do that. A better way to prove these claims and others like them is to employ a special form of argument called mathematical induction. Arguments by mathematical induction are misnamed. They are not inductive arguments at all, and you won’t learn anything about them if you study accounts of induction. Arguments by mathematical induction are actually deductive arguments. They allow us to prove that every one of a large or infinite number of things must have a certain property. To run these arguments, we first arrange all the things we are concerned with in a series of groups. We then argue that what we want to prove is infectious. Given any group at any point in the series, if what we want to prove is true of all the things in all the earlier groups, then it must be true of all the things in that group as well. If we can do that, then all we need to show is that what we want to prove is true of all the things in the first group. From that it follows that what we want to prove must be true of all the things in all the groups. For, if it is infectious (meaning that if all the things in all the earlier groups have it, then all the things in the next group do as well) then if all the things in the first group have it, then all the ones in the second group must have it. And if all the things in the first and second groups have it, then all the things in the third group must have it, and so on. An argument by mathematical induction therefore has this form: All the Group 1’s are B’s If all the members of all the groups from 1 to k are B’s, then all the Group k+1’s are B’s So all the members of all the groups are B’s Here is a simple example: There are cockroaches in all the rooms of the basement of the residence. If there are cockroaches on all the rooms of all the floors beneath you, there are cockroaches on all the rooms of your floor as well. There are cockroaches on all the rooms of all the floors of the residence. Here the series of groups is just the series of floors in a building from bottom to top (the members of each are the rooms on that floor). Note that if the two premises of this argument are true the conclusion must be true. If there are cockroaches in all the rooms of the basement, and it is true that cockroaches in all the rooms on all the lower floors mean cockroaches on the next floor up, then the building must be full to the top with cockroaches, even if it is infinitely tall and has infinitely many floors. This is therefore a deductively valid argument. It is not a truth- functionally valid argument. (It is one of those arguments that SL can’t handle. It rather belongs to a more sophisticated logic, second order predicate logic.) But that need not concern us. We can intuitively grasp that the argument is deductively valid. Of course, just because this argument is deductively valid, that does not mean that it is sound. To be sound, both premises must be true, and the second premise, at least, is as a matter of fact false. Cockroaches evolved at a finite point in past time, and it takes time for them to propagate from one place to the next. Given that cockroaches have only been around for a few million years, and that it takes some time (even if only a few days) for their progeny to move up from one floor of a building to the next, there is no way they could fill an infinitely tall building given that they have only been around for a finite time. But this just means that the argument has a false premise, not that it isn’t deductively valid. Other arguments by mathematical induction that we will look it will have true premises as well as being deductively valid. Here are some labels that we will need to use: We call the first premise of an argument by mathematical induction (the premise that shows that what we want to prove is true of all the things in the first group of the series) the basis clause. We call the second premise (the premise that claims that if what we want to prove is true of all the things in all the earlier groups, then it is true of all the things in the next group as well) the inductive step. The inductive step is always a conditional sentence. We call its antecedent (the claim that what we want to prove is true of all the things in all the earlier groups) the inductive hypothesis. Unfortunately, arguments by mathematical induction are seldom as simple as the one given above about the cockroaches in a building. Rather than being one-paragraph arguments, they often end up being two- or three-page essays. There are three reasons why this is the case. 1. First, before you can even get started with an argument from mathematical induction you have to come up with some way of grouping and listing the groups of things you are concerned with. Not just any way of grouping and listing the objects you are concerned will necessarily work. The grouping and listing procedure needs to be explained, and that takes time. In fact, this is often the most difficult stage of the entire argument. (For this reason, mathematical induction exercises for students often start off with a hint that consists in telling them how to group and list the things under consideration. Once that really hard part is over the rest is, at least for those who understand what is going on, fairly straightforward.) 2. Second, when you give an argument by mathematical induction you need to prove that the basis clause and the inductive step are true. This means that you end up with arguments inside of an argument. You have one big argument, which is your argument by mathematical induction with its basis clause and its inductive step leading to its conclusion. But then you also have supporting arguments that justify your premises. There is really no good way to handle this that won’t confuse or bewilder or try the patience of a novice to mathematical induction. If you state your big argument first, the novice will object that the premises aren’t obviously true. If you give your arguments for your premises first, the novice will wonder what the point is of it all. If you first state your basis clause, then insert a subsidiary argument that serves to prove that the basis clause is true, then state your inductive step, then give a second argument that explains why the inductive step is true, and only then draw your conclusion, the novice is likely to get lost in all the details. For this reason, it is important to i) appreciate the architecture of an argument by mathematical induction so you will feel yourself in familiar territory as you navigate through its different parts, and ii) exercise a lot of patience. 3. The third and final thing that makes mathematical induction complicated is that the proof of the inductive step typically requires considering a number of alternative cases, and then proving the point for each case. This is known as argument by cases. Arguments by cases have the following form: Either C 1r C o2 C or3… If C then D 1 If C2then D If C3then D … Therefore, D. When all these complications are considered together an argument by mathematical induction can end up having the following structure: Introduction: [Here you describe the problem and, most importantly, describe how you mean to group and list the things you are concerned with. You specify what groups the objects fall into and how those groups ought to be ordered from first on.] Statement of Basis Clause: All A ’s are B’s 1 Proof of basis clause: [Here you give an argument for accepting the basis clause.] Statement of Inductive Step: if all the A ’s1to A ’skare B’s, then all the A k+1s are B’s. Proof of inductive step: [You begin by stating the inductive hypothesis]: Suppose all the A 1’s to Ak’s are B’s. [You then identify the alternative cases that need to be considered]: The A k+1’s are either C 1s or C ’2 or C ’3 or … [You then proceed to make the point for each case]: Case one: Suppose the A k+1s are C 1s [here you insert an argument that because all the A ’s t1 A ’s ake B’s this means that the C ’s1are B’s] Case two: Suppose A k+1s are are C 2s [here you insert an argument that because all the A ’s 1o A ’skare B’s this means that the C ’2 are B’s] Case three: Suppose A k+1s are are C 3s [here you insert an argument that because all the A ’s 1o A ’skare B’s this means that the C 3’s are B’s] … [Having considered all the cases, you draw your conclusion]: Since the C ’s to 1 C ns are all the Ak+1s there are, and they are all B’s, any way you look at it, all the Ak+1’s are B’s. Conclusion: All A’s whatsoever are B’s. This is obviously a rather complex form of argument. It is the kind of argument that is presented over pages, rather than in a paragraph, and that requires titles and sub-titles dividing up various stages and frequent pauses to advise the reader what stage you are at, what has been proven so far, and what remains to be done. Your job at this point is not to generate your own arguments by mathematical induction (though if you can do that in simple cases it will certainly help). It is just to understand those arguments when you come across them, where “understanding” means finding them convincing — grasping why the conclusion really does follow. It is best to attempt to familiarize yourself with this pattern of argumentation by working through some simple examples. You should read Chapter 6.1, which contains a very nice exposition of mathematical induction by means of a number of specific examples. You may find that a number of the examples are silly. (For instance, the first example taken up in the text is a proof that in every sentence of SL the number of left hand parentheses equals the number of right hand parentheses.) But the idea, at this stage is not to prove profound or interesting results. It is to work with some very trite and obvious examples just so that you will get a feel for how arguments by mathematical induction work. The only way to really learn this is to try yourself to imitate the arguments you find in the text. You can do this by taking on the exercises, all of which are answered in the solutions manual. (Try to do them without looking at the solutions manual first.) After you have done just one or two examples, you will understand mathematical induction and will be able to follow arguments by mathematical induction given in the rest of the course. Before you have taken on one or two exercises for yourself you may think that you understand mathematical induction, but chances are that you do not. It is very important, therefore, that you read the text and do the exercises. As a
More Less

Related notes for 2250

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.