Show that $\mathbb{Q}\times \mathbb{Q}$ is denumerable [duplicate]

I am new to functions and relations, and with some concepts I am not so familiar. I have a question in an homework:

Show that $\mathbb{Q} \times\mathbb{Q}$ is denumerable.

From what I understood, denumerable means that it is infinitively countable. There are some posts on the web about this topic, but I am still not understanding their explanation, maybe because they are not explained so easily (for me).

From what I understood, a set is denumerable if there's a relation with the natural numbers (but I am still not understanding what is this relation).

I have heard also about equinumerous sets (contain a bijective function = onto + one-to-one function), but I cannot relate this information with the problem to try to solve it.

Solution 1:

Since you already know that the rationals are denumerable, they can be enumerated as $r_1,r_2,r_3,\ldots\,$. Therefore all pairs of rationals can be arranged in a table $$\def\p#1#2{(r_{#1},r_{#2})} \matrix{\p11&\p12&\p13&\cdots\cr \p21&\p22&\p23&\cdots\cr \p31&\p32&\p33&\cdots\cr \vdots&\vdots&\vdots\cr}$$ This table can then be turned into a list diagonal by diagonal, exactly as in the standard proof that $\Bbb Q$ is denumerable. Therefore $\Bbb Q\times \Bbb Q$ is denumerable.

Solution 2:

The relation that's needed with the natural numbers $\mathbb{N}$ has to be a 'bijection', which means a one-to-one correspondence. In practice, that means that a set $S$ is denumerable (or 'countable' as it's more often called) if you can define a scheme for labelling every element of the set with a natural number, so that no natural number is used more than once.

To show $\mathbb{Q}\times \mathbb{Q}$ is denumerable I would proceed in two steps. (1) prove that if a set $S$ is countable then $S\times S$ is countable. (2) show a bijection between $\mathbb{Q}$ and $$\mathbb{N}\times \mathbb{N}$

To prove (1), lay out all elements of $S\times S$ in a grid that takes up one quarter of the number plane, such that the element $(S_i,S_j)$ takes up the grid point with coordinates $(i,j)$, where $S_i$ is the element that has been assigned label $i$. Then imagine a path that goes as follows: (0,0), (1,0),(0,1),(0,2),(1,1),(2,0),(3,0),(2,1),(1,2),(0,3),(0,4),(1,3),(2,2),(3,1),(4,0),(5,0),(4,1).... For any specified grid point, this zigzag path must eventually reach it, so we can label the elements of $S\times S$ by how many steps along the zig-zag path one has to go to get to that point.

(2) Is easier. First prove that the signed integers $\mathbb{Z}$ are countable, by the alternating path on the number line 0,1,-1,2,-2,3,-3,.... THen we know $\mathbb{Q}$ is a subset of $\mathbb{Z}\times\mathbb{Z}$, since a rational number is defined as the ratio of two integers where the denominator is nonzero.