6
$\begingroup$

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).

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

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I see why this shows that $F$ has no minimum, but why does it show that $F$ has no infimum? $\endgroup$ – usul Mar 7 '13 at 3:07
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus Mar 7 '13 at 4:54
  • $\begingroup$ 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. $\endgroup$ – frafl Mar 7 '13 at 8:45
  • $\begingroup$ @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. $\endgroup$ – frafl Mar 7 '13 at 8:52
  • $\begingroup$ mathoverflow.net/questions/49415/… $\endgroup$ – frafl Mar 7 '13 at 10:36
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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)!? $\endgroup$ – frafl Mar 7 '13 at 0:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.