7
$\begingroup$

Is it true that $$O(n) = \bigcap \{ O(g) \mid g \in \omega(n) \}?$$

This appears to be a straighforward question about sets of functions, but on closer examination leads to some murky waters. I would be interested either in a construction of a counterexample function which doesn't require a choice principle independent of ZF set theory, or a proof which avoids invoking such a principle.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

The identity is provable in ZF (or even in $\mathrm{RCA}_0^*$). The $\subseteq$ inclusion is trivial. For the $\supseteq$ inclusion, let $f\notin O(n)$. Define an integer sequence $\{n_k:k\in\mathbb N\}$ by $$n_k=\min\{n:|f(n)|\ge k^2(n+1)\}.$$ Note that $n_k$ is non-decreasing, $n_0=0$, and $\lim_kn_k=\infty$, thus $\mathbb N$ is the disjoint union of the intervals $[n_k,n_{k+1})$, and we can define a function $g$ by $$g(n)=kn,\qquad n_k\le n<n_{k+1}.$$ Then $g\in\omega(n)$, but $f\notin O(g)$, as $|f(n_k)|\ge kg(n_k)$ for all $k$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Perfect, thanks! My handwaving argument was that for any finite subset $F$ of $\omega(n)$ there seems to be a function $f \in \bigcap \{O(g)\mid g \in F\} \setminus O(n)$, so by compactness there must exist a function $f \in \bigcap \{O(g)\mid g \in \omega(n)\} \setminus O(n)$. I am probably assuming that these are all first-order sentences and missed something in there which is not first-order expressible. $\endgroup$
    – András Salamon
    Commented Mar 9, 2022 at 10:56
  • 1
    $\begingroup$ Are you talking about expressibility in models of ZF? Your compactness argument only ensures that any model $M$ has an elementary extension $M'$ with $f\in M'$ such that $M'\models f\notin O(n)$ and $M'\models f\in O(g)$ for each $g\in M$ such that $M\models g\in\omega(n)$. However, there will be new functions $g\in M'\smallsetminus M$ such that $M'\models g\in\omega(n)$, and for these, $M'\models f\in O(g)$ may fail. $\endgroup$
    – Emil Jeřábek
    Commented Mar 9, 2022 at 11:53
  • $\begingroup$ I overlooked that the new functions in the elementary extension may fail to dominate $f$; thank you for the clear exposition. $\endgroup$
    – András Salamon
    Commented Mar 9, 2022 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.