Neatest proof that set of finite subsets is countable?

Question

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

Answer 1

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

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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

Answer 8

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

Answer 9

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.

Answer 10

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.

Answer 11

This answer community wiki. Please fee free to change it into an airtight argument.

To begin, please review the construction of the Cantor Pairing Function found here. The basic idea is that if we can totally order each finite set in a countable family, then the union of those sets is countable and comes equipped with a natural enumeration.

Let $X$ be a finite set with $n$ elements and assume you have a totally ordered $\mathcal{P}(X)$ (the power set) with $\le$. If you add a new element $\hat x$ to $X$, the number of subsets of $X \cup \{\hat x \}$ containing $\hat x$ is $2^n$, so you can copy $\le$ over to these new sets. Not only that, we can 'add' these $2^n$ subsets after $\mathcal{P}(X)$, giving a total ordering on $\mathcal{P}(X \cup \{\hat x\})$, a set with $2^n + 2^n = 2^{n+1}$ elements.

At a minimum for those seeking a mathematical framework, we have to explain how to copy $\le$ over when we add $\hat x$. We simple start by adding $\hat x$ to the $\le$ smallest element in the $\mathcal{P}(X)$ linear chain and then proceed adding it in to each of the following elements in turn.

It is kind of amusing that since there is only one ordering on a set with one element, and we start with $\mathcal{P}(\emptyset)$, there is not much work involved. Any bijective enumeration of $A$ drives the recursion.

---

Here is a partial listing:

Let $A$ be enumerated by $(a_n)_{ \, n \ge 1}$. We enumerate the finite subsets of $A$ as follows:

$\{\}$

$\{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\}$

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

$\{a_6\}$ $\{a_6,a_1\}$

$\{a_6,a_2\}$ $\{a_6,a_2,a_1\}$

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

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

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

Note: I started using a word processor for the last few steps...