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.
Best Answer
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.