Countability of the rationals

69 Views Asked by At

I have read some of the proofs about countability of the rationals and I am okay with those proofs.

But I find a way to get into trouble by doing it like this -

The set of all rationals, of the form $\frac{a}{b}$, can be expressed as a set of ordered pairs $\{(a_{n},b_{n})\}$ where $a_{n}$ $\in$ $\bf{N}$ and $b_{n}$ $\in$ $\bf{N}$.

Now suppose I want to arrange the rationals in this way -

So I first fix the numerator $a$ at $a_{1}$ and the subset of $\bf{Q}$ corresponding to this is all the ordered pairs $\{(a_{1}, b_{n})\}$ where $n$ goes to infinity and since the ordered pairs can be arranged as a sequence, each pair maps to a natural number, and $\{(a_{1}, b_{n})\}$ is countable.

So we map the equivalence $\{(a_{1}, b_{n})\}$ ~ $\{k\}$ where $k \in \bf{N}$.

Now we start the next sequence of pairs $\{(a_{2}, b_{n})\}$.

But since the counting of $\{(a_{1}, b_{n})\}$ ~ $\{k\}$ has already taken us to $infinity$. So where do we start/continue counting $\{(a_{2}, b_{n})\}$? It can't be $k+1$ since $k$ is already at infinity from the counting of the set $\{(a_{1}, b_{n})\}$ ~ $\{k\}$.

1

There are 1 best solutions below

0
On

You're right that dividing your whole set into several infinite sets isn't good enough to complete the proof (unless you do extra work to interleave those sets in the output space). That's why it's better to divide into finite sets, such as $\{(a,b)\in\Bbb N^2:a+b=n\}$.