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 ![[a_1; a_2, a_3, ... a_n + 1]](http://s0.wp.com/latex.php?latex=%5Ba_1%3B+a_2%2C+a_3%2C+...+a_n+%2B+1%5D&bg=ffffff&fg=333333&s=0 "[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 
).
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...
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.
My favorite is #2. It is essentially self-contained and trivial to invert.
I believe #3 should be ordered by
, not 
.
Another proof:
, denoted $latex\langle x,y\rangle$. We then map the sequence 
to 
.
Fix an encoding
Sorry, 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.
“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.
I 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.
Ok, right, I had mistakenly assumed you were referring to some (highly) nonstandard philosophy of mathematics or something like that…
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.