3
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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