1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 6
Текст из файла (страница 6)
Which1.3.5. Let f : A f--t B. Show that the following relation R is an equivalence relationon A: (a, b) E R if and only if f(a) = f(b).1.3: Special Types of Binary Relations19>------{3®1.3.6. Let R <:;:; A x A be a binary relation as defined below. In which cases is Ra partial order'? a total order'?(a) A = the positive integers; (a, b) E R if and only if b is divisible by a.(b) A = N x N; ((a, b)(c, d)) E R if and only if a:::: cor b:::: d.(c) A = N; (a, b) E R if and only if b = a or b = a + l.(d) A is the set of all English words; (a, b) E R if and only if a is no longerthan b.(e) A is the set of all English words; (a, b) E R if and only if a is the sameas b or occurs more frequently than b in the present book.20Chapter 1: SETS, RELATIONS, AND LANGUAGES1.3.7.
Let Rl and R2 be any two partial orders on the same set.4. Show thatRl n R2 is a partial order.1.3.8. (a) Prove that if 5 is any collection of sets, then Rs = {(.4, B) : A, B E5 and A ~ B} is a partial order.(b) Let 5 = 2{1,2,3}. Draw a directed graph representing the partial orderRs defined in (a). Which are the minimal elements of Rs?1.3.9. Under what circumstances does a directed graph represent a function?1.3.10.
Show that any function from a finite set to itself contains a cycle.1.3.11. Let 5 be any set, and let P be the set of all partitions of 5. Let R bethe binary relation on P such that (III, II 2) E R if and only if for every51 E III, there is an 52 E II2 such that 51 ~ 52; if (III, II 2) E R we say thatIII refines II 2. Show that R is a partial order on P. What elements of Pare maximal and minimal? Suppose that P were an arbitrary collection ofsubsets of 2s , which need not be partitions of 5.
Would R necessarily be apartial order?GFINITE AND INFINITE SETSA basic property of a finite set is its size, that is, the number of elements itcontains. Some facts about the sizes of finite sets are so obvious they hardlyneed proof. For example, if A ~ B, then the size of A is less than or equal tothat of B; the size of A is zero if and only if A is the empty set.However, an extension of the notion of "size" to infinite sets leads to difficulties if we attempt to follow our intuition. Are there more multiples of 17(0,17,34,51,68, ...
) than there are perfect squares (0,1,4,9,16, ... )? You arewelcome to speculate on alternatives, but experience has shown that the onlysatisfactory convention is to regard these sets as having the same size.We call two sets A and B equinumerous if there is a bijection I : A f-tB. Recall that if there is a bijection I : A f-t B, then there is a bijection1-1 : B f-t A; hence equinumerosity is a symmetrie relation. In fact, as is easilyshown, it is an equivalence relation. For example, {8,red,{0,b}} and {1,2,3}are equinumerous; let f(8) = 1, I(red) = 2, f( {0, b}) = 3.
So are the multiplesof17 and the perfect squares; a bijection is given by f(17n) = n 2 for each n E N.In general, we call a set finite if, intuitively, it is equinumerous with{I, 2, ... , n} for some natural number n. (For n = 0, {I, ... , n} is the empty set,so (I) is finite, being equinumerous with itself.) If A and {1, ... ,n} are equinumerous, then we say that the cardinality of A (in symbols, IAI) is n. The cardinalityof a finite set is thus the number of elements in it.211.4: Finite and Infinite SetsA set is infinite if it is not finite.
For example, the set N of natural numbersis infinite; so are sets such as the set of integers, the set of reals, and the set ofperfect squares. However, not all infinite sets are equinumerous.A set is said to be countably infinite if it is equinumerous with N, andcountable if it is finite or count ably infinite. A set that is not countable isuncountable. To show that a set A is count ably infinite we must exhibit abijection / between A. and N; equivalently, we need only suggest a way in whichA. can be enumerated asand so on, since such an enumeration immediately suggests a bijection -justtake /(0) = ao, /(1) = a1,'"For example, we can show that the union of any finite number of countablyinfinite sets is count ably infinite.
Let us only illustrate the proof for the caseof three pairwise disjoint, count ably infinite sets; a similar argument works ingeneral. Call the sets A, B, and C. The sets can be listed as above: A ={ao, a1, ... }, B = {b o, b1 , ... }, C = {co, C1, ... }, Then their union can be listedas Au B u C = {ao, bo, Co, a1, b1 , C1, a2, ...
}. This listing amounts to a way of"visiting" all the elements in A U B u C by alternating between different sets,as illustrated in Figure 1-7. The technique of interweaving the enumeration ofseveral sets is called "dovetailing" (for reasons that any carpenter can give afterlooking at Figure 1-7).ABCFigure 1-7The same idea can be used to show that the union of a countably infinitecollection of countably infinite sets is count ably infinite. For example, let usshow that N x N is count ably infinite; note that N x N is the union of {O} x N,{I} x N, {2} x N, and so on, that is, the union of a count ably infinite collectionof countably infinite sets. Dovetailing must here be more subtle than in theChapter 1: SETS, RELATIONS, AND LANGUAGES22example above: we cannot, as we did there, visit one element from each setbefore visiting the second element of the first set, because with infinitely manysets to visit we could never even finish the first round! Instead we proceed asfollows (see Figure 1-8).(1) In the first round, we visit one element from the first set: (0,0).(2) In the second round, we visit the next element from the first set, (0,1), andalso the first element from the second set, (1,0).(3) In the third round we visit the next unvisited elements of the first andsecond sets, (0,2) and (1,1), and also the first element of the third set,(2,0).(4) In general, in the nth round, we visit the nth element of the first set, the(n - l)st element of the second set, and the first element of the nth set.{4} x N0{3} x N(4,3)00(3,3)00(2,4)0{2} x N{I} x N{O} x N(0,0)Figure 1-8Another way of viewing this use of dovetailing is to observe that the pair(i,j) is visited mth, where m = ~[(i + j)2 + 3i + j]; that is to say, the functionf(i,j) = ~[(i + j)2 + 3i + j] is a bijection from N x N to N (see Problem 1.4.4).At the end of the next section, we present a technique for showing that twoinfinite sets are not equinumerous.1.5: Three Fundamental Proof Techniques23Problems for Section 1.41.4.1.
Prove that the following are countable.(a) The union of any three countable sets, not necessarily infinite or disjoint.(b) The set of all finite subsets of N.1.4.2. Explicitly give bijections between each of the following pairs.(a) N and the odd natural numbers.(b) N and the set of all integers.(c) Nand N x N x N.(We are looking for formulas that are as simple as possible and involve only suchoperations as addition and multiplication.)1.4.3.
Let C be a set of sets defined as follows,1.0ECIf Sl E C and S2 E C, then {Sl,S2} E C.If Sl E C and S2 E C, then Sl x S2 E C.2.3.4.(a)(b)Nothing is in C except that which follows from (1), (2), and (3).Explain carefully why it is a consequence of (1-4) that {0, {0}} E C.Give an example of a set S of ordered pairs such that SEC, andlSI>1.(c) Does C contain any infinite sets? Explain.(d) Is C countable or uncountable? Explain.1.4.4. Show that the dovetailing method of Figure 1-8 visits the pair (i, j) mth,wherem=1.512[(i+j)2+3i+j].THREE FUNDAMENTAL PROOF TECHNIQUESEvery proof is different, since every proof is designed to establish a differentresult.
But like games of chess or baseball, observation of many leads one torealize that there are patterns, rules of thumb, and tricks of the trade thatcan be found and exploited over and over again. The main purpose of thissection is to introduce three fundamental principles that recur, under variousdisguises, in many proofs: mathematical induction, the pigeonhole principle, anddiagonalization.The Principle of Mathematical Induction: Let A be a set of natural numbers .mch that24Chapter 1: SETS, RELATIONS, AND LANGUAGES°(1) E A, and(2) for each natural number n, if {O, 1, ... , n}~A, then n+ 1 E A.Then A = N.In less formal terms, the principle of mathematical induction states that anyset of natural numbers containing zero, and with the property that it containsn + 1 whenever it contains all the numbers up to and including n, must in factbe the set of all natural numbers.The justification for this principle should be clear intuitively; every naturalnumber must wind up in A since it can be "reached" from zero in a finitesuccession of steps by adding one each time.
Another way to argue the sameidea is by contradiction; suppose (1) and (2) hold but A f::. N. Then somenumber is omitted from A. In particular, let n be the first number among0,1,2, ... that is omitted from N.t Then n cannot be zero, since E A by (1);and since 0,1, ... , n - 1 ~ A by the choice of n, then n E A by (2), which is acontradiction.In practice, induction is used to prove assertions of the following form: "Forall natural numbers n, property P is true." The above principle is applied to theset A = {n : P is true of n} in the following way.(1) In the basis step we show that E A, that is, that P is true of 0.(2) The ind'uction hypothesis is the assumption that for some fixed but arbitraryn ~ 0, P holds for each natural number 0,1, ...
, n.(3) In the induction step we show, using the induction hypothesis, that P istrue of n + 1. By the induction principle, A is then equal to N, that is, Pholds for every natural number.°°Example 1.5.1: Let us show that for any n ~ 0, 1 + 2 + ...+n=n2:tn.Basis Step. Let n = 0. Then the sum on the left is zero, since there is nothingto add. The expression on the right is also zero.Induction Hypothesis. Assume that, for some n ~ 0, 1 + 2 + ...whenever m ~ n.t+m=m2:}mThis is a use of another principle, called the least number principle, that is actually equivalent to the principle of mathematical induction, so we are not really"proving" the principle of mathematical induction.
The least number principle is:If A <:;:; N and A i= N, then there is a unique least number n E N - A; that is, aunique number n such that n 1:. A but 0,1, ... ,n - 1 E A. A somewhat frivolousexample of the least number principle is the fact that there are no uninterestingnumbers. For s:Ippose there were; then there would have to be a least such number, say n. But then n would have the remarkable property of being the leastuninteresting number, which would surely make n interesting. "1.5: Three Fundamental Proof Techniques25Induction Step.1+ 2+'" + 71 + (71 + 1)+ 2 + ." + 71) + (71 + 1)271 +71- 2 - + (71 + 1) (by the induction hypothesis)71 2 + 71 + 271 + 2= (1=2(71+1)2+(71+1)2as was to be shown. <>Example 1.5.2: For any finite set A, 12AI = 21AI; that is, the cardinality of thepower set of A is 2 raised to a power equal to the cardinality of A.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
