Cartesian product & Surjective functions

[toxi]

I'm a bit stuck here, my question asks me to prove that the product of 2 enumerable sets is indeed enumerable with an argument or a counterexample.
I pretty much have no idea on how to proceed, although i know that the product is enumerable

 

[mathwonk]

this was proved by cantor, by writing the product in a rectangular array and counting in zigzags from the corner.

 

[toxi]

so, by using cantor's zig zag this is the proof it asks me for ?
doesnt this prove just one of the two sides of the rational numbers (i know that Q is in fact the union of negative rationals and positive) ?

 

[CompuChip]

I don't understand your question toxi.
You write down a product of two copies of the naturals (\mathbf{N} \times \mathbf{N}) like this:

(3, 0)  ...
(2, 0)  (2, 1)  (2, 2) ...
(1, 0)  (1, 1)  (1, 2)  ...
(0, 0)  (1, 0)  (2, 0)  (3, 0)  (4, 0) ...

and use Cantors argument to show they are countable (if you want you can explicitly write down a bijection with the natural numbers, mapping (0, 0) to 0, (1, 0) to 1, (0, 1) to 2, (2, 0) to 3, (1, 1) to 4, etc.

Then if you have any two enumerable sets A and B, you know there are bijections \phi: A \to \mathbf{N} and \psi: B \to \mathbf{N} and you can use the previous case.

 

[toxi]

Well as I said, my question is "I need to prove that the product of 2 countable sets is countable"

 

[CompuChip]

So, what ways do you know to prove a set is countable?

 

[toxi]

Apparently cantor's zig zag is the appropriate for this proof

 

[CompuChip]

"Apparently" does not sound convinced. That's why I asked you, in general, when you want to give a rigorous proof that a set is countable, what are your possibilities.

 

[toxi]

I found it, it was in my lecture notes.

now I need a total, surjective, non-injective function from N to Q.
Any suggestions? I'm not really good with this, sorry