Hi,

if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable?

Printable View

- February 28th 2010, 03:40 PMposix_memalignCartesian product, countable?
Hi,

if I let A and B be countable sets, how can I prove that the Cartesian product A x B is countable? - February 28th 2010, 03:52 PMPlato
- February 28th 2010, 04:02 PMposix_memalign
- February 28th 2010, 04:11 PMDrexel28
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. - February 28th 2010, 04:16 PMPlato