0

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\}$.

ahron
  • 289
  • 2
    You cannot construct a bijection in this way, hence why there is usually some version of a "diagonal" argument. Here's another variant: for every integer lattice point $(m,n)\in\Bbb Z\times\Bbb Z$, write the rational number $m/n$. This clearly accounts for every rational. Now start at the origin and spiral outwards in a way which counts every lattice point. – pancini May 28 '22 at 05:20
  • 2
    What you have is a countable collection of countable sets. True, one cannot just string them all together into one long list. However there are fairly standard proofs that a countable union of countable sets is itself countable. – coffeemath May 28 '22 at 05:28
  • @coffeemath Thanks, this fixes it in my (admittedly boneheaded) approach. If you'd write this comment in an answer I'd accept it. – ahron May 28 '22 at 08:18
  • 1
    Ahron-- To me what I wrote is not worth being an answer, since it only passes the buck, so to speak, to a known result about countable unions of countable sets. [I also don't feel it would be appropriate to put here a copy of that proof, which many here already know, and which has likely appeared before on this site. – coffeemath May 28 '22 at 08:54
  • So this attempt at a proof doesn't work. So what? Almost every sequence of symbols is an invalid proof... – David C. Ullrich May 28 '22 at 09:13

1 Answers1

1

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\}$.

Karl
  • 11,446