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

CC BY-SA 4.0
2022-03-09T10:56:19.923Z
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.
András Salamon
CC BY-SA 4.0
2022-03-09T11:53:33.593Z
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.
Emil Jeřábek
CC BY-SA 4.0
2022-03-09T13:04:23.380Z
I overlooked that the new functions in the elementary extension may fail to dominate $f$; thank you for the clear exposition.
András Salamon
CC BY-SA 4.0
2022-03-08T19:44:49.647Z
2022-03-08T21:40:59.347Z
2022-03-08T21:40:59.347Z
Emil Jeřábek
<blockquote>
<p>Is it true that <span class="math-container">$$O(n) = \bigcap \{ O(g) \mid g \in \omega(n) \}?$$</span></p>
</blockquote>
<p>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.</p>

<cc.complexity-theory><set-theory>
Order notation quirk
András Salamon
# Order notation quirk

(Asked by: username_0 on 2022-03-08)

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

**Tags:** cc.complexity-theory, set-theory

---

## 1 answers

### Answer by username_1 on 2022-03-08. Score: 7 | Accepted answer

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
Then $g\in\omega(n)$, but $f\notin O(g)$, as $|f(n\_k)|\ge kg(n\_k)$ for all $k$.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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.  
> **username_0**: I overlooked that the new functions in the elementary extension may fail to dominate $f$; thank you for the clear exposition.  

---

