# Set of all infinite subsets of natural numbers is equipotent with the power set of natural numbers

I am trying to prove the following statement: Set of all infinite subsets of natural numbers is equipotent with the power set of natutal numbers.

My thought is Let the set of all infinite subsets of natural numbers be $S$. We need to show that there is a bijection from $S$ to the power set of natural numbers. But I have no clue on how to start. Any help would be appreciated.

• "The current answers do not contain enough detail." Hmmm... Really?
– Did
Commented Jun 14, 2017 at 17:57

A different approach is to say that $S$ injects into $P(\Bbb N)$ because it is a subset. To inject $P(\Bbb N)$ into $S$, take any subset of $\Bbb N$ and double its members to get a set of even numbers. Take the union of that set with all the odd numbers. This is an infinite set of naturals, so is a member of $S$. We have injections both ways, so can use the Schroeder-Bernstein theorem to show there is a bijection.

Form the disjoint union:

$$A:=\bigcup_{n=1}^{\infty} \mathbb N^n$$

Show that $B:=\{T\subset \mathbb N: T \text{ is finite}\}$ injects into $A$.

Note that $A$ is the countable union of countable sets, so it is countable.

We have:

$$2^{\mathbb N} = S \cup B$$

Hence, since $B$ is countable, we get $|S| = |2^{\mathbb N}|$.

• Thank you for the answer. Would i need extra working out to show that there is an injection from $B$ to $A$? Or is it obvious?? Commented Jun 12, 2017 at 10:59
• a little more help would be appreciated Commented Jun 12, 2017 at 12:25
• It's obvious, though you should write down the injection.
– user384138
Commented Jun 12, 2017 at 12:31
• Sorry I am asking a lot of questions but what do you mean by writing down the injection? Commented Jun 12, 2017 at 13:48
• @CrusoJames to write down the expression of the injective function from $B$ to $A$. No worries, ask whatever you want.
– user384138
Commented Jun 12, 2017 at 13:57

Clearly it suffices to give an injection from the subsets of $\mathbb N$ to the infinite subsets of $\mathbb Z$.

To do this just send $A$ to $A\cup \{-1,-2,\dots\}$

• Where "clearly" is meant to intimidate the reader? :)
– user384138
Commented Jun 11, 2017 at 16:58
• Is there a reason for choosing the set of integers? Commented Jun 11, 2017 at 17:08
• any set with the same cardinality as $\mathbb N$ that contain $\mathbb N$ along withan infinite number of extra points would do the trick. Commented Jun 11, 2017 at 17:24
• What about showing the surjection part? Commented Jun 12, 2017 at 11:03
• @cruso no need, use cantor Schroeder Commented Jun 12, 2017 at 13:22

For every finite $A$ that is a subset of $N$, notice that $N/A$ is infinite. However, NOT for all infinite $B$ that is a subset of $N$, $N/B$ is finite. Therefore, the set infinite subsets of $N$ is denser than the set of finite subsets of $N$. Then, the set of finite subsets of $N$ must be countably infinite and the set of infinite subsets of $N$ must be uncountably infinite but cannot be any denser than their union (or, namely, the power set of $N$). So, the set of infinite subsets of $N$ is equipotent with the power set of $N$.