Class Notes (808,703)
United States (313,202)
Philosophy (46)
2250 (23)
Lecture

# 3 - Math Induction and Extensionality.pdf

23 Pages
63 Views

School
Buffalo State College
Department
Philosophy
Course
2250
Professor
James Hildebrand
Semester
Spring

Description
MATHEMATICAL INDUCTION The name notwithstanding, arguments by mathematical induction are not inductive arguments. They are deductive. (So you won’t learn about them by studying induction.) An argument by mathematical induction presupposes 3 things: • that you are able to line things up somehow • that there is some property or feature of the things you have lined up that carries on down the line • that the first thing in line has the property Supposing all these things are the case, you can use mathematical induction to prove that all the things you have lined up must have the property, even if there are infinitely many of them. Example 1: If all the birds on the power line in front of a given bird fly off the line, that bird flies off the line as well. The first bird flew off the line. All the birds flew off the line. Example 2: If all the cars in the lane in front of a given car crash, that car crashes too. The first car crashed. All the cars crashed. Example 3: If all the earlier dominos fell the next one fell, too The first domino fell. All the dominos fell. An alternative statement of these examples: Example 1: Bird 1 flew off the line. If all the birds from bird 1 to bird k few off the line, bird k+1 flew off the line as well. All the birds flew off the line. Example 2: Car 1 crashed. If all the cars from 1-k crashed, the k+1 car crashed too. All the cars crashed. Example 3: Domino 1 fell. If all the dominos from 1-k fell the k+1 domino fell, too All the dominos fell. A slightly more complex version of arguments from mathematical induction lines up groups of things, rather than individual things. Example 4: All the rooms in the basement of the residence are full of cockroaches. If all the rooms on all the floors from basement-k are full of cockroaches, all the rooms on floor k+1 are full, too All the rooms of all the floors are full. Some terminology: Basis clause: the premise that states that the first thing on the list is a certain way. Inductive step: the premise that states that if all the things on the list up to k are a certain way, the k+1 thing is that way, too. Inductive hypothesis: the antecedent of the inductive step. When giving an argument by mathematical induction we first need to come up with a way of listing and grouping things. Standard groupings for mathematical induction arguments involving sentential logic: • length of sentences (how many vocabulary elements they contain) • number of occurrences of connectives in sentences • list of sentences from top to bottom or bottom to top of a tree branch • list of sentences from top to bottom of a derivation Example 5a Prove that all sentences of SL that contain no binary connectives (call them non-binary sentences) are t-f indeterminate. To prove this by mathematical induction I will group the non-binary sentences by how many occurrences of connectives they contain, and list these groups from 0 occurrences of connectives on up. Every non-binary sentence containing 0 connectives is t-f indeterminate. If every non-binary sentence containing from 0-k occurrences of connectives is t-f indeterminate then every non-binary sentence containing k+1 occurrences of connectives is t-f indeterminate. Every non-binary sentence of SL is t-f indeterminate. When giving an argument by mathematical induction we also need to give supporting arguments to prove the basis clause and the inductive step. Example 5b: Basis clause: Every non-binary sentence containing 0 connectives is t-f indeterminate. Proof: The non-binary sentences containing 0 occurrences of connectives are the atomic sentences. By definition of a truth value assignment there is a tva that assigns a T to any atomic sentence and a tva that assigns an F to that sentence. So, by definition of t-f indeterminacy, all atomic sentences of SL, and hence all non-binary sentences containing 0 occurrences of connectives, are t-f indeterminate. Inductive step: If every non-binary sentence containing from 0-k occurrences of connectives is t-f indeterminate then every non- binary sentence containing k+1 occurrences of connectives is t-f indeterminate. Proof: Suppose: every non-binary sentence containing from 0-k occurrences of connectives is t-f indeterminate. : Any non-binary sentence containing k+1 occurrences of connectives must contain at least one ~ (since ~ is the only non-binary connective and k cannot be less than 0). : So any non-binary sentence containing k+1 occurrences of connectives must have the form ~P. : Consequently, its immediate component, P, must contain fewer than k+1 connectives. : But then, by the inductive hypothesis, P must be t-f indeterminate. : So, by definition of t-f indeterminacy, there must be at least one tva on which P is true and at least one on which it is false. : But then, by ~rule, there must be at least one tva on which ~P is false and at least one on which it is true. : So ~P must also be t-f indeterminate. So, to sum up, if we suppose that that every non-binary sentence containing from 0-k occurrences of connectives is t-f indeterminate, then we are compelled to accept that any non-binary sentence, ~P, containing k+1 occurrences of connectives must be t-f indeterminate as well. Conclusion: Every non-binary sentence of SL is t-f indeterminate. Note how arguments for the inductive step begin by assuming the inductive hypothesis and then use that assumption when arguing for the consequent of the inductive step. Example 6 Prove by mathematical induction on the number of occurrences of connectives that no sentence of SL that contains only binary connectives (call it a binary sentence) is t-f false. Basis clause: There is a truth value assignment on which all the binary sentences containing 0 occurrences of connectives are true. Proof: The binary sentences containing 0 occurrences of connectives are the atomic sentences. By definition of a truth value assignment there is a truth value assignment (the one that assigns a T to each atomic sentence of SL) on which all the atomic sentences are true. So there is a truth value assignment on which all the binary sentences containing 0 occurrences of connectives are true. Inductive step: If there is a truth value assignment on which all the binary sentences containing from 0-k occurrences of connectives are true, then there is a truth value assignment on which all the binary sentences containing k+1 occurrences of connectives are true. Proof: Suppose: there is a truth value assignment, α, on which all the binary sentences containing from 0-k occurrences of connectives are true. : Any binary sentence containing k+1 occurrences of connectives must consist of two not necessarily distinct immediate components, P and Q and a binary connective (since k cannot be less than 0, meaning there must be at least one connective in a sentence containing k+1 occurrences of connectives, and since that connective must be a binary connective, connecting two immediate components) : Since P and Q are components of a k+1 sentence, they must each have k or fewer connectives. : So, by the inductive hypothesis, there is a truth value assignment, α, on which they are both true. : But regardless of which binary connective you consider, if both immediate components are true, the sentence compounded using that connective is true. : So any binary sentence containing k+1 occurrences of connectives must be true on α. So if there is a truth value assignment, α, on which all the binary sentences containing from 0-k occurrences of connectives are true, any binary sentence containing k+1 occurrences of connectives must be true on α as well. Conclusion: So there is a truth value assignment on which all the binary sentences of SL are true. Consequently, none of them can be t-f false. Appealing to the inductive hypothesis to prove the inductive step is not question-begging. That is because the inductive step is a conditional sentence. If you assume that the antecedent of a conditional sentence is true, … and your assumption turns out to be incorrect, … then for sure the conditional sentence is true! (because conditionals with false antecedents are always true) Your concern should never be about what happens if you are wrong to assume the antecedent, … but about what happens if you are right. that is why you go to the work of showing that if the antecedent is in fact true, then the consequent must follow. Moreover, all that you end up proving when you prove the inductive step by assuming the inductive hypothesis is that if all the members of groups 0-k have the property, then all the members of group k+1 have it as well. You aren’t proving that all the members of the groups 0-k in fact have the property. You are merely temporarily supposing it for purposes of argument. The actual proof comes from the basis clause and the fact that you can prove that if all the members of group 0 are a certain way, all the members of group 1 must be as well … and so on. Often, proving the inductive step can involve running through a number of cases, and showing that each case works. Example 7: Prove by mathematical induction on the number of occurrences of conn
More Less

Related notes for 2250

OR

Don't have an account?

Join OneClass

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

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.