1
$\begingroup$

Define $$f:\mathbb Z \times \mathbb{Z}_{>0} \to \mathbb{Q}$$ by $$f(p, q) = \frac{p}{q} $$

Edit: Is there an explicit map then that is a bijection?

$\endgroup$

2 Answers 2

6
$\begingroup$

It doesn't; $f$ is not injective:

$f(2, 4) = \frac{2}{4} = \frac{1}{2} = f(1, 2)$

$\endgroup$
1
$\begingroup$

You asked for an explicit map that is a bijection.

The map $f$ that you've defined is a surjection, but it's not injective. How can we make it injective? Well, we first construct a bijection $g$ from $\mathbb Z_{>0}$ to $\mathbb Z\times\mathbb Z_{>0}$

\begin{align} \color{#c00}{g(1)=}(0,&1)\\ \color{#0a0}{g(2)=}(-1,&1)\\ \color{#0a0}{g(3)=}(0,&2)\\ \color{#0a0}{g(4)=}(1,&1)\\ \color{#00a}{g(5)=}(-2,&1)\\ \color{#00a}{g(6)=}(-1,&2)\\ \color{#00a}{g(7)=}(0,&3)\\ \color{#00a}{g(8)=}(1,&2)\\ \color{#00a}{g(9)=}(2,&1)\\ g(10)=(-3,&1) \end{align} Can you see how the pattern continues?

Now $f\circ g$ is a surjection from $\mathbb Z_{>0}$ to $\mathbb Q$. How do we convert it into a bijection? Define a function $h\colon \mathbb Z_{>0}\to\mathbb Z_{>0}$ by $$ h(n)=\min\{m\colon\textrm{ There exists a sequence }m_1<\dots<m_n=m\textrm{ such that }\\f(g(m_1)),\dots,f(g(m_n))\textrm{ are distinct.}\} $$

Exercise: Show that $f\circ g\circ h$ is a bijection from $\mathbb Z_{>0}$ to $\mathbb Q$.

Then our required bijection from $\mathbb Z\times\mathbb Z_{>0}$ to $\mathbb Q$ is given by $$ f\circ g\circ h\circ g^{-1} $$

This should illustrate the general point: bijections from $\mathbb Z$ (and similar sets) to $\mathbb Q$ exist, but in general they are difficult to construct, they don't have nice formulae and they aren't intuitive.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .