HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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).

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.

Context

StackExchange Computer Science Q#10341, answer score: 7

Revisions (0)

No revisions yet.