if I let A and B be countable sets, how can I prove that the Cartesian product A x B 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.