“mcs”一2017/6/5一19：42一page30一#38 30 Chapter 2 The Well Ordering Principle so any way of expressing the left-hand fraction in lowest terms would also work for mo/no,which implies molp the fraction cannot be in written in lowest terms either. no/p So by definition of C,the numerator mo/p is in C.But mo/p<mo,which contradicts the fact that mo is the smallest element of C. Since the assumption that C is nonempty leads to a contradiction,it follows that C must be empty.That is,that there are no numerators of fractions that can't be written in lowest terms,and hence there are no such fractions at all. We've been using the Well Ordering Principle on the sly from early on! 2.2 Template for WOP Proofs More generally,there is a standard way to use Well Ordering to prove that some property,P(n)holds for every nonnegative integer n.Here is a standard way to organize such a well ordering proof: To prove that"P(n)is true for all n E N"using the Well Ordering Principle: Define the set C of counterexamples to P being true.Specifically,define C ::=n EN NOT(P(n))is true). (The notation n O(n)means "the set of all elements n for which o(n) is true."See Section 4.1.4.) Assume for proof by contradiction that C is nonempty. By WOP,there will be a smallest element n in C. Reach a contradiction somehow-often by showing that P(n)is actually true or by showing that there is another member of C that is smaller than n.This is the open-ended part of the proof task. Conclude that C must be empty,that is,no counterexamples exist. 2.2.1 Summing the Integers Let's use this template to prove
“mcs” — 2017/6/5 — 19:42 — page 30 — #38 Chapter 2 The Well Ordering Principle30 so any way of expressing the left-hand fraction in lowest terms would also work for m0=n0, which implies the fraction m0=p n0=p cannot be in written in lowest terms either. So by definition of C, the numerator m0=p is in C. But m0=p < m0, which contradicts the fact that m0 is the smallest element of C. Since the assumption that C is nonempty leads to a contradiction, it follows that C must be empty. That is, that there are no numerators of fractions that can’t be written in lowest terms, and hence there are no such fractions at all. We’ve been using the Well Ordering Principle on the sly from early on! 2.2 Template for WOP Proofs More generally, there is a standard way to use Well Ordering to prove that some property, P .n/ holds for every nonnegative integer n. Here is a standard way to organize such a well ordering proof: To prove that “P .n/ is true for all n 2 N” using the Well Ordering Principle: Define the set C of counterexamples to P being true. Specifically, define C WWD fn 2 N j NOT.P .n// is trueg: (The notation fn j Q.n/g means “the set of all elements n for which Q.n/ is true.” See Section 4.1.4.) Assume for proof by contradiction that C is nonempty. By WOP, there will be a smallest element n in C. Reach a contradiction somehow—often by showing that P .n/ is actually true or by showing that there is another member of C that is smaller than n. This is the open-ended part of the proof task. Conclude that C must be empty, that is, no counterexamples exist. 2.2.1 Summing the Integers Let’s use this template to prove
“mcs”一2017/6/5一19：42一page31一#39 2.2.Template for WOP Proofs 31 Theorem 2.2.1. 1+2+3+…+n=nn+1)/2 (2.1) for all nonnegative integers n. First,we'd better address a couple of ambiguous special cases before they trip us up: If n =1,then there is only one term in the summation,and so 1+2+3+ ...+n is just the term 1.Don't be misled by the appearance of 2 and 3 or by the suggestion that 1 and n are distinct terms! If n =0,then there are no terms at all in the summation.By convention,the sum in this case is 0. So,while the three dots notation,which is called an ellipsis,is convenient,you have to watch out for these special cases where the notation is misleading.In fact,whenever you see an ellipsis,you should be on the lookout to be sure you understand the pattern,watching out for the beginning and the end. We could have eliminated the need for guessing by rewriting the left side of(2.1) with summation notation: or 1≤i≤n Both of these expressions denote the sum of all values taken by the expression to the right of the sigma as the variable i ranges from 1 to n.Both expressions make it clear what (2.1)means when n 1.The second expression makes it clear that when n =0,there are no terms in the sum,though you still have to know the convention that a sum of no numbers equals 0(the product of no numbers is 1,by the way). OK,back to the proof: Proof.By contradiction.Assume that Theorem 2.2.1 is false.Then,some nonneg- ative integers serve as counterexamples to it.Let's collect them in a set: C=n∈N11+2+3+…+n≠n+》. 2 Assuming there are counterexamples,C is a nonempty set of nonnegative integers. So,by WOP,C has a minimum element,which we'll call c.That is,among the nonnegative integers,c is the smallest counterexample to equation (2.1). Since c is the smallest counterexample,we know that(2.1)is false for n =c but true for all nonnegative integers n<c.But (2.1)is true for n =0,so c >0.This
“mcs” — 2017/6/5 — 19:42 — page 31 — #39 2.2. Template for WOP Proofs 31 Theorem 2.2.1. 1 C 2 C 3 C C n D n.n C 1/=2 (2.1) for all nonnegative integers n. First, we’d better address a couple of ambiguous special cases before they trip us up: If n D 1, then there is only one term in the summation, and so 1 C 2 C 3 C C n is just the term 1. Don’t be misled by the appearance of 2 and 3 or by the suggestion that 1 and n are distinct terms! If n D 0, then there are no terms at all in the summation. By convention, the sum in this case is 0. So, while the three dots notation, which is called an ellipsis, is convenient, you have to watch out for these special cases where the notation is misleading. In fact, whenever you see an ellipsis, you should be on the lookout to be sure you understand the pattern, watching out for the beginning and the end. We could have eliminated the need for guessing by rewriting the left side of (2.1) with summation notation: Xn iD1 i or X 1in i: Both of these expressions denote the sum of all values taken by the expression to the right of the sigma as the variable i ranges from 1 to n. Both expressions make it clear what (2.1) means when n D 1. The second expression makes it clear that when n D 0, there are no terms in the sum, though you still have to know the convention that a sum of no numbers equals 0 (the product of no numbers is 1, by the way). OK, back to the proof: Proof. By contradiction. Assume that Theorem 2.2.1 is false. Then, some nonnegative integers serve as counterexamples to it. Let’s collect them in a set: C WWD fn 2 N j 1 C 2 C 3 C C n ¤ n.n C 1/ 2 g: Assuming there are counterexamples, C is a nonempty set of nonnegative integers. So, by WOP, C has a minimum element, which we’ll call c. That is, among the nonnegative integers, c is the smallest counterexample to equation (2.1). Since c is the smallest counterexample, we know that (2.1) is false for n D c but true for all nonnegative integers n < c. But (2.1) is true for n D 0, so c > 0. This
“mcs”一2017/6/5一19：42page32一#40 32 Chapter 2 The Well Ordering Principle means c-1 is a nonnegative integer,and since it is less than c,equation(2.1)is true for c-1.That is, 1+2+3++c-1)=c-10c 2 But then,adding c to both sides,we get 1+2+3+…+(c-1)+c= (c-1)c 2 +c=2-c+2c=c(e+D 2 2 which means that (2.1)does hold for c,after all!This is a contradiction,and we are done. ■ 2.3 Factoring into Primes We've previously taken for granted the Prime Factorization Theorem,also known as the Unique Factorization Theorem and the Fundamental Theorem of Arithmetic, which states that every integer greater than one has a unique expression as a prod- uct of prime numbers.This is another of those familiar mathematical facts which are taken for granted but are not really obvious on closer inspection.We'll prove the uniqueness of prime factorization in a later chapter,but well ordering gives an easy proof that every integer greater than one can be expressed as some product of primes. Theorem 2.3.1.Every positive integer greater than one can be factored as a prod- uct of primes. Proof.The proof is by WOP. Let C be the set of all integers greater than one that cannot be factored as a product of primes.We assume C is not empty and derive a contradiction. If C is not empty,there is a least element n EC by WOP.This n can't be prime, because a prime by itself is considered a (length one)product of primes,and no such products are in C. So n must be a product of two integers a and b where 1 a,b n.Since a and b are smaller than the smallest element in C,we know that a,bC.In other words,a can be written as a product of primes pip2..pk and b as a product of primes q1…ql.Therefore,n=p1…pkq1…qi can be written as a product of primes,contradicting the claim that n E C.Our assumption that C is not empty must therefore be false. ■ 1...unique up to the order in which the prime factors appear
“mcs” — 2017/6/5 — 19:42 — page 32 — #40 Chapter 2 The Well Ordering Principle32 means c 1 is a nonnegative integer, and since it is less than c, equation (2.1) is true for c 1. That is, 1 C 2 C 3 C C .c 1/ D .c 1/c 2 : But then, adding c to both sides, we get 1 C 2 C 3 C C .c 1/ C c D .c 1/c 2 C c D c 2 c C 2c 2 D c.c C 1/ 2 ; which means that (2.1) does hold for c, after all! This is a contradiction, and we are done. 2.3 Factoring into Primes We’ve previously taken for granted the Prime Factorization Theorem, also known as the Unique Factorization Theorem and the Fundamental Theorem of Arithmetic, which states that every integer greater than one has a unique1 expression as a product of prime numbers. This is another of those familiar mathematical facts which are taken for granted but are not really obvious on closer inspection. We’ll prove the uniqueness of prime factorization in a later chapter, but well ordering gives an easy proof that every integer greater than one can be expressed as some product of primes. Theorem 2.3.1. Every positive integer greater than one can be factored as a product of primes. Proof. The proof is by WOP. Let C be the set of all integers greater than one that cannot be factored as a product of primes. We assume C is not empty and derive a contradiction. If C is not empty, there is a least element n 2 C by WOP. This n can’t be prime, because a prime by itself is considered a (length one) product of primes, and no such products are in C. So n must be a product of two integers a and b where 1 < a; b < n. Since a and b are smaller than the smallest element in C, we know that a; b … C. In other words, a can be written as a product of primes p1p2 pk and b as a product of primes q1 ql . Therefore, n D p1 pkq1 ql can be written as a product of primes, contradicting the claim that n 2 C. Our assumption that C is not empty must therefore be false. 1 . . . unique up to the order in which the prime factors appear
“mcs”一2017/6/5一19：42一page33一#41 2.4.Well Ordered Sets 33 2.4 Well Ordered Sets A set of real numbers is well ordered when each of its nonempty subsets has a minimum element.The Well Ordering Principle says that the set of nonnegative integers is well ordered,but so are lots of other sets of real numbers according to this more general form of WOP.A simple example would be the set rN of numbers of the form rn,where r is a positive real number and ne N.(Why does this work?) Well ordering commonly comes up in computer science as a method for proving that computations won't run forever.The idea is to assign a value to each successive step of a computation so that the values get smaller at every step.If the values are all from a well ordered set,then the computation can't run forever,because if it did, the values assigned to its successive steps would define a subset with no minimum element.You'll see several examples of this technique applied in Chapter 6 to prove that various state machines will eventually terminate. Notice that a set may have a minimum element but not be well ordered.The set of nonnegative rational numbers is an example:it has a minimum element zero, but it also has nonempty subsets that don't have minimum elements-the positive rationals,for example. The following theorem is a tiny generalization of the Well Ordering Principle. Theorem 2.4.1.For any nonnegative integer n the set of integers greater than or equal to-n is well ordered. This theorem is just as obvious as the Well Ordering Principle,and it would be harmless to accept it as another axiom.But repeatedly introducing axioms gets worrisome after a while,and it's worth noticing when a potential axiom can actually be proved.This time we can easily prove Theorem 2.4.1 using the Well Ordering Principle: Proof.Let S be any nonempty set of integers >-n.Now add n to each of the elements in S;let's call this new set S+n.Now S+n is a nonempty set of nonnegative integers,and so by the Well Ordering Principle,it has a minimum element m.But then it's easy to see that m-n is the minimum element of S. The definition of well ordering states that every subset of a well ordered set is well ordered,and this yields two convenient,immediate corollaries of Theo- rem2.4.1: Definition 2.4.2.A lower bound (respectively,upper bound)for a set S of real numbers is a number b such that b≤s(respectively,b≥s)for every s∈S
“mcs” — 2017/6/5 — 19:42 — page 33 — #41 2.4. Well Ordered Sets 33 2.4 Well Ordered Sets A set of real numbers is well ordered when each of its nonempty subsets has a minimum element. The Well Ordering Principle says that the set of nonnegative integers is well ordered, but so are lots of other sets of real numbers according to this more general form of WOP. A simple example would be the set rN of numbers of the form rn, where r is a positive real number and n 2 N. (Why does this work?) Well ordering commonly comes up in computer science as a method for proving that computations won’t run forever. The idea is to assign a value to each successive step of a computation so that the values get smaller at every step. If the values are all from a well ordered set, then the computation can’t run forever, because if it did, the values assigned to its successive steps would define a subset with no minimum element. You’ll see several examples of this technique applied in Chapter 6 to prove that various state machines will eventually terminate. Notice that a set may have a minimum element but not be well ordered. The set of nonnegative rational numbers is an example: it has a minimum element zero, but it also has nonempty subsets that don’t have minimum elements—the positive rationals, for example. The following theorem is a tiny generalization of the Well Ordering Principle. Theorem 2.4.1. For any nonnegative integer n the set of integers greater than or equal to n is well ordered. This theorem is just as obvious as the Well Ordering Principle, and it would be harmless to accept it as another axiom. But repeatedly introducing axioms gets worrisome after a while, and it’s worth noticing when a potential axiom can actually be proved. This time we can easily prove Theorem 2.4.1 using the Well Ordering Principle: Proof. Let S be any nonempty set of integers n. Now add n to each of the elements in S; let’s call this new set S C n. Now S C n is a nonempty set of nonnegative integers, and so by the Well Ordering Principle, it has a minimum element m. But then it’s easy to see that m n is the minimum element of S. The definition of well ordering states that every subset of a well ordered set is well ordered, and this yields two convenient, immediate corollaries of Theorem 2.4.1: Definition 2.4.2. A lower bound (respectively, upper bound) for a set S of real numbers is a number b such that b s (respectively, b s) for every s 2 S
“mcs”一2017/6/5一19：42page34一#42 34 Chapter 2 The Well Ordering Principle Note that a lower or upper bound of set S is not required to be in the set. Corollary 2.4.3.Any set of integers with a lower bound is well ordered. Proof.A set of integers with a lower bound b eR will also have the integer n b|as a lower bound,where bl,called the floor of b,is gotten by rounding down b to the nearest integer.So Theorem 2.4.1 implies the set is well ordered. ■ Corollary 2.4.3 leads to another principle we usually tahe for granted: Corollary 2.4.4.Any nonempty set of integers with an upper bound has a maximum element. Proof.Suppose a set S of integers has an upper bound bER.Now multiply each element of S by-1;let's call this new set of elements-S.Now,of course,-b is a lower bound of-S.So-S has a minimum element-m by Corollary 2.4.3.But then it's easy to see that m is the maximum element of S. ■ Finite sets are yet another routine example of well ordered set. Lemma 2.4.5.Every nonempty finite set of real numbers is well ordered. Proof.Since subsets of finite sets are finite,it is sufficient to prove that every finite set has a minimum element. We prove this using the WOP on the size of finite sets. Let C be the set of positive integers n such that some set of size n has no mini- mum element.Assume for the sake of contradiction that C is nonempty.By WOP, there is a minimum integer m E C. Every set of size one obviously has a minimum element,so m >2. Now let F be a set of m real numbers.We will reach a contradiction by showing that F has a minimum element. So let ro be an element of F.Since m 2,removing ro from F leaves a nonempty set F'smaller than m.Since m is the smallest element of C,we know Fhas a minimum element r1.But that means the smaller of ro and ri is the minimum element of F. ■ 2.4.1 A Different Well Ordered Set(Optional) The set F of fractions that can be expressed in the form n/(n+1): 0123 n '234…n+1… is well ordered.The minimum element of any nonempty subset of F is simply the one with the minimum numerator when expressed in the form n/(n+1)
“mcs” — 2017/6/5 — 19:42 — page 34 — #42 Chapter 2 The Well Ordering Principle34 Note that a lower or upper bound of set S is not required to be in the set. Corollary 2.4.3. Any set of integers with a lower bound is well ordered. Proof. A set of integers with a lower bound b 2 R will also have the integer n D bbc as a lower bound, where bbc, called the floor of b, is gotten by rounding down b to the nearest integer. So Theorem 2.4.1 implies the set is well ordered. Corollary 2.4.3 leads to another principle we usually tahe for granted: Corollary 2.4.4. Any nonempty set of integers with an upper bound has a maximum element. Proof. Suppose a set S of integers has an upper bound b 2 R. Now multiply each element of S by -1; let’s call this new set of elements S. Now, of course, b is a lower bound of S. So S has a minimum element m by Corollary 2.4.3. But then it’s easy to see that m is the maximum element of S. Finite sets are yet another routine example of well ordered set. Lemma 2.4.5. Every nonempty finite set of real numbers is well ordered. Proof. Since subsets of finite sets are finite, it is sufficient to prove that every finite set has a minimum element. We prove this using the WOP on the size of finite sets. Let C be the set of positive integers n such that some set of size n has no minimum element. Assume for the sake of contradiction that C is nonempty. By WOP, there is a minimum integer m 2 C. Every set of size one obviously has a minimum element, so m 2. Now let F be a set of m real numbers. We will reach a contradiction by showing that F has a minimum element. So let r0 be an element of F . Since m 2, removing r0 from F leaves a nonempty set F 0 smaller than m. Since m is the smallest element of C, we know F 0 has a minimum element r1. But that means the smaller of r0 and r1 is the minimum element of F . 2.4.1 A Different Well Ordered Set (Optional) The set F of fractions that can be expressed in the form n=.n C 1/: 0 1 ; 1 2 ; 2 3 ; 3 4 ; : : : ; n n C 1 ; : : : ; is well ordered. The minimum element of any nonempty subset of F is simply the one with the minimum numerator when expressed in the form n=.n C 1/