Results 1 to 12 of 12

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

  1. #1
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    Question [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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    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.

    (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
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    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

    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Suppose that f:A \leftrightarrow \mathbb{Z}^ + counts A and g:A \leftrightarrow \mathbb{Z}^ + counts B.
    Define A \times B) \mapsto \mathbb{Z}^ + ,\;\phi (a,b) = \left( {2^{f(a)} } \right)\left( {3^{g(b)} } \right)" alt="\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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98

    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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,669
    Thanks
    1618
    Awards
    1
    Quote Originally Posted by ilikedmath View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    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. 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?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    Okay, totally my bad. 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
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Member ilikedmath's Avatar
    Joined
    Sep 2008
    Posts
    98
    Quote Originally Posted by Jhevon View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by ilikedmath View Post
    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?

    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.

    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


    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
    Last edited by Jhevon; October 11th 2008 at 07:03 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 5
    Last Post: January 9th 2013, 06:14 AM
  2. Replies: 2
    Last Post: November 11th 2010, 04:56 AM
  3. [SOLVED] Countable union of closed sets/countable interesection of open sets
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: October 8th 2010, 01:59 PM
  4. Replies: 1
    Last Post: February 9th 2010, 01:51 PM
  5. [SOLVED] Rationals and countable intersection of open sets
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: February 8th 2010, 06:16 PM

Search Tags


/mathhelpforum @mathhelpforum