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

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

could someone guide me through this problem?

-

## marked as duplicate by Potato, Amzoti, tomasz, amWhy, Shuhao CaoJun 25 '13 at 3:52

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

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.

-

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

-

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.

-

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

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