2

From C.E. Patrascu and M. Patrascu's "Computing Order Statistics in the Farey Sequence" there is a line:

{all fractions in [0, x) with denominator q} ←→ {reduced fractions with denominator d, for all d|q}

Note q is an integer, x is real.

What is the meaning of a double arrow between sets? I'm familiar with it as implication, but not in this context. It can't be equality, as the denominators are different. Does it mean the cardinalities are equal? If so, an explanation of that would also be appreciated, as it is not mentioned in the text.

Asaf Karagila
  • 393,674
Alex F.
  • 63
  • This probably means that they associate a reduced fraction with its equivalence class – SacAndSac Mar 29 '22 at 16:35
  • 1
    A double arrow symbol $\longleftrightarrow$ between two sets usually indicates a bijection, therefore I would guess that the author means that there is a bijection between the set of rational numbers in $[0,x)$ that can be written as a fraction of integers with denominator $q$ and the set of the pairs $(n,d)$ such that $d$ divides $q$, $\operatorname{gcd}(n,d)=1$ and $0\le n< dx$. The inverse of that bijection being the map $(n,d)\mapsto \frac nd$. – Sassatelli Giulio Mar 29 '22 at 16:58

1 Answers1

2

It's a bijection. Going to the right, $\frac{n}{q}$ maps to its reduced form; going to the left, $\frac{m}{d}$ maps to $\frac{m(q/d)}{d(q/d)} = \frac{n}{q}$ where $n=m(q/d)$.

Mike Stay
  • 293