1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cartesian product & Surjective functions

  1. Jan 14, 2008 #1
    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. jcsd
  3. Jan 14, 2008 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    this was proved by cantor, by writing the product in a rectangular array and counting in zigzags from the corner.
     
  4. Jan 14, 2008 #3
    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) ?
     
  5. Jan 14, 2008 #4

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    I don't understand your question toxi.
    You write down a product of two copies of the naturals ([itex]\mathbf{N} \times \mathbf{N}[/itex]) 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 [itex]\phi: A \to \mathbf{N}[/itex] and [itex]\psi: B \to \mathbf{N}[/itex] and you can use the previous case.
     
  6. Jan 14, 2008 #5
    Well as I said, my question is "I need to prove that the product of 2 countable sets is countable"
     
  7. Jan 14, 2008 #6

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    So, what ways do you know to prove a set is countable?
     
  8. Jan 14, 2008 #7
    Apparently cantor's zig zag is the appropriate for this proof
     
  9. Jan 14, 2008 #8

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    "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.
     
  10. Jan 14, 2008 #9
    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
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cartesian product & Surjective functions
  1. Surjective function (Replies: 3)

  2. Surjective functions (Replies: 1)

  3. Cartesian products (Replies: 4)

Loading...