# Neatest proof that set of finite subsets is countable?

I am looking for a beautiful way of showing the following basic result in elementary set theory:

If $A$ is a countable set then the set of finite subsets of $A$ is countable.

I proved it as follows but my proof is somewhat fugly so I was wondering if there is a neat way of showing it:

Let $|A| \le \aleph_0$. If $A$ is finite then $P(A)$ is finite and hence countable. If $|A| = \aleph_0$ then there is a bijection $A \to \omega$ so that we may assume that we are talking about finite subsets of $\omega$ from now on. Define a map $\varphi: [A]^{<\aleph_0} \to (0,1) \cap \mathbb Q$ as $B \mapsto \sum_{n \in \omega} \frac{\chi_B (n)}{2^n}$. Then $\varphi$ is injective hence the claim follows. (The proof of which is what is the core-fugly part of the proof and I omit it.).

-

If $A$ is an infinite countable set, $S$ is the set of finite subsets of $A$ and $S_k$ is the set of $k$-element subsets of $A$, then

$$|S| = \sum_{k \in \mathbb{N}} |S_k| \leq \sum_{k \in \mathbb{N}} |A|^k \leq \sum_{k \in \mathbb{N}} \aleph_0 = |\mathbb{N}| \cdot \aleph_0 = \aleph_0$$

-
Dear Hurkyl, I think this is exactly what I was looking for when I asked the question. I am dismayed to find that as of now I am the only person to upvote your beautifully short proof. – Rudy the Reindeer Apr 14 '13 at 15:19

Subsets of $A$ are in bijection with subsets of $\mathbb{N}$ so it suffices to enumerate the latter. Any subset of $\mathbb{N}$ can be written as a finite string using the following thirteen characters $$0\ 1\ 2\ 3\ 4\ 5\ 6\ 7\ 8\ 9\ \{\ \}\ ,$$ By setting $${\{}=10 \qquad {\}}=11 \qquad {,}=12$$ writing out a subset of $\mathbb{N}$ is a base-$13$ expression of an integer. For example $$\{ 0,1 \}_{13} = 10 \cdot 13^4 + 0 \cdot 13^3 + 12 \cdot 13^2 + 1 \cdot 13 + 11 = 287662$$

The map sending $$S \mapsto \text{the least}\ n\ \text{represented by}\ S$$ defines an injection into $\mathbb{N}$.

-
never saw this proof before :) (+1) – Ittay Weiss Apr 14 '13 at 14:58
If you want real austerity suitable for the times (and to avoid base 13), you could represent subsets of N by binary strings like 111101111101111111011111 where a block of $n +1$ 1's represents $n$ and $0$ is punctuation. Then reread these as binary numbers! – Peter Smith Apr 14 '13 at 15:14
Indeed! I like this proof because there's no work to do in encoding the string other than assigning values to the extra characters. Of course we could drop $\{$ and $\}$ completely and use base-$11$ instead, but even dropping $\{$ and $\}$ is more work than I can be bothered to do. – Clive Newstead Apr 14 '13 at 15:21

It is sufficient to prove the claim for $A=\mathbb{N}$. Denote by $\operatorname{Fin}(\mathbb{N})$ the set of all finite subsets of $\mathbb N$. We have $$\operatorname{Fin}(\mathbb{N}) = \bigcup_{n\in\mathbb{N}}\left\{ A\subseteq\mathbb{N}: \max(A) = n \right\},$$ which is a countable union of finite sets as for each $n\in\mathbb{N}$ there certainly are less than $2^n = \left|\mathcal{P}(\{1,\ldots,n \})\right|$ subsets of $\mathbb{N}$ whose largest element is $n$. Hence, $\operatorname{Fin}(\mathbb{N})$ is countable itself.

-

Clive's answer works (of course)! Or you could go like this, exploiting the familiar trick of coding a sequence by using powers of primes.

Index the members of $A$ as $a_1$, $a_2$, $a_3$ $\ldots$ (we know we can, because it is countable).

Given a finite non-empty subset $F \subset A$, let $a_f$ be the highest indexed member of $F$, and for $1 \leq j \leq f$, put $c_j = 1$ iff $a_j \in F$ and $c_j = 0$ otherwise. Form the product $n_F = 2^{c_1} \cdot 3^{c_2} \cdot 5^{c_3} \cdot \ldots \cdot \pi_f^{c_f}$, where $\pi_j$ is the $j$-th prime. In an obvious way, $n_F$ uniquely codes for $F$.

The map $F \mapsto n_F$ is plainly an injection from the non-empty finite subsets of $A$ to the natural numbers (distinct subsets go to distinct numbers), so the finite subsets are countable.

-
Both Clive's and your proof seem to be my proof with fractions of powers of two replaced by powers of $13$ and powers of primes respectively : ) – Rudy the Reindeer Apr 14 '13 at 15:10
I suppose there are only so many different ways in which one can prove results that are as basic as what I am asking. (and +1, of course) – Rudy the Reindeer Apr 14 '13 at 15:11

Perhaps you'll find the following more to your liking. Let $S$ be a countable set and let $F$ be the set of all finite subsets of $S$. Let $E$ be the set of all finite sequences of elements of $S$. Clearly $|F|\le |E|$. Now, for each natural number $n$, let $E_n=S^n$ be the set of all sequences of $S$ of length $n$. Then $E=\bigcup _n E_n$. Now, a countable union of countable sets is countable, thus $E$ is countable, and thus also $F$ is countable.

Of course, this argument relies on the fact that a countable union of countable sets is countable and that for a countable set $S$, the sets $S^n$ are all countable, which have elegant proofs.

-
Why the detour through sequences? The set $S_n$ of all subsets of $[1, n]$ of $\mathbb{N}$ is finite, so $\bigcup_{n \in \mathbb{N}} S_n$ is a countable union of countable sets. – vonbrand Apr 14 '13 at 15:04
Yes, thank you, I like this one also better than my own proof. – Rudy the Reindeer Apr 14 '13 at 15:24

Let $A$ denote the set of all finite subsets of $\mathbb N$. Then

$$f: A \to \mathbb N \,;\, f(F)=\sum_{k \in F} 2^k \,$$

is a bijection.

Note: $f^{-1}$ identifies a non-negative integer with the possitions of $1's$ in its binary representation.

-

For $n$ in $\mathbb N$ let the tupel $(b^n_{\lfloor\text{ ld}(n)\rfloor},\dots,b^n_0)$ represent the binary expression of $n$, where we define $b^n_k=0$ for all $k>$ ld$(n)$. Then $f_n:\omega\to\{0,1\}$, $m\mapsto b^n_m$ defines a finite subset of $\omega$. This gives a bijection from $\mathbb N$ to the set of finite subsets of $\omega$.

-
I'm sorry for being slow: what is $\mathrm{ld}(n)$? – Rudy the Reindeer Apr 14 '13 at 15:13
@MattN. The logarithmus duālis, the binary logarithm, logarithm to the base 2. – Stefan Hamcke Apr 14 '13 at 15:18

A proof for finite subsets of $\mathbb{N}$:

For every $n \in \mathbb{N}$, there are finitely many finite sets $S \subseteq \mathbb{N}$ whose sum $\sum S = n$.

Then we can enumerate every finite set by enumerating all $n \in \mathbb{N}$ and then enumerating every (finitely many) set $S$ whose sum is $\sum S = n$.

Since every finite set has such an $n$, every finite set is enumerated. QED.

If you want the proof to hold for any countable $A$, first define any injective function $f: A \to \mathbb{N}$.

-

Let $n \in \mathbb{N}$. Note $n$ is finite.

Let $A_n \subseteq \mathbb{N}$ where $n = max(A_n)$.

Since $n$ is finite, $A_n$ is finite.

$\mid \mathcal{P}(A_n) \mid = 2^n$. Since $n$ is finite, $2^n$ is finite.

$\mathcal{F}(\mathbb{N}) = \bigcup_{n=1}^\infty \mathcal{P}(A_n)$

Since union of countable sets is countable and $\mathcal{F}(\mathbb{N})$ is such, it is countable.

-
And this differs from the accepted answer how? – Asaf Karagila May 12 '15 at 22:39

Let $\mathbb{N}$ include $0$.

Every finite subset of $\mathbb{N}$ can be represented uniquely as a binary string terminated by a $\mathtt{1}$. For example $\mathtt{1011}$ codes for $\{0,1,3\}$.

Then since every integer can be expressed uniquely in binary, we have a direct bijection between $\text{Fin}(\mathbb{N})$ and $\mathbb{N}$. In this case, the number $0$ corresponds to the empty set.

-