Mathematics for Computer Science
5.2. Infinite Cardinality 93 For example, the most basic countably infinite set is the set,N, itself. But the set,Z, ofallintege ...
Chapter 5 Infinite Sets94 5.2.3 Power sets are strictly bigger Cantor’s astonishing discovery was thatnot all infinite sets are ...
5.3. The Halting Problem 95 Larger Infinities There are lots of different sizes of infinite sets. For example, starting with the ...
Chapter 5 Infinite Sets96 ment to prove that if an analysis program tries to recognize non-halting programs, it is bound to give ...
5.3. The Halting Problem 97 Proof. Namely, letSbe the set of ASCII strings, and for any strings 2 S, letf.s/ be the set of strin ...
Chapter 5 Infinite Sets98 commonlyintendedto be analyzable in order to confirm that they do what they’re supposed to do. So it’s ...
5.4. The Logic of Sets 99 sell’s Paradox^4 which reasons in nearly the same way as the proof of Cantor’s Theorem 5.2.6. This was ...
Chapter 5 Infinite Sets100 5.4.2 The ZFC Axioms for Sets It’s generally agreed that, using some simple logical deduction rules, ...
5.5. Does All This Really Work? 101 Foundation.There cannot be an infinite sequence 2xn22x 12 x 0 of sets each of which is ...
Chapter 5 Infinite Sets102 maybe Zermelo, just like Frege, didn’t get his axioms right and will be shot down by some successor t ...
5.5. Does All This Really Work? 103 5.5.1 Large Infinities in Computer Science If the romance of different size infinities and c ...
Chapter 5 Infinite Sets104 Lemma 5.2.3. LetAbe a set andb...A. IfAis infinite, then there is a bijection fromA[fbgtoA. Proof.Her ...
5.5. Does All This Really Work? 105 ZC/, of all pairs of positive integers: .1;1/;.1;2/;.1;3/;.1;4/;.1;5/;::: .2;1/;.2;2/;.2;3/; ...
Chapter 5 Infinite Sets106 thef-arrows define a bijection between theAandBelements on the path, or theg-arrows define a biject ...
5.5. Does All This Really Work? 107 where each set is “strictly smaller” than the next one by Theorem 5.2.6. LetPn.N/ be thenth ...
Chapter 5 Infinite Sets108 x2f0;1g. The details of the representation don’t matter, except that there ought to be a display pro ...
5.5. Does All This Really Work? 109 (b)An infinite sequence of the decimal digitsf 0 ; 1 ;:::; 9 gwill be calledlongif it has in ...
Chapter 5 Infinite Sets110 Problem 5.14. For any sets,A, andB, letŒA!Bçbe the set of total functions fromAtoB. Prove that ifAis ...
5.5. Does All This Really Work? 111 Problem 5.16. LetRWA!Abe a binary relation on a set,A. Ifa 1 R a 0 , we’ll say thata 1 is “R ...
...
«
1
2
3
4
5
6
7
8
9
10
»
Free download pdf
