Prove: $\mathcal P(\mathbb N) \sim (\mathcal P(\mathbb N)\setminus \{\emptyset\})$

My attempt:

One side is obvious since $\mathcal P(\mathbb N) \supset (\mathcal P(\mathbb N)\setminus \{\emptyset\})$ so $|\mathcal P(\mathbb N)| > |(\mathcal P(\mathbb N)\setminus \{\emptyset\})|$ so we know there's an injective function from the RHS to LHS.

For the other side, define $f$ to be:

$$ f(X)=\begin{cases} \{1\} &,X=\emptyset \\ \{n+1\} &, X=\{n\} \\ X &, else \end{cases} $$

We just performed a linear operation on all sets $X=\{n\}$ otherwise the function is the identity, therefore it's injective.

From CSB we can conclude that $\mathcal P(\mathbb N) \sim (\mathcal P(\mathbb N)\setminus \{\emptyset\})$

Is that alright?

  • $\begingroup$ It is OK, but why refer to CSB when you can exhibit a bijection? $\endgroup$ – André Nicolas Feb 4 '15 at 13:11
  • $\begingroup$ @AndréNicolas haven't thought about that, is the explanation for $f$ being onto the same? $\endgroup$ – shinzou Feb 4 '15 at 13:13
  • $\begingroup$ Yes, the mapping is a bijection, the old Hilbert infinite hotel trick. $\endgroup$ – André Nicolas Feb 4 '15 at 13:16

Your solution is alright. You can do it also like this:

$$\newcommand{\PP}{\mathcal{P}} \Big|\PP(\mathbb{N})\Big| = \Big|\PP(\mathbb{N}\setminus\{0\})\Big| = \Bigg|\Big\{A \cup \{0\}: A \in \PP\big(\mathbb{N}\setminus\{0\}\big)\Big\}\Bigg| \leq \Big|\PP(\mathbb{N})\setminus\{\varnothing\}\Big| \leq \Big|\PP(\mathbb{N})\Big|.$$

I hope this helps $\ddot\smile$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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