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!

1:1 correspondance between ints and ration

  1. Apr 22, 2014 #1
    this isn't a homework problem it's just something our professor mentioned today that he didn't know how to do and I was curious.

    How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals.

    I think it would have something to do with countability and i remember something about using diagonal lines with countability but it was a few semesters ago and I can't find my notes to tell if thats even the right direction.

    Looking for pointers or even online resources about how you would prove this and the theory behind it. thanks a bunch :)
     
  2. jcsd
  3. Apr 22, 2014 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    You just need a way to sort all positive rationals into a single infinite sequence. Start by considering all those with a given numerator+denominator total. It doesn't matter if you count some more than once.
     
  4. Apr 22, 2014 #3

    lurflurf

    User Avatar
    Homework Helper

    There are many ways to do it, but one I like is consider numbers of the form

    $$p_{l+1}^{(-2)^m}$$
    where l and m are nonnegative integers
    l,m=0,1,2,3,4,...
    that is primes to a power of -2

    each positive rational can be written as a product of such numbers without repetition
    arrange such numbers in any way you like
    if n is a positive integer and r is a positive rational we have a bijection between

    $$\text{let} \, \, a_k \in \{0,1\} \\ n=1+\sum_{k=0}^\infty a_k 2^k \\ r=\prod_{k=0}^\infty {b_k}^{a_k}$$
    where b_k is the above numbers listed in any order
    and the number of a_k that are one is finite
     
  5. Apr 22, 2014 #4
    Your method may be a little to advanced for me. I am having trouble following what you're doing. Do you ha e a link to a website that explains this method or do you know a method in simpler language?
     
  6. Apr 23, 2014 #5

    lurflurf

    User Avatar
    Homework Helper

    It is very simple, maybe it is the notation that is confusing.
    consider the numbers
    $$2,2^{-4},2^{16},2^{-32},... \\
    3,3^{-4},3^{16},3^{-32},... \\
    5,5^{-4},5^{16},5^{-32},... \\
    ...$$
    That is a prime to a power of -2

    See that each positive rational is a product (without repetition) of such numbers
    See also that each positive integer is the sum of 1 and numbers of the form 2^n
    ie
    1,2,4,8,16,32,...

    So any bijection between powers of two and primes to powers of -2 will give a bijection bewteen positive integers and positive rationals.
     
  7. Apr 23, 2014 #6

    lurflurf

    User Avatar
    Homework Helper

    I think this a better more clear example

    any positive integer is a (unique) product of primes to nonnegative integer powers
    any positive rational integer is a (unique) product of primes to integer powers

    We can induce a bijection between positive integers and positive rational integers using any bijection between nonnegative integers and integers. For example if p(x) is a polynomial with coefficients either 0 or 1 we have a bijection between any two of
    p(x) polynomials as described
    p(2) a nonnegative integer
    p(-2) an integer

    Is that more clear?
     
  8. Apr 25, 2014 #7
    This explanation is still really confusing to me. i found the notes from a few semesters ago and I think the proof I am looking for involves basic countability. this is the video we watched and I know we went into how to prove this but I can not for life of me remember it or replicate it in a written proof.

    The part I am thinking of starts at 2:10
    https://www.youtube.com/watch?v=UPA3bwVVzGI

    Can anyone help me with this?

    the section this was listed under was set theory, denumerable and countable sets and infinity if that helps.
     
    Last edited: Apr 25, 2014
  9. Apr 25, 2014 #8

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Did you consider my post (#2)? Do I need to explain more?
     
  10. Apr 25, 2014 #9
    I think i just don't have any background in what you are talking about. I understand on the surface what you are saying but
    "We can induce a bijection between positive integers and positive rational integers using any bijection between nonnegative integers and integers. For example if p(x) is a polynomial with coefficients either 0 or 1 we have a bijection between any two of"
    confuses me.
    I get that they are related by taking - and + powers but I don't see how to prove a one to one correspondence with that.

    Oh sorry i was reading the other post. I did consider that, you are saying to just add the numerator and denomerator but how can it be a one to one correspondence when you have 2/2 3/1 and 1/3?

    I don't see how it can not matter that you are counting some more than once.
     
  11. Apr 25, 2014 #10

    lurflurf

    User Avatar
    Homework Helper

    bijection just means 1:1 correspondence
    haruspex gave the usual example
    consider numbers m/n where m,n=1,2,3,4,...
    so we have pairs of nonnegative integers
    Do you see how pairs of nonneative integers and nonnegaitive integers can be put in correspondence?
    Next as you say we must deal with repeats such as 4/2=2/1/=274/137
    That is easy to do as we just skip repeats, it is the same reasoning we use to show that primes, integers, even integers and so on are in correspondence

    What I do not like about that example is it is hard to figure out the number of repeats

    My example uses the fact that nonnegative integers and integers are in correspondence
    we say a positive rational and positive integer correspond if the powers of the primes in each correspond

    in other words in my example

    137^[(-2)^7+(-2)^4+(-2)^2] <---> 137^[(2)^7+(2)^4+(2)^2]

    my example follows the facts
    1)
    positive integers can be written as a product of primes to nonnegative integer powers
    positive rational can be written as a product of primes to integer powers
    2)
    nonnegative integers can be written as sums of powers of 2
    integers can be written as sums of powers of -2
    3)if we write positive integers and positive rationals as I describe we have a 1:1 correspondence by switching -2 and 2

    So given a positive integers or positive rationals we can find some function f(x) and in the other direction
    f(2) is a positive integers
    f(-2) is a positive rational
     
  12. Apr 25, 2014 #11

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    As lurflurf says, you can discard the repeats. What you are left with is an ordered list which contains every positive rational. It is then trivial to pair them up with the natural numbers.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: 1:1 correspondance between ints and ration
  1. Int (1/dx) (Replies: 8)

  2. Int 1/(sin^3x+cos^3x) (Replies: 33)

Loading...