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

The question is to prove the set $S$ of all the functions $f:\mathbb{N}\to \{0,1\}$, for which $f^{-1}(\{1\})$ is finite, is countable.

After considering this for a while I do understand what it means, but I have no idea how to solve it. How do I even make a function from neutral numbers to functions and how can I prove such function is bijective?

I'm not even sure how to start this, so I'll be happy with any push in the right direction.

edit: Thanks you guys for your answers. from them I realized I'm missing something since I didn't understand half of what you said. Though I'm a bit surprised since I only missed a 1-hour lecture once and I don't remember discussing most of what written here. The exercise itself is due in a bit less then a week. I'll go study for a bit and come back to this soon. Will leave the question open in the meantime.

Edit 2: OK, after asking around for a bit and reading some stuff, and then sitting for 15 minutes just thining about all the pieces, I think I finally understand this. I haven't written the proof yet, but I feel like I know how to do this, so I'll be closing the question. Thanks again everyone.

share|cite|improve this question
Thanks for your edit/update: It seems you want to consider all/only functions that map a finite number of $n\in \mathbb{N}$ to $1$, and maps all other (countably many) $n^{\prime} \in \mathbb{N}$ to $0$? Am I correct? – amWhy Nov 6 '12 at 15:32
Yep, these are the functions I try to prove there are countably infinite number of. – Nescio Nov 6 '12 at 15:44
up vote 4 down vote accepted

You shouldn’t try to find a bijection: that gets very messy very quickly. You should look for a more indirect argument.

Here’s one possible approach. There’s an easy bijection between your set of functions and the set of finite subsets of $\Bbb N$: pair a function $f$ with $\{k\in\Bbb N:f(k)=1\}$. For each $n\in\Bbb N$ let $[\Bbb N]^n$ be the set of subsets of $\Bbb N$ having exactly $n$ elements. If you can show that each $[\Bbb N]^n$ is countable, you can then use the fact that the union of a countable family of countable sets is countable.

To show that $[\Bbb N]^n$ is countable, find an injection (one-to-one mapping) of $[\Bbb N]^n$ into $\Bbb N^n$, the set of $n$-tuples of natural numbers. (I’m assuming here that you’ve already shown that $\Bbb N^n$ is countable.) HINT: You can list any set of natural numbers in increasing order.

share|cite|improve this answer
actually we didn't talk at all about of $\mathbb{N}^n$ like that. unless I missed a lot more then I can remember – Nescio Nov 7 '12 at 9:14
@Nescio: In that case you should read about the pairing function, which shows that $\Bbb N^2$ is countable; you can then use induction to get countability of $\Bbb N^n$ for $n>2$. – Brian M. Scott Nov 7 '12 at 9:20

Hint: Any natural number can be written in binary. Prepend an infinite sequence of zeros the the front of such a binary representation, and then reverse it.

share|cite|improve this answer

Any such function is uniquely determined by $f^{-1}(\{1\})$, you can construct a bijection between the set of such functions and the set of all finite subsets of $\mathbb N$.

Thus, we need to prove that the set of all finite subsets of $\mathbb N$ is countable..

Hint Can you prove that for every $n$, the set of subsets of $\mathbb N$ with $n$ elements is countable?

Can you get the problem from here?

share|cite|improve this answer

Hint: first try to prove that the set of all functions for which $|f^{-1}(\{1\})|=1$ is countable. Then the same for the set of all functions for which $|f^{-1}(\{1\})|=2$. Then generalize.

share|cite|improve this answer
I just touched up typos in the formatting...Check to make sure I got what you intended! – amWhy Nov 6 '12 at 15:06
Yes, this is it. Thanks! – Dan Shved Nov 6 '12 at 15:09
I tried looking at the private case of $|f^{-1}(\{1\})|=1$, But I'm not exactly sure how to write it. I understand that exists a function $g$ that maps every $n\in\mathbb{N}$ to the function for which $f(n)=1$, but how do I write it formally? – Nescio Nov 7 '12 at 9:09
Hmm, I don't think that you really need to write it any more formally than you just did... I guess you could use indicator functions, so then you can say that $g \colon n \to \mathbf{1}_{\{n\}}$ is a bijection from $\mathbb{N}$ to the set of all functions for which $|f^{-1}(\{1\})|=1$. But again, in my opinion, what you already said in your comment seems like enough to me. – Dan Shved Nov 7 '12 at 9:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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