# Bijective function from naturals to primes

• I

## Main Question or Discussion Point

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

Related Set Theory, Logic, Probability, Statistics News on Phys.org
fresh_42
Mentor
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".

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

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

Last edited:
fresh_42
Mentor
It's an embedding (injective), but is is no surjection.

Can you give a counterexample?

fresh_42
Mentor
Can you give a counterexample?
The map is into and not onto, e.g. you don't hit any prime greater than three.

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 2m3n 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