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

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}$?

-
cusier: The cardinality of ${\mathcal P}(X)$ is the same as the size of the set of functions from $X$ into $\{0,1\}$, usually denoted $2^{|X|}$. Beyond this, for infinite $X$ not much can be said. We know that $2^{|X|}>|X|$ but the usual axioms of set theory cannot tell you how much larger $2^{|X|}$ must be. – Andrés E. Caicedo Jan 2 '11 at 17:04
Should this be tagged [elementary-set-theory]? – Nuno Jan 2 '11 at 20:03

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

-
You clearly misunderstood the last question. His question was not about the "set of all functions" (an object which is isomorphic (or at the very least equivalent) to the category of functors $\Delta^1\to Set$ (using universes, this is not completely asinine)), but about the "cardinality of a function set", that is to say, a hom-set between sets. – deeeez Jan 2 '11 at 18:25

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$

-
you can find a good cheatsheat here: en.wikipedia.org/wiki/Beth_number – deoxygerbe Jan 2 '11 at 18:28

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.

-
@deeeez: you've written down some facts about cardinal arithmetic that would be nice answers to some questions, but I don't see how they address the specific question of the OP. Yes, the cardinality of the power set of $\mathbb{R}$ is $2^{\mathbb{R}}$, i.e., the cardinality of the set of all functions from $\mathbb{R}$ to a $2$-element set. But that's almost a tautology. Moreover, I don't know a good answer to this question: i.e., I don't know how to describe this cardinal in any simpler way than "the cardinality of the power set of $\mathbb{R}$". – Pete L. Clark Jan 2 '11 at 17:04
@Pete, yes. There is no better way to describe it. That was essentially my point. – deeeez Jan 2 '11 at 17:09
@deeeez: okay, fair enough. – Pete L. Clark Jan 2 '11 at 17:14
This is great, but I feel as though it would be even more helpful if you added an explanation for why $2^{X} > X$ even when $X$ is a transfinite cardinal. Then at least it would resolve the question of whether or not $|\mathcal{P}(\mathbb{R})| = |\mathbb{R}|$ – Alex Basson Jan 2 '11 at 17:17
@Alex: Given $f:X\to{\mathcal P}(X)$, Cantor considered the set $A=\{a\in X\mid a\notin f(a)\}$ and showed that $A\ne f(b)$ for any $b\in X$: If $A=f(b)$, then $b\in A$ iff (by definition of $A$) $b\notin f(b)$, i.e., $b\in A$ iff $b\notin A$. This is a contradiction, and it follows that $A$ is not in the range of $f$. The definition of $A$ is an instance of diagonalization, as deeeez points out. – Andrés E. Caicedo Jan 2 '11 at 19:29

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

-

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}$?

-
Ok, I see what You mean, but what is cardinality of set containing these functions ($f:\mathbb{N} \rightarrow \mathbb{R}$)? And what about $f:\mathbb{R} \rightarrow \mathbb{N}$ set? – cusier Jan 2 '11 at 17:05
@cusier: as deeeez says, the set of functions $f:\mathbb{N} \rightarrow \mathbb{R}$ has cardinality $|\mathbb{R^{N}}|=|\mathbb{R}|$ and the set of functions $f:\mathbb{R} \rightarrow \mathbb{N}$ has cardinality $|\mathbb{N^R}|=|2^{\mathbb{R}}|$ – Ross Millikan Jan 2 '11 at 19:13

cardinality of P(R) is beth-2,cardinality of P(P(R)) is beth-3.if we don't assume GCH,we don't know which aleph it is.here is the definition of beth numbers,beth-0=aleph-0,beth-(x+1)=2^beth-x (power set),

-