Why is this a bijection?

Question

Two fractions $\frac{p}{q}$, $\frac{p'}{q'}$ are said to be a Farey Pair if $pq'-p'q=\pm1$. Let $\frac{p}{q} < \frac{p'}{q'}$ be a Farey Pair, then $$ f:\left[\frac{0}{1}, \frac{1}{1}\right] \cap \mathbb{Q} \to \left[\frac{p}{q}, \frac{p'}{q'}\right] \cap \mathbb{Q} $$ defined by $$ f\left(\frac{u}{v}\right) = \frac{(p'-p)u+pv}{(q'-q)u+qv} $$ is a bijection. Why is that?

From here, pg. 49 - 50.

Answer 1

The plan of the proof:

• Show that the definition of $f$ is correct, i.e. it doesn't depend on the choice of $u,v$. Precisely, prove that $R(u,v)=R(u',v')$ if $u/v=u'/v'$ where $R(u,v)$ is a right-hand side of the formula defining $f$.
• Show that $f(u/v)\in [p/q,p'/q']\cap\Bbb Q$ if $u/v\in [0,1]\cap \Bbb Q$. To do it, prove that $$ \frac pq\leq \frac{(p'-p)u+pv}{(q'-q)u+qv}\leq \frac {p'}{q'}\text{ provided } 0\leq u\leq v\neq 0.$$
• Find the formula for the inverse function $g$. To do it solve the equation $y=f(u/v)$ for $u/v$ and put $g(y)=u/v$. You'll get $$g(y)=\frac uv = \frac{qy-p}{(q-q')y+(p'-p)}.$$
• Show that $g(y)\in [0,1]\cap\Bbb Q$ if $y\in y\in [p/q,p'/q']\cap\Bbb Q$.
• That's it. If you want to be sure everything is correct, calculate $f\circ g$ and $g\circ f$. You should get identities.

Remark There are more or less two ways to prove that a given function $f$ is a bijection.

• One can show that $f$ is injection and surjection.
• One can find an inverse function $g$, which (is well defined and) acts from the codomain of $f$ to the domain of $f$. To verify $g$ is an inverse it suffices to show that $f\circ g$ and $g\circ f$ are identities.

You can do it by solving the equation $y=f(x)$ for $x$. If you find the unique solution in the domain of $f$ for any $y$ from the codomain, you get both injectivity (uniqueness of solution) and surjectivity (existence of solutions). Moreover, you find an invere function $g(y)=x$ such that $y=f(x)$.

In this situation it seems important to verify that $f$ is well defined, i.e. the value doesn't depend on the choice of the form the argument is presented and that all the values lie in the codomain.