Hi,
if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?
Basically the idea in Plaot's post is that you can prove that is countable, because clearly the mapping given by is an injection and so is given by where is the th prime. It follows by the Schroder- Bernstein theorem that the two sets are equipotent. But, if is countable we know that for each there is a mapping which is bijective. So, define a mapping by .This is readily verified to be a bijection, and since is countable it follows that is countable.
Note: this is only true for finite cases. For example consider . This is uncountable, for if we could list it's elements in the fashion then we can construct a tuple where and so it follows that but . This clearly shows that we have not, and thus cannot, list all the elements of . It follows that is uncountable.