
Re: Nathan counts the powerset
Posted:
Dec 22, 1998 2:36 PM


Ulrich Weigand wrote in message <75k0a2$hfb@faui11.informatik.unierlangen.de>... >"Bob Street" <bob@belgrave.clara.net> writes: > >>Ulrich: Proof of the uncountability of the complete powerset of N? > >>Can/Do we rejig the above proof using noninteger binary values (placing all >>the digits after the binary point, as opposed to before it, thus allowing >>infinitely many digits) to map the powerset of N onto the unit real >>interval, and hence parallel the proof for the uncountability of R? > >Yup, that would work. On the other hand, Cantor's diagonal method can >be formulated even *simpler* for the power set of N than for R: > >Take any countable list of subsets of N, say X_1, X_2, X_3, X_4, ... >Construct an new subset Y of N be defining > Y := { n \in N  n \not\in X_n } > >Obviously, Y <> X_1, Y <> X_2, ..., hence our countable list did not >list all subsets of N. This applies to any countable list, hence the >power set of N is uncountable. > >(I really prefer this version of Cantor's argument to the one formulated >in terms of R, since here we completely avoid all that quibble about what >a real number really is, whether we need to distinguish real numbers from >their representations as infinite decimals, what about 0.9999... and so >on :/) >
Yeah, that's nicer.
I remember having vague misgivings when I first saw Cantor's Diagonal to prove the uncountability of [0, 1) (hence R), but forgot them when I couldn't put them into words.
You've just clarified the matter for me:
The proof as originally presented to me doesn't actually prove the uncountability of [0, 1), it merely proves the uncountability of the set of all infinite sequences of digits (where 'digit' can be generalized to mean an element of a given set, D, with #D > 1)
Fortunately, I think it's fairly easy to work round this  with careful wording, we can make the number/representation issue irrelevent.
We deal with the .999... problem by removing them from consideration, i.e. we construct a 'complete list' of sequences of digits which do not 'end' 999.... then ensure that the constructed diagonal doesn't end 999....
(For a general digitset, we designate one element of D to be 'nine')
We thus prove this set to be uncountable, and note that each element of this set of all sequences of digits maps to an element of [0,1):
f(<a,b,c,d,...>) = 0.abcd....
(paralleled for a general digitset by mapping onto {0, 1, ..., #D1}, ensuring that the element of the digitset designated as 'nine' maps to #D1, and representing in base #D)
S := (x in [0,1) : exists <a,b,c,d,...> with f(<a,b,c,d,...>) = x)
(S is the 'representable subset' of [0,1))
(*)
and that this mapping is a bijection (because we didn't consider the <a,b,c,...,9,9,9,9,...> sequences)
Hence S is uncountable. (It's isomorphic to an uncountable set) Hence [0,1) is uncountable. (It's a superset of S) Hence R is uncountable. (It's a superset of [0,1))
(*) We may reasonably conjecture that S == [0,1), but whether or not this is so is not relevent to the proof.

