# How many Big $O$ equivalence classes are there?

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.

• Thank you. I really thought this question would be downvoted because of some obvious solution I was missing, but I guess the research I did on it myself would help? I guess one could generalize my logic to show that trying to find any cardinality $\beth_\alpha\leq\kappa\leq\beth_\beta$ is futile unless showing it's $\beth_\alpha$ or $\beth_\beta$ for $\alpha\geq1$ and $\beta>\alpha$. – user477899 Sep 19 '17 at 23:32

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.

• You've been really helpful to me lately, thank you. – user477899 Sep 20 '17 at 0:05
• As for your last comment in your answer, the same can be said about the big $O$ classes in $\mathbb{R}^\mathbb{N}$ – Maxime Ramzi Sep 20 '17 at 0:52
• Very true, good use of the "theorem". (I put it in quotation marks because it isn't really a theorem, but a mathematical observation of whether or not something is "hopeless" to prove.) – user477899 Sep 20 '17 at 4:24