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

Bijection from N to Q

  1. Jun 29, 2007 #1
    I am bored and feel like doing something useless today so I'm going to try to give an explicit formula that maps N to Q that is a one-to-one correspondence. If you want to waste some time, too, then feel free to post your functions or ideas towards that goal.

    Something that might be very useful is a formula I found a while back for this integer sequence (a Smarandache crescendo sequence):
    S={1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, 6, ...} .
    Right now, I'm thinking this formula could be used to specify the denominators of the rational numbers mapped to by the desired function. This would give us the positive rationals and then compose it with another function that will give us all rationals, not forgetting zero of course.

    Of course, redundancy (like 1/1=2/2=3/3...) will have to be dealt with to ensure that the result is one-to-one.

    I'll give a formula that maps N to S (where N starts at 1 in this case):
    [tex]a_{n}=\frac{1}{2}\left( 2n+\left[ \sqrt{2n}\right] -\left[ \sqrt{2n}\right]
    ^{2}\right) [/tex]
    where [x] is the closest integer to x.

    I haven't proved that this formula works for all n yet but I'm fairly sure it does. I (meaning Mathematica) have checked for the first 400,000 natural numbers that
    [tex]a_{n}>1\rightarrow a_{n}=a_{n-1}+1[/tex]
    where the arrow is logical implication,
    and that
    [tex]a_{r\left( n\right) }=1[/tex] where [tex]r\left( n\right) =\frac{1}{2}\left( n^{2}-n+2\right) [/tex].
    Incidentally, for all n>1,
    [tex]a_{r\left( n\right) -1}=n-1[/tex]
     
  2. jcsd
  3. Jun 29, 2007 #2
    Preform the following steps to show:
    [tex]|\mathbb{Q}^+ | = |\mathbb{N}|[/tex].

    Any element in Q can be written in reduced form as m/n.

    Now we exploit the fundmental theorem of arithmetic.

    Either:
    a)m=1 or [tex]m = p_1^{a_1} .... p_k^{a_k}[/tex].
    b)n=1 or [tex]n=q_1^{b_1}.... q_s^{a_s}[/tex].

    Define [tex]f:\mathbb{Q}^+ \mapsto \mathbb{N}[/tex] as follows:
    1)f(1) = 1
    2)[tex]f(m/n) = p_1^{2a_1}...p_k^{2a_k}[/tex] if n=1 and m!=1
    3)[tex]f(m/n) = q_1^{2b_1-1}...q_s^{2a_s-1}[/tex] if n!=1 and m=1
    4)[tex]f(m/n) = p_1^{2a_1}...p_k^{2a_k}q_1^{2b_1-1}...q_s^{2a_s-1}[/tex] if n!=1 and m!=1

    Now show that f is a bijection.
     
  4. Jun 29, 2007 #3
    As I said initially,
    So your map might be helpful if you can exhibit its inverse.
     
  5. Jun 30, 2007 #4
    I think I found a map from N onto Q which satisfies me enough for now...It's pretty obvious that |N| <= |Q| via the identity map and the interesting thing would be that |N| >= |Q| via the exhibition of a map from N onto Q.

    First some definitions ([x] still means the integer closest to x...the case
    where x=z+1/2 for a whole number z doesn't occur in the formulas below):

    [tex]s\left( n\right) =\frac{1}{2}\left( 2n+\left[ \sqrt{2n}\right] -\left[
    \sqrt{2n}\right] ^{2}\right) [/tex]

    [tex]t\left( n\right) =\frac{1}{2}\left( 2-2n+\left[ \sqrt{2n}\right] +\left[
    \sqrt{2n}\right] ^{2}\right) [/tex]

    [tex]f\left( n\right) =\frac{s\left( n\right) }{t\left( n\right) }[/tex]

    The outputs of s start with 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5, ...
    and the outputs of t start with
    1, 2, 1, 3, 2, 1, 4, 3, 2, 1, 5, 4, 3, 2, 1,... .

    The intuition behind this whole idea is the array that is often used to
    visualize the bijection between N and Q+; you have in the ith row and jth
    column the rational number i/j and then "count" the array by going
    diagonally: (1,1)-->1, (1,2)-->2, (2,1)-->3, (1,3)-->4, (2,2)-->5, (3,1)-->6, etc. Note that the pattern is ( s(n) , t(n) ) --> n.

    This f seems very likely to map N onto Q+ but is definitely not injective.
    To show that it is onto, first define a function from NxN to N:
    [tex]I\left( p,q\right) =\frac{1}{2}\left( p^{2}+q^{2}+2pg-p-3q+2\right) [/tex]

    I've checked for p and q up to 200 (40,000 cases) that
    [tex]f\left( I\left( p,q\right) \right) =p/q[/tex]

    though it will take some more work to show that this is always true. If it
    is true, then the element mapped to p/q in Q+ is I(p,q).

    The next idea is to map N onto the set of nonnegative rationals via g where
    g(1)=0 and g(n)=f(n-1) for n>1.

    Finally, N will be mapped to Q via h where
    [tex]h\left( n\right) =\left( -1\right) ^{n}g\left( \left\lfloor
    n/2\right\rfloor +1\right) [/tex]

    where [tex]\left\lfloor x\right\rfloor [/tex] is the greatest integer less than or
    equal to x. Thus the outputs of h look like this:
    -g(1), g(2), -g(2), g(3), -g(3), ... which is the same as
    0, f(1), -f(1), f(2), -f(2), ... .

    Now if for some reason you just want to have s and t in the answer, then
    here is (very likely to be) an onto map from N to Q:
    [tex]1\mapsto 0[/tex] and for n>1,

    [tex]n\mapsto \left( -1\right) ^{n}\frac{s\left( \left\lfloor n/2\right\rfloor
    \right) }{t\left( \left\lfloor n/2\right\rfloor \right) }[/tex] so in other words
    for n>1, n gets mapped to

    [tex]\left( -1\right) ^{n}\frac{2\left\lfloor n/2\right\rfloor +\left[ \sqrt{
    2\left\lfloor n/2\right\rfloor }\right] -\left[ \sqrt{2\left\lfloor
    n/2\right\rfloor }\right] ^{2}}{2-2\left\lfloor n/2\right\rfloor +\left[
    \sqrt{2\left\lfloor n/2\right\rfloor }\right] +\left[ \sqrt{2\left\lfloor
    n/2\right\rfloor }\right] ^{2}}[/tex]

    This last map seems to have an interesting graph. I'll give some sketches for some domains of increasing magnitude:
    [​IMG]
    [​IMG]
    [​IMG]
    [​IMG]


    Now the same graphs but all cropped to a range of [-7,7]:
    [​IMG]
    [​IMG]
    [​IMG]
    [​IMG]
    It seems like some kind of fractal...
     
  6. Aug 23, 2010 #5
    I believe I have a function from N onto Z^2... Z^2 has obvious connections to Q.

    This is how it looks



    And the formulas along with the mathematica code I used is here.
     
    Last edited by a moderator: Sep 25, 2014
  7. Aug 26, 2010 #6
    I found some simpler formulas as well as a "many-valued" inverse.

    pdf

    In this animation, the point (x,y) is identified with the rational number x/y; the map is onto but not even close to 1-1.

    Yeah, so the title of this thread is a misnomer...these are not bijections, just surjections.
     
    Last edited: Aug 26, 2010
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Bijection from N to Q
  1. Bijective function (Replies: 1)

Loading...