Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We know that if set $S$ is countable then this set and set of all natural numbers are equivalent, which means that there must be some bijection between this two sets $F:S\rightarrow N$.

We know that set of all Prime numbers is countable as well as set of all Natural numbers.
So how to find bijection between Prime numbers and Natural numbers in an easy way?

share|improve this question
20  
Send $n$th prime to $n$? –  fretty Oct 31 '12 at 9:06
    
Is the question about how to prove that there is one? –  Julian Kuelshammer Oct 31 '12 at 9:06
    
An "easy way" probably indicates desire for a formula. There are several formulas for primes, but none of them is really useful. –  lhf Jul 15 at 13:09

2 Answers 2

Let $\mathbb{P}$ be the set of all prime numbers.

$\mathbb{P} \subsetneq \mathbb{N}$


Then you need to prove that $\mathbb{P}$ is infinite.

Suppose it is finite.

Let $p = 1 + \prod\limits_{i \in \mathbb{P}} i \in \mathbb{N}$

$\forall k \in \mathbb{P}, k \nmid p$ because otherwise, since $k \mid \prod\limits_{i \in \mathbb{P}} i$, $i \mid p - \prod\limits_{i \in \mathbb{P}} i$, ie $p \mid 1$ which is absurd.

So $p \in \mathbb{P}$. Absurd.

So $\mathbb{P}$ is infinite.

(At this point, you probably can say something like "$\mathbb{P}$ is infinite and in $\mathbb{N}$ hence countably infinite so you can get a bijection from $\mathbb{N}$ to $\mathbb{P}$. But I haven't learned that kind of things yet so I'm not sure...)


Then, since $\mathbb{P} \subset \mathbb{N}$, $\forall X \subset \mathbb{P}, \min( X )$ exists.

Let $X_0 = \mathbb{P}$ and $\forall n \geq 1, X_n = X_{n-1} \setminus \{ \min( X_{n-1}) \}$

Then you can use $\forall n \in \mathbb{N}, f(n)=min(X_n)$.

share|improve this answer

Xavier shows a "non-constructive" proof of the fact that $\#\mathbb P=\#\mathbb N$. I will show a constructive one:

Let $F_n=2^{2^n}+1$ be the $n$-th Fermat number. It is proved that Fermat numbers a coprime. Let $P_n$ be the smallest prime number dividing $F_n$. Then $P_n\neq P_m$ if $n\neq m$ (because the Fermat numbers are coprime hence having different primes in thei factorizations).

This means that the map $\mathbb N\to\mathbb P$ given by $n\to P_n$ is injective.

As well, the identity map $\mathbb P\to\mathbb N$ given by $p\to p$ is injective.

Therefore by Cantor-Bernstein theorem, we have $\#\mathbb P=\#\mathbb N$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.