= Solution
A set is <countable set>[countable] if it is finite or admits an injection into the <natural numbers>; equivalently, its elements can be listed by a finite list or a sequence.
The product of two countable sets is countable: after choosing enumerations, its elements are indexed by pairs $(m,n)\in\mathbb N^2$, and these pairs can be listed diagonally. Thus an injection $X\to A\times B$ followed by an injection $A\times B\to\mathbb N$ proves that $X$ is countable.
The integers are listed as $0,1,-1,2,-2,\ldots$, so $\mathbb Z$ is countable. Every <rational number> is represented by a pair $(p,q)\in\mathbb Z\times\mathbb N_{>0}$, so $\mathbb Q$ is countable as the image of a countable set.
Finally, if $A_0,A_1,\ldots$ are countable, choose listings $A_n=\{a_{n,0},a_{n,1},\ldots\}$, allowing repetitions for finite sets. The diagonal listing of the pairs $(n,m)$ lists every $a_{n,m}$, proving that a <countable union of countable sets> is countable.
Back to article page
