How many Big $O$ equivalence classes are there?

Question

I'm talking about the set theory definition of $O(f(n))$, which is the set of all functions $g$ such that $O(f(n))=O(g(n))$.

What is the cardinality of $\{O(f(n)):f\in\mathbb{R}^\mathbb{R}\}$?

We can denote this cardinality $\kappa$. We know that $\kappa\geq\mathfrak{c}$ (because for every real number $x$, $O(x^n)$ is distinct).

We also know that $\kappa\leq\mathfrak{c}^\mathfrak{c}=2^\mathfrak{c}$, because the set it is the cardinality of has an injection onto $\{f:f\in\mathbb{R}^\mathbb{R}\}=\mathbb{R}^\mathbb{R}$.

So, we have upper and lower bounds. Assuming GCH holds for $\aleph_0$ and $\aleph_1$ (i.e. $\mathfrak{c}=\aleph_1$ and $2^\mathfrak{c}=\aleph_2$), then it is shown that $\aleph_1\leq\kappa\leq\aleph_2$, meaning it is either $\mathfrak{c}$ or $2^\mathfrak{c}$.

However, if ZFC can prove that $\mathfrak{c}<\kappa<2^\mathfrak{c}$, it would immediately disprove GCH. Assuming ZFC is consistent and $\mathfrak{c}<\kappa<2^\mathfrak{c}$, then ZFC can't prove this is true, and clearly can't give an exact cardinality for $\kappa$.

So, I would encourage those solving this problem to try and either prove $\kappa=\mathfrak{c}$ or $\kappa=2^\mathfrak{c}$, or your won't get very far.

Answer 1

For $A\subseteq\mathbb{R}$, let $f_A(x)=0$ if $0\not\in A$ and $x^2$ if $x\in A$. Then we have the following:

Suppose there are arbitrarily large elements of $A\setminus B$. Then $f_A\not\in O(f_B)$.

From here it's not hard to show that $\kappa=2^{\mathfrak{c}}$, as follows. Given $C\subseteq [0, 1)$, let $\hat{C}$ be defined as follows:

• For $x\in [2k, 2k+1)$, $x\in\hat{C}$ iff $x-2k\in C$.

• For $x\in [2k+1, 2k+2)$, $x\in\hat{C}$ iff $x-2k-1\in C$.

If $C_0\not=C_1$, then $\hat{C_0}$ contains arbitrarily large reals not in $\hat{C_1}$; so the set $$\{f_{\hat{C}}: C\subseteq [0,1)\}$$ is a big-O antichain and has size $2^\mathfrak{c}$.

---

Meanwhile, if we restrict attention to continuous functions only, we get $\mathfrak{c}$, since there are only continuum-many continuous functions in the first place.