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.
Map a finite sequence of positive integers to the positive integer . This map is a bijection by the uniqueness of binary expansion.
Map a finite sequence of non-negative integers to the positive integer . This map is a bijection by the uniqueness of prime factorization.
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.
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.
Does anyone know any other genuinely different proofs?