# [SOLVED] I need help proving that the cross product of 2 countable sets is countable.

• Oct 11th 2008, 01:33 PM
ilikedmath
[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!
• Oct 11th 2008, 01:52 PM
Jhevon
Quote:

Originally Posted by ilikedmath
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.

no, this is wrong. it is like you are using the converse of an implication that is not true. for example, this proof could show that the real numbers are countable! since the naturals are a subset of the reals that are countable. be careful of how you read theorems, they are not always true going backwards. the theorem says if you are given a countable set, then all its subsets will be countable, not if given any set that is countable, then any set containing it will be as well.

Quote:

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

it suffices to show that $\mathbb{N} \times \mathbb{N}$ is countable (why?)

Now, construct the function $f : \mathbb{N} \times \mathbb{N} \mapsto \mathbb{N}$ given by

$f(m,n) = 2^m \cdot (2n + 1) - 1$

where $(m,n) \in \mathbb{N} \times \mathbb{N}$

now show that this function is a bijection (one-to-one and onto)

an alternate way would be to draw a grid (which is usually a nice way to visualize a cross-product of countable sets). where the elements of one set are the first column and the elements of the other form the first row, then the cells in between are the ordered pairs formed from the elements of their respective rows and columns. find a way to traverse this grid to come up with a function
• Oct 11th 2008, 01:56 PM
ilikedmath
Quote:

Originally Posted by Jhevon
no, this is wrong. it is like you are using the converse of an implication that is not true. for example, this proof could show that the real numbers are countable! since the naturals are a subset of the reals that are countable. be careful of how you read theorems, they are not always true going backwards. the theorem says if you are given a countable set, then all its subsets will be countable, not if given any set that is countable, then any set containing it will be as well.

right.

it suffices to show that $\mathbb{N} \times \mathbb{N}$ is countable (why?)

Now, construct the function $f : \mathbb{N} \times \mathbb{N} \mapsto \mathbb{N}$ given by

$f(m,n) = 2^m \cdot (2n + 1) - 1$

where $(m,n) \in \mathbb{N} \times \mathbb{N}$

now show that this function is a bijection (one-to-one and onto)

Okay, thanks for pointing out my error in reading the converse of the theorem. I need to be more careful.

So since "N x N is countable" was already proven as a theorem, I don't need to prove it again,right? I can use that statement to justify that A x B ~ N since A x B goes to N because A goes to N and B goes to N?
• Oct 11th 2008, 02:01 PM
Jhevon
Quote:

Originally Posted by ilikedmath
So since "N x N is countable" was already proven as a theorem, I don't need to prove it again,right?

well, it would be reinventing the wheel if you did. i guess what you have to do, is show how the theorem relates to this problem and why you can use it. once you show that the proof must essentially be the same, then you can just quote the theorem and move on

Quote:

I can use that statement to justify that A x B ~ N since A x B goes to N because A goes to N and B goes to N?
hmm, not exactly. i was thinking more along the lines of A and N as well as B and N are the same "size". so because the proof doesn't say anything about the particular elements of the sets, but rather how many there are, we can replace the sets with N, since as far as the number of elements go, there is no difference between the sets. or you can think of enumerating the elements of each of the sets with the naturals.
• Oct 11th 2008, 02:15 PM
Plato
Suppose that $f:A \leftrightarrow \mathbb{Z}^ +$ counts $A$ and $g:A \leftrightarrow \mathbb{Z}^ +$ counts $B$.
Define $\phi :(A \times B) \mapsto \mathbb{Z}^ + ,\;\phi (a,b) = \left( {2^{f(a)} } \right)\left( {3^{g(b)} } \right)$.
By showing that $\phi$ is an injection, you have completed the problem.
It does not have to be a bijection.
If we can map any set injectively into a countable set the that set is countable.
• Oct 11th 2008, 03:46 PM
ilikedmath
Rethinking my approach
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.
• Oct 11th 2008, 03:50 PM
Jhevon
Quote:

Originally Posted by ilikedmath
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.

if you can find the bijection, yes. i gave you a bijection and Plato gave you an injection already. your approach would present some unique challenges, i think. it is not impossible though, but i do not think it would be as "easy" as you think. i would follow my grid approach to come up with such a function
• Oct 11th 2008, 03:54 PM
Plato
Quote:

Originally Posted by ilikedmath
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.

I would like to see how you would define such a bijection.
I think it would be difficult.
Take another at my suggestion.
• Oct 11th 2008, 06:07 PM
ilikedmath
Quote:

Originally Posted by Jhevon
if you can find the bijection, yes. i gave you a bijection and Plato gave you an injection already. your approach would present some unique challenges, i think. it is not impossible though, but i do not think it would be as "easy" as you think. i would follow my grid approach to come up with such a function

Okay, totally my bad.(Nod) I got help from another source which told me
that I could use:
f: N to A and g: N to B are bijections so consider h: N to A x B where
h(n) = (f(n), g(n)). And show that h is a bijection from N to A x B.
Is that a possible route to go to approaching this proof?
• Oct 11th 2008, 07:26 PM
Jhevon
Quote:

Originally Posted by ilikedmath
Okay, totally my bad.(Nod) I got help from another source which told me
that I could use:
f: N to A and g: N to B are bijections so consider h: N to A x B where
h(n) = (f(n), g(n)). And show that h is a bijection from N to A x B.
Is that a possible route to go to approaching this proof?

yes, that would work. a very nice approach!

i don't suppose you have problems showing that you have a bijection here? there is a little snag about showing it is onto that's bothering me, but it's probably nothing
• Oct 11th 2008, 07:39 PM
ilikedmath
Quote:

Originally Posted by Jhevon
yes, that would work. a very nice approach!

i don't suppose you have problems showing that you have a bijection here? there is a little snag about showing it is onto that's bothering me, but it's probably nothing

We did something similar to this in class except the claim was:
If A ~ X and B ~ Y, then (A x B) ~ (X ~ Y).
A ~ X implied g: A to X is a bijection.
B ~ Y implied h: B to Y is a bijection.
We needed (A x B) ~ (X ~ Y) which implied f: (A x B) to (X ~ Y) a bijection.
Consider f(a, b) = (g(a), h(b))

1-1: Assume f(a1, b1) = f(a2, b2).
That implies (g(a1), h(b1)) = (g(a2), h(b2)). For ordered pairs to be equal the 1st elements must be equal and the 2nd elements are equal. That is:
g(a1) = g(a2) and h(b1) = h(b2)
Since g is 1-1 then a1 = a2. Since h is 1-1 then b1 = b2.
So (a1, b1) = (a2, b2) and f is 1-1.

Onto: Let (x, y) be in X x Y. g is onto which implies there is an a in A such that g(a) = x. h is onto which implies there is a b in B such that h(b) = y. Therefore (a, b) in A x B and f(a, b) = (g(a), h(b)) = (x, y). So f is onto.

Thus f is a bijection and (A x B) ~ (X ~ Y).

---
That was the proof we did in class. So now I'm trying to "see" how I can use that for this proof.
• Oct 11th 2008, 07:49 PM
Jhevon
Quote:

Originally Posted by ilikedmath
We did something similar to this in class except the claim was:
If A ~ X and B ~ Y, then (A x B) ~ (X ~ Y).

what does that mean? (A x B) ~ (X ~ Y) ?? what is X ~ Y describing?

Quote:

1-1: Assume f(a1, b1) = f(a2, b2).
That implies (g(a1), h(b1)) = (g(a2), h(b2)). For ordered pairs to be equal the 1st elements must be equal and the 2nd elements are equal. That is:
g(a1) = g(a2) and h(b1) = h(b2)
Since g is 1-1 then a1 = a2. Since h is 1-1 then b1 = b2.
So (a1, b1) = (a2, b2) and f is 1-1.
yup, proving injectivity for your problem is pretty much identical to this proof. so no worries here.

Quote:

Onto: Let (x, y) be in X x Y. g is onto which implies there is an a in A such that g(a) = x. h is onto which implies there is a b in B such that h(b) = y. Therefore (a, b) in A x B and f(a, b) = (g(a), h(b)) = (x, y). So f is onto.
this is the proof i thought of to prove surjectivity. but as you can see, there is a snag. a might not be equal to b in this proof. so our function h(n) = (f(n), g(n)) might not work.

and i don't think defining $h : \mathbb{N} \mapsto A \times B$ by $h(n) = (f(n), g(m))$ for some $m \in \mathbb{N}$ works either

hmmm (Thinking)

EDIT: hey, maybe $h(n) = (f(n + j), g(n + k))$ for some $j,k \in \mathbb{Z}$ works! i think so. yeah, i think that does it

of course, you would have to say specifically how you would pick j and k. but i think you can figure that out