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
– 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
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
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
Either C 1r C o2 C or3…
If C then D
If C2then D
If C3then 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
Proof of basis clause: [Here you give an argument for accepting the basis
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
[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.