3
$\begingroup$

Find the cardinality of $A=\{f: \mathbb{N} \rightarrow \mathbb{P}(\mathbb{N}) \mid (\forall n ) ( n \in f(n) ) \}$.

I know $A\subseteq \mathbb{P}(\mathbb{N})^{\mathbb{N}}$, so ${\#}A \leq \mathfrak{c}$.

I want to show the other inequality by defining a function $\phi: \mathbb{P}(\mathbb{N}) \rightarrow A$. If $K \subseteq \mathbb{N}$ then $\phi(K)=f_{K}$ where $f_{K}: \mathbb{N} \rightarrow \mathbb{P}(\mathbb{N})$ is defined by $$f_{n}= \begin{cases} K, &\text{if }n \in K \\ \{ n \}, &\text{if }n \notin K. \end{cases} $$

Is this correct? If so how can I prove this function is injective. If I prove that then I think I prove ${\#}A=\mathfrak{c}$.

$\endgroup$
3
$\begingroup$

$\phi$ is not one-to-one, but allmost: All singletons are mapped to the same function. For each $m,n$ we have $$ \phi(\{m\})(n) = f_{\{m\}}(n) = \{n\} $$ so $\phi(\{m\}) = \phi(\{m'\})$, every $m, m'$.

But if $|K| \ge 2$, and $K \ne L$, choose $n \in K$, if $n \not\in L$, then $$ f_K(n) = K \ne \{n\} = f_L(n) $$ and if $n\in L$, then $$ f_K(n) = K \ne L = f_L(n) $$ Hence $f_K \ne f_L$. As there are only $\aleph_0$ singletons in $\mathbb P(\mathbb N)$, the set $B := \{ K \in \mathbb P(\mathbb N)\mid |K| \ge 2\}$ has cardinality $\mathfrak c$. As - we showed this above - $\phi|_B \colon B \to A$ is one-to-one, $\mathfrak c = |B| \le |A|$.

So, by Schröder-Bernstein, $|A| = \mathfrak c$.

$\endgroup$
  • $\begingroup$ thanks a lot for the answer! $\endgroup$ – Maxi Dec 7 '13 at 14:43
1
$\begingroup$

martini seems to have aptly answered the immediate problem, so I'll give an alternate method of showing the inequality $\mathfrak{c} \leq |A|$.

Consider the following subset of $A$: $$A^\prime = \{ f \in A : ( \forall n \neq 33687 )( f(n) = \{ n \} ) \}.$$ Note that the mapping $\psi : A^\prime \to \mathcal{P} ( A )$ defined by $\psi(f) = f(33687)$ is one-to-one, and the range of $\psi$ is $\{ K \subseteq \mathbb{N} : 33687 \in K \}$. As this set can easily be put into one-to-one correspondence with $\mathcal{P} ( \mathbb{N} )$ it follows that $\mathfrak{c} = | \{ K \subseteq \mathbb{N} : 33687 \in K \} | = | A^\prime | \leq |A|$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.