I am studying infinite sets,and I can't understand the following proof of the fact that the set of positive rational numbers and the set of positive integers are of the same size.
Proof from book
(…)Even the set of all positive rational numbers .which seems
immensely larger than the set of positive integers,is actually the
same size.We make the correspondence by writing the rationals in a
grid:$\begin{pmatrix} \cfrac{1}{1} & \cfrac{1}{2} & \cfrac{1}{3} &
\cfrac{1}{4} & \cdots \\ \cfrac{2}{1}& \cfrac{2}{2} & \cfrac{2}{3}
&\cfrac{2}{4}&\cdots\\ \cfrac{3}{1}&\cfrac{3}{2}&\cfrac{3}{3}&
\cfrac{3}{4}& \cdots\\\ \cfrac{4}{1}&\cfrac{4}{2}&\cfrac{4}{3}&\cfrac{4}{4}&\cdots\\ \vdots&\vdots&\vdots&\vdots&\ddots\
\end{pmatrix}$We can create a similar grid for the positive integers by filling up
along the diagonals as follows:$\begin{pmatrix} 1&2&4&7&\cdots\\3 & 5 & 8 & 12&\cdots \\ 6&9&13&18& \cdots\\
10&14&19&25& \cdots\\\vdots&\vdots&\vdots&\vdots&\ddots \end{pmatrix}$We then correspond each rational to the integer in the correspond
place in the grid.
Question: What is the one-to-one correspondence the author is talking about?
Is the fact that for every diagonal in the rational numbers grid we have that the sum of the numberators (or denominators) is equal to the number on the $1^{st}$ column of the positive integers grid ?
Best Answer
Two sets $A, B$ have the same cardinality (the same 'size') if there is a bijection $A \to B$. That is, a one-to-one correspondence between the elements of $A$ and the elements of $B$.
The famous 'diagonalization' argument you are giving in the question provides a map from the integers $\mathbb Z$ to the rationals $\mathbb Q$. The trouble is it is not a bijection. For instance, the rational number $1$ is represented infinitely many times in the form $1/1, 2/2, 3/3, \cdots$.
Thus this diagonalization provides a map $\mathbb Z \to \mathbb Q$ which is onto the rationals but not one-to-one. Hence whatever the cardinalities of the two sets are, all we can conclude for now is that the cardinality of the integers is more than or equal to the cardinality of the rationals. Write
$$|\mathbb Q| \leq |\mathbb Z|$$
To complete the argument, note that $|\mathbb Z| \leq |\mathbb Q|$, as we can easily see by constructing a map $\mathbb Z \to \mathbb Q$ defined by mapping each integer $n$ to the rational number $n/1 = n$. This map is clearly one-to-one, but it is not onto.
Therefore
$$|\mathbb Z| \leq |\mathbb Q| \leq |\mathbb Z|$$
and we can conclude that
$$|\mathbb Z| = |\mathbb Q| $$