Mathematics for Computer Science

7.1. Infinite Cardinality 213 Nowbis a function from real numbers to infinite bit strings.^1 It is not a total function, but it ...

Chapter 7 Infinite Sets214 Larger Infinities There are lots of different sizes of infinite sets. For example, starting with the ...

7.2. The Halting Problem 215 Here is why the diagonal argument has its name: we can form a sequenceDcon- sisting of the bits on ...

Chapter 7 Infinite Sets216 is, given an arbitrary program, to determine whether the program will run forever if it is not interr ...

7.2. The Halting Problem 217 Definition 7.2.1. No-haltWWDfs 2 ASCIIjPsapplied tosdoes not haltg: (7.3) We’re going to prove The ...

Chapter 7 Infinite Sets218 For example, most compilers do “static” type-checking at compile time to ensure that programs won’t m ...

7.3. The Logic of Sets 219 7.3 The Logic of Sets 7.3.1 Russell’s Paradox Reasoning naively about sets turns out to be risky. In ...

Chapter 7 Infinite Sets220 But denying thatW is a set means we mustrejectthe very natural axiom that every mathematically well-d ...

7.3. The Logic of Sets 221 Union. The union,u, of a collection,z, of sets is also a set: 8 z: 9 u: 8 x:. 9 y: x 2 yANDy 2 z/IFFx ...

Chapter 7 Infinite Sets222 7.3.3 Avoiding Russell’s Paradox These modern ZFC axioms for set theory are much simpler than the sys ...

7.4. Does All This Really Work? 223 Cantor’sContiuum Hypothesis: There is no set,A, such that NstrictAstrict pow.N/: The Continu ...

Chapter 7 Infinite Sets224 Problem 7.2. Show that the setf0;1gof finite binary strings is countable. Problem 7.3. Describe an e ...

7.4. Does All This Really Work? 225  jAjis undefined.  Ais countably infinite.  Ais uncountable.  Ais finite.  NsurjA.  8n ...

Chapter 7 Infinite Sets226 1.Cis finite. 2.Cis countable. 3.Cis uncountable. 4.Ccontains only finitely many non-integers. 5.Ccon ...

7.4. Does All This Really Work? 227 (a)Define a bijection between the set,ZC, of positive integers, and the set,.ZC ZC/, of all ...

Chapter 7 Infinite Sets228 (d)Show that for each type of path, either thef-arrows define a bijection between theAandBelements o ...

7.4. Does All This Really Work? 229 is one that has infinitely many occurrences of nonzero digits. LetLbe the set of all such lo ...

Chapter 7 Infinite Sets230 (b)Prove that ifC is a countable set andDis infinite, then there is a bijection betweenDandC[D. Probl ...

7.4. Does All This Really Work? 231 Problems for Section 7.2 Class Problems Problem 7.22. LetN!be the set of infinite sequences ...

Chapter 7 Infinite Sets232 set, leads to many important results in logic and computer science. In this problem we’ll apply that ...