Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

marked as duplicate by Potato, Amzoti, tomasz, amWhy, 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.

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.

share|cite|improve this answer

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

share|cite|improve this answer

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.

share|cite|improve this answer

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.

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

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