How can a bijection be made from $\mathbb{N}$ to $\mathbb{Q}$ using diagonalization?

Question

I'm studying Cantor's diagonalization, but something seems unclear to me.

There is this table for diagonalization:

╔═══════════════════════╗
║ X  1   2   3   4   5  ║
║ 1 1/1 1/2 1/3 1/4 1/5 ║
║ 2 2/1 2/2 2/3 2/4 2/5 ║
║ 3 3/1 3/2 3/3 3/4 3/5 ║
║ 4 4/1 4/2 4/3 4/4 4/5 ║
║ 5 5/1 5/2 5/3 5/4 5/5 ║
╚═══════════════════════╝

And there can be a bijection between the diagonal

From 2/1 -> 1/2

From 3/1 -> 1/3 (diagonals)

From 4/1 -> 1/4

I don't understand where the bijection really is? I guess 2/1=2 ($\mathbb{N}$) is mapped to 1/2 ($\mathbb{Q}$)

But what about 2/5? I can only see that 2/5 will make |$\mathbb{N}$| < |$\mathbb{Q}$|

However, I can only think that |$\mathbb{N}$x$\mathbb{N}$| = |$\mathbb{Q}$|

What am I missing or misunderstanding and where's the bijection? Can you give me 2 elements that are mapping to each other?

Answer 1

Consider this sequence and see if it helps:

1 maps to 1/1

2 maps to 2/1

3 maps to 1/2

4 maps to 1/3

5 maps to 3/1 (As the 2/2 is already included in the list we are building)

6 maps to 4/1

7 maps to 3/2

8 maps to 2/3

9 maps to 1/4

10 maps to 1/5

11 maps to 5/1 (As the others are already done on this diagonal.)

12 maps to 6/1

13 maps to 5/2

14 maps to 4/3

15 maps to 3/4

16 maps to 2/5

Thus there is keeping track of what is already handled if there are common factors.

Answer 2

This answer may not be what you're looking for, but the fact is that in this proof, one rarely actually gives a bijection itself. Instead, the countability of the rationals is proved much more easily using some simpler theorems.

Namely, a countable union of countable sets is countable.

Now define $A_n$ as the set of rationals in reduced form with denominator $n$. For example, $A_1$ is the set of integers, $A_2$ is the set of odd numbers with denominator $2$, and so forth.

Since each of these sets is countable, we have $\Bbb{Q}=A_1\cup A_2\cup A_2\cup\cdots$ is rational.

Now to relate that back to diagonalization, it turns out that Cantor is basically doing the same thing. To be rigorous, once we count a number, we have to remove it from the list. So once we could $1/1$, we need to remove $2/2$, $3/3$, etc.

One possible bijection could start as follows: $1/1$ maps to $1$, $2/1$ maps to $2$, $1/2$ maps to $3$, and so on. The point that I am trying to make is that the bijection itself doesn't really matter; the point is that we know we can make one.