不可数集

1 .Uncountable Sets 2/22/12 1

2 .Countably Infinite 2/13/12 2 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 i s a bijection from Natural Numbers → Integers

3 .I nfinite S izes Are all infinite sets the same size? NO! Cantor’s Theorem shows how to keep finding bigger infinities. 2/22/12 3

4 .P( N ) How many sets of natural numbers? The same as there are natural numbers? Or more? 2/22/12 4

5 . C ountably Infinite Sets ::= { finite bit strings} … is countably infinite 2/22/12 5 Proof: List strings shortest to longest, and alphabetically within strings of the same length

6 . C ountably infinite Sets = { e , 0, 1, 00, 01, 10, 11, …} 2/22/12 6 = { e , 0, 1, 00, 01, 10, 11, 000, … } = { f(0), f(1), f(2), f(3), f(4), …}

7 . Unc ountably Infinite Sets Claim: : := { ∞ -bit strings } is uncountable . 2/22/12 7 What about infinitely long bit strings? Like infinite decimal fractions but with bits

8 .Diagonal Arguments Suppose 0 1 2 3 . . . n n+1 . . . s 0 0 0 1 0 . . . 0 0 . . . s 1 0 1 1 0 . . . 0 1 . . . s 2 1 0 0 0 . . . 1 0 . . . s 3 1 0 1 1 . . . 1 1 . . . . . . 1 . . . 1 . . 0 2/22/12 8

9 .Diagonal Arguments Suppose 0 1 2 3 . . . n n+1 . . . s 0 0 0 1 0 . . . 0 0 . . . s 1 0 1 1 0 . . . 0 1 . . . s 2 1 0 0 0 . . . 1 0 . . . s 3 1 0 1 1 . . . 1 1 . . . . . . 1 . . . 1 . . 0 0 0 0 0 1 1 1 2/22/12 9

10 .So cannot be listed: this diagonal sequence will be missing …differs from every row! Diagonal Arguments Suppose 0 0 0 0 1 1 1 ⋯ 2/22/12 10

11 .Cantor’s Theorem For every set, A (finite or infinite) , there is no bijection A↔P(A) 2/22/12 11

12 .There is no bijection A↔P(A) W::= {a ∈ A | a ∉ f(a)} , so for any a, a ∈ W iff a ∉ f(a) . f is a bijection , so W=f(a 0 ) , for some a 0 ∈ A . ( ∀ a) a ∈ f(a 0 ) iff a ∉ f(a ) . Pf by contradiction: suppose f:A↔P(A ) is a bijection . Let Pf by contradiction: 2/22/12 12

13 .There is no bijection A↔P(A) W::= {a ∈ A | a ∉ f(a)} , so for any a , a ∈ W iff a ∉ f(a) . f is a bijection , so W=f(a 0 ) , for some a 0 ∈ A . a ∈ f(a 0 ) iff a ∉ f(a ) . Pf by contradiction: suppose f:A↔P(A ) is a bijection . Let Pf by contradiction: 0 0 0 contradiction 2/22/12 13

14 .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