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?

  • $\begingroup$ 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 $\endgroup$ – Brennan Vincent Jan 7 '19 at 4:07

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.



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.


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.