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: 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

 Messages: [ Previous | Next ]
 Dave L. Renfro Posts: 4,792 Registered: 12/3/04
Re: The cardinality of the collection of all partitions of the
natural numbers equals that of the real numbers.

Posted: Mar 17, 2011 11:16 AM

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).

It's well-known that there is a 1-1 correspondence between the
set of all possible partitions of a set and the set of all possible
equivalence relations on a set. Since each equivalence relation
on N (the set of natural numbers) is a subset of N x N, it follows
that an upper bound on the cardinality of partitions of N is the
cardinality of the power set of N x N, which is continuum.

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.

Dave L. Renfro

Date Subject Author
3/17/11 ksoileau
3/17/11 Tony Orlow
3/17/11 Tony Orlow
3/17/11 Jack Markan
3/17/11 David C. Ullrich
3/17/11 Dave L. Renfro
3/17/11 Butch Malahide
3/17/11 fishfry
3/17/11 fishfry
3/17/11 Jack Markan
3/17/11 fishfry
3/18/11 Tony Orlow
3/18/11 Jack Markan
3/18/11 David R Tribble
3/17/11 Jack Markan