patternMinor
Is $\{\Theta(f)|f:\mathbb{N}\rightarrow\mathbb{N}\}$ Dedekind-complete?
Viewed 0 times
thetamathbbdedekindcompleterightarrow
Problem
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).
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).
Solution
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.
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.
Context
StackExchange Computer Science Q#10341, answer score: 7
Revisions (0)
No revisions yet.