1
$\begingroup$

Possible Duplicate:
Show that the set of all finite subsets of $\mathbb{N}$ is countable.

How can I prove in a proper way that the "set of all finite subsets of $\mathbb{N}$ (the set of natural numbers) is a countable set"? Please help me with this.Thank you.

  • 0
    Since $\mathbb{N}$ is a countably infinite set, it may help to see as well http://math.stackexchange.com/questions/27096/the-cardinality-of-the-set-of-all-finite-subsets-of-an-infinite-set?rq=1.2013-11-07

2 Answers 2

2

Let $S$ be the set of all finite subsets of $N$. It is easy to verify that the function $f:S\rightarrow N$ that sends $A$ to $\sum_{a\in A} 2^{a}$ is a bijection

1

For an approach with cardinal numbers:

  • The set of all finite subsets of $\mathbb{N}$ is the union over $n$ of the set of all subsets of size $n$.
  • The set of all subsets of size $n$ is no bigger than the set of all ordered tuples of length $n$.

Therefore, the set of all finite subsets of $\mathbb{N}$ has cardinality less than or equal to:

$ \sum_{i \in \mathbb{N}} |\mathbb{N}|^i = \sum_{i \in \mathbb{N}} |\mathbb{N}| = |\mathbb{N}| \cdot |\mathbb{N}| = |\mathbb{N}|$