proof that countable unions are countable
Let be a countable set of countable sets. We will show that is countable.
Let be the set of positive primes (http://planetmath.org/Prime). is countably infinite, so there is a bijection between and . Since there is a bijection between and a subset of , there must in turn be a one-to-one function .
Each is countable, so there exists a bijection between and some subset of . Call this function , and define a new function such that for all ,
Note that is one-to-one. Also note that for any distinct pair , the range of and the range of are disjoint due to the fundamental theorem of arithmetic.
We may now define a one-to-one function , where, for each , for some where (the choice of is irrelevant, so long as it contains ). Since the range of is a subset of , is a bijection into that set and hence is countable.