9
$\begingroup$

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?

$\endgroup$
3
  • 26
    $\begingroup$ Send $n$th prime to $n$? $\endgroup$
    – fretty
    Oct 31, 2012 at 9:06
  • $\begingroup$ Is the question about how to prove that there is one? $\endgroup$
    – Julian Kuelshammer
    Oct 31, 2012 at 9:06
  • $\begingroup$ An "easy way" probably indicates desire for a formula. There are several formulas for primes, but none of them is really useful. $\endgroup$
    – lhf
    Jul 15, 2014 at 13:09

2 Answers 2

Reset to default
4
$\begingroup$

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)$.

$\endgroup$
1
  • $\begingroup$ you can do better than prove existence of a bijection. since all subsets of the integers are well ordered, you can use the explicit bijection p_n->n $\endgroup$
    – Oscar Smith
    Feb 24 at 5:46
4
$\begingroup$

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$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .