Order structure of asymptotics

Question

Consider the set $A = \{\theta(f) \mid f : \mathbb{R} \rightarrow \mathbb{R},\;f\,\text{non-decreasing}\}$ where $\theta(f)$ denotes the set of functions which are asymptotically within a constant factor of $f$. Define an order on $A$ by setting $\theta(f) \le \theta(g)$ if $f \in O(g)$.

What is the order structure of $A$? For that matter, what is the cardinality?

$\mathbb{R}$ can be embedded in $A$ by sending $\alpha$ to $x\mapsto x^\alpha$, but $A$ has a bottom element, so they are certainly not isomorphic.

Answer 1

Edit: I found a book on this sort of thing: G H Hardy Orders of Infinity, The 'Infinitärcalcül' of Paul Du Bois-Reymond. Some of the remarks below (2, 5 and 6) are similar to results in the book.

For non decreasing functions on the reals under this ordering, you can say the following:

1. It has cardinality $\mathfrak{c} = 2^{\aleph_0}$.
2. It is not a linear ordering.
3. It is dense. That is, whenever $f < g$, there is $h$ with $f < h < g$.
4. It has binary meets and joins.
5. Every countable subset has an upper bound.
6. It is not complete. In fact, I think one can show that no strictly increasing countable sequence (eg the polynomials) has a least upper bound.
7. One can use 3 and 6 to show that $\omega_1$ embeds into $\{h \;|\; f \leq h \leq g \}$ for every $f < g$.

Proof of 1

The set of all non decreasing functions $\mathbb{R} \rightarrow \mathbb{R}$ has cardinality $\mathfrak{c}$. This is because any non decreasing function has only countably many discontinuities (Froda's theorem). This means that there are only $\mathfrak{c}^{\aleph_0} = \mathfrak{c}$ possible sets of discontinuities. Then for each set of discontinuities, you can recover the function $f$ from its value on $\mathbb{Q}$ together with the set of discontinuity (which is countable). Hence $A$ has cardinality at most $\mathfrak{c}$. But as it says in the question, the reals can be embedded into $A$, so the cardinality is exactly $\mathfrak{c}$.

Proof of 2

We will construct $f$ and $g$ such that $f \nleq g$ and $g \nleq f$. For $x < 0$, set $f(x) = g(x) = 0$. For $n \in \mathbb{N}$, set $$f(n) = \begin{cases} n! & n \text{ is even} \\ (n+1)! & n \text{ is odd} \end{cases}$$ and $$g(n) = \begin{cases} (n+1)! & n \text{ is even} \\ n! & n \text{ is odd} \end{cases}$$ Then extend $f$ and $g$ to $\mathbb{R}$ piecewise linearly. See that we have ensured that for any $n_0$, if $n > n_0$ is even, then $g(n) > n_0 f(n)$, and if $n > n_0$ is odd then $f(n) > n_0 g(n)$. Hence we can't have $f \leq g$ or $g \leq f$, as required.

Proof of 3

Suppose that $f < g$. Note that we can assume WLOG that $f(x), g(x) \geq 0$ for all $x$. We need to construct $h$ such that $f < h < g$. First, set $h(x) = f(x)$ for $x < 0$. We now define $h$ in $\omega$ stages. At each stage $n$, we define a real $x_n$, and define $h$ on $[x_{n-1}, x_n]$.

At odd stages we ensure that $g \nleq h$. We do the following. Let $M = \max(1, h(x_{n - 1}) / f(x_{n - 1}))$. Since $g \nleq f$, there is some $x > x_{n-1}$ such that $g(x) > M n f(x)$. Let $x_n = x + 1$ and define $h(x) = \max(h(x_{n-1}), f(x))$ for $x \in [x_{n-1}, x_n]$. Note that at $x$, we have $g(x) > M n f(x) \geq M n f(x_{n-1}) \geq n h(x_{n-1})$ and $g(x) > n f(x)$ and so $g(x) > n h(x)$.

At even stages we ensure that $h \nleq f$. Note that there is some $x > x_{n-1}$ such that $g(x) > n f(x)$. Let $x_n = x + 1$ and for $x \in [x_{n-1}, x_n]$ define $h(x) = \max(h(x_{n-1}), g(x))$. Then at $x$ we have $h(x) \geq g(x) > n f(x)$.

See that we do have $f < h < g$, as required.

Answer 2

NB: The following is for an earlier version of the question in which the functions are not necessarily monotone.

Here are two things you can say:

1. $\langle \mathcal{P}([0, 1)), \subseteq \rangle$ can be embedded into $A$. In particular, $A$ has cardinality $2^\mathfrak{c}$.
2. $A$ is dense. That is, whenever $f < g$ there is $h$ such that $f < h < g$.

There are probably a lot more things you can say as well. For instance, I suspect that it's possible to embed $\omega_2$ into $A$.

Proof of 1

For $X \subseteq [0, 1)$ define for each $n \in \mathbb{Z}$ and each $x \in [0, 1)$, $$f_X(n + x) = \begin{cases} 0 \qquad x \notin X \\ n \qquad x \in X \end{cases}$$ Note that this defines a total function on $\mathbb{R}$ for each $X$. We clearly have that $X \subseteq Y$ implies $f_X \leq f_Y$. For the converse, suppose that $f_X \leq f_Y$. Then there is some $M$ and some $x_0$ such that for $x > x_0$, $f_X(x) \leq M f_Y(x)$. Choose $n > x_0$ such that $n \in \mathbb{N}$, and let $x \in X$. Then $f_Y(n + x)$ can't be zero, because then $M f_Y(n + x) = 0$ and that would contradict $f_X(n + x) \leq M f_Y(n + x)$.

Proof of 2

Suppose that $f < g$. Since $g \nleq f$, we know that for every $n$ there is some $x_n \in \mathbb{R}$ such that $x_n > n$ and $g(x_n) > n f(x_n)$. Define $h$ as follows: $$h(x) = \begin{cases} f(x) \qquad \exists n \text{ such that } x = x_{2n} \\ g(x) \qquad \text{otherwise} \end{cases}$$

Then we clearly have $f \leq h \leq g$. Suppose that $g \leq h$. Then there would be some $N$ such that whenever $x > N$, $g(x) \leq N h(x)$. However, we know that $x_{2N} > N$ and $g(x_{2N}) > 2N f(x_{2N}) = 2N h(x_{2N})$, giving a contradiction. Hence, $h < g$ and a similar argument using $2N + 1$ instead of $2N$ shows that $f < h$.