Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

Let me assume that you mean the order on functions $f$ and $g$ by which $f\leq g$ if and only if $\exists C\exists x_0\forall x\geq x_0$ $f(x)\leq C\cdot g(x)$. In other words, $f(x)$ is eventually less than $C\cdot g(x)$. This order is a linear smoothing out of the usual eventually-less-than order on functions, which has been considered in many other questions here on MO. This relation is more properly called a pre-order than an order, since we can have $f\leq g\leq f$ for distinct $f$ and $g$, but there is an underlying equivalence relation. We may say that $f\lt g$ if $f\leq g$ but $g\not\leq f$. Finally, let me say that much of the interesting phenomenon in this order arises already in the case of functions $f:\mathbb{N}\to\mathbb{N}$ rather than $f:\mathbb{R}\to \mathbb{R}$.

(Note that this way of defining the order does not presume that the limit $\lim_{x\to\infty} \frac{f(x)}{g(x)}$ exists, and this makes a huge difference in the nature of the order. For example, if you insist that the limit exist, then even a function $f$ that is everywhere less than $g$ will not necessarily be less in the order, if $f$ periodically jumps up nearly to $g$ and then down to $0$ in such a way that prevents the limit from converging.)

This is a partial order on the function space, and you are seeking a natural linearly ordered family of functions that is maximal, in the sense that no additional functions can be added to it while preserving pairwise order-comparability of the elements. I claim that there will be no nice such family along the lines that you seek, even in the case just of functions $f:\mathbb{N}\to\mathbb{N}$.

First, as observed by Yuval Filmus, there is no countable maximal linearly ordered subset. He explains that one can always exceed any given countable family with a higher rate growth. This observation can be refined to show a bit more: if $f_n\lt g$ for all $n$, then there is $f\lt g$ with $f_n\lt f$ for all $f$. That is, we can exceed all the $f_n$ even while staying below $g$. To see this, observe that $f_n$ is eventually less than $c_n g_n$ for some constant $c_n$. We may assume that $c_n=1$ by absorbing the constant $\frac 1{c_n}$ into the function $f_n$. Let $d_n$ be the point beyond which $f_n$ is less than $c_n g$. Now build a function $f$ which at value $m$ is the maximum of the $f_n(m)$ for which $d_n\leq m$. Thus, $f$ is eventually bounding every $f_n$ and if $g$ is eventually below $c\cdot f$, then it is also eventually below many $c\cdot f_n$ for large enough $n$. So $f$ is as desired. This argument is essentially the same as Hausdorff used to show that countable Hausdorff gaps can always be filled, as I explain in this MO answer.

The previous observation shows that the order has no cuts of order type $(\omega,\omega)$. That is, any partition of the order into a lower family and an upper family, each countable, can be extended by placing additional functions in the middle. For example, you can continually add functions in this way to the lower family.

My main observation now is that, because of this, there can be no maximal linearly ordered family that is parameterized by reals $f_c$ or by finite sequences of reals $f_{\vec c}$, in such a way that increasing the parameters makes a higher function. (This is true even for the functions $\mathbb{N}\to\mathbb{N}$.) The reason is that the real parameters all have countable cofinality, and so as we increase parameters from below and decrease them from above, we can find a countable cofinal subfamily. Our parameterized family will have just one function in the gap, but the argument above shows that we can fill this gap with uncountably many. The problem is that every point in $\mathbb{R}$ is approachable by a countable sequence, but the order $\leq$ on functions is not at all like that.

There is indeed a rich set-theoretic interaction with the possible cofinalities that arise in the order (and this is the reason I suggested the set-theory tag). In particular, although the observation above shows that uncountable cofinalities must arise, the particular cardinals that arise as the cofinality of the entire order are independent of ZFC. This phenomenon is studied in the theory of cardinal characteristics of the continuum via such concepts as the bounding number and the dominating number.

Finally, despite all this, let me say that it is consistent with ZFC that there is a definable, constructible maximal linearly ordered subset of your order, because in Goedel's constructible universe $L$ there is a $\Delta^1_2$-definable well-ordering of the reals, and one can use this order to produce a canonical family by transfinite recursion, whose definition is fairly low by descriptive set-theoretic standards.

Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k