1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 7
Текст из файла (страница 7)
We shallprove this statement by induction on the cardinality of A.Basis Step. Let A be a set of cardinality 71 = 0. Then A = 0, and 21AI = 2° = 1;on the other hand, 2A = {0}, and 12AI = 1{0}1 = 1.Induction Hypothesis. Let 71IAI ::;71.> 0, and suppose that12A I = 21AI provided thatInduction Step. Let A be such that IAI = 71 + 1. Since 71 > 0, A contains at leastone element a. Let B = A - {a}; then IBI = n.
By the induction hypothesis,12BI = 21BI = 2n. Now the power set of A can be divided into two parts, thosesets containing the element a and those sets not containing a. The latter partis just 2 B , and the former part is obtained by introducing a into each memberof 2B. Thus2A = 2B U {CU {a}: C E 2B}.This division in fact partitions 2A into two disjoint equinumerous parts, so thecardinality of the whole is twice 21B1 , which, by the induction hypothesis, is2· 2n = 2n +1 , as was to be shown.<>We next use induction to establish our second fundamental principle, thepigeonhole principle.The Pigeonhole Principle: If A and B are finite sets and IAI > IBI, thenthere is no one-to-one function from A to B.In other words, if we attempt to pair off the elements of A (the "pigeons")with elements of B (the "pigeonholes"), sooner or later we will have to put morethan one pigeon in a pigeonhole.Proof: Basis Step.
Suppose IBI = 0, that is, B = 0. Then there is no functionf : A r-+ B whatsoever, let alone a one-to-one function.26Chapter 1: SETS, RELATIONS, AND LANGUAGESInduction Hypothesis. Suppose that f is not one-to-one, provided that f : A r-+and IBI S; n, where n 2 o.B, IAI > IBI,Induction Step. Suppose that f : A r-+ Band IAI > IBI == n + 1. Choose someA (since IAI > IBI = n + 1 2 1, A is nonempty, and therefore such a choiceis possible).
If there is another element of A, say a', such that f (a) == f (a'),then obviously f is not a one-to-one function, and we are done. So, supposethat a is the only element mapped by f to f (a). Consider then the sets A - {a},B - {f(a)}, and the function g from A - {a} to B - {f(a)} that agrees withf on all elements of A - {a}. Now the induction hypothesis applies, becauseB - {f(a)} has n elements, and 1..1 - {a}1 = IAI- 1 > IBI- 1 = IB - {f(a)} I·Therefore, there are two distinct elements of A - {a} that are mapped by g (andtherefore by f) to the same element of B - {b}, and hence f is not one-to-one .•a EThis simple fact is of use in a surprisingly large variety of proofs.
We presentjust one simple application here, but point out other cases as they arise in laterchapters.Theorem 1.5.1: Let R be a binary relation on a finite set A, and let a, bE A.If there is a path from a to b in R, then there is a path of length at most IAI.Proof: Suppose that (al' a2, ... ,an) is the shortest path from al = a to an = b,that is, the path with the smallest length, and suppose that n > IAI. By thepigeonhole principle, there is an element of A that repeats on the path, sayai = aj for some 1 S; i < j S; n. But then (al,a2, ...
,ai,aHl, ... ,an ) is ashorter path from a to b, contradicting our assumption that (al, a2, . .. ,an) isthe shortest path from a to b.•Finally, we come to our third basic proof technique, the diagonalizationprinciple. Although it is not as widely used in mathematics as the other twoprinciples we have discussed, it seems particularly well-suited for proving certainimportant results in the theory of computation.The Diagonalization Principle: Let R be a binary relation on a set A, andlet D, the diagonal set for R, be {a: a E A and (a, a) ¢ R}.
For each a E A, letRa = {b : b E A and (a, b) E R}. Then D is distinct from each Ra.If A is a finite set, then R can be pictured as a square array; the rows andcolumns are labeled with the elements of A and there is a cross in the box withrow labeled a and column labeled b just in case (a, b) E R. The diagonal set Dcorresponds to the complement of the sequence of boxes along the main diagonal,boxes with crosses being replaced by boxes without crosses, and vice versa. Thesets Ra correspond to the rows of the array. The diagonalization principle canthen be rephrased: the complement of the diagonal is different from each row.271.5: Three Fundamental Proof TechniquesExample 1.5.3: Let us consider the relation R{(a, b), (a, d), (b, b), (b, c),(c, c), (d, b), (d, c), (d, e), (d, I), (e, e), (e, I), (1, a), (1, c), (1, d), (1, e)}; notice thatRa = {b,d}, Rb = {b,c}, Rc = {c}, Rd = {b,c,e,j},R e = {e./} and RJ ={a,c,d,e}.
All in all, R may be pictured like this:abaxbxcdfxxxxxxxcdxxefexxxxThe sequence of boxes along the diagonal isIts complement iswhich corresponds to the diagonal set D = {a, d, j}. Indeed, D is different fromeach row of the array; for D, because of the way it is constructed, differs fromthe first row in the first position, from the second row in the second position,and so on.OThe diagonalization principle holds for infinite sets as well, for the samereason: The diagonal set D always differs from the set Ra on the question ofwhether a is an element, and hence cannot be the same as Ra for any a.We illustrate the use of diagonalization by a classic theorem of Georg Cantor(1845-1918).28Chapter 1: SETS, RELATIONS, AND LANGUAGESTheorem 1.5.2: The set 2N is uncountable.Proof: . Suppose that 2N is count ably infinite.
That is, we assume that thatthere is a way of enumerating all members of 2N as(notice that these are the sets Ra in the statement of the diagonalization principle, once we consider the relation R = ((i,j) : j E Rd). Now consider thesetD={nEN:n~Rn}(this is the the diagonal set). D is a set of natural numbers, and therefore itshould appear somewhere in the enumeration {Ra, R 1 , R 2 , ••• } But D cannot beRa, because it differs from it with respect to containing 0 (it does if and onlyif Ra does not); and it cannot be Rl because it differs from it with respect to1; and so on. We must conclude that D does not appear on the enumeration atall, and this is a contradiction.To restate the argument a little more formally, suppose that D = Rk forsome k 2: 0 (since D is a set of natural numbers, and {Ra, Rl, R2, ...
} wassupposed to be a complete enumeration of all such sets, such a k must exist).We obtain a contradition by asking whether k E R k :(a) Suppose the answer is yes, k E Rk. Since D = {n EN: n ~ Rn}, it followsthat k ~ D; but D = Rk, a contradiction.(b) Suppose the answer is no, k ~ Rk; then kED. But D is R k , so k E Rk,another contradiction.We arrived at this contradiction starting from the assumption that 2N iscountably infinite, and continuing by otherwise impeccably rigorous mathematical reasoning; we must therefore conclude that this asumption was in error.Hence 2N is uncountable .•For a different rendering of this proof, in terms of establishing that the setof real numbers in the interval (0,1] is uncountable, see Problem 1.5.11.Problems for Section 1.51.5.1.
Show by induction that1·2·3+ 2 ·3·4 + ... + n· (n + 1) . (n + 2) =n' (n + 1) . (n + 2) . (n + 3)4.291.6: Closures and Algorithms1.5.2. Show by induction that n 4-4n 2 is divisible by 3 for all n ~ O.1.5.3. What is wrong with the following purported proof that all horses are thesame color?Proof by induction on the number of horses:Basis Step. There is only one horse. Then clearly all horses have the samecolor.Induction Hypothesis.
In any group of up to n horses, all horses have thesame color.Induction Step. Consider a group of n + 1 horses. Discard one horse; by theinduction hypothesis, all the remaining horses have the same color. Nowput that horse back and discard another; again all the remaining horseshave the same color. So all the horses have the same color as the ones thatwere not discarded either time, and so they all have the same color.1.5.4. Show that, if A and B are any finite sets, then there are IBIIAI functionsfrom A to B.1.5.5. Prove by induction: Every partial order on a nonempty finite set has atleast one minimal element.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
