# 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.

• Do you understand the proof that $\Bbb Q$ is denumerable? – David Dec 19 '14 at 1:22
• @David I think the only think I understood is the visual representation: $x$ and $y$ contain respectively the $numerator$ and $denominator$... – nbro Dec 19 '14 at 1:24
• If you know that $\mathbb N\times \mathbb N$ is denumarable, and $\mathbb Q$ is denumerable, you can prove this very quickly. – Thomas Andrews Dec 19 '14 at 1:26
• Here is a proof that $\Bbb Q$ is denumerable. I suggest you make absolutely sure you understand this, then come back to your question. – David Dec 19 '14 at 1:27
• "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)." A set is denumerable if there is a bijection between the set and the natural numbers. (That is, a set is denumerable if it is equinumerous with $\mathbb{N}$.) – Trold Dec 19 '14 at 1:29

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.
• By pairs of rationals, you mean, for example, $\frac{1}{2}, \frac{1}{2}$, resulted by the cartesian product of $\mathbb{Q} \times \mathbb{Q}$? – nbro Dec 19 '14 at 1:48
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. • How do you handle fractions with the same value like$1/2$and$2/4$? Or asked the other way round what rational is given by$(0,0)$? What by$(1,1)\$? – mvw Dec 19 '14 at 1:43