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.

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

I'm not sure how to do this problem. I keep trying to think of an explicit formula for 1-1 correspondence like adding all the elements in each subset and sending that sum to itself in the natural numbers, but that wouldn't be 1-1 because, for example, the set {1,2,3} would send to 6 and so would the set {2,4}. Multiplying all the elements in each subset and sending that product to itself in the natural numbers wouldn't work either since, for example, {2,3} would send to 5 and so would the set {1,5}. Any ideas?

share|improve this question
2  
$2\times3\not=5$ :) –  Ben Millwood Sep 21 '12 at 17:53
1  
Set of Finite Subsets of Countable Set is Countable at ProofWiki. See also this question for a generalization of your question ($\mathbb N$ is replaced by arbitrary infinite set $X$ and it is shown that set of all finite subset of $X$ has the same cardinality as $X$). –  Martin Sleziak Sep 22 '12 at 6:50

7 Answers 7

up vote 15 down vote accepted

Consider an enumeration of the (positive) prime numbers by $n\mapsto p_n$. Then if you're given the set $\{n_1,...,n_k\}$, map that to $$p_{n_1}^{n_1}\cdots p_{n_k}^{n_k}.$$ For example, if we've enumerated the primes increasingly ($p_1=2$, $p_2=3$, and so on), then $$\{1,3,4\}\mapsto 600250=2\cdot 5^3\cdot 7^4=p_1^1\cdot p_3^3\cdot p_4^4,$$ and $$\{1,3\}\mapsto 250=2\cdot 5^3=p_1^1\cdot p_3^3.$$

You'll need the fact that there are countably infinitely many prime numbers, and uniqueness of prime factorization. From there, it shouldn't be hard to prove this is an injection from the set of finite subsets of $\Bbb N$ into $\Bbb N$, so there are at most countably many such subsets. To show that there are at least (and so exactly) countably many finite subsets of $\Bbb N$, you need only find an injection from $\Bbb N$ into the set of finite subsets of $\Bbb N$, which should be easy.

share|improve this answer
    
So if I was given a set {1,3} and a set {1,3,4}, you're saying to map that to 1,3 and 1,2^2,3? Am I understanding correctly? –  user39794 Sep 21 '12 at 17:28
    
Not quite. I'll include an example to clarify. –  Cameron Buie Sep 21 '12 at 17:31
    
It's ok I think I get it now from reading the other answer! :) Thanks though! –  user39794 Sep 21 '12 at 17:32
    
The other answer is in the same vein, certainly. Note that for that one, the condition $a_1<...<a_n$ (or one like it) is crucial for the function to be well-defined, as otherwise, for example, $$\{1,2\}\mapsto 2\cdot 3^2=18,$$ but $$\{2,1\}\mapsto 2^2\cdot 3=12.$$ The map I gave has the advantage of working for any way of writing a given finite subset of $\Bbb N$. Marlu's map has the advantage of smaller range values, though that doesn't particularly matter, since we aren't interested in what the values are, only that distinct sets yield distinct values. –  Cameron Buie Sep 21 '12 at 17:43

Define three new digits: $$\begin{align} \{ &= 10 \\ \} &= 11\\ , &= 12 \end{align}$$ Any finite subset of $\mathbb{N}$ can be written in terms of $0,1,\cdots,9$ and these three characters, and so any expression of a subset of $\mathbb{N}$ is just an integer written base-$13$. For instance, $$\{1,2\} = 10 \cdot 13^4 + 1 \cdot 13^3 + 12 \cdot 13^2 + 2 \cdot 13^1 + 12 \cdot 13^0 = 289873$$

So for each finite $S \subseteq \mathbb{N}$, take the least $n_S \in \mathbb{N}$ whose base-$13$ expression gives an expression for $S$. This defines an injection into $\mathbb{N}$.


More generally, any set whose elements can be written as finite strings from some finite (or, in fact, countable) alphabet, is countable.

share|improve this answer
2  
+1 Really nice answer. –  Fly by Night Sep 2 '13 at 18:07
    
The user @TimothySwan tried to edit your question to add a comment, I have copied his comment here since the user can't comment himself. He commented: However, this proof is not correct since there must be an injection from $\mathbb N$. –  Kristoffer Ryhl Sep 22 at 14:34
1  
Thanks @Darksonn. (For the benefit of anyone else reading, that's not true; every infinite set has an injection from $\mathbb{N}$ into it!) –  Clive Newstead Sep 22 at 20:32

The other answers give some sort of formula, like you were trying to do. But, the simplest way to see that the set of all subsets of $\mathbb{N}$ is countable is probably the following.

If you can list out the elements of a set, with one coming first, then the next, and so on, then that shows the set is countable. There is an easy pattern to see here. Just start out with the least elements.

$$\emptyset, \{1\}, \{2\}, \{1, 2\}, \{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}, \{4\}, \ldots$$

In other words, first comes $\{1\}$, then comes $\{2\}$. Each time you introduce a new integer, $n$, list all the subsets of $[n] = \{1, 2, \ldots, n\}$ that contain $n$ (the ones that don't contain $n$ have already showed up). Therefore, all subsets of $[n]$ show up in the first $2^{n}$ elements of this sequence.

share|improve this answer
    
It must be "...the set of all finite subsets of $\Bbb N$.." –  leo Dec 22 '12 at 18:57

Alternatively, just use base $2$, so send $\{a_1,...,a_n\}$ to $2^{a_1}+...2^{a_n}$. (Assuming your $\mathbb N$ includes $0$, this is $1-1$ and onto.)

share|improve this answer
1  
+1 Put in other way: any finite subset of positive integers can be represented as a binary string (with a finite number of ones), which in turn can be interpreted as a binary number which correspond to a positive integer. –  leonbloy Mar 17 at 20:09

Let $p_1,p_2,\ldots$ the sequence of primes. Then map each finite subset $\{a_1,\ldots,a_n\} \subset \mathbb N$ to $p_1^{a_1}\cdots p_n^{a_n}$ where $a_1 < \ldots < a_n$. This gives an injective map from the set of finite subsets of $\mathbb N$ to $\mathbb N$.

Alternatively, notice that for every $s$ there are only finitely many finite subsets of $\mathbb N$ whose sum is $\leq s$. Let $A_s$ be the set of those subsets, then $\mathbb N = \bigcup_{s} A_s$ is a countable union of finite sets, hence countable.

share|improve this answer
    
You beat me to the post ... slightly different, but the same important idea - You can show that the set $C_N$ of subsets of $\mathbb N$ whose members sum to $N$ is finite for each $N\in\mathbb N$. Then each finite subset of $\mathbb N$ has a finite sum $N$ and hence is in one of the $C_N$, and the union of the $C_N$ is a countable union of finite sets, hence is countable. –  Mark Bennet Sep 21 '12 at 18:41
    
@Mark: Not that it's probably relevant to the OP, but a countable union of finite sets needn't be countable in general without sufficient Choice. Here, of course, we're dealing with well-ordered finite sets, so it works out. –  Cameron Buie Jul 31 at 10:48

I'm surprised nobody else has said this, so I worry that I've missed the point of the question. But I would argue as follows: Let $N_i$ be the family of all subsets of $\Bbb N$ with exactly $i$ elements. $N_0$ is finite, and $N_1$ is countable. $N_2$ is countable also, since it's a subset of $\Bbb N\times \Bbb N$. There's an easy induction argument that $N_i$ is countable for all $i>0$, since it's contained in the product $\Bbb N\times N_{i-1}$ of two countable sets.

Then, since the set you want, $\bigcup N_i$, is a countable union of countable sets, it is countable.

share|improve this answer
    
Well, a countable union of countable sets needn't be countable. It depends on your axioms. –  Cameron Buie Sep 29 '12 at 22:09
    
What axioms would those be? –  MJD Sep 29 '12 at 22:28
    
Set theoretic axioms--which you need at least some of before you can talk about sets, countability, unions, etc. For example, there are models of ZF in which $\Bbb R$ is a countable union of countable sets. If one takes countable choice (or stronger) as an axiom, then countable unions of countable sets are countable (that's a strictly weaker statement than countable choice). Now, it's worth noting that countable unions of enumerated sets (countable sets with a given bijection with $\Bbb N$) are countable, with no need for choice principles. –  Cameron Buie Sep 29 '12 at 23:07

If $S$ is the set of all finite subsets of $\mathbb{N}$, define $f:S\rightarrow \mathbb{Q}$ by

$f(A)=.x_1x_2x_3x_4\cdots$ where $x_{i}=\begin{cases}1 &\mbox{, if }i\in A\\0 &\mbox{, if } i\not\in A \end{cases}$.

Then $f$ is clearly injective, so $S$ is countable since $\mathbb{Q}$ is countable and any subset of a countable set is countable.

share|improve this answer

Your Answer

 
discard

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