Is Collection of Big O's a Set?

Question

Is the object $$ M = \{ \mathcal{O}(f(x)) \mid f: \mathbb{R} \to \mathbb{R} \}$$ a set? Or perhaps take $\Omega(f(x))$ instead?

Answer 1

Yes, it's a set (at least according to the standard axioms of set theory).

What you've described is a set of sets of functions. Sets of sets of sets of ... may feel weird at first, but are perfectly legal objects, and the axioms of ZFC in fact prove that they exist.

---

In fact, in ZFC everything is a set! For example, here is one way the real numbers can be implemented inside ZFC (in the same way that an algorithm can be implemented in a language via a specific program):

• A real number is a set of rational numbers (the left Dedekind cut).

• A rational number is a set of ordered pairs of integers (= the set of representations of that rational).

• An integer is a pair of the form $(m, i)$ where $m$ is a natural number and $i=0$ ("negative") or $1$ ("positive") - with the rule that we don't allow $(0, 0)$ (we don't distinguish between $+0$ and $-0$).

• Natural numbers - this part is standard in set theory - are finite ordinals: $0$ is $\emptyset$ and $n+1$ is $n\cup\{n\}$.

And all of this is ultimately built just out of the emptyset, via complicated "sets-of-sets-of..." business! (Note that for now I'm ignoring the question of whether e.g. $0$ actually is $\emptyset$ - I'm thinking of ZFC as simply giving a specific way to implement mathematics that I already know about "somehow else.")