0
$\begingroup$

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) ?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

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