# Given a surjection $f:\mathbb{N}\to\mathcal{P}(X)$, how can one construct an injection $X\to\mathbb{N}$?

I'm proving that $|X|\leq^*\mathbb{N}$ iff $\mathbb{N}\leq\mathcal{P}(X)$. One direction is trivial, but I'm not sure how to proceed for the other direction. Any suggestions?

Update

My apologies. The result as listed above is not necessarily correct, and in any case, not what I was trying to prove. I have made a new post with the relevant changes, here Given an injection $\mathbb{N}\to\mathcal{P}(X)$, how can we construct a surjection $X\to\mathbb{N}$?

-
There is an obvious injection $\mathbb{N} \to \mathcal{P}(\mathbb{R})$, but no injection exists $\mathbb{R} \to \mathbb{N}$.... – Hurkyl May 1 '12 at 21:19
Maybe the first inequality should be reversed? – Dylan Moreland May 1 '12 at 21:20
What does the asterisk on the inequality signify? – David Mitra May 1 '12 at 21:22
@Dylan: Given the $*$, I suspect that what's wanted is a SURjection from $X$ to $\Bbb N$. – Brian M. Scott May 1 '12 at 21:22
You should have just edited this post and corrected the mistake, instead of posting an entirely new one... – Arturo Magidin May 2 '12 at 1:57

## 1 Answer

"How to do it" depends on what other things you already know.

Here is a hint: if there is a surjection $f$ from $\mathbb{N}$ to $P(X)$, then every singleton subset of $X$ is obtained as $f(i)$ for at least one $i \in \mathbb{N}$.

-
Now I just feel silly for not seeing that. The rest follows rather easily from well-ordering. Seems like an easy generalization to replace $\mathbb{N}$ with any well-ordered set, too. Thanks! – Cameron Buie May 2 '12 at 0:27