Statement to prove: If A and B are countable sets, prove A x B is countable. My work so far: I've thought of 2 ways to approach proving this. (1) I read that "Every subset of a countable set is again countable." So my first choice of proving this would be to state that it's given A and B are countable sets. Okay, so now A and B are subsets of A x B (would I have to prove that, or is it known already?). And then from there I can say that since A and B are countable and subsets of A x B, then A x B itself is countable by that statement that every subset of a countable set is again countable. (2) The other way I thought of proving this was: Let A and B be countable sets. This means A ~ N and B ~ N (N the set of naturals). A ~ N implies there is a bijection from A to N, and B ~ N implies there is a bijection from B to N. So now I have to show there is a bijection from A x B to N, right? This is where I got stuck. There is a theorem that says N x N is countable, but I didn't think that helped for this particular proof since sets A and B are not specifically defined except that they are countable. I did find http://planetmath.org/encyclopedia/ProductOfAFiniteNumberOfCountableSetsIsCountable.html" [Broken], but I found it hard to understand with the notations and some of the wording. Any help is greatly appreciated. Thank you for your time!