# Cartesian product & Surjective functions

1. Jan 14, 2008

### 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

2. Jan 14, 2008

### mathwonk

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

3. Jan 14, 2008

### 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) ?

4. Jan 14, 2008

### 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:
Code (Text):

(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.

5. Jan 14, 2008

### toxi

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

6. Jan 14, 2008

### CompuChip

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

7. Jan 14, 2008

### toxi

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

8. Jan 14, 2008

### 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.

9. Jan 14, 2008

### 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