Calculate the cardinality of the following sets:

$A=\{f:\mathbb N \to \mathcal{P}(\mathbb N) : n \in f(n) \space \forall \space n \}$

$B=\{f:\mathbb N \to \mathcal{P}(\mathbb N) : n \notin f(n) \space \forall \space n \}$

My attempt at a solution (corrected after Greg's comments).

I define $S=\{f:\mathbb N \to \mathcal{P}(\mathbb N)\: f(n)=\{n,2n\} \space \vee \space f(n)=\{n,3n\}\}$. Then, for each $n$, $f(n)$ can take two values. Clearly, $S \subset A$ and $|S|=2^{\aleph_0}=c$, so $c=|S|\leq |A|.

Now, I define $S'=\{f:\mathbb N \to \mathcal{P}(\mathbb N)\: f(n)=\{2n,3n\} \space \vee \space f(n)=\{3n,4n\}\}$. Note that $S' \subset B$ and, as in the other case, $f(n)$ can take two values for each $n \in \mathbb N$, then $c=2^{\aleph_0} =|S'|\leq |B|\leq c \implies |B|=c$.

A candidate for cardinal of both sets $A$ and $B$ is the cardinal $c$. I've proved that $c\leq |A|$ and $c\leq |B|$. Now, I would like to show that $|A|,|B|\leq c$. There are two ways I thought of proving these:

1) Find sets $P$, $P'$ such that $A \subset P$ ,$B \subset P'$ and $|P|=c=|P'|$.

2) Try to define an injective function from $A$ ($B$ respectively) or $A \cup B$ to a set with cardinality $c$.

  • $\begingroup$ It should be pointed out that $\aleph$ without an index usually either denotes an arbitrary cardinal (although this is a bad notation); or more commonly it is a symbol for $2^{\aleph_0}$, much like $\frak c$. I suppose that you meant to write $\aleph_0$ wherever you wrote $\aleph$. $\endgroup$
    – Asaf Karagila
    Dec 1, 2013 at 8:33
  • 1
    $\begingroup$ Just because there are only two statements $n\in f(n)$ and $n\notin f(n)$ that can hold, that doesn't mean there are only two possible different functions. The same reasoning, concerning functions from $\{1\}$ to $\mathcal P(\mathbb N)$, would imply that there are only two such functions, when in fact there is such a function for each element of $\mathcal P(\mathbb N)$. The cardinality of the set of functions from $\mathbb N$ to $\mathcal P(\mathbb N)$ is equal to the cardinality of $\mathcal P(\mathbb N)$ raised to the power of the cardinality of $\mathbb N$, just like any space of functions. $\endgroup$ Dec 1, 2013 at 9:06
  • 1
    $\begingroup$ But note also that $A\cup B$ is not equal to the set of all functions from $\mathbb N$ to $\mathcal P(\mathbb N)$: there are functions not in either $A$ or $B$. So it's possible that their cardinalities are rather smaller than $\aleph_0^{2^{\aleph_0}}$. $\endgroup$ Dec 1, 2013 at 9:07
  • $\begingroup$ @Greg Martin I understood your correction, you're right, for example, for the set $A$, each $n$ has more than two possibilities: I could send $n$ to any subset of the natural numbers that contains $n$ (there are clearly more than two options for each $n$). How could I find a set $P$ such that $P=c$ and $A \subset P$ (or $B \subset P$?) Or maybe it's easier if I can make an injection from the set $A$ ($B$ respectively) to another set with cardinality $c$. $\endgroup$
    – user100106
    Dec 1, 2013 at 16:17

1 Answer 1


The cardinality of the entire set of functions $f\colon \mathbb N \to \mathcal P(\mathbb N)$ equals $(2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0\cdot \aleph_0} = 2^{\aleph_0} = c$.

Or, let $\mathcal F(S,T)$ denote the set of functions from $S$ to $T$. Note that $\mathcal P(S)$ is (canonically) isomorphic to $\mathcal F(S,\{0,1\}$); note also that $\mathcal F(S,\mathcal F(T,U))$ is (canonically) isomorphic to $\mathcal F(S\times T,U)$. (This latter statement is what proves the cardinal equality $(u^t)^s = u^{t\cdot s}$.) Therefore $$ \mathcal F(\mathbb N, \mathcal P(\mathbb N)) \cong \mathcal F(\mathbb N, \mathcal F(\mathbb N, \{0,1\})) \cong \mathcal F(\mathbb N \times \mathbb N,\{0,1\}) \cong \mathcal F(\mathbb N,\{0,1\}) \cong \mathcal P(\mathbb N). $$

Either argument shows that the upper bound of $c$ for the cardinalities of $A$ and $B$ is trivial, and you've already proved the lower bound.

Alternatively, given any number $n\in\mathbb N$ and any set $S\in\mathcal P(\mathbb N)$, define two shift operators \begin{align*} G_0(n,S) &= \big( S \cap \{1,2,\dots,n-1\} \big) \cup \big( (S+1) \cap \{n+1,n+2,\dots\} \big) \\ G_1(n,S) &= \big( S \cap \{1,2,\dots,n-1\} \big) \cup \{n\} \cup \big( (S+1) \cap \{n+1,n+2,\dots\} \big) \end{align*} (where $S+1 = \{s+1\colon s\in S\}$). Then define two functions $H_0,H_1\colon \mathcal F(\mathbb N,\mathcal P(\mathbb N)) \to \mathcal F(\mathbb N,\mathcal P(\mathbb N))$ by $$ H_0(F)(n) = G_0(n,F(n)) \quad\text{and}\quad H_1(F)(n) = G_1(n,F(n)). $$ You can then check that both $H_0$ and $H_1$ are injective and that their ranges are $B$ and $A$, respectively. This gives a bijective proof that the cardinalities of $A$ and $B$ equal the cardinality of the set of all functions from $\mathbb N$ to $\mathcal P(\mathbb N)$.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .