1
$\begingroup$

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.

  • 0
    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}$...2012-12-11

4 Answers 4

2

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.

1

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.

0

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.