Big O notation and the maximal set of comparable functions - MathOverflow

Big O notation and the maximal set of comparable functions

2010-11-10T02:13:54Z

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).

Answer by Ross Millikan for Big O notation and the maximal set of comparable functions

2010-11-10T03:44:41Z

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$.

Answer by Yuval Filmus for Big O notation and the maximal set of comparable functions

2010-11-10T04:47:20Z

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.

Answer by Joel David Hamkins for Big O notation and the maximal set of comparable functions

2010-11-10T12:21:57Z

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.