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

This question already has an answer here:

In my last question, I asked for a proof of "Are the set of all finite subsets in $\mathbb{Z}$ countable?" . I had a good answer that showed me that it is an $f: \mathbb{N} \to \{\text{finite subsets of }\mathbb{Z}\}$. So knowing that there exists a bijection $\mathbb{N} \leftrightarrow \mathbb{Z}$, then it is proved.

But I am curious about an example (if it exists) of a function $f: \mathbb{Z} \to \{\text{finite subsets of }\mathbb{Z}\}$ Does such an example exist?

share|cite|improve this question

marked as duplicate by Brian M. Scott, Ittay Weiss, Thomas Andrews, Andrés E. Caicedo, dtldarek Feb 12 '13 at 7:48

This question was marked as an exact duplicate of an existing question.

Do you mean that each finite subset is countable (which would depend on exactly which definition of "countable" you subscribe to), or the the set of all finite subsets is countable (which is true)? – Henning Makholm Feb 12 '13 at 7:35
The set of all finite subsets. Thanks – Pedro Feb 12 '13 at 8:04

To prove that the set of all finite subsets of $\mathbb{Z}$ is countable, it is enough to show that there is a function $f : \mathbb{N} \xrightarrow{onto} \{\text{finite subsets of }\mathbb{N}\}$. (It is easier to work with $\mathbb{N}$ and there is a bijection $\mathbb{N} \leftrightarrow \mathbb{Z}$.)

An example of such function could be:

$$f\left(\prod_{k=0}^\infty p_k^{\alpha_k}\right) = \{ k \mid \alpha_k \text{ is odd}\},$$

where $\{p_0, p_1, \ldots\}$ is the set of prime numbers and $\prod_{k=0}^\infty p_k^{\alpha_k}$ is the unique factorization of the input.

I hope this helps ;-)

share|cite|improve this answer
Thank you very much :-) – Pedro Feb 12 '13 at 8:05

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