Could we prove $\mathbb{Q}$ is countably infinite by choosing a different 'path' to define the list?

Question

I'm not sure if this question makes sense, but it is based on the proof from Hammack's how to prove it. I have attached a picture from the book for reference.

The proof in the book uses the theorem that the set A is countably infinite if and only if its elements can be arranged in an infinite list (sequence).

From the picture, we define a sequence/function from $\mathbb{N} \to \mathbb{Q}$ by following the snaking grey path that is shown in the picture. Obviously by following this path, we can define any rational number, and if you give me any rational number, and I can tell you what finite $n$ will tell you the position of the rational number in the sequence. This makes perfect sense to me, and I understand why we can claim $\mathbb{Q}$ is countably infinite.

However, I was wondering what would happen if we DIDN'T use the snaked path, and instead tried to define the list following the orange highlighted path. Here I informally define the list by saying count off per column. Intuitively I don't think this would work, and I think that's because it wouldn't be possible to give a finite $n$ such that $f(n) \to \frac{3}{2}$ for example, since to complete the first column of rationals, $n$ would have to be infinite.

My confusion now comes because I don't see why a subsequence of our sequence is somehow not valid to prove $\mathbb{Q}$ is rational, while the original sequence is? Is my reasoning correct that indeed defining a sequence 'per row' would not work? If not, why does it not work? Wouldn't this imply the original sequence is uncountable?

I have a feeling it's maybe because I cannot define a subsequence (highlighted) from the main sequence (grey path), but I'm not quite sure why this is.

Thank you.

Answer 1

The OP might be confused over the fact that there are many injective sequences (paths)

$\tag 1 \mathbb{N} \to \mathbb{Q}$

that are not surjective.

Intuitively, an injective sequence is defined with any method that keeps 'crossing-off' the rational numbers displayed in the tabular list. But to take 'care of them all' (surjectivity) you have to make sure every number in all the rows and columns eventually gets 'crossed-off'.

Interestingly, the page display of rational numbers entries allowed the OP to cross off the entire first column and then move on to the second column. But, you can't ever finish counting off that 'big gulp' at once - you have to stop and 'chew' somewhere else to 'complete the meal'.

Answer 2

There are very many solutions to this, not just the grey snaked path. However, your orange path is not one of them as you will never get to the end of the first column and hence start on the second.

What is important is that you will get to any particular rational number in a finite number of steps. This does not happen with your orange path.

Personally, I use a slightly different approach: I do all rational numbers $\frac{p}{q}$ where $p + q = 1$, followed by $p + q = 2$, then $p + q = 3$, etc. Each group is finite and hence I finish and move to the next. Actually, this only covers the non-negative rationals, you could add the negatives immediately after the corresponding positive.

Answer 3

You are right, the orange path cannot be used to prove that there is a bijection from $\mathbb{Q}\to\mathbb{N}$. However, this does not means that none exists.

We can build an easier example : Lets try to count all elements in $\mathbb{N}$ first by starting with all even numbers, and then all odds numbers... Clearly this fails because we never finish the first step. But it does not means that we can't count it. The bijection $\mathbb{N}\to\mathbb{N}$ exists, but this way of doing it fails.