[SOLVED] I need help proving that the cross product of 2 countable sets is countable.
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 this proof online, 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!