Suppose X and Y are countably infinite sets Show that A x B

Suppose X and Y are countably infinite sets.
Show that A x B is also countable.

Solution

Let A and B be countably infinite sets.

Then for a fixed x A, let B_x= {(x, y) A × B | y B}. Since B is countable, each B_x is countable.

Since _xAB_x is the countable union of countable sets, and hence is countable.

Since A × B = _xAB_x, we have that A × B is countable.