1
$\begingroup$

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}$?

  • 1
    You should have just *edited* this post and corrected the mistake, instead of posting an entirely new one...2012-05-02

1 Answers 1

6

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

  • 0
    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!2012-05-02