Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?


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

share|cite|improve this question
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
up vote 5 down vote accepted

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

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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