6.042/18.] Mathematics for Computer Science February 16, 2005 Srini devadas and Eric Lehman Notes for recitation 5 1 Well-ordering principle Every non-empty set of natural numbers has a minimum element Do you believe this statement? Seems obvious, right? Well, it is. But dont fail to realize how tight it is. Crucially, it talks about a non-empty set -otherwise, it would clearly be false. And it also talks about natural numbers -otherwise, it might again be false: think or example what would happen with the integers, or even the positive rational numbers This statement has a name, it is called the well-ordering principle. And, as most things we give names to, it's important. Why? Because it is equivalent to induction Something can be proved by induction iff it can be proved by the well-ordering principle We could go on and give a general proof of this, but we wont. Instead, we'll just convince ourselves of it by going through an example. Well reprove something that in the very first lecture(see Lecture Notes"Induction I")was proved by induction. Read the next page For reference, here is the outline that a proof by the well-ordering principle has. ( Compare it with the corresponding outline of a proof by strong induction. To prove that"P(n)is true for all n E N"using the well-ordering principle Use proof by contradiction Assume that P(n) has counterexamples. I.e., that P(n) is false on at least one n Define the set of counterexamples C=nENIP(n)) Invoke the well-ordering principle to select the minimum element c of C Since c is the smallest counterexample to P(n), conclude that both P(c) and P(0), P(1),., P(c-1). Use these to arrive at a contradiction. Watch out: the list 0. 1.... c-1 will contain no numbers at all if c=0 Conclude that P(n)must have no counterexamples. Namely, that(n)P(n)6.042/18.062J Mathematics for Computer Science February 16, 2005 Srini Devadas and Eric Lehman Notes for Recitation 5 1 Well­ordering principle Every non­empty set of natural numbers has a minimum element. Do you believe this statement? Seems obvious, right? Well, it is. But don’t fail to realize how tight it is. Crucially, it talks about a non­empty set —otherwise, it would clearly be false. And it also talks about natural numbers —otherwise, it might again be false: think for example what would happen with the integers, or even the positive rational numbers. This statement has a name, it is called the well­ordering principle. And, as most things we give names to, it’s important. Why? Because it is equivalent to induction. Something can be proved by induction iff it can be proved by the well­ordering principle. We could go on and give a general proof of this, but we won’t. Instead, we’ll just convince ourselves of it by going through an example. We’ll reprove something that in the very first lecture (see Lecture Notes “Induction I”) was proved by induction. Read the next page. For reference, here is the outline that a proof by the well­ordering principle has. (Compare it with the corresponding outline of a proof by strong induction.) To prove that “P(n) is true for all n ∈ N” using the well­ordering principle: • Use proof by contradiction. • Assume that P(n) has counterexamples. I.e., that P(n) is false on at least one n. • Define the set of counterexamples C = {n ∈ N | ¬P(n)}. • Invoke the well­ordering principle to select the minimum element c of C. • Since c is the smallest counterexample to P(n), conclude that both ¬P(c) and P(0), P(1), . . . , P(c − 1). Use these to arrive at a contradiction. Watch out: the list 0, 1, . . . , c − 1 will contain no numbers at all if c = 0. • Conclude that P(n) must have no counterexamples. Namely, that (∀n)P(n)