6.042J/18.062J 3. Well Ordering Principle

1/30/10 1 Lec 2M.1 Albert R Meyer February. 8, 2010 This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported License. Mathematics for Computer Science MIT 6.042J/18.062J The Well Ordering Principle Lec 2M.2 Albert R Meyer February. 8, 2010 Well Ordering principle Every nonempty set of nonnegative integers has a least element. Familiar? Now you mention it, Yes. Obvious? Yes. Trivial? Yes. But watch out: Lec 2M.3 Albert R Meyer February. 8, 2010 Every nonempty set of nonnegative integers has a least element. Well Ordering principle rationals NO! Lec 2M.4 Albert R Meyer February. 8, 2010 Well Ordering principle Every nonempty set of nonnegative integers has a least element. NO! Lec 2M.11 Albert R Meyer February. 8, 2010 Well Ordering Principle Proofs To prove using WOP: • define set of counterexamples • assume C is not empty. By WOP, have minimum element • Reach a contradiction somehow … usually by finding with c < m ∀n ∈N. P(n) C ::= n ∈N | NOT P(n) { } m ∈C c ∈C Lec 2M.12 Albert R Meyer February. 8, 2010 available stamps: 5¢ 3¢ Thm: Get any amount n ≥ 8¢ Prove by WOP. Suppose not. Let m be least counterexample: if m > n ≥ 8, can get n¢. Well Ordered Postage 1/30/10 2 Lec 2M.13 Albert R Meyer February. 8, 2010 m > 8: Well Ordered Postage m > 9: m > 10: Lec 2M.14 Albert R Meyer February. 8, 2010 = m¢ Now m > m-3 ≥ 8 so can get m-3¢. m-3¢ + 3¢ Well Ordered Postage So m ≥ 11. contradiction! But Lec 2M.15 Albert R Meyer February. 8, 2010 Geometric sums 1+r+r2 +r3 ++rn = rn+1 −1 r−1 But = for n = 0, so m > 0, and 1+r+r2 +r3 ++rm−1 = rm −1 r−1 Proof by WOP. Let m be smallest n with ≠. Lec 2M.16 Albert R Meyer February. 8, 2010 Geometric sums 1+r+r2 +r3 ++rm−1 = rm −1 r−1 add rm to both sides LHS = 1+r+r2 +r3 ++rm−1 +rm RHS = rm −1 r−1 +rm = rm+1 −1 r−1 so = at m, contradicting ≠:there is no counterexample. rm+1 −rm r−1 Lec 2M.17 Albert R Meyer February. 8, 2010 Team Problems Problems 1－3 MIT OpenCourseWare http://ocw.mit.edu 6.042J /18.062J Mathematics for Computer Science Spring 2010 For information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/terms.