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
    It won't be easy to create a bijection, if you wish to do so, look at, e.g. [Stern-Brocot tree](http://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_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}$.2012-12-11
  • 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