Is the Cartesian Product of Two Countable Sets Countable?

[dancergirlie]

Homework Statement

Definition:. Let A and B be sets. The Cartesian product AXB of A and B is the set of ordered pairs (a, b)

(3) Assume that A and B are countable sets. Prove that the Cartesian product A x B is countable.

Homework Equations

The Attempt at a Solution

I know that to prove that something is countable, you need to check if the function is a bijection, which I know how to do. However, I am having a little trouble understanding what the function for this question would be. Would it be:

f:AxB------>AxB where
f(AxB)=(A,B)?

 

[VeeEight]

Since each set is countable, they can be put into 1-1 correspondence with the naturals. That is, you can 'label' each element using the naturals. One proof for this exercise uses a diagonal argument - that is you can arrange all the elements into a grid and show correspondence between diagonal entries. This is not very intuitive but it is used often so you can ask your prof or consults a real analysis book for further discussion.
Another exercise that is useful is to show that the finite product of countable sets is countable. This proof makes use of the fundamental theorem of arithmetic