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!

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.

    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.
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Bijections Homework
  1. Homework ? (Replies: 3)

  2. This homework (Replies: 13)