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.

I know that $|\mathbb{N}|=|\mathbb{Z}|=|\mathbb{Q}|=\aleph_0$ but which is the cardinal of $|\mathbb{P}|$? since there is no formula for primes, then I can conclude that there is not bijection between $\mathbb{N}$ and $\mathbb{P}$ and so $|\mathbb{P}|\ne\aleph_0$?

share|improve this question
2  
$\aleph$ is often the notation for a general [well-ordered] cardinal or for the cardinal of the continuum. The cardinality of $\mathbb N$ is denoted $\aleph_0$. –  Asaf Karagila Jan 10 '13 at 18:43
    
There no practical/nice/closed-form/easily-computable formula for the $n-$th prime, but it's easy to program an algorithm for that. Furthermore, any infinite subset of the naturals can be put in bijective correspondence with the naturals. –  leonbloy Jan 10 '13 at 18:50
    
Just because there is no formula for a bijection does not mean there isn't a bijection. The common misunderstanding that a lot of people have is that functions need to have "formulas" or "equations". This is not always the case. Check out the Dirichlet Function. –  chharvey Feb 10 '13 at 17:37
add comment

4 Answers

up vote 8 down vote accepted

Since $\Bbb P\subseteq\Bbb N$ and $\Bbb P$ is infinite, it follows automatically that $|\Bbb P|=|\Bbb N|$: every infinite subset of $\Bbb N$ has the same cardinality as $\Bbb N$.

Suppose that $A\subseteq\Bbb N$ is infinite. Then we can recursively define a bijection $\varphi$ from $\Bbb N$ to $A$ by setting $$\varphi(n)=\min\big(A\setminus\{\varphi(k):k<n\}\big)\;:$$

$\Bbb N$ is well-ordered by $\le$ so $\min S$ is well-defined for any non-empty $S\subseteq\Bbb N$, and the hypothesis that $A$ is infinite ensures that $A\setminus\{\varphi(k):k<n\}\ne\varnothing$ for each $n\in\Bbb N$.

share|improve this answer
    
@Peter: You must have commented while I was adding exactly that argument. –  Brian M. Scott Jan 10 '13 at 18:46
    
@Peter: There is no need to use the axiom of choice. If you have an injection into a well-ordered set, or a surjection from a well-ordered set, then things can be done constructively from those functions. –  Asaf Karagila Jan 10 '13 at 19:43
    
@AsafKaragila Yes, I realized that later. –  Pedro Tamaroff Jan 10 '13 at 19:56
add comment

In short $|\mathbb{P}| = \aleph_0$. There are infinitely many primes, and every prime is an integer. So the primes are a countably infinite set, just like $\mathbb{N}$, $\mathbb{Z}$ and $\mathbb{Q}$. To put them in their place, consider the sum:

$$\sum_{k=1}^{\infty} \frac{1}{k^2} = \frac{\pi^2}{6} \, . $$

However, the sum of reciprocals $1/p$ where $p$ is prime, i.e. $1/2 + 1/3 + 1/5 + 1/7 + 1/11 + \cdots $ actually diverges! So, in some sense, there are "more" primes than there are square numbers. In short: there are "less" primes than there are natural numbers, but "more" primes than there are square numbers.

share|improve this answer
    
Fewer? You mean more. Bigger sum, more summands. –  Asaf Karagila Jan 10 '13 at 18:58
    
@AsafKaragila Absolutely! Thanks for picking that up. –  Fly by Night Jan 10 '13 at 19:00
    
Nice argument. Can this notion of "more" and "less" be somehow formalized? –  dtldarek Jan 10 '13 at 19:23
1  
@dtldarek: You can define a "measure" on the natural numbers which assigns $A\subseteq\mathbb N$ the measure $\sum_{n\in A}\frac1n$ (assume $0\notin\mathbb N$ for that matter). I never sat to fully verify this but it seems that most of the axioms of a measure hold here. Then you can really say what's less and what's more. –  Asaf Karagila Jan 10 '13 at 20:04
1  
@AsafKaragila But what happens to the sequences $(a_i)$ for which $\sum a_i^{-1}$ diverges? With this measure the primes and the natural numbers are indistinguishable. –  Fly by Night Jan 10 '13 at 20:08
show 14 more comments

Theorem: If $f\colon\mathbb N\to A$ is surjective then either $A$ is finite, or $|A|=|\mathbb N|$. Alternatively if $g\colon A\to\mathbb N$ is injective then the same conclusion about $A$ is true.

Theorem: The set of prime numbers is not finite.

Corollary: There are countably many prime numbers.


I should also add that there are not many formulas we can write, and there are many subsets to $\mathbb N$. The result is that almost all infinite subsets of $\mathbb N$, while having the same cardinality as $\mathbb N$ do not have a "formulated bijection" between them.

I should add that if we are given the set then we can produce from that set the bijection, but this is already a parameter which we use in the formula.

For such bijection, see If $X$ is an infinite set and there exists an injection $X \to \mathbb{N}$, is there also a bijection?

share|improve this answer
add comment

The primes are subset of $\Bbb N$. But they are infinite. Since $\Bbb N$ is well ordered we can define an injection from $\Bbb P$ to $\Bbb N$ as follows. Let $p_1$ be the least element of $\Bbb P$. Let $p_2$ be the least element of $\Bbb P-\{p_1\}$ and in general let $p_{n+1}$ be the least element of $\Bbb P_n=\Bbb P-\{p_1,\dots,p_n\}$. Then $n\mapsto p_n$ is a bijection. This works in the general case that $B$ is an infinite subset of $\Bbb N$.

share|improve this answer
add comment

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.