Bijective function from naturals to primes

[asmani]

What's the problem with this trivial solution: n --> n'th prime.

 

[fresh_42]

None.

 

[S.G. Janssens]

When I googled what I found were mind boggling functions...

Can you give an example?

Your solution does of course use the result that the number of primes is not finite, so depending on what can be assumed known, that solution may not be "trivial".

 

[asmani]

Can you give an example?

Your solution does of course use the result that the number of primes is not finite, so depending on what can be assumed known, that solution may not be "trivial".

https://math.stackexchange.com/ques...nction-from-the-natural-numbers-to-the-primes

 

[asmani]

I was thinking about bijection from Q to N. here is what I came up with: m/n --> 2^m3ⁿ
And it's easy to show there's a bijection from the set "2^m3ⁿ for all coprime n and m" to N.

Edit: This is Q+ to N. Does it work?

 

[fresh_42]

It's an embedding (injective), but is is no surjection.

 

[asmani]

Can you give a counterexample?

 

[fresh_42]

Can you give a counterexample?

The map is into and not onto, e.g. you don't hit any prime greater than three.

 

[asmani]

Oh I see what you mean. Let me clarify: It's a bijection from Q+ to W, and then from W to N, where W is the set of all 2^m3ⁿ for all coprime n and m.

Here is the bijection from W to N: Map the smallest member of W to 1, the second smallest member of W to 2, and so on

 

[fresh_42]

This will do, I guess, but then you could as well use the standard diagonalization scheme.
Here's an interesting paper about the repetitions in it:
http://www.cs.utexas.edu/users/sandip/acl2-09/presentations/rationals-talk.pdf