Class Notes
(808,703)

United States
(313,202)

Philosophy
(46)

2250
(23)

James Hildebrand
(23)

Lecture

# 3 - Math Induction and Extensionality.pdf

Unlock Document

Buffalo State College

Philosophy

2250

James Hildebrand

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