Induction Proof课件.pptVIP

Well-ordering A set S is well ordered if every subset has a least element. [0, 1] is not well ordered since (0,1] has no least element. Examples: N is well ordered (under the ? relation). Any coutably infinite set can be well ordered. The least element in a subset is determined by a bijection (list) which exists from N to the countably infinite set. Z can be well ordered but it is not well ordered under the ? relation. Z has no smallest element. The set of finite strings over an alphabet using lexicographic ordering is well ordered. 精品文档 Mathematical Induction Let P(x) be a predicate over a well ordered set S. In the case that S = N, the natural numbers, the principle has the following form. P(0) P(n) ? P(n +1) ??x P(x) The hypotheses are H1: P(0) (Basis Step) H2: P(n) ? P(n +1) for n arbitrary. (Induction Step) 精品文档 How It Works First, prove that the predicate is true for the smallest element of the set S (0 if S = N). Then, show if it is true for an element (n if S=N) implies it is true for the “next” element in the set (n + 1 if S=N). Meaning Knowing it is true for the first element means it must be true for the element following the first or the second element Knowing it is true for the second element implies it is true for the third and so forth. Therefore, induction is equivalent to modus ponens applied an countable number of times!! 精品文档 Outline of Induction Proof State what P(n) is. Basis: Prove that P(0) is true. Induction hypothesis: Assume that P(n) is true, for an arbitrary n. Induction step: Prove that P(n+1) is true, using P(n). (Usually, direct proof) 精品文档 Example Prove:?ni = n(n +1)/2 i=0 In logical notation we wish to show ?n [?ni = n(n +1)/2 ] i=0 Hence, P(n) is [?ni] = n(n +1)/2 i=0 Basis: Prove H1: P(0): 0=0(0 +1)/2 Induction Hypotheses: Assume P(n) is true for n arbitrary. Now use this and anything else you know to establish that P(n+1) must be true. 精品文档 E