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
    There is an obvious injection $\mathbb{N} \to \mathcal{P}(\mathbb{R})$, but no injection exists $\mathbb{R} \to \mathbb{N}$....2012-05-01
  • 0
    Maybe the first inequality should be reversed?2012-05-01
  • 1
    What does the asterisk on the inequality signify?2012-05-01
  • 1
    @Dylan: Given the $*$, I suspect that what's wanted is a SURjection from $X$ to $\Bbb N$.2012-05-01
  • 0
    @David: The notation $|A|\le^*|B|$ often means that there is a surjection from $B$ onto $A$.2012-05-01
  • 0
    Oh, no! I misspoke in the title. I will edit it now.2012-05-01
  • 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