Cardinality of $P(\mathbb{R})$ and $P(P(\mathbb{R}))$

Question

What is cardinality of $P(\mathbb{R})$? And $P(P(\mathbb{R}))$?

P is a Power Set, $\mathbb{R}$ is set of real numbers.

In general - how can find cardinality of different sets? Is/are there a good method(s)? And is there some kind of handout, that provides list of cardinality of popular sets ($\mathbb{R}$, $\mathbb{Q}$, $P(\mathbb{Q})$) etc.?

And, how to find cardinality of sets of functions? For example, what is the cardinality of set that contains all functions? What about set of functions $f: \mathbb{N} \to \mathbb{R}$?

Answer 1

Cardinal arithmetic and diagonalization.

The cardinality of the power set is $2^{|X|}$, which is why we write the power set as $2^X$, which also represents the set of characteristic functions of subsets of $X$ (i.e. the set of functions $X\to\{0,1\})$.

This is very cool when you first realize it: A function of the form above is determined by its elements. Given such a function $f: X\to\{0,1\}$, let $S_f:=f^{-1}(1)$ be the subset defined by $f$, and given a subset $S\subseteq X$, let $f_S$ denote the characteristic function of $S$ with respect to $X$. Then we see immediately that these functions $S_{(-)}:\{0,1\}^X\to \mathcal{P}(X)$ and $f_{(-)}: \mathcal{P}(X)\to \{0,1\}^X$ are inverse to one another. Therefore, it follows that the power set is precisely a function set as noted above. Edit: I should note that in abstract nonsense language, this means that that $2=\{0,1\}$ is the "subobject classifier" for the category of sets.

To see that $|\mathbf{R}^\mathbf{N}|=|\mathbf{R}|$, notice that this becomes $(2^\mathbf{N})^\mathbf{N}\cong 2^{\mathbf{N}\times \mathbf{N}}\cong 2^\mathbf{N}\cong \mathbf{R}$, where $\cong$ here represents an isomorphism of sets, or a bijective function (baby Rudin calls this equivalence relation "equipotence").

To find that $|\mathbf{R}|=2^{|\mathbf{N}|}$, this is a matter of using the technique called diagonalization.

To find that the integers and rationals represent the same cardinal as $\mathbf{N}$, you have to do a little bit of tricky encoding, but it is easy to find on the page about cardinality on wikipedia.

To see a worked out proof of why $|2^X|>|X|$ for any set $X$, look at this whimsical link.

Answer 2

As for the set of functions $f:\mathbb{N} \rightarrow \mathbb{R}$, consider the functions $f:\mathbb{N} \rightarrow \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ (i.e. the functions that map each natural number to a single base-10 digit) and compare that to the closed interval $[0, 1]$. What conclusions can you then draw about the set of all functions $f:\mathbb{N} \rightarrow A$ where $A$ is a countably infinite set? And so what conclusions can you draw about the set of all functions $f:\mathbb{N} \rightarrow \mathbb{R}$?

Answer 3

Let $X$ be any set. Then, the cardinality of $\mathcal{P}(X)$ is $\left| 2^X \right| = 2^{|X|}$, since there is a bijection $\mathcal{P}(X) \to 2^X$, where $2^X$ is the set of all functions $X \to \{0, 1\}$. I'm afraid this is best answer that I can give, since, for example, it is not possible to prove that $\aleph_1 = | \mathcal{P}(\mathbb{N}) |$, or that $\aleph_1 \ne | \mathcal{P}(\mathbb{N}) |$, from the usual axioms of mathematics (ZFC).

In terms of aleph numbers, the cardinalities of $\mathbb{R}$, $\mathbb{Q}$, and $\mathcal{P}(\mathbb{Q})$ are $2^{\aleph_0}$, $\aleph_0$, and $2^{\aleph_0}$, respectively. $\aleph_0 = | \mathbb{N} |$ by definition. Here's an interesting fact: the set of all functions $\mathbb{R} \to \mathbb{R}$ has cardinality strictly greater than $| \mathbb{R} |$, but the subset of all continuous functions has cardinality equal to $| \mathbb{R} |$. (Can you prove this?)

Now, as for the "set" of all functions — this isn't a well-defined set under ZFC. So you can't talk about the cardinality. However, if you fix the domain and codomain, then we do get a set, and we write $Y^X$ for the set of all functions $X \to Y$. The cardinality, as the notation suggests, is $|Y|^{|X|}$. (Actually, this is a small lie. We define the notation $|Y|^{|X|}$ to mean $\left| Y^X \right|$. But it happens to agree with the arithmetic definition of exponentiation in the case where $X$ and $Y$ are finite sets.)

Answer 4

If you are willing to assume the Generalized Continuum Hypothesis (GCH), then the cardinalities in question are simply $\aleph_2$ and $\aleph_3$, i.e., the third and fourth smallest infinite cardinals.

However, I don't know anyone seriously interested in set theory who wants to assume GCH: it's basically assuming away all of the subtleties of cardinal exponentiation. But without this assumption, I don't think the OP's question has a good answer.

I agree that a "cheatsheet" of cardinalities of commonly encountered infinite sets would be a nice thing, and on that sheet one of the lines would read $\mathbb{2}^{\mathbb{R}}$: i.e., this is the simplest description of a certain cardinality of sets, and one could then rather list other sets which happen to be equinumerous with it: the number of topologies on a countably infinite set,$\ldots$

Answer 5

Glib answer:

If you feel like it, you can assume that $|\mathbb{R}|=\aleph_{7}$, $|P(\mathbb{R})|=\aleph_{13}$, and $|P(P(\mathbb{R}))|=\aleph_{\aleph_{\omega_3+4}}$.

Less glib:

as other posters have pointed out, the descriptions as power-sets is generally the simplest description. One of the reasons is that the standard axioms of set-theory (ZFC) do not "pin down" the cardinalities of these sets in terms of the alephs ($\aleph$). A technique called "forcing" (in particular "Easton forcing") shows that it is consistent that the cardinalities of power-sets can be just about anything. There are a few constraints coming from cardinal arithmetic ($\alpha<\beta$ implies $2^\alpha\leq2^\beta$, $\text{cof}(2^\alpha)>\text{cof}(\alpha)$), but they are very weak. Thus it is consistent that we have:

$\aleph_0 < \aleph_1 < \aleph_2=2^{\aleph_0}=|\mathbb{R}| < \aleph_3 $ ${} < \cdots < \aleph_{\omega+1} = 2^{\aleph_1} = 2^{\aleph_2} = |P(\mathbb{R})| $ ${} < \aleph_{\omega+2} = 2^{\aleph_3} = 2^{\aleph_4} = \cdots = 2^{\aleph_\omega} = 2^{\aleph_{\omega+1}} = |P(P(\mathbb{R}))|$ etc.

(But we could not have $2^{\aleph_0}=\aleph_\omega$ due to the cofinality restriction.)

On the other hand, GCH would say that $2^{\aleph_{\alpha}}=\aleph_{\alpha+1}$ for any ordinal $\alpha$ (in particular, $|\mathbb{R}|=\aleph_1$, $|P(\mathbb{R})|=\aleph_2$, and $|P(P(\mathbb{R}))|=\aleph_3$ as pointed out above) and GCH is also consistent.

Note that I am not claiming that these wild cardinal arithmetics are natural or reasonable, simply that they are consistent and one needs further assumptions to pin down the cardinalities of power-sets in terms of alephs; and thus it's hard to give the kind of answers we might want for "what is the cardinality of $P(\mathbb{R})$?" for example...