Analysis and countable sets

1. Sep 22, 2009

dancergirlie

1. The problem statement, all variables and given/known data

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.

2. Relevant equations

3. 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)?

2. Sep 22, 2009

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