
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


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

