Define the collection of sets $\left\{Q_n\right\}$ as follows: $$Q_1 = \{0\};\quad Q_2 = \left\{\frac{1}{2}\right\} \cup Q_1; \quad Q_3 = \left\{\frac{1}{3}, \frac{2}{3}\right\} \cup Q_2;$$ $$\left\{\frac{1}{4}, \frac{2}{4}, \frac{3}{4}\right\} \cup Q_3; \quad \left\{\frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \frac{4}{5}\right\} \cup Q_4;$$ and then generally $$Q_n = \left\{\frac{1}{n}, \frac{2}{n}, \frac{3}{n}, \frac{4}{n}, \ldots, \frac{n-1}{n}\right\} \cup Q_{n-1}.$$ (There will of course be repeated rational numbers that, once reduced to lowest terms, will only be counted once).
Observe now that the cardinality of $Q_n$ grows more rapidly than $n$: $$|Q_n| \leq \frac{n(n-1)}{2} + 1, \text{ so thus } |Q_n| \in \mathcal{O}(n^2).$$
However, if we account for reduction of each quotient $\frac{k}{n}$ into lowest terms, we have the stricter inequality $$|Q_n| < \frac{n(n-1)}{2} + 1$$ for values of $n$ greater than $n = 3$.
Define a sequence $\left\{q_n\right\}_{n = 1}^{\infty}$ by $q_n = \frac{|Q_n|}{n}$.
Does the sequence $\{q_n\}$ diverge as $n$ goes to infinity?
In other words, accounting for reduction to lowest terms, does the cardinality of $Q_n$ still grow faster than linearly for increasing $n$?
I am guessing that a strict solution will somehow involve the Möbius function. This will allow us to account somehow for the number of prime divisors of each integer $n$ (via inclusion and exclusion, i.e. we want to account for everything divisible by 2 and 5, but not double count those divisible by 10). But I do not know how to actually use the Möbius function to enumerate the number of unique rational numbers with denominator $n$.