Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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

3 Answers 3

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.