Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: Nathan counts the powerset
Replies: 144   Last Post: Jan 26, 1999 9:26 AM

 Messages: [ Previous | Next ]
 Bob Street Posts: 63 Registered: 12/12/04
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.

Date Subject Author
12/20/98 Nathaniel Deeth
12/20/98 Ulrich Weigand
12/20/98 Bob Street
12/20/98 Ulrich Weigand
12/22/98 Bob Street
12/22/98 Ulrich Weigand
12/21/98 Nathaniel Deeth
12/21/98 Ulrich Weigand
12/24/98 Nathaniel Deeth
12/24/98 Dik T. Winter
12/25/98 Nathaniel Deeth
12/26/98 Dik T. Winter
12/27/98 jsavard@ecn.ab.ca
12/28/98 Math Icon
12/28/98 David C. Ullrich
12/25/98 Nathaniel Deeth
12/21/98 graham_fyffe@hotmail.com
12/22/98 Nathaniel Deeth
12/24/98 Nathaniel Deeth
12/21/98 David C. Ullrich
12/22/98 Nathaniel Deeth
12/22/98 Bob Street
12/23/98 Nathaniel Deeth
12/24/98 Bob Street
12/25/98 Nathaniel Deeth
12/25/98 Bob Street
12/26/98 Bob Street
12/24/98 Bob Street
12/24/98 Virgil Hancher
12/25/98 Nathaniel Deeth
12/27/98 jsavard@ecn.ab.ca
12/28/98 Robert Harrison
12/22/98 Bob Street
12/22/98 Ulrich Weigand
12/23/98 David C. Ullrich
12/24/98 Nathaniel Deeth
12/24/98 Bob Street
12/25/98 Nathaniel Deeth
12/24/98 David C. Ullrich
12/24/98 Bob Street
12/25/98 Nathaniel Deeth
12/25/98 Nathaniel Deeth
12/25/98 Bob Street
12/25/98 Nathaniel Deeth
12/25/98 Arturo Magidin
12/26/98 Bob Street
12/27/98 Nathaniel Deeth
12/27/98 Nathaniel Deeth
12/28/98 Arturo Magidin
12/28/98 Bob Street
12/30/98 Nathaniel Deeth
12/30/98 Bob Street
12/30/98 Matt Brubeck
12/30/98 Nathaniel Deeth
12/30/98 Bob Street
12/31/98 Nathaniel Deeth
12/31/98 Bob Street
12/31/98 modern life is rubbish
1/3/99 Nathaniel Deeth
1/1/99 standebj@SLU.EDU
1/3/99 Nathaniel Deeth
1/5/99 Bob Street
12/26/98 David C. Ullrich
12/27/98 Nathaniel Deeth
12/28/98 Math Icon
12/28/98 David C. Ullrich
12/25/98 Robert Harrison
12/25/98 Robert Harrison
12/26/98 David C. Ullrich
12/26/98 David C. Ullrich
12/26/98 David C. Ullrich
12/26/98 Bob Street
12/27/98 jsavard@ecn.ab.ca
12/28/98 Nathaniel Deeth
12/28/98 Ronald Bruck
12/28/98 feldmann4350@my-dejanews.com
12/29/98 John Savard
12/30/98 Nathaniel Deeth
12/31/98 Bob Street
12/31/98 Nathaniel Deeth
12/31/98 John Savard
12/31/98 Planar
1/2/99 Bob Street
1/3/99 Nathaniel Deeth
1/5/99 Bob Street
1/3/99 Nathaniel Deeth
1/26/99 Clothes Rod
12/31/98 Planar
1/3/99 Nathaniel Deeth
1/3/99 David C. Ullrich
1/4/99 Bob Street
1/4/99 John Savard
12/31/98 John Savard
1/3/99 Nathaniel Deeth
1/3/99 standebj@SLU.EDU
1/4/99 John Savard
12/31/98 Dave Seaman
1/3/99 Nathaniel Deeth
1/3/99 Ian Storey
1/4/99 Dave Seaman
12/31/98 John Savard
1/3/99 Nathaniel Deeth
1/4/99 John Savard
12/28/98 Bob Street
12/21/98 Nathaniel Deeth
12/21/98 Ulrich Weigand
12/22/98 Nathaniel Deeth
12/22/98 Ulrich Weigand
12/24/98 Nathaniel Deeth
12/24/98 David C. Ullrich
12/28/98 Nathaniel Deeth
12/28/98 Nathaniel Deeth
12/28/98 David C. Ullrich
12/30/98 Nathaniel Deeth
12/31/98 David C. Ullrich
1/1/99 standebj@SLU.EDU
1/3/99 Nathaniel Deeth
1/3/99 standebj@SLU.EDU
12/24/98 Ulrich Weigand
12/28/98 Nathaniel Deeth
12/20/98 David C. Ullrich
12/21/98 Kirby Cook
12/21/98 Nathaniel Deeth
12/21/98 John Starrett
12/21/98 Kirby Cook
12/21/98 John Savard
12/21/98 Jeremy Boden
12/21/98 John Savard
12/22/98 Nathaniel Deeth
12/22/98 Bob Street
12/22/98 John Savard
12/21/98 Barrie Snell
12/22/98 David C. Ullrich
12/23/98 Barrie Snell
12/22/98 Bob Street
12/22/98 zenevsky@wwa.com
12/23/98 Bob Street
12/22/98 John Starrett
12/22/98 Jeremy Boden
12/22/98 Jeremy Boden
12/23/98 Jeremy Boden
12/24/98 David C. Ullrich
12/24/98 John Starrett
12/30/98 Jeremy Boden
12/31/98 brian tivol