A question about the size of the set of all countably-infinite subsets of a countably-infinite set

Question

Let $A$ be a countably-infinite set , then how do we prove that the power set of $A$ and the set of all countably-infinite subsets of $A$ have the same cardinality (i.e. that there is a bijection) ?

Answer 1

Let $B$ be the set of all finite subsets of $A$ and $C$ the set of all countably infinite subsets of $A$. Then $$|\mathscr P(A)|=|B|+|C|\leq2|C|=|C|\leq|\mathscr P(A)|$$ because surely $|B|\leq|C|$.

Answer 2

Instead of talking about an arbitrary countable set, let's talk about $\omega$ (the first limit ordinal, the set of finite ordinals). Of course this has nothing to do with which set we take, it's just a matter of cardinality.

Let us use some common notations, $[\omega]^{<\omega}$ is the set of finite subsets of $\omega$ and $[\omega]^\omega$ is the set of countably infinite subsets of $\omega$. Since $\omega$ is countable, being infinite and being countably infinite is the same thing.

It is clear, if so, why $\mathcal P(\omega)=[\omega]^{\omega}\cup[\omega]^{<\omega}$ and that union is disjoint.

1. Show that $[\omega]^{<\omega}$ is countable. This can done using the classic function $f(X)=\sum_{i\in X}2^i$ when $X\in[\omega]^{<\omega}$, and this is a bijection.

2. Now you have two options.

   1. If you have the axiom of choice, you're about done. $|\mathcal P(\omega)|=|[\omega]^\omega|+\aleph_0=\max\{|[\omega]^\omega|,\aleph_0\}>\aleph_0$, and so equality is easily deduced.

   2. If you wish to avoid the axiom of choice, fix an enumeration of $[\omega]^{<\omega}$, say $F_n$ for $n\in\omega$. Now consider the bijection from $\mathcal P(\omega)$ into $[\omega]^\omega$ defined as follows:

      $$f(X)=\begin{cases}X & X,\omega\setminus X\in[\omega]^\omega\\ \omega\setminus F_{2n} & X=F_n\\ \omega\setminus F_{2n+1} & X=\omega\setminus F_n\end{cases}$$ This bijection shows that $[\omega]^\omega$ has size continuum.

(Coming to think about it, you can just do steps 1 and 2.2 directly.)