2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "The current answers do not contain enough detail." Hmmm... Really? $\endgroup$ – Did Jun 14 '17 at 17:57
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?? $\endgroup$ – Cruso James Jun 12 '17 at 10:59
  • $\begingroup$ a little more help would be appreciated $\endgroup$ – Cruso James Jun 12 '17 at 12:25
  • $\begingroup$ It's obvious, though you should write down the injection. $\endgroup$ – user384138 Jun 12 '17 at 12:31
  • $\begingroup$ Sorry I am asking a lot of questions but what do you mean by writing down the injection? $\endgroup$ – Cruso James Jun 12 '17 at 13:48
  • $\begingroup$ @CrusoJames to write down the expression of the injective function from $B$ to $A$. No worries, ask whatever you want. $\endgroup$ – user384138 Jun 12 '17 at 13:57
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$

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.