Ling 726: Mathematical Linguistics, Lecture 9: Induction. V. Borschev and B. Partee, October 19, 2004 p. 1 1 Lecture 9: Proof by Induction. 8.1.1. Recursive definitions. ....................................................................................................................................1 8.4. Peano’s axioms and Proof by Induction. ..........................................................................................................2 Homework 10 ..........................................................................................................................................................4 APPENDIX: ............................................................................................................................................................5 How to use Induction in a Proof. ........................................................................................................................5 Introduction....................................................................................................................................................5 Example 1 ......................................................................................................................................................5 Example 2 ......................................................................................................................................................7 Conclusion .....................................................................................................................................................8 Feedback. .......................................................................................................................................................8 Read: PtMW, Chapter 8, Section 8.4 (192-198) and Section 8.5.7 (214-215). Attention: Induction is a mind-bender, more than it seems at first! 8.1.1. Recursive definitions. First let’s review recursive definitions from Section 8.1.1 of PtMW. There is in fact a close connection between being able to specify the membership of some set recursively and being able to use some version of the Principle of Mathematical Induction to prove that all members of the set have some property or other. Consider the set M of all even-length mirror-image strings on {a,b}. An even-length mirror-image string is a string that can be divided into two halves, with the right half a mirror-image reversal of the left half (a “palindrome”). Examples: abba, babbab, aaaa, bbabbabb. Non-examples: babb, aaab, bab. Recursive definition of M: (8-1) 1. aa ∈ M & bb ∈ M 2. (∀x)(x ∈ M → (axa ∈ M & bxb ∈ M)) 3. Nothing is in M except by virtue of rules 1 and 2. (Line 1 is called the base of the recursion, line 2 the recursion step, and line 3 is an obligatory restriction that is often omitted, but always understood to be included.) The recursive step of a recursive definition looks a lot like a “circular definition”, as in the “definition” of subset in (8-2). (8-2) For any sets A and B, A is a subset of B iff every subset of A is a subset of B. The “definition” in (8-2) is no good as a definition; it contains a vicious circle. But (8-1) is a perfectly good recursive definition. What makes the difference? The presence of the base, and the possibility of applying the recursive step repeatedly, one iteration at a time.Ling 726: Mathematical Linguistics, Lecture 9: Induction. V. Borschev and B. Partee, October 19, 2004 p. 2 2 The derivation of a string abaaba ∈ M can be presented in a form virtually identical to the form of a proof. (8-3) 1. aa ∈ M & bb ∈ M Ax. 1 2. (∀x)(x ∈ M → (axa ∈ M & bxb ∈ M)) Ax. 2 3. aa ∈ M 1, Simplification 4. aa ∈ M → (aaaa ∈ M & baab ∈ M)) 2, Universal Instantiation 5. aaaa ∈ M & baab ∈ M 3,4, Modus Ponens 6. baab ∈ M 5, Simplification 7. baab ∈ M → (abaaba ∈ M & bbaabb ∈ M 2, Universal Instantiation. 8. abaaba ∈ M & bbaabb ∈ M 6,7, Modus Ponens And we could keep going. Deriving longer strings just requires longer proofs with more of the same sorts of steps. We can similarly give a recursive definition of the wffs of statement logic. (See pp 182-183.) If we want to have the possibility of arbitrarily many basic statements, p, q, r, p’, q’, r’, p’’, q’’, etc., then we have to start with a recursive definition of atomic statement, and then use that in giving a recursive definition of the set of all wffs. 8.4. Peano’s axioms and Proof by Induction. In this section we will look at an axiomatic approach to the natural numbers. “Peano’s axioms” for the natural numbers, actually due to Dedekind, are one of the most well-known axiomatic systems in the history of mathematics. And they also give rise to the important Principle of Mathematical Induction and the related technique of proof by induction. In the axiomatic approach to natural numbers, the aim is to set forth some essential properties of the natural numbers from which all their other properties are derivable as theorems, just as in Euclid’s axiomatization of plane geometry. We start with three primitive (undefined) notions: two primitive predicates and one primitive constant. (i) a 1-place predicate ‘is a natural number’, which we will symbolize by N x; (ii) a 2-place predicate ‘is a (the) successor of’: we write Sxy for ‘x is successor of y’; (iii) the constant 0. The axioms: P1. N0 (0 is a natural number) P2. (∀x)(Nx → (∃y)(Ny & Syx & (∀z)(Szx → z = y))) (Every natural number has a unique successor.) P3. ~(∃x)(Nx & S0x) (0 is not the successor of any number.)Ling 726: Mathematical Linguistics, Lecture 9: Induction. V. Borschev and B. Partee, October 19, 2004 p. 3 3 P4. (∀x)(∀y)(∀z)(∀w)((Nx & Ny & Szx & Swy & z=w) → x = y) (No two distinct natural numbers have the same successor. P5. If Q is a property which has properties (i) and (ii) below, (i) Q0 (zero has Q), and (ii) (∀x)(∀y)((Nx & Qx & Ny & Syx) → Qy) (if a natural number has Q then its successor has Q, i.e. Q is a ‘hereditary’ property) then (∀x)(Nx → Qx) (every natural number has Q) The fifth Peano postulate is very important; it introduces the notion of mathematical induction. It is not and cannot be expressed in our familiar first-order predicate logic, because it involves quantification over