良序定理

1 . Proof by the Well ordering principle 09/28/18 

2 .Well Ordering Principle • Every nonempty set of nonnegative integers has a least element 09/28/18 

3 .Well Ordering Principle • Every nonempty set of nonnegative integers has a least element 09/28/18 

4 .Well Ordering Principle • Every nonempty set of nonnegative integers has a least element 09/28/18 

5 .Well Ordering Principle  Every nonempty set of nonnegative integers has a least element  We actually used this already when arguing that a fraction can be reduced to “lowest terms”  The set of factors of a positive integer is nonempty 09/28/18 

6 . To prove P(n) for every nonnegative n: • Let C = {n: P(n) is false} (the set of “counterexamples”) • Assume C is nonempty in order to derive a contradiction • Let m be the smallest element of C • Derive a contradiction (perhaps by finding a smaller member of C) 09/28/18 

7 . A Proof Using WOP • Given a stack of pancakes, make a nice stack with the smallest on top, then the next smallest, …, and the biggest on the bottom • By using only one operation: Grabbing a wad off the top and flipping it! • Theorem: n pancakes can be sorted using 2n-3 flips (n≥2) 09/28/18 

8 . One way to do it • Grab under the biggest pancake and bring it to the top • Flip the entire stack over • Repeat, ignoring the bottom pancake 09/28/18 

9 . Why does this take 2n-3 flips? • For n≥2, let P(n) := “n pancakes can be sorted using 2n-3 flips” • Suppose this is false for some n • Let C = {n: P(n) is false} • C has a least element by WOP. Call it m. • So m pancakes cannot be sorted using 2m-3 flips and m is the smallest number for which that is the case 09/28/18 

10 . Why does this take 2n-3 flips? • m≠2 since one flip sorts 2 pancakes • But if m>2 then it takes 2 flips to get the biggest pancake on the bottom … • and 2(m-1)-3 to sort the rest since P(m-1) is true (since m-1 < m) … • for a total of 2(m-1)-3+2 = 2m-3, contradicting the assumption that P(m) is false 09/28/18 

11 .09/28/18 

12 . Summing powers of 2 • Thm: 1+2+22+23+…+2n =2n+1-1 • E.g. 1+2+22 = 1+2+4 = 7 = 23-1 09/28/18 

13 . Summing powers of 2 • Thm: For every n≥0, 1+2+22+23+…+2n =2n+1-1 • E.g. 1+2+22 = 1+2+4 = 7 = 23-1 • Let P(n) be the statement 1+2+22+23+…+2n = 2n+1-1 09/28/18 

14 . Summing powers of 2 • Let C = {n: P(n) is false} = {n: 1+2+22+23+…+2n ≠2n+1-1}. • Then C is nonempty by hypothesis. • Then C has a minimal element m by WOP. • m cannot be 0 since P(0) is true: 1=20=20+1-1 • So m > 0 09/28/18 

15 . Summing powers of 2 • But if 1+2+22+23+…+2m ≠2m+1-1 • then subtracting 2m from both sides: 1+2+22+23+…+2m-1 ≠2m+1-1-2m = 2m-1 (since 2m+2m = 2m+1) • But then P(m-1) is also false, contradiction. 09/28/18 

16 . Summing powers of 2 • Where did we use the fact that P(0) is true, so m > 0? 09/28/18 

17 . A Notational Note • Learn to avoid ellipses …! n P(n) ≡∑ 2 =2i n+1 −1 i=0 Theorem: (∀n)P(n) 09/28/18 

18 . A geometric “proof” n ∑2 i =2n+1 −1≡ i=0 n 2 n+1 =1+∑ 2 ≡ i 1 i=0 1 1/2 1/2 n 1 2= n +∑ 2i−n 1+½+¼+⅛+… 1+½+¼+⅛ 1 1+½+¼ +½ 2 i=0 09/28/18