# 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).
-
I don't think you've defined the order relation how you intended. And I sugges the set-theory tag in place of complexity-theory. – Joel David Hamkins Nov 10 '10 at 2:28
Perhaps you want $f\leq g$ iff $\exists C\, f\leq^\ast Cg$, or in other words, $\exists z\forall x\geq z\, f(x)\leq Cg(x)$. – Joel David Hamkins Nov 10 '10 at 2:53
I think what Joel means in his first comment is that you have switched the order of $f$ and $g$ between the two clauses of your definition. – Thierry Zell Nov 10 '10 at 3:03
@Thierry Zell: I did not realize that until I read your comment (thanks), but I do not know if that is all he meant. The right-hand side of the inequality contains x as a free variable and I do not know what this definition (as is written) means even if we swap f and g. – Tsuyoshi Ito Nov 10 '10 at 3:49
Perhaps related to Hamkins answer here: mathoverflow.net/questions/3057/… – Gerald Edgar Nov 10 '10 at 4:34

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.

-
Uncountability says nothing about explicit construction (it need not to be recursive). For example $x^\alpha$ (for $\alpha\in\mathbb{R}$) form a uncountable set. Thanks for link to 'fast-growing hierarchy'. – Piotr Migdal Nov 10 '10 at 10:15
But the point is that a continuum-indexed family will have a cofinal countable subset, and Yuval's argument can get above it, contradicting maximality. So no continuum-parameterized family can be maximal, if increasing the parameters makes the function higher in the order. In my answer, I tried to explain how this is not just about fast-growing functions, but pervasive in every local region of the order, since countable cuts can always be filled. – Joel David Hamkins Nov 10 '10 at 14:54

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.

-
Is it known that there can't be a Borel maximal chain in this preorder? – Andreas Blass Nov 10 '10 at 17:25
I think perhaps there can't be, since if $b$ is the Borel code for it, then the assertion that $b$ is the code of a maximal Borel chain is $\Pi^1_1$ and hence absolute to forcing extensions. But it seems that we can ruin this possibility by forcing to make the bounding number intermediate in a model where $\omega_1^L$ is also collapsed. Doesn't this rule out such Borel orders in the extension by the Mansfield-Solovay theorem? If so, then there couldn't have been a Borel order to begin with. (But I'm not sure if this all works.) – Joel David Hamkins Nov 10 '10 at 17:38
Well, I haven't been able to make that idea work out. Do you know how to ruin a Borel maximal linear subfamily by forcing? I think that your version of the question---whether there is a Borel maximal linear chain---is the best way to take the question. Perhaps this should be asked as a separate question... – Joel David Hamkins Nov 11 '10 at 0:15
There is no Borel (or even analytic) maximal chain. Kechris and Saint-Raymond proved (independently) that any analytic subset A of $\omega^\omega$ either (1) is bounded in the "smaller on a cofinite set" order or (2) includes all the branches of some superperfect tree (= Miller tree). In case (1) one easily gets a strict upper bound in the "big O" ordering, so A can't be a maximal chain. In case (2), it's easy to check that A can't be a chain at all. (I'm rather embarrassed not to have remembered the theorem of Kechris and Saint-Raymond in the first place, since I've often cited it.) – Andreas Blass Nov 14 '10 at 21:07
Andreas, great! You should post this as an answer. – Joel David Hamkins Nov 14 '10 at 22:16

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

-
If anybody can explain why the $x\rightarrow \infty$ didn't go under the $lim$ in the last I would appreciate it. Still learning LaTex. – Ross Millikan Nov 10 '10 at 4:06
Concerning the LaTeX-question: Probably you just forgot the backslash in front of lim? – Dirk Nov 10 '10 at 4:36
Can't you add $f(x)=x$ to your set? – Yuval Filmus Nov 10 '10 at 4:49
I fixed the \lim. – Gerry Myerson Nov 10 '10 at 4:51
The right hand side of the $\Leftrightarrow$ is pretty strange. You meant to say that the limit exists, or that the $\limsup$ is finite, or that $|f/g|$ is bounded on some right half-line; but what you wrote is more or less meaningless. – Mariano Suárez-Alvarez Nov 10 '10 at 4:58