
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 wellknown? > 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 offhand, I don't know of a specific reference, and all my books are at home and I'm elsewhere).
It's wellknown that there is a 11 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

