0
$\begingroup$

This question already has an answer here:

So I was given a question that begins like this.

Let $P_{\text{fin}}(\mathbb{N})$ be the following set (called the finite power set of $\mathbb{N}$): $$ P_{\text{fin}}(\mathbb{N}) = \{X \subseteq N \,\mid\, X \text{ is finite}\} $$

Prove that this set is countably infinite.

From my understanding of Cantor's theorem, I assumed that the Power set of natural numbers has the same cardinality with the real numbers. So, it is uncountable. Apparently in this question it is true that it is countable infinite, but i do not understand how to prove this.

$\endgroup$

marked as duplicate by 6005, Community Aug 11 '15 at 3:46

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

0
$\begingroup$

hint

With each subset $X$ you can associate a unique finite binary string. For example with $X=\{3,4,6,9\}$ you can associate the binary string $100101100$. The idea behind this association is as follows: if a number $k$ appears in the set then in the binary string $1$ appears at the $k^{\text{th}}$ place, otherwise a $0$ appears. Now the (decimal) value of this binary string will be a natural number that gets uniquely associated with this set. This creates an injection from the given set to $\mathbb{N}$. Thus showing that your set is countable.

$\endgroup$

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