Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

marked as duplicate by amWhy, Asaf Karagila, Davide Giraudo, MJD, Nameless Dec 22 '12 at 16:34

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.

Grazel: I think you'll find some nice answers to your question by clicking on the link immediately above. – amWhy Dec 22 '12 at 15:24
Also see:… – Asaf Karagila Dec 22 '12 at 15:27
Since $\mathbb{N}$ is a countably infinite set, it may help to see as well…. – Timere Nov 7 '13 at 1:27

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

share|cite|improve this answer

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

share|cite|improve this answer

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