Mathematics for Computer Science

4.4. Binary Relations 73 For another example, let’s take the “search for a 1 ” function,f 5. If we letXbe the set of binary word ...

Chapter 4 Mathematical Data Types74 a < b. Similarly, the subset relation relates a set,A, to another set,B, precisely whenA ...

4.4. Binary Relations 75 Some subjects in the codomain, SubNums, do not appear among this list of pairs—that is, they are not in ...

Chapter 4 Mathematical Data Types76  isbijectivewhen it has both theŒD 1 arrowoutçand theŒD 1 arrowinç property. From here on, ...

4.4. Binary Relations 77 pairs in graph.chrg/given above implies that f6.011, 6.881, 6.882, 6.UATgchrg.fG. Freeman;T. Engg/: Fi ...

Chapter 4 Mathematical Data Types78 Hint:PORQORRis equivalent to .PANDQ/OR.QANDR/OR.RANDP/OR.PANDQANDR/: Class Problems Problem ...

4.4. Binary Relations 79 second player picks the subset whose sole member is the third element. Both cases produce positions equ ...

Chapter 4 Mathematical Data Types80 Problems for Section 4.2 Homework Problems Problem 4.6. Prove that for any setsA,B,C, andD, ...

4.4. Binary Relations 81 For each of the following possible properties ofR, indicate whether it is always determined by graph.R ...

Chapter 4 Mathematical Data Types82 Class Problems Problem 4.10. Define asurjection relation, surj, on sets by the rule Definiti ...

4.4. Binary Relations 83 A arrows C M MAND.P IMPLIESM/ PANDQ Q PORQ PORQ NOT.PANDQ/ PXORQ (b)Circle the properties below possess ...

Chapter 4 Mathematical Data Types84 Problem 4.13. Letf WA!BandgWB!Cbe functions. (a)Prove that if the compositiongıf is a biject ...

4.4. Binary Relations 85 This agrees with the Definition 4.3.1 of composition in the special case whenR andSare functions. We ca ...

...

5 Infinite Sets This chapter is about infinite sets and some challenges in proving things about them. Wait a minute! Why bring u ...

Chapter 5 Infinite Sets88 5.1 Finite Cardinality A finite set is one that has only a finite number of elements. This number of e ...

5.1. Finite Cardinality 89 Proof. We’ve already given an “arrow” proof of implication 1. Implication 2. fol- lows immediately fr ...

Chapter 5 Infinite Sets90 For example, the three-element setfa 1 ;a 2 ;a 3 ghas eight different subsets: ; fa 1 g fa 2 g fa 1 ;a ...

5.2. Infinite Cardinality 91 enemies in his own time because of his work: the general mathematical commu- nity doubted the relev ...

Chapter 5 Infinite Sets92 pretty technical. Just because there is a surjective functionf WA!B—which need not be a bijection —and ...