# 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
• In the phrase "Any subset of $N$ can be written as...", I think it should be "Any finite subset of ..." instead. – evaristegd Aug 29 '18 at 13:44

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.

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

• Correction: For example $\mathtt{1011}$ codes for $\{0,2,3\}$. – CopyPasteIt Jun 2 at 12:00
• @CopyPasteIt Thanks, fixed – ogogmad Jun 2 at 13:15

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 $$A$$ be enumerated by $$(a_n)_{ \, n \ge 1}$$.

We'll enumerate all the finite subsets of $$A$$ by defining a recursive function $$f$$.

Define $$f(1) = \emptyset$$.

If $$f$$ has been defined on $$\{n \in \Bbb N \mid 1 \le n \le 2^k \}$$ for $$k \ge 0$$ and $$2^k \lt m \le 2^{k+1}$$, define

$$\tag 1 \displaystyle f(m) = f(m - 2^k) \cup \{a_{k+1}\}$$

Note: It is possible to specify $$f$$ in the more standard 'step-by-step' recursion format:

$$\quad \text{specify } f(n+1) \text{ by transforming } f(n)$$

One can associate to each subset of $$A$$ (using the $${a_n}$$ enumeration) a chain and can perform 'gap' analysis; depending on the 'gap structure' of $$f(n)$$ the specification for $$f(n+1)$$ can be given.

These are the $$f(n)$$ outputs from $$n=1$$ to $$16$$:

$$\{\}$$
$$\{a_1\}$$
$$\{a_2\}$$
$$\{a_2,a_1\}$$
$$\{a_3\}$$
$$\{a_3,a_1\}$$
$$\{a_3,a_2\}$$
$$\{a_3,a_2,a_1\}$$
$$\{a_4\}$$
$$\{a_4,a_1\}$$
$$\{a_4,a_2\}$$
$$\{a_4,a_2,a_1\}$$
$$\{a_4,a_3\}$$
$$\{a_4,a_3,a_1\}$$
$$\{a_4,a_3,a_2\}$$
$$\{a_4,a_3,a_2,a_1\}$$

I know that this questions is old, but I want to show another approach using the Fundamental Theorem of Arithmetic. As Andy Brandi mentioned, is enough prove the result for $$A=\mathbb{N}$$. Take a finite set $$B \subset \mathbb{N}$$ with $$|B|=n$$, and order their elementes in increasing order, that is, $$B=\{b_{1},b_{2},\ldots,b_{n}\}$$ with $$b_{i} for $$i \in \{1,\ldots,n-1\}$$. Let us write $$p_{1} the sequence of prime numbers in increasing order. Define \begin{align*} f:\{\text{finite sets of \mathbb{N}}\} & \to \mathbb{N}, \\ B & \mapsto p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots p_{n}^{b_{n}}. \end{align*} By the Fundamental Theorem of Arithmetic, $$f$$ is inyective, and it is clear that is surjective. So, $$f$$ is a bijection and we have the result.