## Some countability proofs

September 21, 2009 by Qiaochu Yuan

**Theorem:** The set of finite sequences of elements of a countable set 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 of positive integers to the positive integer . This map is a bijection by the uniqueness of binary expansion.

**Proof 2**

Map a finite sequence of non-negative integers to the positive integer . This map is a bijection by the uniqueness of prime factorization.

**Proof 3**

There are finitely many sequences of positive integers with for a fixed positive integer 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 and then lexicographically.

**Proof 4**

If you believe that is countable, map a finite sequence of positive integers to the continued fraction . This map is a bijection by the uniqueness of continued fraction expansions (as long as they end in a positive integer greater than ).

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?

### Like this:

Like Loading...

*Related*

on September 28, 2012 at 7:03 am |muhammed emresuppose non negative integers $a_0, a_1, … a_k$ are coefficients of a kth order polynomial. then the set of all polynomials are countable.

on September 22, 2009 at 2:45 pm |Akhil Mathew“If you believe that 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 |Qiaochu YuanI just mean that none of the other proofs assume any other countability results. I also mean that proving that is countable gets you most of the way to this result anyway, since it is tantamount to giving the encoding that makes Jeremy’s proof work.

on September 22, 2009 at 6:24 pm |Akhil MathewOk, right, I had mistakenly assumed you were referring to some (highly) nonstandard philosophy of mathematics or something like that…

on September 21, 2009 at 8:40 pm |Jeremy HMy favorite is #2. It is essentially self-contained and trivial to invert.

I believe #3 should be ordered by , not .

Another proof:

Fix an encoding , denoted $latex\langle x,y\rangle$. We then map the sequence to .

on September 22, 2009 at 4:12 am |Qiaochu YuanSorry, I meant for fixed one should order by ; in other words, order by , then , then lexicographically. (Alternately one can pad the end of a sequence with zeroes and just order by , 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.

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