# Apostol proof for $\mathbb{Q}$ being countable.

I am trying to understand a proof from Mathematical Analysis by Apostol for the following theorem:

The set of rationals $$\mathbb{Q}$$ is countable.

Here is the proof (I rewrote a few things):

Let $$A_n$$ be the set of positive rational numbers that have denominator $$n$$. Then the following is true: $$\mathbb{Q}^+=\bigcup_{i=1}^\infty A_i$$ Since each $$A_i$$ is countable, $$\mathbb{Q}^+$$ is countable. Similarly for $$\mathbb{Q}^-$$ and $$\{0\}$$. Then $$\mathbb{Q}=\mathbb{Q}^-\cup\{0\}\cup\mathbb{Q}^+$$ is countable.

For some reason, I cannot understand the bold part. How is that each $$A_{i}$$ is countable?

• Think about A_2 for concreteness. There is one element of A_2 for every positive integer that you put in the denominator (or zero, if you don't want to count non-reduced fractions, but it doesn't matter either way). Explicitly, the elements of A_2 are 1/2, 2/2, 3/2, 4/2, 5/2, and so on – Brennan Vincent Jan 7 '19 at 4:07

## 2 Answers

Consider the map $$f_i:A_i\rightarrow \mathbb{N}$$ defined by $$f({a\over i})=a$$, it is injective. This implies that $$A_i$$ has a cardinality of a subset of $$\mathbb{N}$$ so it is countable.

Rephrasing:

Fix $$i$$ , $$i \in \mathbb{Z^+}$$.

$$A_i=$${$$1/i,2/i,3/i,.......$$}.

$$f(\mathbb{Z^+}) \rightarrow A_i,$$

$$f(n)= n/i$$, $$i$$ fixed, is a bijection.

$$A_i$$ is countable.