Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Bob Street

Posts: 63
Registered: 12/12/04
Re: Nathan counts the powerset
Posted: Dec 22, 1998 2:36 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply




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

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.