Feeds:
Posts
Comments

## 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. on September 28, 2012 at 7:03 am | Reply muhammed emre

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. on September 22, 2009 at 2:45 pm | Reply Akhil Mathew

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

• on September 22, 2009 at 2:56 pm | Reply Qiaochu Yuan

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.

• on September 22, 2009 at 6:24 pm | Reply Akhil Mathew

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

3. on September 21, 2009 at 8:40 pm | Reply Jeremy H

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

• on September 22, 2009 at 4:12 am | Reply Qiaochu Yuan

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. on September 21, 2009 at 7:24 pm | Reply Harrison

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.