Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Bijections Homework

  1. May 31, 2005 #1
    I am not sure how to start these proofs.

    Prove that there is a bijection between Q and Q x X if

    a. X = N
    B. X = {0,1,...n-1}

    We're learning about cardinality, but I was thinking that I have to show that it's one-to-one and onto.
     
  2. jcsd
  3. May 31, 2005 #2

    Andrew Mason

    User Avatar
    Science Advisor
    Homework Helper

    One can associate a rational number, a/b, with the point (a,b) on a cartesian plane. One can then proceed to count all of the points on the cartesian graph by starting at the origin and proceeding in a spiral outward. One will eventually reach the point (a,b) for any value of a and b. So there is a bijection between Q and N.

    [edit:]To make a bijection between Q and Q x N, associate each rational number (a,b) with (a,b,n) where [itex]n \epsilon N[/itex].

    A bijection exists between Q and Q x X = {0,1,...n-1} as X is a subset of N.

    AM
     
    Last edited: May 31, 2005
  4. May 31, 2005 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    It states a bijection from Q to QxN and QxX.

    note it doesn't state you have to find a bijection, merely show one exists. How you do that will depend on what you know already.

    For instance, do you know there is a bijection between Q and N? if so we can immediately restrict to showing a bijection between N and NxN. Clearly all we need to do is send a pair (a,b) to 2^a3^b, this is a bijection from NxN to an infinite subset of N, this implies they have the same cardinality and hence a bijection exists (note we've not found one).

    The casen of a bijection between N and NxX as above is easier, in that it can be done explicitly.

    send the element (a,b) to an+b that is a bijection between N and NxX.
     
  5. Jun 1, 2005 #4
    Finding a bijection can be very confusing. I know that I have to map stuff to Q and N to find that its one-to-one and onto.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook