-2
$\begingroup$

This question already has an answer here:

show that the set of all 2-element subsets of $\mathbb{N}$ is countable

could someone guide me through this problem?

$\endgroup$

marked as duplicate by Potato, Amzoti, tomasz, Namaste, Shuhao Cao Jun 25 '13 at 3:52

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 1
    $\begingroup$ Isn't it naturally a subset of $\mathbb{N} \times \mathbb{N}$? $\endgroup$ – tkr May 9 '13 at 17:32
  • $\begingroup$ is $\mathbb{N}\times \mathbb{N}\subset \mathbb{N}$? $\endgroup$ – H.E May 9 '13 at 17:38
  • 2
    $\begingroup$ $\Bbb N\times\Bbb N$ isn't a subset of $\Bbb N$, but it is countable. And infinite subsets of countable sets are countable. $\endgroup$ – MJD May 9 '13 at 17:41
12
$\begingroup$

Hint: Let $\{a,b\}$ be a pair of natural numbers, then $a<b$ or $b<a$. Without loss of generality $a<b$. Then the map $\{a,b\}\mapsto 2^a3^b$ is injective.

$\endgroup$
5
$\begingroup$

Hint: Use the same technique as you did to prove that the set of rationals is countable.

$\endgroup$
1
$\begingroup$

More generally, the set of all finite subsets of $\mathbb{N}$ is countable.

For any such set, $K = \{k_i\}_{i=1}^m$ where each $k_i \in \mathbb{N}$, map $K$ into $\prod_{i=1}^m p_i^{k_i}$ where $p_i$ is the $i$-th prime.

By unique factorization, the map is into, so the set of finite subsets is countable.

$\endgroup$
0
$\begingroup$

The set of subsets $\{a, b\}$ with $a < b$ is countable, and each of them is countable. So what you are looking at is a countable union of countable sets, thus countable.

$\endgroup$
  • $\begingroup$ It seems like what you argument shows is that $\mathbb{N}$ itself is countable. $\endgroup$ – Trevor Wilson May 10 '13 at 15:42

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