===========================================================================
CSC 236 On the importance of being precise... Winter 2012
===========================================================================
Consider the following "proof" by induction.
Let P(n) denote the statement: "Every list L of size n whose last
element is the largest contains some element L[i] such that
L[i-1] <= L[i]".
We prove \-/ n >= 2, P(n) by simple induction.
Base Case: Suppose L is a list of size 2 whose last element is the
largest, i.e., L[0] <= L[1]. Then, L contains an element i such
that L[i-1] <= L[i] (pick i = 1).
Hence, P(2).
Ind. Hyp.: Suppose n >= 2 and P(n).
Ind. Step: To prove P(n+1), suppose L is a list of size n whose last
element is the largest. Then L contains some element L[i_0] such
that L[i_0-1] <= L[i_0], by the I.H. Suppose x >= L[n-1]. Then,
L' = [L[0],...,L[n-1],x] is a list of size n+1 whose last element
is the largest, and it contains an element i such that L[i-1] <=
L[i]-- pick i = i_0 or i = n.
Hence, P(n+1).
Therefore, by induction \-/ n, P(n).
You may think that everything seems fine with this proof, but that's not
the case. The first (minor) problem is that induction is not necessary to
prove the statement. In itself, this does not make the proof incorrect.
To convince you that there is another, more serious error, consider the
following "proof", whose structure is *identical* to the one above (thanks
to Arnold Rosenbloom at UTM for the example below).
Let P(n) denote the statement: "Every list of size n which ends with
the largest element is sorted".
We prove \-/ n, P(n) by simple induction.
Base Case: Every list of size 0 is sorted (vacuously), so P(0).
Every list of size 1 is sorted, so P(1)-- not necessary to prove
this as a base case, but it doesn't hurt either.
Ind. Hyp.: Suppose n >= 1 and P(n).
Ind. Step: To prove P(n+1), suppose L is a list of size n whose last
element is the largest. Then L is sorted, by the I.H. Now assume
x >= L[n-1]. Then, L' = [L[0],...,L[n-1],x] is a list of size n+1
that ends with the largest element, and it is sorted. So P(n+1).
Therefore, by induction \-/ n, P(n).
It should be clear that the statement being "proved" in the second case is
false-- a list can very well be unsorted even though its largest element
occurs last. This means that there must be an error somewhere in the proof,
because we know induction is a sound proof technique (i.e., any statement
proved by induction must be true-- we cannot use induction to "prove" false
statements).
Since the structure of both "proofs" above is identical, it's not possible
for one proof to be correct and for the other proof to be incorrect: either
both are correct or both are incorrect-- even though the statement is true
in one case and false in the other.
So where is the mistake?
In order to find it, we have to spell out P(n) more precisely. So, let A
denote the set of all lists, and for any list L (- A, let len(L) denote the
size of list L. Finally, let L[0],L[1],...,L[n-1] denote the elements in
any list L, where n = len(L) (i.e., list indices start at 0).
Then, the statement P(n) can be written as follows.
- For the first example, P(n) is the statement:
\-/ L (- A, len(L) = n -> (L[n-1] is maximum ->
L contains an element L[i] such that L[i-1] <= L[i])
- For the second example, P(n) is the statement:
\-/ L (- A, len(L) = n -> (L[n-1] is maximum -> L is sorted)
In both cases, P(n) has the form \-/ x (- D, Q(n,x) -> P'(x), for some
domain D and predicates Q(n,x), P'(x)-- in this case, D = A, Q(n,L) is the
statement "len(L) = n", and P'(L) is the statement between parentheses in
each case. Also, both "proofs" have the following structure:
Base Case: To prove P(0), let x (- D such that Q(0,x). Then, P'(x).
So P(0).
Ind. Hyp.: Suppose n (- N and P(n), i.e., \-/ x (- D, Q(n,x) -> P'(x).
Ind. Step: To prove P(n+1), suppose x (- D and Q(n,x).
Then, P'(x) by the I.H.
Consider x' = f(x) (a new element of D constructed from x).
By construction, x' (- D and Q(n+1,x').
...proof of P'(x') goes here, making use of P'(x)...
Hence, P(n+1).
However, the correct conclusion for the inductive step is actually
\-/ x (- D, Q(n,x) -> P'(f(x)),
which is *not* the same as P(n+1). It is *incorrect* to conclude P(n+1):
\-/ x (- D, Q(n+1,x) -> P'(x),
because x was *not* chosen to be an arbitrary element of D such that
Q(n+1,x)-- rather, the inductive step proved P'(f(x)), where f(x) is a
specific element of D constructed from some arbitrary element x (- D such
that Q(n,x).
A correct structure to prove statements P(n): \-/ x (- D, Q(n,x) -> P'(x)
by induction on n would be as follows.
Base Case: To prove P(0), suppose x (- D and Q(0,x).
...work to prove P'(x) goes here...
Then, P'(x).
So \-/ x (- D, Q(0,x) -> P'(x), i.e., P(0).
Ind. Hyp.: Suppose n (- N and P(n), i.e., \-/ x (- D, Q(n,x) -> P'(x).
Ind. Step: To prove P(n+1), suppose x (- D and Q(n+1,x).
Figure out how to use the fact that P'(y) holds for all
elements y (- D such that Q(n,y) (by the I.H.) in order to
conclude P'(x).
Hence, \-/ x (- D, Q(n+1,x) -> P'(x), i.e., P(n+1).
For example, the first statement above (which was true) would be correctly
proved as follows.
Let P(n) denote the statement: "Every list L of size n whose last
element is the largest contains some element L[i] such that
L[i-1] <= L[i]".
We prove \-/ n >= 2, P(n) by simple induction.
Base Case: Suppose L is a list of size 2 whose last element is the
largest, i.e., L[0] <= L[1]. Then, L contains an element i such
that L[i-1] <= L[i] (pick i = 1).
Hence, P(2).
Ind. Hyp.: Suppose n >= 2 and P(n).
Ind. Step: To prove P(n+1), suppose L is a list of size n+1 whose last
element is the largest. Then L contains some element L[i] such
that L[i-1] <= L[i]-- just pick i = n.
Hence, P(n+1).
Therefore, by induction \-/ n, P(n).
Of course, in this case, induction was not really necessary-- but the proof
above *is* correct.
MORAL: It really pays to take the time to define P(n) *precisely*, and
when proving the inductive step, *always* start from P(n+1) (what you are
trying to prove) and work "backward" to make use of P(n) (the I.H.). This
will always work, compared to starting with P(n) and trying to "add" to it
to get to P(n+1), which can fail for many predicates P().