1:1 correspondance between ints and ration

[mikky05v]

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 that's 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 :)

 

[haruspex]

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.

 

[lurflurf]

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

 

[mikky05v]

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?

 

[lurflurf]

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.

 

[lurflurf]

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?

 

[mikky05v]

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.

 

[haruspex]

This explanation is still really confusing to me.

Did you consider my post (#2)? Do I need to explain more?

 

[mikky05v]

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.

 

[lurflurf]

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

 

[haruspex]

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.

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.