I proving that the cross product of 2 countable sets is countable.

[pzzldstudent]

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" , 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!

 

[maze]

http://img384.imageshack.us/img384/6088/productcountingln2.png

 

[pzzldstudent]

http://img384.imageshack.us/img384/6088/productcountingln2.png

Oh, I'm afraid I don't know what that is since my professor did not cover that. All that was mentioned was some diagonalizing, but we're not going into that this semester.
Thanks for your time though.

 

[Hurkyl]

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.

If would help if you could prove AxB and NxN are equipollent, wouldn't it?

 

[Mark44]

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.

But A and B are not subsets of A x B, which pretty well shoots down the rest of your argument. The set A x B is the set of ordered pairs (a, b), such that a \in A and b \in B. The elements of A are not ordered pairs, so they can't also be in A x B. Same for the elements of B.

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

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 think you might be able to use the ideas of that theorem in your problem. IIRC, the theorem you cite arranges the ordered pairs of N x N in a triangular pattern, and devises a way to count them that is a one-to-one and onto (i.e., bijective) map between N x N and N. Something like this:
(0, 0)
(0, 1) (1, 0)
(0, 2) (1, 1) (2, 0)
(0, 3) (1, 2) (2, 1) (3, 0)
(0, 4) (1, 3) (2, 2) (3, 1) (4, 0)
(0, 5) (1, 4) (2, 3) (3, 2) (4, 1) (5, 0)
and so on.

The counting scheme weaves through the array of pairs diagonally, establishing this map:
(0, 0) --> 1
(0, 1) --> 2
(1, 0) --> 3
(0, 2) --> 4
(0, 3) --> 5
(1, 1) --> 6
(2, 0) --> 7
(1, 2) --> 8
(0, 4) --> 9
(0, 5) --> 10
(1, 3) --> 11
(2, 1) --> 12
(3, 0) --> 13
(2, 2) --> 14

and so on. You'll probably need to write the triangular array of pairs and draw a curve that sweeps back and forth to see how I got the pairing above.

It's easy to see that each ordered pair maps to a specific integer, and that each integer maps to a specific ordered pair. It's also easy to see that this counting scheme exhausts all of the ordered pairs and all of the integers.

Now, how can you use this idea in your problem?

I did find http://planetmath.org/encyclopedia/ProductOfAFiniteNumberOfCountableSetsIsCountable.html" , 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!

 

[Hurkyl]

Now, how can you use this idea in your problem?

That seems like an awful lot of work, doesn't it? After all, someone already used that idea to prove a theorem. So why not just figure out how to use the theorem?

 

[pzzldstudent]

Thanks for the feedback. I could also go the other direction, right?
Since A and B are countable, that also means N ~ A and N ~ B.
Which means for functions f and g where f: N → A and g: N → B, the functions are both 1-1 and onto. There are bijections from N to A and N to B. So I can show there is a bijection from N to A x B, right? This seems 'easier' in a way rather than the original way I was approaching the proof.

---
Ehh...apparently it wasn't as 'easy' as I thought. (What in the world what was I thinking?!)
I am confused by this problem.
I know the elements in A x B are ordered pairs that have the form (a , b) where a is in A and b is in B.
Our textbook doesn't do a lot of explaining or examples on concepts, and lectures move at a rapid pace so I always feel behind.

We didn't learn the "triangular array of pairs" and drawing of a curve. If that makes this easier I wish we were taught that. It's not even in our text either. I feel our text does a lot of high assumptions about us students reading it. It seems like the author expects us to know a lot and remember a lot from previous math classes (yeah right!). This class is the reason why I used to like math. It is so abstract. :| My professor's awesome; it's the material that is hard. I may just be really dense lol.