-1

I attempted to prove that there's a surjective function $\mathbb{N} ^{|2^\mathbb{N}|} \rightarrow 2^\mathbb{N}$ and that there isn't one in the opposite way, however I wasn't able to prove the former.

Is there another way to prove this cardinal inequality?

Tarek Zoabi
  • 15

1 Answers1

2

That is quite easy to see. Clearly $\mathbb N^{2^\mathbb N}\geq 2^{2^\mathbb N}$ (as any function that maps into $\{0,1\}$ also maps into $\mathbb N$). But as $|2^A| = |\mathcal P(A)|$ for any set, and by a simple proof by cantor $\mathcal P(A)>A$ for any $A$, we get $$ 2^{2^\mathbb N} > {2^\mathbb N}$$ and thus your statement.

Lazy
  • 4,519
  • 1
    For the cantor property: Assume there is a bijection $f: A\to \mathcal P(A)$. Then any subset of $A$ has a unique preimage. Let $B$ be the set of all $x\in A$ so that $x\not\in f(x)$. Then there exists a $y\in A$ so that $f(y) = B$. Now, if $y\in B$ this is a contradiction, as then $y\not \in f(y) = B$. But if $y\not\in B$ then $y\not\in f(y)$ and thus $y\in B$. Also a contradiction. Thus such an $f$ cannot exists. – Lazy Sep 30 '21 at 20:02
  • Why, oh why, do you cast that as a proof by contradiction? Ugh. Don't. It's unnecessary. Assume $f\colon A\to \mathcal{P}(A)$ is any function. Let $B={x\in A\mid x\notin f(x)}$. Then for any $x$, if $x\in f(x)$ then $x\notin B$, so $f(x)\neq B$. If $x\notin f(x)$, then $x\in B$, hence $f(x)\neq B$. Thus, $B$ is not in the image of $f$, so $f$ is not surjective. QED – Arturo Magidin Sep 30 '21 at 20:33