Big O notation and the maximal set of comparable functions One can easily find a set of functions that are comparable with respect to the big O notation that is,
$$f \leq g \Leftrightarrow \exists c \exists x_0 \forall x\geq x_0: |f(x)| \leq c|g(x)|,$$
for $f,g \in \mathbb{R}\rightarrow \mathbb{R}$ and continuous.
For example, a set containing all products of polynomials, logarithms, exponential functions and factorial is good. However, it is not a maximal one (e.g. $\ln \ln x$ is lesser than all of its elements).
According to Kuratowski-Zorn lemma, there is a maximal set of comparable functions. My questions are:


*

*Is there one canonical maximal set of comparable functions with respect to big O notation?

*Is there an explicit construction of any such set?


Edit:


*

*There was $\lim_{x\rightarrow\infty} |f(x)| \leq C|g(x)|$ which was in my intention an informal notation for the above ($\lim$ about the whole inequality, not only the left hand site).

*However, I do not cling to the definition (especially if some tinkering is going to give more interesting results).

 A: 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.
A: There is no countable chain which is maximal: if $f_i$ is a sequence of functions, then define
$g(n) = n \cdot \max_{i \leq n} f_i(i)$
The function $g$ grows faster than all the functions in the sequence.
So there's probably no simple explicit construction other than the one obtained through transfinite induction.
You could ask what is the (minimal/maximal) cardinality of a maximal sequence - that probably depends on cardinal characteristics of the continuum (given the CH it's $\aleph_1$ since you can take all piecewise linear functions whose values at the natural numbers are all natural).
You can further ask what happens if the functions need to be recursive - that's the fast-growing hierarchy.
A: It seems what you really want is a set of functions $A$ such that $$\forall (f,g\in A) f \leq g \Leftrightarrow \exists C\in\mathbb{R}:\lim_{x\rightarrow\infty}\frac{|f(x)|}{|g(x)|}\leq C$$  I think the set of functions that have non-zero finite limits qualifies.  If you put in too many growth choices it fails because there is no $$\lim_{x\rightarrow\infty}\frac{|f(x)|}{|g(x)|}$$ for some pairs, if $g$ grows slower than $f$.
