Subsection 8.8.5 The Principle of Mathematical Induction
Now we need to formalize the ladder method so that we can use it as the basis for a new, sound inference rule.
Before we do that, let’s first define an important set:
N = the natural numbers, i.e., the nonnegative integers. So N contains 0, 1, 2, 3 and so forth.
Notice that N possesses properties [A] and [B] as described on the previous slide:
N contains a smallest (first) element, namely 0.
Every element of N has a unique successor (i.e., next element). For any number n, its successor is n+1.
Now we can define a new inference rule that can be used to reason about N. It is called the Principle of Mathematical Induction:
If: P(b) is true for some natural number base case b, and
For all natural numbers n ≥ b, P(n) → P(n+1)
Then: For all natural numbers n ≥ b, P(n)
We’ll use this new rule when we want to show that some property P is true of every natural number (or maybe some subset of them, for example starting at 1 instead of 0).
And, by the way, we’ll look later at examples in which we use mathematical induction to reason about sets other than the natural numbers. But typically, when we do that, we start by assigning a natural number to each element of the original set. So these is a first one, a second one, and so forth.
Nifty Aside
The soundness of the principle of mathematical induction rests on several key properties of the natural numbers. Where do those properties come from? Answer: the same place that everything we reason about comes from. We choose a set of axioms (premises) and then prove additional facts that can be derived from those axioms. In the case of the natural numbers, it’s common to start with a set of axioms proposed by Giuseppe Peano (1858 – 1932). Peano’s axioms form the basis for a large part of modern number theory.
A proof using mathematical induction, of an assertion of the form ∀n (P(n)) about some set of natural numbers greater than or equal to some specific value b, has three parts:
A clear statement of the predicate P(n).
A proof that that P holds for some base case b, the smallest value with which we are concerned. Often, b = 0 or 1, but sometimes P may hold only once we get past some initial unusual cases.
A proof that, for all integers n ≥ b, if P(n) is true, then it is also true that P(n+1). We’ll call the claim P(n) the inductive hypothesis.
Let’s look closely at what is going on in step 3. Let n be an arbitrary natural number. We reason as follows:
[1] P(n) (Conditional) Premise
….. Some reasoning steps in which we treat n as an arbitrary variable and we derive:
[*] P(n + 1)
[**] P(n) → P(n + 1) Conditionalization Discharge [1], [*]
[***] ∀n (P(n) → P(n + 1)) Universal Generalization [**]
Sometimes people read this process and come away thinking that we’ve assumed the thing we’re trying to prove. No we haven’t. We’ve assumed a conditional premise and then released it at the end by constructing a guarded conclusion. Then, since n was an arbitrary variable, we can generalize the claim to all values.
Returning to the ladder model: We are not assuming that it’s possible to stand on rung n. We are assuming only that, if it is possible to stand on rung n, then it is possible to climb to rung n + 1.
Once steps 1 – 3 have been done, we appeal to the Principle of Mathematical Induction to assert:
∀n (P(n))