If two sets are countable and infinite show the Cartesian product is countable.

Question

If I have two sets say A and B which are countable and infinite then how would I show that the Cartesian product is countable.

Answer 1

The set of natural numbers is the prototype for countable sets; anything in bijective correspondence with this set, by definition, is a countable set.

Let us see the natural numbers in their physical/visual form. We write them out in base 10. Then we get all possible finite sequences formed by the symbols $0,1,2,\ldots,9$ (avoiding 0 at the starting position).

As numbers can be written uniquely in any basis (binary system, decimal system) it follows that given a finite set of symbols, the collection of strings of all possible finite length composed of these symbols is a countable set.

Now let us take a visual description of the cartesian product: a typical element looks like $(13374,26905)$. We can see that physically these are subset of all possible strings of finite length composed of the thirteen symbols: the decimal digits, opening and closing parentheses, the comma.

So this is a subset of the countable set of all strings of finite length formed with 13 symbols, hence countable.

Note that this actually proves that product of three (or any finite number of) countable sets is also countable.

BONUS: To prove countability of rationals look at their physical forms, other than the minus sign, the slash sign for division should be enlisted, and same argument will work.