Bijective function from naturals to primes

  • I
  • Thread starter asmani
  • Start date
  • #1
105
0

Main Question or Discussion Point

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

Answers and Replies

  • #2
12,343
8,727
None.
 
  • #3
S.G. Janssens
Science Advisor
Education Advisor
862
624
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".
 
  • #5
105
0
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:
  • #6
12,343
8,727
It's an embedding (injective), but is is no surjection.
 
  • #7
105
0
Can you give a counterexample?
 
  • #8
12,343
8,727
Can you give a counterexample?
The map is into and not onto, e.g. you don't hit any prime greater than three.
 
  • #9
105
0
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
 

Related Threads for: Bijective function from naturals to primes

  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
5
Views
19K
  • Last Post
Replies
1
Views
1K
Replies
3
Views
9K
Replies
2
Views
2K
Replies
8
Views
4K
Top