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}$?
Best Answer
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.)