[Math] Bijective function between $\mathbb Q$ and $\mathbb Q\ge 0$

elementary-set-theoryfunctions

I have to prove that $\mathbb Q$ and $\mathbb Q \ge 0$ have the same cardinality. In order to do this I need to create bijective function between these sets. And I need help with this. I can't come up with any ideas.

Thanks.

Best Answer

Hint 1: There are obvious inclusions $$\mathbb{N} \hookrightarrow \mathbb{Q}_{\ge 0} \hookrightarrow \mathbb{Q}$$ so if you can find an injection $\mathbb{Q} \to \mathbb{N}$ then you'll have proved that all three sets have the cardinality.

Hint 2: (hover mouse over to see)

Every rational number has a unique expression in the form $$(-1)^i \cdot \dfrac{m}{n}$$ where $i \in \{ 0,1 \}$, $m \ge 0$, $n > 0$, and $p$ and $q$ are coprime. Consider encoding the triple $(i,m,n)$ as a natural number.

Hint 3: (hover mouse over to see)

Encode $(i,m,n)$ as $2^i3^m5^n$ and prove this defines an injective function using a familiar fact about natural numbers.