Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

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

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.

1  
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

1 Answer 1

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