Fact-checked by Grok 2 weeks ago

Total order

In mathematics, a total order (also called a linear order) is a binary relation on a set that is reflexive, antisymmetric, transitive, and total, meaning that for any two elements in the set, one precedes the other or they are equal.^[1] This structure extends a partial order by requiring comparability between every pair of distinct elements, ensuring a linear arrangement without incomparable pairs.^[2] The strict variant, denoted by <, is irreflexive, transitive, and total (trichotomous). Total orders appear ubiquitously in mathematics and its applications; for instance, the natural numbers \mathbb{N} under the standard \leq relation form a total order, as do the integers \mathbb{Z} and real numbers \mathbb{R}.^[2] In this framework, every finite nonempty subset has both a least and greatest element, and finite total orders are well-ordered, isomorphic to initial segments of the ordinals.^[1] Key properties include the absence of cycles and the ability to represent the order via a Hasse diagram as a single chain.^[2] Beyond pure mathematics, total orders underpin concepts in computer science, such as sorting algorithms, where they enable efficient ordering of data structures like lists or arrays.^[3] They also facilitate scheduling tasks by providing a consistent linear precedence.^[3] In set theory and order theory, total orders relate to chains and well-orders.^[1]

Definitions and Variants

Non-strict total order

A non-strict total order, also known as a total order or linear order, is a binary relation \leq on a set X that is reflexive, antisymmetric, transitive, and total.^[4] This means that for every pair of elements in X, they are comparable under \leq, allowing for the possibility that x \leq y and y \leq x if and only if x = y.^[4] The axioms defining a non-strict total order on a set X are as follows:

Reflexivity: For all x \in X, x \leq x.^[4]
Antisymmetry: For all x, y \in X, if x \leq y and y \leq x, then x = y.^[4]
Transitivity: For all x, y, z \in X, if x \leq y and y \leq z, then x \leq z.^[4]
Totality: For all x, y \in X, either x \leq y or y \leq x.^[4]

These properties ensure that the relation \leq provides a complete and consistent way to compare elements, distinguishing it from weaker order relations. Every non-strict total order is a partial order, as it satisfies the defining axioms of reflexivity, antisymmetry, and transitivity; the totality condition simply strengthens comparability without violating these.^[4]^[5] To see this, note that the first three axioms directly match those of a partial order, and totality does not contradict them.^[5] However, the converse does not hold: not every partial order is a total order, as partial orders may contain incomparable elements (pairs x, y where neither x \leq y nor y \leq x).^[5] The notation \leq is standard for non-strict total orders, with the associated strict total order defined as x < y if x \leq y and x \neq y, serving as its irreflexive counterpart.^[4] Hasse diagrams can visualize non-strict total orders by representing the relation as a chain of elements, omitting reflexive and transitive edges for clarity.

Strict total order

A strict total order, also known as a strict linear order, is a binary relation < on a set X that satisfies four key axioms: irreflexivity, asymmetry, transitivity, and strict totality (or trichotomy).^[6]^[7] Irreflexivity requires that no element is related to itself: for all x \in X, \neg (x < x). Asymmetry ensures that the relation cannot hold in both directions: if x < y, then \neg (y < x). Transitivity means that if x < y and y < z, then x < z. Strict totality, or trichotomy, states that for any x, y \in X, exactly one of the following holds: x < y, x = y, or y < x.^[8]^[6] Strict total orders are in bijective correspondence with non-strict total orders. Given a non-strict total order \leq on X, define the strict relation by

x < y \iff x \leq y \land x \neq y.

This < satisfies irreflexivity (since x \not\leq x is false), asymmetry (if x < y then y \not< x by antisymmetry of \leq), transitivity (inherited from \leq), and trichotomy (from totality and reflexivity of \leq).^[7]^[6] Conversely, given a strict total order < on X, define the non-strict relation by

x \leq y \iff x < y \lor x = y.

This \leq is reflexive (by irreflexivity of <), antisymmetric (by asymmetry of <), transitive (by transitivity of <), and total (by trichotomy). These constructions are inverses: applying the first to \leq and then the second yields the original \leq, and vice versa, establishing the bijection.^[7]^[6] In graph theory, a strict total order corresponds to a tournament where the directed edges reflect the ordering, though the focus here remains on relational properties.^[9]

Examples

Real numbers and integers

The standard total order on the integers \mathbb{Z} is defined by n \leq m if and only if m - n is a non-negative integer. This relation is reflexive, as n - n = 0 \geq 0 for any n \in \mathbb{Z}. It is antisymmetric, since if n \leq m and m \leq n, then m - n \geq 0 and n - m \geq 0, implying m - n = 0 and thus n = m. Transitivity holds because if n \leq m and m \leq k, then k - n = (k - m) + (m - n) \geq 0. The order is total, as for any n, m \in \mathbb{Z}, either m - n \geq 0 or n - m \geq 0.^[1]/19:_Partially_ordered_sets/19.04:_Total_Orders) The standard total order on the real numbers \mathbb{R} is defined analogously by x \leq y if and only if y - x \geq 0. This satisfies the axioms of a total order in the same manner as for \mathbb{Z}, leveraging the ordered field structure of \mathbb{R}. Unlike \mathbb{Z}, the order on \mathbb{R} is dense: for any x < y in \mathbb{R}, there exists z \in \mathbb{R} such that x < z < y. Additionally, \mathbb{R} is complete, meaning every non-empty subset of \mathbb{R} that is bounded above has a least upper bound in \mathbb{R}. The real numbers also satisfy the Archimedean property: for any x > 0 and y \in \mathbb{R}, there exists n \in \mathbb{N} such that n x > y.^[1]/01:_Tools_for_Analysis/1.05:_The_Completeness_Axiom_for_the_Real_Numbers)^[10]^[11] The rational numbers \mathbb{Q} inherit the standard total order from \mathbb{R}, defined by p \leq q if and only if q - p \geq 0 for p, q \in \mathbb{Q}. However, \mathbb{Q} is not complete; for example, the set \{ q \in \mathbb{Q} \mid q^2 < 2 \} is bounded above but has no least upper bound in \mathbb{Q}./19:_Partially_ordered_sets/19.04:_Total_Orders)^[12]

Ordinal numbers

Ordinal numbers provide a canonical example of well-ordered total orders, extending the natural numbers into the transfinite realm. An ordinal number \alpha is defined as the order type of a well-ordered set, meaning it represents a total order that is isomorphic to the initial segment of ordinals up to \alpha. The smallest infinite ordinal, denoted \omega, is the order type of the natural numbers \mathbb{N} under the standard ordering, serving as the base case for transfinite ordinals.^[13] A key property distinguishing ordinal total orders is well-ordering: every non-empty subset of an ordinal has a least element with respect to the order. This ensures no infinite descending chains exist, enabling systematic traversal. In contrast, the real numbers \mathbb{R} under the usual order do not form a well-order, as the set of negative reals has no least element.^[14]^[15] Transfinite induction is a fundamental principle for proving properties on ordinals, analogous to mathematical induction on naturals but extended to well-ordered sets. To show a property P(\alpha) holds for all ordinals \alpha, verify P(0) for the zero ordinal, and assume P(\beta) for all \beta < \alpha to prove P(\alpha); the well-ordering then implies P(\alpha) for every \alpha. This method, developed by Cantor in the 1880s, underpins many results in set theory.^[16] Examples illustrate the structure of ordinals beyond \omega. The ordinal \omega + 1 consists of the naturals followed by an additional point greater than all of them. The ordinal \omega \cdot 2 is two copies of \omega in sequence, while \omega^2 arranges \omega many copies of \omega. Finite total orders correspond briefly to the initial ordinals n for n \in \mathbb{N}. Ordinal arithmetic, such as addition, is defined recursively and lacks commutativity: $1 + \omega = \omega, as adding one before \omega absorbs into the limit, whereas \omega + 1 appends one after and yields a distinct successor ordinal.^[13]^[17]

Equivalent Concepts

Chain in a poset

In a partially ordered set (poset) (P, \leq), a chain is a subset C \subseteq P such that for every pair of elements a, b \in C, either a \leq b or b \leq a, making C totally ordered under the induced order from P.^[18] A chain C is maximal if there is no larger chain C' \subsetneq P that properly contains C. A poset (P, \leq) is itself a total order if and only if P is a chain, meaning every pair of elements in P is comparable.^[19] Zorn's lemma states that if every chain in a nonempty poset (P, \leq) has an upper bound in P, then P has a maximal element.^[20] This result has significant applications, such as proving that every vector space has a basis by applying Zorn's lemma to the poset of linearly independent subsets ordered by inclusion.^[21] Dilworth's theorem provides a duality between chains and antichains in finite posets, where an antichain is a subset A \subseteq P in which no two distinct elements are comparable (i.e., for all distinct a, b \in A, neither a \leq b nor b \leq a).^[22] Specifically, the theorem asserts that the size of the largest antichain in (P, \leq) equals the minimum number of chains needed to cover P.^[23]

Linear order

A total order is also known by several synonymous terms, including linear order, complete order, and serial order. The term "total order" (or Totalordnung in German) was introduced by Felix Hausdorff in his seminal 1914 work Grundzüge der Mengenlehre, where he formalized the concept within the foundations of set theory.^[24] In contrast, the term "linear order" emerged earlier in set theory from the contributions of Georg Cantor, who in the 1890s developed the theory of order types to classify linearly arranged sets, such as the rationals as the unique countable dense linear order without endpoints. The synonym "serial order" appears in early 20th-century literature, notably in Edward V. Huntington's 1917 exposition on continua as types of serial order.^[25] "Complete order" is occasionally used interchangeably with total order to emphasize the comparability of every pair of elements, though it can overlap with notions of completeness in ordered fields.^[26] In set theory, a total order is frequently conceptualized as a linear extension of a partial order—a total order that contains the original partial order as a subrelation, ensuring all elements remain comparable while preserving existing inequalities. This perspective is central to constructions like topological sorting, an algorithm that produces a linear extension of the partial order induced by a directed acyclic graph, with applications in scheduling and dependency resolution. Such extensions highlight total orders as maximal chains within broader partially ordered sets (posets). Two total orders (X, \leq) and (Y, \leq') are order-isomorphic if there exists a bijection f: X \to Y such that for all x, y \in X, x \leq y if and only if f(x) \leq' f(y). This bijection preserves the order structure entirely, establishing that the orders are essentially identical up to relabeling of elements. Order types are the equivalence classes of total orders under order isomorphism, providing a way to classify them up to structural similarity. For instance, the order type of the integers \mathbb{Z} under the standard order \leq is the bidirectional infinite discrete sequence \dots, -2, -1, 0, 1, 2, \dots, often denoted as \zeta.^[27] In contrast, the order type of the rational numbers \mathbb{Q} under \leq is dense, meaning between any two distinct elements there exists another, and it is the unique countable dense linear order without endpoints, as characterized by Cantor.^[1]

Properties and Constructions

Lattice connections

Every total order (P, \leq) induces a lattice structure where the meet operation is defined as x \wedge y = \min(x, y) and the join operation as x \vee y = \max(x, y).^[28] These operations always exist for any pair of elements due to the totality of the order, ensuring that every pair has a unique greatest lower bound and least upper bound.^[29] The resulting lattice is distributive, satisfying the identities x \wedge (y \vee z) = (x \wedge y) \vee (x \wedge z) and its dual x \vee (y \wedge z) = (x \vee y) \wedge (x \vee z). This follows from the comparability of elements in the total order, which guarantees that the min and max operations distribute over each other across all possible orderings of x, y, z.^[28] Lattices arising from total orders are also modular, satisfying x \vee (y \wedge z) = (x \vee y) \wedge z whenever x \leq z, a property weaker than distributivity but implied by it in this context.^[28] In such lattices, infima and suprema exist for all bounded subsets if the underlying total order is conditionally complete, meaning every nonempty subset bounded above (below) has a least upper bound (greatest lower bound); however, general total orders are not Dedekind-complete unless specified, as exemplified by the rational numbers where certain bounded subsets lack suprema within the set.^[30] Finite total orders form special cases of these finite distributive lattices.^[28]

Finite total orders

A finite total order on a set of n elements is unique up to order isomorphism, consisting solely of the linear chain where the elements are strictly increasing: $1 < 2 < \dots < n. This uniqueness arises because any total order on a finite set must compare every pair of distinct elements, resulting in a single, unbroken sequence without branches or incomparable elements.^[31] When the underlying set is labeled with n distinct elements, the number of possible total orders equals n!, as each permutation of the labels corresponds to a unique way to extend the set into a total order via linear arrangement.^[32] This enumeration highlights the simplicity of finite total orders, where the totality ensures that every permutation serves as a valid ordering without violating comparability.^[33] The Hasse diagram of a finite total order with n elements forms a single vertical path of n-1 edges, connecting each consecutive pair in the chain, with no additional branches due to the complete comparability of all elements.^[34] This linear structure in the Hasse diagram underscores the absence of parallelism or forks typical in more general partially ordered sets. In applications to computer science, the structure of finite total orders informs the analysis of sorting algorithms, where determining the order of n elements under a total order requires at least \Omega(n \log n) comparisons in the worst case for any comparison-based method, reflecting the n! possible orderings.^[35] Finite total orders also serve as bounded lattices, with the infimum and supremum operations defined explicitly by the minimum and maximum elements in any subset.

Sums of total orders

In order theory, the sum of two total orders (A, \leq_A) and (B, \leq_B) is defined on their disjoint union A \sqcup B, where the order \leq_{A+B} preserves the original orders within A and within B, and every element of A is strictly less than every element of B.^[36] This construction, often called the ordinal sum or lexicographic sum, concatenates the orders sequentially, placing B entirely after A.^[37] The operation is associative but not commutative. For instance, the sum of a singleton total order (order type 1) and the order type \omega of the natural numbers satisfies $1 + \omega \cong \omega, as the initial element merges into the countable chain without extending it beyond \omega; however, \omega + 1 is strictly larger than \omega, introducing a maximal element absent in \omega.^[37] Iterating this sum yields multiples, such as \omega + \omega denoting two copies of \omega in sequence.^[36] More generally, for a total order (I, \leq_I) and an indexed family of total orders \{A_i \mid i \in I\}, the sum \sum_{i \in I} A_i is the total order on the disjoint union \sqcup_{i \in I} A_i, equipped with elements represented as pairs (i, a) for i \in I and a \in A_i. The order is lexicographic: (i, a) \leq_{\sum} (j, b) if i <_{I} j, or if i = j and a \leq_{A_i} b.^[38] This extends the binary case recursively: for successor indices, append the next component; for limit indices, take the supremum of prior partial sums.^[36] Such sums preserve totality: the resulting order on the disjoint union is always a total order, as the lexicographic rule ensures comparability between any two elements via their indices or within components.^[37] If each A_i is well-ordered and I is well-ordered, the sum is well-ordered, with no infinite descending chains due to the well-founded indices and components.^[36] In the context of ordinal numbers as canonical well-orders, these sums define ordinal addition, exemplified by \omega + \omega = \omega \cdot 2.^[37]

Advanced Structures

Categorical view

In category theory, the category TO has as objects all total orders, that is, pairs (X, \leq) where X is a set equipped with a total order relation \leq. The morphisms in TO are the order-preserving maps, also known as monotone functions: for total orders (X, \leq) and (Y, \leq'), a morphism f: (X, \leq) \to (Y, \leq') satisfies x \leq y implies f(x) \leq' f(y) for all x, y \in X. Isomorphisms in TO are the bijective order-preserving maps whose inverses are also order-preserving. These isomorphisms identify total orders that are order-isomorphic, preserving the relational structure exactly. The category TO is a full subcategory of the category Pos of posets and order-preserving maps, via the inclusion functor that forgets the totality property. The initial object in TO is the empty total order, the empty set with the (vacuously total) empty relation, as there exists a unique morphism from it to any total order. The terminal object is the singleton total order, a set with one element, to which there is a unique morphism from any total order. Additionally, there is an embedding functor from the category FinSet of finite sets and functions to TO, sending a finite set to its free total order (a chain of the same cardinality) and functions to their induced order-preserving maps where applicable, though typically realized through canonical enumerations. An important adjunction involves the free total order completion of posets. The inclusion functor i: \mathbf{TO} \to \mathbf{Pos} has a left adjoint F: \mathbf{Pos} \to \mathbf{TO} that constructs a linear extension of a given poset, extending the partial order to a total order while preserving the original relations; this "free" completion ensures the universal property that any order-preserving map from the poset to a total order factors uniquely through the extension. This adjunction captures the process of linear extensions categorically, highlighting how total orders freely generate from partial ones.

Order topology

The order topology on a totally ordered set X is generated by the subbasis consisting of all open rays (a, +\infty) = \{x \in X \mid x > a\} and (-\infty, b) = \{x \in X \mid x < b\}, for all a, b \in X.^[39] The basis for this topology is formed by finite intersections of these subbasis elements, yielding open intervals (a, b) = \{x \in X \mid a < x < b\}, along with unbounded rays when X lacks a minimum or maximum element.^[40] On the real numbers \mathbb{R} equipped with the standard total order, the order topology coincides with the familiar Euclidean topology, which is Hausdorff and connected.^[41] In general, the order topology on any totally ordered set is Hausdorff—and thus satisfies the T_0 separation axiom—since for distinct points x < y in X, the open sets (-\infty, y) and (x, +\infty) separate them.^[39] The order topology is compact if and only if the total order on X is Dedekind complete (every nonempty subset bounded above has a least upper bound in X) and X possesses both a least and a greatest element; representative examples include all finite total orders and the closed unit interval [0, 1] under the standard ordering.^[42] Moreover, when the total order is dense (between any two distinct elements there lies another), Dedekind completeness ensures that the resulting topological space is connected.^[43]

Completeness axioms

A total order (P, \leq) is said to be Dedekind-complete if every non-empty subset of P that is bounded above has a least upper bound, or supremum, in P.^[44] This property ensures the absence of "gaps" in the order beyond those filled by elements of P. For instance, the real numbers \mathbb{R} under the standard order form a Dedekind-complete total order, as every bounded above non-empty subset has a supremum.^[44] In contrast, the rational numbers \mathbb{Q} are not Dedekind-complete; the set \{q \in \mathbb{Q} \mid q^2 < 2\} is bounded above but has no least upper bound in \mathbb{Q}.^[44] A stronger notion is well-completeness, where every subset of P—bounded or unbounded—has both a supremum and an infimum in P. This property implies Dedekind-completeness, as bounded above subsets are a special case. The class of ordinal numbers provides an example: under the standard order, every set of ordinals has a supremum given by their union, and every non-empty subset has an infimum given by its least element, making the ordinals well-complete.^[45] For initial segments (subsets bounded above), this aligns with the well-ordering ensuring suprema exist without gaps.^[45] In the context of ordered fields, another form of completeness is Cauchy completeness: every Cauchy sequence converges to an element of the field. The real numbers \mathbb{R} are Cauchy complete, while the rationals \mathbb{Q} are not, as the sequence approximating \sqrt{2} is Cauchy but does not converge in \mathbb{Q}.^[46] For Archimedean ordered fields, Dedekind-completeness is equivalent to Cauchy completeness.^[44] A total order (P, \leq) is Dedekind-complete if and only if every Dedekind cut (L, U)—a partition of P into non-empty L and U with all elements of L less than all of U, L having no maximum, and U having no minimum—fails to exist without being filled; equivalently, every such potential cut has either a maximum in L or a minimum in U.^[47] This characterization highlights that completeness prevents irrational gaps definable by cuts. Dedekind-complete ordered fields are precisely the real closed fields, as the completeness ensures algebraic closure in the ordered sense: every positive element has a square root, and every odd-degree polynomial has a root.^[44] The real numbers \mathbb{R} exemplify this, being the unique (up to isomorphism) Dedekind-complete real closed field.^[44]

Products and Extensions

Lexicographic product

The lexicographic order, also known as dictionary order, on the Cartesian product X \times Y of two totally ordered sets (X, \leq_X) and (Y, \leq_Y) is defined by declaring (x_1, y_1) \prec_{\lex} (x_2, y_2) if and only if either x_1 \prec_X x_2 or (x_1 = x_2 and y_1 \prec_Y y_2), where \prec denotes the strict part of the order.^[48] The corresponding non-strict order \leq_{\lex} is obtained by including equality: (x_1, y_1) \leq_{\lex} (x_2, y_2) if x_1 \leq_X x_2 and, in the case x_1 = x_2, y_1 \leq_Y y_2.^[48] This construction prioritizes the first component, comparing elements only in the second component when the first components are equal. The lexicographic order preserves totality: if both (X, \leq_X) and (Y, \leq_Y) are total orders, then (X \times Y, \leq_{\lex}) is also a total order.^[48]^[49] For any two elements (x_1, y_1) and (x_2, y_2) in X \times Y, either x_1 < x_2, x_2 < x_1, or x_1 = x_2, ensuring comparability via the total orders on the components.^[48] Unlike the componentwise product order, which is generally partial, the lexicographic order is a linear extension that guarantees totality on the product.^[49] The lexicographic order is not commutative, meaning the order on X \times Y differs from that on Y \times X. For example, on \mathbb{N} \times \mathbb{N} with the standard order on \mathbb{N}, the lexicographic order yields the order type \omega^2, isomorphic to \omega \cdot \omega, where sequences are ordered first by the initial natural number (running through copies of \omega) and then within each copy by the second component.^[48]^[50] Reversing the components would instead produce an order where the second (now first) component is primary, resulting in a different structure, such as \omega \cdot 2 for finite cases or highlighting the asymmetry in infinite products.^[50] Regarding well-ordering, the lexicographic product of two well-orders is itself a well-order. If (X, \leq_X) and (Y, \leq_Y) are well-orders, then every non-empty subset of X \times Y has a least element under \leq_{\lex}, as any descending chain must stabilize in the first component (by well-ordering of X) and then descend in the second (impossible by well-ordering of Y).^[50] For instance, \mathbb{N} \times \mathbb{N} under lexicographic order is well-ordered with type \omega^2.^[48] In applications, the lexicographic order is fundamental for dictionary ordering of sequences or tuples, where elements are compared position-by-position until a difference arises, as in alphabetical listings.^[49] It also enables multi-dimensional sorting in computing, such as ordering records by primary key first and secondary key thereafter, ensuring a total ranking for data structures like arrays or databases.^[49] A total order is a partial order in which every pair of distinct elements is comparable, meaning for any two elements x and y, either x \leq y or y \leq x. In contrast, a partial order is a binary relation that is reflexive, antisymmetric, and transitive, but it permits the existence of incomparable elements, where neither relation holds between a pair. For example, the componentwise order on \mathbb{R} \times \mathbb{R}, defined by (a, b) \leq (c, d) if a \leq c and b \leq d, is a partial order because pairs like (1, 2) and (2, 1) are incomparable.^[51]^[52] Preorders generalize partial orders by relaxing antisymmetry, requiring only reflexivity and transitivity, which allows for symmetric pairs representing indifference. A total preorder, also known as a weak order, is a preorder where every pair of elements is comparable, either x \preceq y or y \preceq x, but non-antisymmetry permits equivalence classes of elements that are indifferent to each other, ordered totally among classes. For instance, in preference relations, a total preorder might rank options with ties, where indifferent options form equivalence classes that are themselves totally ordered relative to other classes.^[53] The quotient of a total preorder by its indifference relation—defined as x \sim y if x \preceq y and y \preceq x—yields a total order on the set of equivalence classes, effectively collapsing ties into single representatives.^[53]^[54] Weak orders, synonymous with total preorders, further emphasize this structure as complete preorders that induce a partial order on the quotient by indifference, becoming a total order when the original is total. An example is numerical comparisons allowing ties, such as a ranking of candidates where some are deemed equal, partitioning the set into tied groups ordered linearly. This contrasts with strict total orders by incorporating non-strict comparisons without violating comparability.^[53] In graph theory, tournaments provide another related structure: a tournament is an orientation of a complete graph, a directed graph where every pair of distinct vertices has exactly one directed edge between them, corresponding to a total relation that is asymmetric but not necessarily transitive. A tournament represents a strict total order if and only if it is transitive (acyclic), as cycles indicate intransitivities like rock-paper-scissors preferences. Thus, while every strict total order induces a transitive tournament, not all tournaments are transitive, making them a broader class that may embed total orders as Hamiltonian paths.^[55]^[56]

References

[1]
Totally Ordered Set -- from Wolfram MathWorld
A total order (or "totally ordered set," or "linearly ordered set") is a set plus a relation on the set (called a total order) that satisfies the conditions ...
[2]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/A_Spiral_Workbook_for_Discrete_Mathematics_(Kwong)/07%3A_Relations/7.04%3A_Partial_and_Total_Ordering
[3]
[PDF] 6.042J Chapter 7: Relations and partial orders - MIT OpenCourseWare
Relations are widely used in computer science, especially in databases and scheduling applications. A relation can be defined across many items in many sets,.
[4]
Total Order -- from Wolfram MathWorld
### Summary of Total Order (Non-Strict Version) from Wolfram MathWorld
[5]
Partial Order -- from Wolfram MathWorld
For a partial order, the size of the longest chain (antichain) is called the partial order length (partial order width). A partially ordered set is also called ...
[6]
Strict Order -- from Wolfram MathWorld
A strict order is total if, for any a,b in S, either a<b, b<a, or a=b. Every partial order <= induces a strict order a<b:a<=b ^ a!=<|control11|><|separator|>
[7]
[PDF] Part II - Logic and Set Theory - Dexter Chua
We start with a few definitions. Definition ((Strict) total order). A (strict) total order or linear order is a pair. (X, <), ...
[8]
[PDF] 1 Introduction 2 Ordering relations
R is a strict total order if it is a strict partial order and satisfies ∀x ∈ A∀y ∈. A(xRy ∨ yRx ∨ x = y). The reflexive closure of a strict partial order (resp.
[9]
[PDF] Unavoidable structures in infinite tournaments - Paul Larson
May 7, 2024 · Given a strict total order τ = (V,≺), let Kτ be the tournament on V where (u, v) ∈. E(Kτ ) if and only if u ≺ v. We write τ∗ to be the ...
[10]
[PDF] The Archimedean Property - Penn Math
Sep 3, 2014 · Definition An ordered field F has the Archimedean Property if, given any positive x and y in F there is an integer n > 0 so that nx > y. Theorem ...
[11]
[PDF] Math 117: Density of Q in R
Although the Archimedean property of R is a consequence of the completeness axiom, it is weaker than completeness. Notice that N is also unbounded above in Q, ...
[12]
[PDF] Basic Analysis: Introduction to Real Analysis - IRL @ UMSL
May 16, 2022 · We saw there is no rational square root of two. The set {x ∈ Q : x2. < 2} implies the existence of the real number. √2, although this fact ...
[13]
Ordinal Number -- from Wolfram MathWorld
An ordinal number is defined as the order type of a well ordered set (Dauben 1990, p. 199; Moore 1982, p. 52; Suppes 1972, p. 129). Finite ordinal numbers are ...
[14]
well-order in nLab
Dec 26, 2023 · More generally, any set of ordinal numbers (or even the proper class of all ordinal numbers) is well-ordered under the usual order < \lt (which, ...Idea · Definition · Examples · Interpretation as an ordinal...
[15]
https://mathworld.wolfram.com/WellOrderedSet.html
[16]
Transfinite Induction -- from Wolfram MathWorld
Transfinite induction, like regular induction, is used to show a property P(n) holds for all numbers n. The essential difference is that regular induction ...
[17]
ordinal arithmetic - PlanetMath
Mar 22, 2013 · In particular, ordinal addition is not commutative . For example,. ω+1=ω+S0=S(ω+0)=Sω ω + 1 = ω ...Missing: non- | Show results with:non-
[18]
Chain -- from Wolfram MathWorld
In a partially ordered set, a chain is a set of pairwise comparable elements, which is a totally ordered subset.
[19]
flag - PlanetMath.org
Mar 22, 2013 · More generally, a flag can be defined as a maximal chain in a partially ordered set . If one considers the poset ...
[20]
chain - PlanetMath.org
Mar 22, 2013 · A chain in a poset is a subset where any two elements are comparable, meaning either a≤b or b≤a. A poset is a chain if it is a chain as a ...<|control11|><|separator|>
[21]
Zorn's Lemma -- from Wolfram MathWorld
Zorn's Lemma. If S is any nonempty partially ordered set in which every chain has an upper bound, then S has a maximal element.
[22]
Zorn's lemma and bases for vector spaces - PlanetMath.org
Mar 22, 2013 · In this entry, we illustrate how Zorn's lemma can be applied in proving the existence of a basis for a vector space.
[23]
Antichain -- from Wolfram MathWorld
An antichain in P is a set of pairwise incomparable elements. Antichains are also called Sperner systems in older literature.<|control11|><|separator|>
[24]
Dilworth's Lemma -- from Wolfram MathWorld
Dilworth's Lemma: The partial order width of a set P is equal to the minimum number of chains needed to cover P.
[25]
Grundzüge der Mengenlehre : Hausdorff, Felix, 1868-1942
Dec 2, 2008 · Grundzüge der Mengenlehre ; Publication date: 1914 ; Topics: Set theory ; Publisher: Leipzig Viet ; Collection: gerstein; toronto; ...Missing: total | Show results with:total
[26]
The Continuum and Other Types of Serial Order: Second Edition ...
This classic of mathematics presents the best systematic elementary account of the modern theory of the continuum as a type of serial order. Based on the ...
[27]
(PDF) Particular order - ResearchGate
deciders in order to perform the ﬁnal selection. I chose to adopt a partial order since it has a total (or complete) order as a. particular case and since ...
[28]
[PDF] Chapter 8 Ordered Sets
In this chapter, we will look at certain kinds of ordered sets. If a set is ordered in a reasonable way,. \ then there is a natural way to define an “order ...<|control11|><|separator|>
[29]
None
Below is a merged summary of the lattice theory content from Garrett Birkhoff's *Lattice Theory* (1948, Revised Edition), focusing on total orders, chains, distributivity, and modularity. To retain all information in a dense and organized manner, I will use a combination of narrative text and a table in CSV format for detailed proofs, definitions, and statements. The narrative provides an overview, while the table captures specific details across chapters and sections.
[30]
[PDF] Lattice theory - Stanford Concurrency Group
Any chain forms both an upper and a lower semilattice, with x ∨ y being the max (larger) of x and y and x ∧ y being their min (smaller). 2. The power set of a ...<|control11|><|separator|>
[31]
Continuous set - Encyclopedia of Mathematics
Oct 18, 2014 · A continuous set is a conditionally-complete lattice which is a dense total order. The phrase "continuous set" is not used in the Western literature.<|control11|><|separator|>
[32]
Finite ordered sets and their isomorphism - Math Stack Exchange
Apr 2, 2013 · How many ways are there to prove that if X and Y are two finite orders (total orders) on n elements, then X and Y are isomorphic? There is a ...
[33]
1.2 Combinations and permutations
A useful special case is k=n, in which we are simply counting the number of ways to order all n objects. This is n(n−1)⋯(n−n+1)=n!.
[34]
Number of total orders on set with n elements [duplicate]
Nov 4, 2019 · The smallest element can be any of n. Once this has been selected, the next smallest can be any of n−1. Continuing in this way we obtain.Number of distinct total orders on a set - Math Stack ExchangeCount of permutations with N fixed order elements (chromozomes)More results from math.stackexchange.com
[35]
[PDF] RELATIONS - DePaul University
Note that the Hasse diagram for a total order relation can be drawn as a single vertical “chain.” Many important partial order relations have elements that are ...
[36]
[PDF] 5.1 Introduction 5.2 Sorting lower bound
Sep 10, 2024 · Theorem 5.2.1 Any sorting algorithm in the comparison model must make at least log(n!) = Θ(nlog n) comparisons in the worst case.
[37]
Ordinal Addition -- from Wolfram MathWorld
Ordinal addition combines disjoint ordered sets. If elements are from different sets, the order type is alpha+beta. It is associative but not commutative in ...
[38]
ordinal sum in nLab
Aug 10, 2023 · Ordinal sum is a natural addition on ordered sets, where the second ordinal's elements are bigger than the first's, and elements from the first ...
[39]
https://planetmath.org/ordertopology
[40]
order topology - PlanetMath
Mar 22, 2013 · If there is a z z such that x<z<y x < z < y , then (−∞,z) ( - ∞ , z ) and (z,∞) ( z , ∞ ) are disjoint open sets separating x x and y y . If no ...
[41]
[PDF] Section 14. The Order Topology
May 29, 2016 · Definition. Let X be a set with a simple order relation <. The following sets are intervals in X: (a, b) = {x ∈ X | a<x<b} (open intervals).
[42]
[PDF] Lecture 14: The Order Topology - ECE, IISc
If we consider the intersection of the open rays of the form (−∞,b) and (a,+∞), then it is the open interval of the form (a,b).The set (a,b) is a basis element ...
[43]
Compact, densely ordered spaces - MathOverflow
Jun 23, 2014 · The linear orders which are compact in the order topology are precisely the complete totally ordered sets X.Properties of the category of compact Hausdorff spacesHow do the compact Hausdorff topologies sit in the lattice of all ...More results from mathoverflow.net
[44]
a space is connected under the ordered topology if and only if it is a ...
Mar 22, 2013 · A space is connected under the ordered topology if and only if it is a linear continuum. If X is connected, then X is a linear continuum. If X ...
[45]
[PDF] Completeness of Ordered Fields - arXiv
K is sequentially complete if every fundamental (Cauchy) sequence in K converges. Recall that a sequence {an} in a totally ordered field K (not necessarily ...
[46]
Section 3.4 (05N1): Ordinals—The Stacks project
Given a set A of ordinals, we define the supremum of A to be \sup _{\alpha \in A} \alpha = \bigcup _{\alpha \in A} \alpha . It is the least ordinal bigger or ...<|separator|>
[47]
11.3.4 Cauchy reals are Cauchy complete - PlanetMath
Theorem 11.3. Every Cauchy approximation in Rc has a limit. ordered field in which every Cauchy approximation has a limit is called Cauchy complete. The Cauchy ...
[48]
Dedekind cuts - Paul Taylor
Dedekind originally defined a cut (D,U) as a partition of the rationals. This means that there are two representations of each rational number q as a cut.
[49]
[PDF] ORDERED SETS
Show that the lexicographic product of total orderings is a total ordering. ♢. 2.2.4 Ordered subsets, chains and antichains. Let (E,≤) be an ordered set. A ...<|control11|><|separator|>
[50]
Lexicographic Ordering | Baeldung on Computer Science
May 2, 2024 · Lexicographic ordering is a generalized alphabetical order, like in dictionaries, used for ordering elements in programming languages.
[51]
[PDF] Ordinal Arithmetic - Open Logic Project Builds
Ordinal arithmetic involves performing operations on ordinals, such as addition, which can be defined by constructing a well-ordered set or using recursion.
[52]
[PDF] Order Relations
A partial order on a set is, roughly speaking, a relation that behaves like the relation ≤ on R. Definition. Let X be a set, and let ∼ be a relation on X. ∼ is ...
[53]
Order Relation
Definition(well order): A total order R on a set A is a well order if every non-empty subset of A has the least element. Example 9: The poset of the set of ...
[54]
[PDF] Order Theory - Columbia University
A complete partial order is a linear order. Note the difference between a preorder and a partial order. The former allows for indifferences, while the latter ...
[55]
[PDF] What is a Sorting Function? ? - Department of Computer Science
Dec 25, 2008 · A total preorder canonically induces an equivalence relation (S,≡O): x ≡O y ⇔ O(x, y) ∧ O(y, x). (S, O) is a total order if it is a total ...
[56]
[PDF] Lecture 19: Tournaments 1 Definitions - Faculty Web Pages
A tournament is a special kind of directed graph. It has no loops, and for every pair of vertices v and w, exactly one of the possible arcs (v, w) or (v, ...Missing: strict | Show results with:strict
[57]
[PDF] 6.042J Lecture 12: Solutions - DSpace@MIT
Mar 1, 2010 · Some tournament graphs represent transitive relations and others don't. (c) Show that a tournament graph represents a total order iff there are ...