|
|
Re: Nathan counts the powerset
Posted:
Dec 22, 1998 2:36 PM
|
|
Ulrich Weigand wrote in message
<75k0a2$hfb@faui11.informatik.uni-erlangen.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 non-integer 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 digit-set, 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 digit-set by mapping onto {0, 1, ..., #D-1},
ensuring that the element of the digit-set designated as 'nine'
maps to #D-1, 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.
|
|
