Feeds:
Posts

## Some countability proofs

Theorem: The set of finite sequences of elements of a countable set $S$ is countable.

I like this result because it specializes to several other basic countability results: for example, it implies that countable unions, finite products, and the set of finite subsets of countable sets are countable. I know several proofs of this result and I am honestly curious which ones people prefer.

Proof 1

Map a finite sequence $a_1, ... a_n$ of positive integers to the positive integer $\sum_{i=1}^{n} 2^{a_1 + ... + a_i}$. This map is a bijection by the uniqueness of binary expansion.

Proof 2

Map a finite sequence $a_1, ... a_n$ of non-negative integers to the positive integer $2^{a_1} 3^{a_2} ... p_n^{a_n}$. This map is a bijection by the uniqueness of prime factorization.

Proof 3

There are finitely many sequences $a_1, ... a_n$ of positive integers with $a_1 + ... + a_n = m$ for a fixed positive integer $m$ and a countable union of finite sets is countable. In the interest of being more explicit about the bijection here, one can order these sequences first by $n$ and then lexicographically.

Proof 4

If you believe that $\mathbb{Q}$ is countable, map a finite sequence $a_1, ... a_n$ of positive integers to the continued fraction $[a_1; a_2, a_3, ... a_n + 1]$. This map is a bijection by the uniqueness of continued fraction expansions (as long as they end in a positive integer greater than $1$).

Composing this map with the inverse of the map in Proof 1 gives an explicit enumeration of the rationals. I believe it was on the Putnam one year.

Question

Does anyone know any other genuinely different proofs?

### 7 Responses

1. suppose non negative integers $a_0, a_1, … a_k$ are coefficients of a kth order polynomial. then the set of all polynomials are countable.

2. “If you believe that $\mathbb{Q}$ is countable…”

Why wouldn’t one believe this?

The one I first learned was #3, but I kind of like #2 as well.

• I just mean that none of the other proofs assume any other countability results. I also mean that proving that $\mathbb{Q}$ is countable gets you most of the way to this result anyway, since it is tantamount to giving the encoding $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ that makes Jeremy’s proof work.

• Ok, right, I had mistakenly assumed you were referring to some (highly) nonstandard philosophy of mathematics or something like that…

3. My favorite is #2. It is essentially self-contained and trivial to invert.

I believe #3 should be ordered by $m$, not $n$.

Another proof:
Fix an encoding $N\times N\rightarrow N$, denoted $latex\langle x,y\rangle$. We then map the sequence $a_1,\ldots,a_n$ to $\langle n, \langle a_1, \langle\ldots\langle a_{n-1},a_n\rangle\ldots\rangle\rangle\rangle$.

• Sorry, I meant for fixed $m$ one should order by $n$; in other words, order by $m$, then $n$, then lexicographically. (Alternately one can pad the end of a sequence with zeroes and just order by $m$, then lexicographically.)

I’m honestly surprised that both of you prefer #2 to #1. The inversion of the binary expansion map is fast both in principle and in practice: you’re just counting stretches of consecutive zeroes. On the other hand, factoring is hard.

4. My favorite has always been the prime factorization one, although it’s probably just because it’s the first one I learned. It’s also easily the most direct map.