# Strategies for proving that a set is denumerable?

This concept has been troubling me. For example, I want to prove that $$\mathbb Q \times \mathbb Q \sim \mathbb N.$$

This is what my professor has told us:

$$\mathbb Q \sim \mathbb N$$

$$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N \times \mathbb N \sim \mathbb N$$ $$\Rightarrow \mathbb Q \times \mathbb Q \sim \mathbb N$$

But this isn't a complete proof because I haven't shown why $\mathbb Q \sim \mathbb N$, and I'm not sure how to do that. I know that if a set is denumerable, that means that it is equinumerous with $\mathbb N$. And I also know that if one is equinumerous with another, that means that there exists a bijection between the two sets. I'm just having trouble putting all of these ideas together into one proof.

-
It won't be easy to create a bijection, if you wish to do so, look at, e.g. Stern-Brocot tree. On the other hand, it would be quite easy to find injections $f$ and $g$ such that $\mathbb{Q}\times\mathbb{Q} \xrightarrow{f} \mathbb{N}$ and $\mathbb{N} \xrightarrow{g} \mathbb{Q}\times\mathbb{Q}$. – dtldarek Dec 11 '12 at 9:20
Can you prove that $\mathbb{N}\sim \mathbb{Z}$? Because then you could try to find an injection $\mathbb{Q} \hookrightarrow \mathbb{Z}\times \mathbb{N}$... – Jan Keersmaekers Dec 11 '12 at 9:20

You'll agree that $\mathbb{Z}$ is equipotent to $\mathbb{N}$; $\mathbb{Q}$ is defined as a quotient of $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, thus the cardinality of $\mathbb{Q}$ is less or equal to that of $\mathbb{Z} \times (\mathbb{Z} \setminus \{0\})$, which is the same as the cardinality of $\mathbb{N}$. Of course you have the opposite "inequality" (think of $\mathbb{N}$ as included in $\mathbb{Q}$, even if it's not correct), and you conclude by Schroeder-Bernstein theorem.

-

Here is a "graphical" construction of a bijection between $\mathbb{Q}$ and $\mathbb{N}$ - it's going to be really hard to put into a formula, but I believe, and hope you will too, that it constitutes a valid proof:

We're going to build a sequence $q_n$ of all rational numbers such that each rational number appears only once. (This is exactly the meaning of a bijection.)

1. Draw an infinite two-dimensional grid, such that at each square in the grid you have two integers: The "x" coordinate and the "y" coordinate. The "center" square is $(0, 0)$.

2. Traverse the grid "inside out", by starting at the center square and going counterclockwise in a spiral: $(0, 0), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (1, 2), (0, 2), ...$

3. Whenever you are at a square $(x, y)$, if $y=0$ then skip this square. Otherwise, use $x/y$ as the next element of your sequence $q_n$, unless you've already used this exact value, in which case - skip this square.

-

Do you know the Schröder-Bernstein theorem? With it you need only find an injection from $\Bbb N$ to $\Bbb Q$, which is trivial, and from $\Bbb Q$ to $\Bbb N$. The latter is easily done using a pairing function from $\Bbb N\times\Bbb N$ to $\Bbb N$: just map each rational as the ordered pair of its numerator and denominator when it’s written in lowest terms with positive denominator.

-