Total order

A total order is a reflexive, antisymmetric, transitive relation in which every two elements are comparable.

The cofinality of a linear order is the least cardinality of a cofinal subset. It is preserved by order isomorphisms. The order sum of ${\omega }_1$ copies of the rational order has cofinality ${\aleph }_1$, whereas appending one final rational block changes its cofinality to ${\aleph }_0$ without changing its cardinality or the dense-linear-order axioms.

There are at most continuum many binary relations on a countable set. For the matching lower bound, order the blocks $\{2n,2n+1\}$ by their index and independently choose the internal comparison in each block. A binary sequence determines those choices and distinct sequences give distinct labelled total orders. The resulting order types can all coincide; the count concerns relations, not isomorphism classes.

Two elements $u<v$ of a totally ordered set form an adjacent pair when no domain element lies strictly between them. Every pair of consecutive integers is adjacent, while a dense order has no adjacent pair. A gap in a subset of the real numbers matters here only through which points belong to the domain: $1,2$ are adjacent in $[0,1]\cup [2,3]$.

A minimum of $A$ is a member of $A$ less than or equal to every member of $A$. It equals the infimum when that lower bound is attained. A nonempty finite subset of a totally ordered set has a minimum; a nonempty open real interval does not.

A maximum of a subset $S$ of a total order is an element $m\in S$ with $s\le m$ for every $s\in S$. If it exists it is unique. Every nonempty finite subset has a maximum, by repeated pairwise comparison. Unlike a supremum, a maximum must belong to the subset. The completion time of jobs processed on finitely many parallel machines is the maximum of the machine completion times.

A totally ordered set is a set equipped with a total order. Internally in a topos, weak totality does not imply decidable equality. The empty ordered set is allowed unless an inhabitation axiom is explicitly imposed.

A total order is dense when between every two distinct ordered points lies a third. Endpoints are allowed; “without endpoints” is an additional condition. A dense order with two points $a<b$ cannot be a well-order, since $\{x:a<x\}$ is nonempty and has no least member. Its first-order axioms are the total-order axioms plus $\forall x,y(x<y\Rightarrow \exists z(x<z<y))$. Countability and uncountability are not first-order axiomatizable restrictions, by the upward and downward witness constructions of the Löwenheim-Skolem theorem.

An aleph-one-like linear order has size ${\aleph }_1$ and every point has only countably many predecessors. Consequently every proper initial segment is countable, since it is bounded by any point outside it. This differs from requiring every nonempty interval to be uncountable.

For a subset $S$ of the nonzero countable limit ordinals, let $B_{\alpha }=1+\mathbb{Q}$ when $\alpha \in S$ and $B_{\alpha }=\mathbb{Q}$ otherwise. The order sum is an aleph-one-like linear order whose nonempty proper initial segments are $\mathbb{Q}$ or $\mathbb{Q}+1$. At the limit cut before block $\delta$, the complementary final segment has a least point exactly when $\delta \in S$. Club agreement of countable filtrations makes this condition invariant modulo a nonstationary difference. Disjoint stationary subsets of omega-one consequently supply $2^{{\aleph }_1}$ nonisomorphic orders.

The topology generated by open intervals and open initial and final rays in a total order. For a dense order without endpoints, a subset is dense in this topology exactly when it meets every nonempty open interval.

Give ${\mathbb{R}}^2$ the lexicographic order and the order topology. Every point $(a,b)$ has an interval neighbourhood between $(a,b-\epsilon )$ and $(a,b+\epsilon )$, lying entirely in the vertical line $\{a\}\times \mathbb{R}$. These intervals give each such line its usual real topology, and every line is open. Thus this space is a disjoint union of uncountably many open copies of the real line and is not a second-countable space: any basis of a topology must supply a different member inside each of these disjoint nonempty open sets.

Every pairwise disjoint collection of nonempty open intervals is countable. This is one of the defining properties of a Suslin line.

A subset of a total order meeting every nonempty open interval between two distinct points. A countable order-dense subset witnesses separability in the order topology of a dense order.

Every nonempty bounded-above subset of a total order has a least upper bound. In the real line this is the supremum property used to extend maps defined on an order-dense subset.

The completion of a total order by its nonprincipal proper cuts, supplying least upper bounds. For a dense order it contains the original order densely, and preserves the interval countable chain condition and separability or nonseparability.

An order isomorphism is a bijection preserving and reflecting the order relation. It transfers well-foundedness and order type between a coded order and its ordinal interpretation.

The order sum $A+B$ is the disjoint union of two total orders, preserving each order and placing every element of $A$ before every element of $B$. For example $\mathbb{N}+\mathbb{Z}$ has a least element but also has elements with infinitely many predecessors.

An order automorphism of a total order $(I,<)$ is a bijection $\pi :I\to I$ such that $i<j$ if and only if $\pi (i)<\pi (j)$. Composition and inverses are again order automorphisms. Transporting the indices of an order-indiscernible sequence by such a map preserves every first-order formula on increasing finite tuples.

An order-dense subset with no nonidentity order automorphism. A transfinite diagonal construction marks an included point and an excluded image for every nonidentity real-line order automorphism, yielding such a subset of size $2^{{\aleph }_0}$.

An order automorphism of an order-dense subset $D$ of the real line extends uniquely by $\tilde{\phi }(x)=\sup \{\phi (d):d\in D,d<x\}$. Order completeness supplies the extension, and the lower cuts in $D$ give uniqueness.

A strict total order is an irreflexive and transitive relation $<$ for which exactly one of $x<y$ and $y<x$ holds whenever $x\ne y$. It corresponds to a total order through $x\le y$ if and only if $x<y$ or $x=y$.

A well-order is a total order in which every nonempty subset has a least element.

A decidable well-order on the natural numbers is a well-order whose comparison relation is computable. Comparing two codes is an effective finite task; the proof that the relation has no infinite descending chain is a separate mathematical assertion. Computable Cantor normal form notation gives such an order of type epsilon zero.

The empty order is the unique total order on the empty set.

An initial segment contains every element below each of its elements.