In mathematics, a Hausdorff gap consists roughly of two collections of sequences of natural numbers, such that there is no sequence lying between the two collections. The first example was found by Hausdorff (1909). The existence of Hausdorff gaps shows that the partially ordered set of possible growth rates of sequences is not complete.
Definition Let ω ω {\displaystyle \omega ^{\omega }} be the set of all sequences of non-negative integers, and define f < g {\displaystyle f<g} to mean lim ( g ( n ) − f ( n ) ) = + ∞ {\displaystyle \lim \left(g(n)-f(n)\right)=+\infty } . If X {\displaystyle X} is a partially ordered set (poset) and κ {\displaystyle \kappa } and λ {\displaystyle \lambda } are cardinals, then a ( κ , λ ) {\displaystyle (\kappa ,\lambda )} -pregap in X {\displaystyle X} is a set of elements f α {\displaystyle f_{\alpha }} for α ∈ κ {\displaystyle \alpha \in \kappa } and a set of elements g β {\displaystyle g_{\beta }} for β ∈ λ {\displaystyle \beta \in \lambda } such that:
The transfinite sequence f {\displaystyle f} is strictly increasing; The transfinite sequence g {\displaystyle g} is strictly decreasing; Every element of the sequence f {\displaystyle f} is less than every element of the sequence g {\displaystyle g} . A pregap is called a gap if it satisfies the additional condition:
There is no element h {\displaystyle h} greater than all elements of f {\displaystyle f} and less than all elements of g {\displaystyle g} . A Hausdorff gap is a ( ω 1 , ω 1 ) {\displaystyle (\omega _{1},\omega _{1})} -gap in ω ω {\displaystyle \omega ^{\omega }} such that for every countable ordinal α {\displaystyle \alpha } (i.e. every α ∈ ω 1 {\displaystyle \alpha \in \omega _{1}} ) and every natural number n {\displaystyle n} there are only a finite number of β {\displaystyle \beta } less than α {\displaystyle \alpha } such that for all k > n {\displaystyle k>n} we have f α ( k ) < g β ( k ) {\displaystyle f_{\alpha }(k)<g_{\beta }(k)} . There are some variations of these definitions, with the ordered set ω ω {\displaystyle \omega ^{\omega }} replaced by a similar set. For example, one can redefine f < g {\displaystyle f<g} to mean f ( n ) < g ( n ) {\displaystyle f(n)<g(n)} for all but finitely many n {\displaystyle n} . Another variation introduced by Hausdorff (1936) is to replace ω ω {\displaystyle \omega ^{\omega }} by the power set of ω {\displaystyle \omega } , with the order given by A < B {\displaystyle A<B} if A {\displaystyle A} has only finitely many elements not in B {\displaystyle B} but B {\displaystyle B} has infinitely many elements not in A {\displaystyle A} .
… excerpt ends here. Continue reading the full article.
