The set of all total order types is preordered by inclusion. As a consequence, total order types can generally be understood by their location within this preorder. Although this forms a preorder in general, the subset of well orders forms a total order, as does the set of all inverse well orders.
An example of a total order type whose subtypes don't form a total order is $\mathbb{Z}$. The integral order $\mathbb{Z}$ has two predecessor order types: $\omega$ and $\omega^*$ both of which are incomparable to one another. The predecessors of $\mathbb{Z}$ still form a partial order. Finally, all countable total orders which are non-scattered are embeddable in one another by the theorem of Hausdorff.
A real representation embeds a total order in $\mathbb{R}$. The selection of $\mathbb{R}$ as the target for an order embedding is motivated by the fact that any countable total order can be embedded in it. With respect to its order topology, $\mathbb{R}$ is a complete dense topological space.
The notion of that total order types are preordered by size plays a role in our approach to embeddings. A key invariant is the sequence size, which is essentially the number of limit points that a given total order can have in an embedding. Sequence size is monotone over the embedding order.
The sequence size is one instance whereby we can get a better understanding of total orders by real embeddings. While $\mathbb{Z}$ and $\mathbb{N}$ are both topologically discrete, they have different topological behaviour with respect to embeddings. $\mathbb{Z}$ can have two limit points while $\mathbb{N}$ can only have one. While they have the same internal topological behaviour, they behave differently externally.
Geometry of linear orders:
The real number line forms a topological manifold: the simplest example of such. In geometric topology, it is one of only two connected manifolds of dimension one, the other being the circle manifold.As a geometric realisation of a total order, an embedding function $f: T \to \mathbb{R}$ provides a total order with a one dimensional geometry. The fact that every countable order can be embedded in $\mathbb{R}$ means that any total order can be given a one dimensional geometric realisation.
A consequence of order embedding in the continuous real number line is that an embedded linear order can have limit points, while its total order doesn't have any. This gets around the limitations of studying total orders by their own order topologies.
Although the real number line $\mathbb{R}$ is among the simplest manifolds, its subsets can still exhbit remarkable behaviour because they are part of a continuum. Total orders which you might not otherwise consider to be related to $\mathbb{R}$ can be embedded within in it by going deep into its infinite continuum
Algebra of total orders:
A total order is a subtotal commutative semigroup: it is a commutative semigroup $S$ for which $Sub(S)$ is equal to $\wp(S)$. Every subset of a total order is a subsemilattice, because the join/meet of a finite set of elements of a total order is always contained within that set. This provides an internally semigroup-theoretic perspective on total order theory.The class of total orders with order embeddings between them forms a category. The preorder on isomorphism types of total orders we previously discussed is simply the object preorder of this category of total order embeddings modulo isomorphism. This provides an entirely categorical descriptive of the preorder on total order types.
Real representations $f: T \to \mathbb{R}$ form a comma category within the category of order embeddings. A real representation $f: T \to \mathbb{R}$ is embedded within another real representation $g: U \to \mathbb{R}$ provided there exists a morphism $h : T \to U$ such that $g \circ h = f$.
The real numbers $\mathbb{R}$ themselves are considered to form a complete Archimedean ordered field which is simultaneously a topological field by its order topology. Some of the basic field operations of $\mathbb{R}$ are useful in constructing real representations, and so we will need to make reference to some of their basic order-theoretic properties.
Finite total orders:
The smallest non-trivial total order is the total order on a single element $T_1$. Real representations of this form consist of the selection of a single element from $\mathbb{R}$. This could be anything from $1,2,3,4,1/2,2/3,-15/2,\sqrt{17},\sqrt{23},\frac{1+\sqrt{5}}{2}$ to something trascendental like $e,\pi,\frac{\pi^2}{6}$, etc \[ f : T_1 \to \mathbb{R} \] The next case is the total order on two elements $T_2$. A real representation of a total order on two elements is of course any pair of real numbers such as $\{1,2\}$. All pairs of real numbers are the same with respect to order type, but they can have different geometric properties such as distance. \[ f : T_2 \to \mathbb{R} \] To cut a long story short, every real representation of a finite total order on $n$ elements is equivalent to an $n$ element subset of $\mathbb{R}$. We can define a rank complete homogeneous family of sets $F$ consisting of all $n$ element subsets of $\mathbb{R}$. Then a bijection can be formed between $F$ and real representations in the hom class $Hom(T_n,\mathbb{R})$. \[ F = \{ s : s \subseteq \mathbb{R} \wedge |s| = n \} \] The bijection $f : F \to Hom(T_n,\mathbb{R})$ solves the classification of real embeddings of finite total orders completely. Finite total orders are basically a trivial case as far as the classification of total orders goes.Sequence size one
In the hierarchy of complexity of total orders, the simplest infinite total orders are those which are sequence size one. These are total orders whose real representations have no more then a single limit point. These finite limit points can be either finite of infinite. An example is $\omega$ which can be embedded in $\mathbb{R}$ by either $-\frac{1}{n}$ $\mathbb{Z}_+$. \[ -1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4}, ... \] \[ 1,2,3,4,5,6,7,8,9,... \] The dual concept is that of a decreasing sequence which has order type $\omega^{*}$. As before, these can be either diverging like the negative integers $\mathbb{Z}_{-}$ or converging like $\frac{1}{n}$. Increasing and decreasing sequences $\omega$ and $\omega^*$ are the simplest building blocks of all infinite total orders. \[ ...,\frac{1}{4},\frac{1}{3},\frac{1}{2},1 \] \[ ...,-9,-8,-,7,-6,-5,-4,-3,2,-1\] Of course, infinite total orders like these don't need to have trivial limits like zero. Any real number is a limit point of infinite and decreasing sequences in an infinite number of ways. For example, the infinite series formula for calculating $e$ determines an infinite increasing sequence with $\omega$ order type: \[ 1,2,2+\frac{1}{2},2+\frac{2}{3},2+\frac{17}{24},2+\frac{43}{60},... \] The addition of points beyond the limit like with $\omega+n$ and $n+\omega^{*}$ does nothing to change the number of limit points in the total order, so they are both technically of sequence size one. In either case, the addition of points beyond the limit necessitates that the total order is bounded because there are no points beyond infinity in an Archimedean totally ordered field.Two well orders of type $\omega+1$ are $\{1-\frac{1}{n},1\}$ and $\{ 1-\frac{1}{n},2 \}$. The distinction between the two is that the first includes its limit point and the second doesn't. So a distinctione xists between rather or not an embedding $f : \omega+1 \to \mathbb{R}$ includes its limit point or not.
A key realisation of real representation theory is that the sequence size determines the capability of a total order to have limits externally, even while the total order may not have any limits within itself internally. Total orders $\omega$ and $\omega^{*}$ both have a discrete order topology, but they still determining limit points in embeddings.
Sequence size two
The integers $\mathbb{Z}$ form a discrete total order, and so they are topologically isomorphic to $\omega$ and $\omega^*$ but they have a different behaviour under embedding because they can have two limit points. Therefore, we can say that $\mathbb{Z}$ has sequence size two. The limit points of $\mathbb{Z}$ can be either finite or infinite. $\mathbb{Z}$ has infinite limit points while $-1+\frac{1}{n},1-\frac{1}{n}$ has finite limit points $-1$ and $1$. \[ ...,-2,1,0,1,2,... \] \[ ...,-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0,\frac{1}{2},\frac{2}{3},\frac{3}{4},...\] The order type $\omega + \omega^*$ has two types of limiting behaviour: common convergence and separate convergence. Common converge means that the two sequences of the embedding produce the same limit point: an example is $\pm \frac{1}{n}$ which converges to zero from both sides. The total order $-1-\frac{1}{n},1+\frac{1}{n}$ on the other hand converges separately to one and negative one. \[ -1,-\frac{1}{2},-\frac{1}{3},-\frac{1}{4}...\frac{1}{4},\frac{1}{3},\frac{1}{2},1 \] \[ -2,-1-\frac{1}{2},-1-\frac{1}{3},1-\frac{1}{4},...,1+\frac{1}{4},1+\frac{1}{3},1+\frac{1}{2},2\] The previous two order types $\mathbb{Z}$ and $\omega + \omega^*$ are the two sequence size two order types that are neither well orders nor inverse well orders. The basic example of a well order with sequence size two is $2\omega$. These total orders can have either a limit point at infinity like $\{1-\frac{1}{n},n\}$ or two finite limit points $\{1-\frac{1}{n},2-\frac{1}{n}\}$. \[ 0,\frac{1}{2},\frac{2}{3},\frac{3}{4},...,1,2,3,..\] \[ 0,\frac{1}{2},\frac{2}{3},\frac{3}{4}...,1,1+\frac{1}{2},1+\frac{2}{3},...\] This naturally has a dualization the order transpose of the ordinal $2\omega$ consisting of two sequences both going in the decreasing direction. As before, these can have at most one infinite limit point and the other limit point must be finite. \[ ...-3,-2,-1,...-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0 \] \[ ...-1-\frac{2}{3},-1-\frac{1}{2},-1, ...,-\frac{3}{4},-\frac{2}{3},-\frac{1}{2},0 \] These four types consistute all the types of total order types that are sequence size two except for the inclusion of individual points along the infinite sequences. Only the order type $\omega + \omega^*$ can have bidirectional convergenece and only $\mathbb{Z}$ can have two infinite limit points.Finite sequence sizes:
The sequences of a total order can be represented as directions in the real number line so that $\omega$ is equal to $\rightarrow$, $\omega^*$ is $\leftarrow$, $\mathbb{Z}$ is $\leftrightarrow$, bidirectional converge is $\rightarrow \leftarrow$, $2\omega$ is $\rightarrow \rightarrow$, and ${2\omega}^*$ is $\leftarrow \leftarrow$. The order type of a finite sequence size total order can always be represented by a finite sequence of arrows.Consider the scattered total order $\rightarrow \leftarrow \rightarrow \leftarrow$ then this can have up to four limit points or it can have two bidirectional limit points. An example of this is the real representation $1\pm \frac{1}{n}, 2\pm \frac{1}{n}$. An example of the later is $1-\frac{1}{n},2+\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$.
A finite ordinal like $n\omega$ can be visualized as a sequence of rightarrows $\rightarrow \rightarrow \rightarrow ...$. These can be constructed in the familiar manner we have done so far by subtracting an infinitesimal value from a limit point. So for example $4\omega$ can be represented by $1-\frac{1}{n},2-\frac{1}{n},3-\frac{1}{n},4-\frac{1}{n}$. Dually, an inverse ordinal $4\omega^*$ can be represented by adding an infinitesimal value to a sequence of values: $1+\frac{1}{n},2+\frac{1}{n},3+\frac{1}{n},4+\frac{1}{n}$.
We can represent $2\mathbb{Z}$, the order type of two integer order types by a series by adjoining a bidirectionally convergent limit point to the integers like $\{-n,1+\pm \frac{1}{n},n \}$. All these different methods together constitute a sufficient basis for the theory of representation of total orders of finite sequence size.
Infinite sequence size
As we can construct a total order embedding for any total order of finite sequence size $n$, we can continue this process to construct a total order with infinite sequence size. A first example is the order embedding $f : \omega^2 \to \mathbb{R}$ of the infinite sequence size ordinal $\omega^2$ into $\mathbb{R}$ determinined by subtracting an infinitesimal value from each positive integer: \[ \{n - \frac{1}{m} : n,m \in \mathbb{Z}_+ \} \] A natural dualization of this is to construct the ordinal $(\omega^2)^{*}$ by taking the set of negative integers and adding an infinitesimal value to each of them. Then this produces an embedding of the inverse ordinal $(\omega^2)^{*}$ in the real numbers $\mathbb{R}$. \[ -n + \frac{1}{m} : n,m \in \mathbb{Z} \] The integers squared $\mathbb{Z}^2$ can be constructed by taking each integer and adding and subtracting an infinitesimal value from it. In this case, each integer is the bidirectional limit point of both an infinite sequence asceding into it and an infinite sequence descending into it. \[ \{n \pm \frac{1}{m} : n \in \mathbb{Z}, m \in \mathbb{Z} - \{0\} \} \] In each case we can take a discrete set of points in $\mathbb{R}$ and we turn them into limit points by adding or subtracting a vanishing value from them. This works for any finite or discrete set of limit points, but more advanced methods are required to embed larger total order types in $\mathbb{R}$.
Higher limit points:
Any suborder of the real numbers $\mathbb{R}$ induces a set of limit points which is again a subset of $\mathbb{R}$. In the first part of this theory we can undertook the study the suborders of the reals with a finite number of limit points. Suppose that the limit points of $S \subseteq \mathbb{R}$ are infinite, then they form an infinite order type which can be used to study the suborder.In the previous section of infinite sequence size total orders, we constructed the first examples of embeddings whose order types are infinite and they are all necessarily discrete and of the form $\omega$,$\omega^*$, or $\mathbb{Z}$. The limit points of these sets of limit points are all either positive or negative infinity.
The fact that the set of limit points of a total order can themselves have limit points, means that there exists a concept of higher limits. These are the limit points of the limit points of a total suborder of the real numbers. These higher limit points are the basis of the next step in the classification of the total suborders of the real numbers.
The higher limit points of a scattered total order don't need to be infinite as we will see. These higher limit points can represent any real number, furthermore they can be nested. So we can form higher limit points of higher limit points, and so on. These higher limit points form the next step in our classification of total orders.
Finite depth total orders:
In order to form deeper total orders then the ones we have constructed so far, we need to some of the basic properties of the ordered field $\mathbb{R}$. In $\mathbb{R}$ the functions $\frac{1}{x}$ and $-x$ are both order reversing, so if we combine them together to get $-\frac{1}{x}$ we can an order embedding of $\mathbb{R}_{\ge 1}$ into $[-1,0)$. \[ \frac{1}{x} : \mathbb{R}_{\ge 1} \to [-1,0) \] We have already applied this to the positive integers to get $-\frac{1}{n}$ which has the same order type $\omega$ as the positive integers, and we then added it onto each positive integer to get an order type $\omega^2$. We can now take the negative reciprocal of this to get a bounded $\omega^2$ embedding. \[ -\frac{1}{n-\frac{1}{m}} \] We can get ordinals now like $2\omega^2$ by simply combining a $\omega^2$ ordinal in one interval with a $\omega^2$ ordinal in another. To get something like $\omega^2 + 2\omega + 1$ we simply combine a finite number of ordinals in separate intervals which have each of these order types: \[ 1-\frac{1}{n-\frac{1}{m}}, 2-\frac{1}{n-\frac{1}{m}}, 3-\frac{1}{n},4-\frac{1}{n}, 5\] This same process can be iterated to get an ordinal like $\omega^3$ which has an infinite set of higher limit points: \[ -\frac{1}{n-\frac{1}{m-\frac{1}{o}}} \] The embedding of $\omega^4$ and any larger ordinals in $\mathbb{R}$ can be achieved by further iterating this process: \[ -\frac{1}{n-\frac{1}{m-\frac{1}{o-\frac{1}{p}}}} \] This process is sufficient to construct any ordinal number that is less then some ordinal polynomial. Other scattered total orders of the same sort can be constructed in the same manner by simply switching around the signs of the some of the variables.Large ordinals:
The ordinal numbers constructed so far all have finite exponent e.g $\omega^2, \omega^3, \omega^4, etc$. The next is to construct an ordinal like $\omega^\omega$ which essentially has some ordinal depth and this can be continued to get $\omega^{\omega^\omega}$, $\omega^{\omega^{\omega^\omega}}$ and so on. Embedding these larger total orders in $\mathbb{R}$ is a bit more involved.The first ordinal larger then any exponential tower of ordinals is $\epsilon_0$, then any other ordinal number constructed so far can be embedded in $\epsilon_0$. In order to get a real representation of $\epsilon_0$ the reader is referred to the work of Jeff Erickson on fusible numbers [2].
The fusible numbers are constructed recursively so that a fusible number is $0$ or $\frac{a+b+1}{2}$ with $a$ and $b$ fusible numbers and $|a-b| \leq 1$. Then the fact that the fusible numbers are scattered ordered, any exponential tower can be constructed from them.
As fusible numbers are constructed recursively, the definition of real suborder with larger order types will require the use of recursive formulas. With this primitive recursive ordinals can be embedded in the continuum.
Non-scattered total orders:
The preorder on the isomorphism classes of total orders induced by the category of order embeddings has the property that all countable non-scattered orders are embedding equivalent to one another, so they can be embedded in one another. Therefore, there is no corresponding measure on the complexity of countable non-scattered total orders. A first example is $\mathbb{Q}$ itself, but there are several well known subsets with the same ordering:- All localisations of the PID $\mathbb{Z}$ in the field $\mathbb{Q}$ are densely ordered and have the same order type as $\mathbb{Q}$. For example, the dyadic rationals.
- All rings of real algebraic numbers like $\mathbb{Q}(\sqrt{2}), \mathbb{Q}(\sqrt{3})$, and so on are all denesly ordered and have the same order type as $\mathbb{Q}$.
References:
[1] Real number line
[2] Fusible numbers
No comments:
Post a Comment