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!