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

Topic: The cardinality of the collection of all partitions of the natural
numbers equals that of the real numbers.

Replies: 14   Last Post: Mar 18, 2011 2:09 PM

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Butch Malahide

Posts: 894
Registered: 6/29/05
Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.

Posted: Mar 17, 2011 5:17 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

On Mar 17, 10:16 am, "Dave L. Renfro" <renfr...@cmich.edu> wrote:
> Kerry Soileau wrote:
> > Let P be the collection of all partitions of the natural numbers.
> > A partition of a set X is a pairwise disjoint collection of
> > sets whose union is X. I have a proof that the cardinality of P
> > is the cardinality of the real numbers. Is this well-known?
> > If so, would someone provide a reference?

>
> This seems to me to be around the average difficulty level of
> a problem in an undergraduate set theory or real analysis text,
> so it's not something anyone would bother citing a reference
> to if they wanted to use the result somewhere (and off-hand,
> I don't know of a specific reference, and all my books are at
> home and I'm elsewhere).


Exercise 6 on p. 76 of W. Sierpinski, _Cardinal and Ordinal Numbers_,
Second Edition Revised, Warszawa, 1965: "Prove that if X is the set of
all natural numbers, then the set Z of all partitions of the set N is
effectively of the power of the continuum." Here "effectively of the
power of the continuum" means that the equivalence is established by
an effectively definable bijection. The author provides a detailed
solution on the same page.

> To show that there are at least continuum many possible partitions
> of N, let E be the set of positive even integers. Then, for each
> subset B of E, the set {B, N - B} is a partition of N. Moreover,
> if B, B' are distinct subsets of E, then {B, N - B} is not equal
> to {B', N - B'}. Thus, there are at least continuum many partitions,
> since there are continuum many subsets of E.


Alternatively, you can associate with each real number a partition of
the set Q of rational numbers into two classes (Dedekind cuts), and
then use a bijection between Q and N.


Date Subject Author
3/17/11
Read The cardinality of the collection of all partitions of the natural
numbers equals that of the real numbers.
ksoileau
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Tony Orlow
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Tony Orlow
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Jack Markan
3/17/11
Read Re: The cardinality of the collection of all partitions of the natural numbers equals that of the real numbers.
David C. Ullrich
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Dave L. Renfro
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Butch Malahide
3/17/11
Read Re: The cardinality of the collection of all partitions of the natural numbers equals that of the real numbers.
fishfry
3/17/11
Read Re: The cardinality of the collection of all partitions of the natural numbers equals that of the real numbers.
fishfry
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Jack Markan
3/17/11
Read Re: The cardinality of the collection of all partitions of the natural numbers equals that of the real numbers.
fishfry
3/18/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Tony Orlow
3/18/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Jack Markan
3/18/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
David R Tribble
3/17/11
Read Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.
Jack Markan

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.