=========================================================================== 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().