# Is $\{\Theta(f)|f:\mathbb{N}\rightarrow\mathbb{N}\}$ Dedekind-complete?

Let $\Theta$ and $o$ be defined as usual (Landau-notation). For two equivalence classes defined by $\Theta$ we define $$\Theta(f) <_o \Theta(g) :\Leftrightarrow f \in o(g)\qquad.$$ Let $$\mathbb{F}:= \{\Theta(f)\mid f:\mathbb{N}\rightarrow\mathbb{N}\}$$

My question: Is $\langle \mathbb{F},<_o\rangle$ Dedekind-complete, i.e. given a set $F\subseteq \mathbb{F}$ with an upper bound $f_u,\forall f \in Ff\in o(f_u)$ are there $f_\inf$ and $f_\sup$ s.t. $$\forall \Theta(f)\in F: \Theta(f_\inf) <_o \Theta(f) \qquad{(1)}$$ $$\forall g: (g\text{ fulfills (1)} \Rightarrow g \in o(f_\inf))$$

($f_\sup$ is defined analogously)?

Note: We don't need to assume a lower bound, since there is no infinite strictly decreasing series of $n \in \mathbb{N}$, i.e. $\Theta(0)$ is always a lower bound.

Background: I'd like to consider $\inf \{f \mid L \in N/DTIME/SPACE(f)\}$ for some Language $L$, but that only makes sense if such a (class of) function(s) exist(s).

• Should the second line of maths read "$g$ fulfills (1) $\implies f_{\inf} \in o(g)$"? – usul Mar 7 '13 at 2:52

Let $F$ be the set of all functions $f(n)$ such that $\sum_n f(n)$ diverges. Then $F$ is bounded from below by $f(n) = 1/n^2$ (for example), but there is no infimum: for every divergent sequence, you can find a sequence which diverges more slowly. This is a classical result of Hausdorff.

Similarly, if $F$ is the set of all functions $f(n)$ such that $\sum_n 1/f(n)$ converges, then $F$ is bounded from above by $f(n) = n$, but there is no supremum since for every convergent sequence you can find a convergent sequence which grows much faster.

Edit: This paper (among others) provides a proof of these claims.

• I see why this shows that $F$ has no minimum, but why does it show that $F$ has no infimum? – usul Mar 7 '13 at 3:07
• Well, the infimum cannot be divergent (since then it's not a lower bound), and it cannot be convergent (since then it's not the greatest lower bound). – Yuval Filmus Mar 7 '13 at 4:54
• Thanks, if knew to search for a "minimal diverging series", I found math.stackexchange.com/questions/198999/… (which was even asked by Kaveh). I'll accept this answer even though, you have to upscale the infimum part by e.g. $2^n$, because in $\mathcal{N}^\mathcal{N}$ only the functions in $\Theta{0}$ have converging series. – frafl Mar 7 '13 at 8:45
• @usul: The set of those whose series converges/diverges are the upper bounds/lower bounds to the other set, so if there is an infimum/supremum it has to belong to one of the sets. – frafl Mar 7 '13 at 8:52
• mathoverflow.net/questions/49415/… – frafl Mar 7 '13 at 10:36

No and no. If you have a supposed function $f(n)$ as infimum, the function $f(n) / n$ is smaller; if $F(n)$ is a supposed supremum, $n F(n)$ is larger.

• Sorry, I don't understand that. That argument would work for $\{r \in \mathbb{R}|r>\pi\}$, too ($\pi$ is not an infimum, because $e$ is smaller)!? – frafl Mar 7 '13 at 0:16