Cardinality of a set of functions , $f:\mathbb N \to \mathcal{P}(\mathbb N)$

Question

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

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