Define $A=\{n|n\text{ is prime number}\}.$ Then I wish to know whether the set is countable or not. Recall that a set $A$ is countable if $\mathbb{N}$ has the same cardinality as $A$. Now in order to show that both the sets $\mathbb{N}$ and $A$ have the same cardinality we must be able to construct a function $f:\mathbb{N}\to A$ such that $f$ is both $1-1$ and onto. I tried to think of some functions but couldn't come up with anything. Any ideas regarding this problem will be much appreciated.
3
$\begingroup$
$\endgroup$
-
2$\begingroup$ There are unlikely to be more prime numbers than natural numbers $\endgroup$ – Henry Nov 5 '16 at 18:20
-
1$\begingroup$ Oh! what a fool I am. We could simply use a theorem that states: if $A\subseteq\mathbb{N}$ then $A$ is either finite, empty or countable. Since $A$ is infinite (due to Euclid), non-empty we therefore, conclude that $A$ is a countable set. $\endgroup$ – nls Nov 5 '16 at 18:25
-
$\begingroup$ Nevertheless, I would like to see a bijective function. $\endgroup$ – nls Nov 5 '16 at 18:28
-
1$\begingroup$ In one direction the function is the $n$th prime and in the other the prime counting function. There is a reason there are not useful closed forms $\endgroup$ – Henry Nov 5 '16 at 18:33
-
1$\begingroup$ Any infinite subset of $\mathbb{N}$ is countable, since every non-empty subset of $\mathbb{N}$ has a minimum. Or, simply, the map sending $n$ to $p_n$ (the $n$-th prime number) is clearly injective. $\endgroup$ – Jack D'Aurizio Nov 5 '16 at 19:10
1
$\begingroup$
$\endgroup$
HINT: Think about the map sending $n$ to the $n$th prime . . .
In general, you can prove that any infinite subset of $\mathbb{N}$ is countable by using the idea above. Suppose $A\subseteq\mathbb{N}$ is infinite. I want to argue that for every $n\in\mathbb{N}$, "the $n$th element of $A$" is something that makes sense. This is a proof by induction on $n$: show that for every $n\in \mathbb{N}$, there is exactly one element $a\in A$ such that $\vert \{b\in A: b<a\}\vert=n$. (I'm assuming "$0\in\mathbb{N}$" here; otherwise, replace "$<$" with "$\le$".)
Also, note that the definition of "countable" you give is not universally accepted: many texts (the majority, as far as I'm aware) define countable as "in bijection with some subset of $\mathbb{N}$," so that finite sets are countable.
answered Nov 5 '16 at 18:18
