Bijective function from naturals to primes

  • Context: Undergrad 
  • Thread starter Thread starter asmani
  • Start date Start date
  • Tags Tags
    Function Primes
Click For Summary

Discussion Overview

The discussion revolves around the concept of establishing bijective functions between sets of natural numbers and prime numbers, as well as between rational numbers and natural numbers. Participants explore various proposed mappings and their properties, including injectivity and surjectivity, while also referencing related mathematical concepts and examples.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant suggests a trivial solution mapping natural numbers to the nth prime.
  • Another participant questions the triviality of this solution, noting that it relies on the assumption that the number of primes is infinite.
  • Several participants request examples of complex functions related to the topic.
  • A participant proposes a mapping from rational numbers to natural numbers using the formula m/n --> 2m3n, claiming it shows a bijection from a specific subset of rational numbers to natural numbers.
  • Another participant challenges this claim, stating that the proposed mapping is injective but not surjective, providing a counterexample that highlights primes greater than three are not included.
  • A clarification is made regarding the mapping being a bijection from rational numbers to a set W, which is defined as all numbers of the form 2m3n for coprime m and n, and then from W to natural numbers.
  • A later reply suggests that the proposed mapping could also utilize a standard diagonalization scheme, referencing an external paper on the topic.

Areas of Agreement / Disagreement

Participants express differing views on the nature of the proposed mappings, with some asserting the existence of bijections while others contest the completeness of these mappings. The discussion remains unresolved regarding the validity of the bijections and the implications of the proposed functions.

Contextual Notes

Limitations include assumptions about the finiteness of primes and the specific definitions of the sets involved. The discussion also reflects varying interpretations of injective and surjective properties in the context of the proposed functions.

asmani
Messages
104
Reaction score
0
What's the problem with this trivial solution: n --> n'th prime.
 
Physics news on Phys.org
None.
 
asmani said:
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:
It's an embedding (injective), but is is no surjection.
 
Can you give a counterexample?
 
asmani said:
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
 
  • #10
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
 

Similar threads

Undergrad Logical representation of prime numbers
  • · Replies 19 ·
Replies
19
Views
5K
Undergrad Is there a "smallest" infinite subset of the naturals?
  • · Replies 24 ·
Replies
24
Views
6K
Undergrad Primes -- Probability that the sum of two random integers is Prime
  • · Replies 26 ·
Replies
26
Views
3K
Undergrad What are the unique prime factors of -30?
  • · Replies 22 ·
Replies
22
Views
2K
Undergrad Probability of Sum of 2 Random Ints Being Prime
  • · Replies 6 ·
Replies
6
Views
2K
High School Calculating the coprime probability of two integers in a different way
  • · Replies 13 ·
Replies
13
Views
2K
MHB How Can I Solve a Problem Using Euler's Totient Function for Odd Prime Numbers?
  • · Replies 1 ·
Replies
1
Views
1K
MHB Prime Or Composite - Proof required?
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Question about the gaps between prime numbers
  • · Replies 6 ·
Replies
6
Views
2K
Undergrad Is √9x a Bijection from N to R?
  • · Replies 7 ·
Replies
7
Views
2K