Report

Uncountable Sets 2/22/12 1 Countably Infinite There are as many natural numbers as integers 0 1 2 3 4 5 6 7 8… 0, -1, 1, -2, 2, -3, 3, -4, 4 … f(n) = n/2 if n is even, -(n+1)/2 if n is odd is a bijection from Natural Numbers → Integers 2/13/12 2 Infinite Sizes Are all infinite sets the same size? NO! Cantor’s Theorem shows how to keep finding bigger infinities. 2/22/12 3 P(N) • How many sets of natural numbers? • The same as there are natural numbers? • Or more? 2/22/12 4 Countably Infinite Sets ::= {finite bit strings} … is countably infinite Proof: List strings shortest to longest, and alphabetically within strings of the same length 2/22/12 5 Countably infinite Sets = {e, 0, 1, 00, 01, 10, 11, …} = { e, = { f(0), 0, 1, f(1), f(2), 00, 01, 10, 11, f(3), f(4), …} 000, … } 2/22/12 6 Uncountably Infinite Sets What about infinitely long bit strings? Like infinite decimal fractions but with bits Claim: ::= {∞-bit strings} is uncountable. 2/22/12 7 Diagonal Arguments Suppose 0 1 2 3 . . . n n+1 . . . s0 s1 s2 s3 0 0 1 0 . . . 0 0 . . . 0 1 1 0 . . . 0 1 . . . 1 0 0 0 . . . 1 0 . . . 1 0 1 1 . . . 1 1 . . . . . . . . . 2/22/12 1 . 1 . 0 8 Diagonal Arguments • Suppose 0 1 2 3 . . . n n+1 . . . s0 s1 s2 s3 10 0 1 0 . . . 0 0 . . . 0 01 1 0 . . . 0 1 . . . 1 0 10 0 . . . 1 0 . . . 1 0 1 01 . . . 1 1 . . . . . . . . . 2/22/12 01 . 01 . 10 9 Diagonal Arguments Suppose 1 ⋯ 0 …differs from every row! 1 So cannot be listed: 0 this diagonal sequence 0 0 will be missing 1 2/22/12 10 Cantor’s Theorem For every set, A (finite or infinite), there is no bijection A↔P(A) 2/22/12 11 There is no bijection A↔P(A) Pf by contradiction: suppose f:A↔P(A) is a bijection. Let W::= {a A | a f(a)}, so for any a, a W iff a f(a). f is a bijection, so W=f(a0), for some a0 A. (∀a) a f(a0) iff a f(a ). 2/22/12 12 There is no bijection A↔P(A) Pf by contradiction: suppose f:A↔P(A) is a bijection. Let W::= {a A | a f(a)}, so for any a, a W iff a f(a). f is a bijection, so W=f(a0), for some a0 A. 2/22/12 a f(a0) iff a f(a ). 0 0 contradiction 0 13 So P(N) is uncountable P(N) = set of subsets of N ↔ {0,1}ω ↔ infinite “binary decimals” representing reals in the range 0..1 2/22/12 14