Total order (original) (raw)

From Wikipedia, the free encyclopedia

Order whose elements are all comparable

In mathematics, a total order or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation ≤ {\displaystyle \leq } {\displaystyle \leq } on some set X {\displaystyle X} {\displaystyle X}, which satisfies the following for all a , b {\displaystyle a,b} {\displaystyle a,b} and c {\displaystyle c} {\displaystyle c} in X {\displaystyle X} {\displaystyle X}:

  1. a ≤ a {\displaystyle a\leq a} {\displaystyle a\leq a} (reflexive).
  2. If a ≤ b {\displaystyle a\leq b} {\displaystyle a\leq b} and b ≤ c {\displaystyle b\leq c} {\displaystyle b\leq c} then a ≤ c {\displaystyle a\leq c} {\displaystyle a\leq c} (transitive).
  3. If a ≤ b {\displaystyle a\leq b} {\displaystyle a\leq b} and b ≤ a {\displaystyle b\leq a} {\displaystyle b\leq a} then a = b {\displaystyle a=b} {\displaystyle a=b} (antisymmetric).
  4. a ≤ b {\displaystyle a\leq b} {\displaystyle a\leq b} or b ≤ a {\displaystyle b\leq a} {\displaystyle b\leq a} (strongly connected, formerly called total).

Reflexivity (1.) already follows from connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders.[1]Total orders are sometimes also called simple,[2] connex,[3] or full orders.[4]

A set equipped with a total order is a totally ordered set;[5] the terms simply ordered set,[2] linearly ordered set,[3][5] and loset[6][7] are also used. The term chain is sometimes defined as a synonym of totally ordered set,[5] but generally refers to a totally ordered subset of a given partially ordered set.

An extension of a given partial order to a total order is called a linear extension of that partial order.

Strict and non-strict total orders

[edit]

A strict total order on a set X {\displaystyle X} {\displaystyle X} is a strict partial order on X {\displaystyle X} {\displaystyle X} in which any two distinct elements are comparable. That is, a strict total order is a binary relation < {\displaystyle <} {\displaystyle <} on some set X {\displaystyle X} {\displaystyle X}, which satisfies the following for all a , b {\displaystyle a,b} {\displaystyle a,b} and c {\displaystyle c} {\displaystyle c} in X {\displaystyle X} {\displaystyle X}:

  1. Not a < a {\displaystyle a<a} {\displaystyle a<a} (irreflexive).
  2. If a < b {\displaystyle a<b} {\displaystyle a<b} then not b < a {\displaystyle b<a} {\displaystyle b<a} (asymmetric).
  3. If a < b {\displaystyle a<b} {\displaystyle a<b} and b < c {\displaystyle b<c} {\displaystyle b<c} then a < c {\displaystyle a<c} {\displaystyle a<c} (transitive).
  4. If a ≠ b {\displaystyle a\neq b} {\displaystyle a\neq b}, then a < b {\displaystyle a<b} {\displaystyle a<b} or b < a {\displaystyle b<a} {\displaystyle b<a} (connected).

Asymmetry follows from transitivity and irreflexivity;[8] moreover, irreflexivity follows from asymmetry.[9]

For delimitation purposes, a total order as defined above is sometimes called non-strict order. For each (non-strict) total order ≤ {\displaystyle \leq } {\displaystyle \leq } there is an associated relation < {\displaystyle <} {\displaystyle <}, called the strict total order associated with ≤ {\displaystyle \leq } {\displaystyle \leq } that can be defined in two equivalent ways:

Conversely, the reflexive closure of a strict total order < {\displaystyle <} {\displaystyle <} is a (non-strict) total order.

The term chain is sometimes defined as a synonym for a totally ordered set, but it is generally used for referring to a subset of a partially ordered set that is totally ordered for the induced order.[1][11] Typically, the partially ordered set is a set of subsets of a given set that is ordered by inclusion, and the term is used for stating properties of the set of the chains. This high number of nested levels of sets explains the usefulness of the term.

A common example of the use of chain for referring to totally ordered subsets is Zorn's lemma which asserts that, if every chain in a partially ordered set X has an upper bound in X, then X contains at least one maximal element.[12] Zorn's lemma is commonly used with X being a set of subsets; in this case, the upper bound is obtained by proving that the union of the elements of a chain in X is in X. This is the way that is generally used to prove that a vector space has Hamel bases and that a ring has maximal ideals.

In some contexts, the chains that are considered are order isomorphic to the natural numbers with their usual order or its opposite order. In this case, a chain can be identified with a monotone sequence, and is called an ascending chain or a descending chain, depending whether the sequence is increasing or decreasing.[13]

A partially ordered set has the descending chain condition if every descending chain eventually stabilizes.[14] For example, an order is well founded if it has the descending chain condition. Similarly, the ascending chain condition means that every ascending chain eventually stabilizes. For example, a Noetherian ring is a ring whose ideals satisfy the ascending chain condition.

In other contexts, only chains that are finite sets are considered. In this case, one talks of a finite chain, often shortened as a chain. In this case, the length of a chain is the number of inequalities (or set inclusions) between consecutive elements of the chain; that is, the number minus one of elements in the chain.[15] Thus a singleton set is a chain of length zero, and an ordered pair is a chain of length one. The dimension of a space is often defined or characterized as the maximal length of chains of subspaces. For example, the dimension of a vector space is the maximal length of chains of linear subspaces, and the Krull dimension of a commutative ring is the maximal length of chains of prime ideals.

"Chain" may also be used for some totally ordered subsets of structures that are not partially ordered sets. An example is given by regular chains of polynomials. Another example is the use of "chain" as a synonym for a walk in a graph.

One may define a totally ordered set as a particular kind of lattice, namely one in which we have

{ a ∨ b , a ∧ b } = { a , b } {\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}} {\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}} for all a, b.

We then write a ≤ b if and only if a = a ∧ b {\displaystyle a=a\wedge b} {\displaystyle a=a\wedge b}. Hence a totally ordered set is a distributive lattice.

Finite total orders

[edit]

A simple counting argument will verify that any non-empty finite totally ordered set (and hence any non-empty subset thereof) has a least element. Thus every finite total order is in fact a well order. Either by direct proof or by observing that every well order is order isomorphic to an ordinal one may show that every finite total order is order isomorphic to an initial segment of the natural numbers ordered by <. In other words, a total order on a set with k elements induces a bijection with the first k natural numbers. Hence it is common to index finite total orders or well orders with order type ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).

Totally ordered sets form a full subcategory of the category of partially ordered sets, with the morphisms being maps which respect the orders, i.e. maps f such that if a ≤ b then f(a) ≤ f(b).

A bijective map between two totally ordered sets that respects the two orders is an isomorphism in this category.

For any totally ordered set X we can define the open intervals

We can use these open intervals to define a topology on any ordered set, the order topology.

When more than one order is being used on a set one talks about the order topology induced by a particular order. For instance if N is the natural numbers, < is less than and > greater than we might refer to the order topology on N induced by < and the order topology on **N** induced by > (in this case they happen to be identical but will not in general).

The order topology induced by a total order may be shown to be hereditarily normal.

A totally ordered set is said to be complete if every nonempty subset that has an upper bound, has a least upper bound. For example, the set of real numbers R is complete but the set of rational numbers Q is not. In other words, the various concepts of completeness (not to be confused with being "total") do not carry over to restrictions. For example, over the real numbers a property of the relation ≤ is that every non-empty subset S of R with an upper bound in R has a least upper bound (also called supremum) in R. However, for the rational numbers this supremum is not necessarily rational, so the same property does not hold on the restriction of the relation ≤ to the rational numbers.

There are a number of results relating properties of the order topology to the completeness of X:

A totally ordered set (with its order topology) which is a complete lattice is compact. Examples are the closed intervals of real numbers, e.g. the unit interval [0,1], and the affinely extended real number system (extended real number line). There are order-preserving homeomorphisms between these examples.

For any two disjoint total orders ( A 1 , ≤ 1 ) {\displaystyle (A_{1},\leq _{1})} {\displaystyle (A_{1},\leq _{1})} and ( A 2 , ≤ 2 ) {\displaystyle (A_{2},\leq _{2})} {\displaystyle (A_{2},\leq _{2})}, there is a natural order ≤ + {\displaystyle \leq _{+}} {\displaystyle \leq _{+}} on the set A 1 ∪ A 2 {\displaystyle A_{1}\cup A_{2}} {\displaystyle A_{1}\cup A_{2}}, which is called the sum of the two orders or sometimes just A 1 + A 2 {\displaystyle A_{1}+A_{2}} {\displaystyle A_{1}+A_{2}}:

For x , y ∈ A 1 ∪ A 2 {\displaystyle x,y\in A_{1}\cup A_{2}} {\displaystyle x,y\in A_{1}\cup A_{2}}, x ≤ + y {\displaystyle x\leq _{+}y} {\displaystyle x\leq _{+}y} holds if and only if one of the following holds:

  1. x , y ∈ A 1 {\displaystyle x,y\in A_{1}} {\displaystyle x,y\in A_{1}} and x ≤ 1 y {\displaystyle x\leq _{1}y} {\displaystyle x\leq _{1}y}
  2. x , y ∈ A 2 {\displaystyle x,y\in A_{2}} {\displaystyle x,y\in A_{2}} and x ≤ 2 y {\displaystyle x\leq _{2}y} {\displaystyle x\leq _{2}y}
  3. x ∈ A 1 {\displaystyle x\in A_{1}} {\displaystyle x\in A_{1}} and y ∈ A 2 {\displaystyle y\in A_{2}} {\displaystyle y\in A_{2}}

Intuitively, this means that the elements of the second set are added on top of the elements of the first set.

More generally, if ( I , ≤ ) {\displaystyle (I,\leq )} {\displaystyle (I,\leq )} is a totally ordered index set, and for each i ∈ I {\displaystyle i\in I} {\displaystyle i\in I} the structure ( A i , ≤ i ) {\displaystyle (A_{i},\leq _{i})} {\displaystyle (A_{i},\leq _{i})} is a linear order, where the sets A i {\displaystyle A_{i}} {\displaystyle A_{i}} are pairwise disjoint, then the natural total order on ⋃ i A i {\displaystyle \bigcup _{i}A_{i}} {\displaystyle \bigcup _{i}A_{i}} is defined by

For x , y ∈ ⋃ i ∈ I A i {\displaystyle x,y\in \bigcup _{i\in I}A_{i}} {\displaystyle x,y\in \bigcup _{i\in I}A_{i}}, x ≤ y {\displaystyle x\leq y} {\displaystyle x\leq y} holds if:

  1. Either there is some i ∈ I {\displaystyle i\in I} {\displaystyle i\in I} with x ≤ i y {\displaystyle x\leq _{i}y} {\displaystyle x\leq _{i}y}
  2. or there are some i < j {\displaystyle i<j} {\displaystyle i<j} in I {\displaystyle I} {\displaystyle I} with x ∈ A i {\displaystyle x\in A_{i}} {\displaystyle x\in A_{i}}, y ∈ A j {\displaystyle y\in A_{j}} {\displaystyle y\in A_{j}}

The first-order theory of total orders is decidable, i.e. there is an algorithm for deciding which first-order statements hold for all total orders. Using interpretability in S2S, the monadic second-order theory of countable total orders is also decidable.[16]

Orders on the Cartesian product of totally ordered sets

[edit]

There are several ways to take two totally ordered sets and extend to an order on the Cartesian product, though the resulting order may only be partial. Here are three of these possible orders, listed such that each order is stronger than the next:

Each of these orders extends the next in the sense that if we have x ≤ y in the product order, this relation also holds in the lexicographic order, and so on. All three can similarly be defined for the Cartesian product of more than two sets.

Applied to the vector space Rn, each of these make it an ordered vector space.

See also examples of partially ordered sets.

A real function of n real variables defined on a subset of Rn defines a strict weak order and a corresponding total preorder on that subset.

Transitive binary relations vte
Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Total, Semiconnex Anti-reflexive Equivalence relation Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗ Preorder (Quasiorder) ✗ ✗ ✗ ✗ ✗ ✗ Green tickY ✗ ✗ Partial order ✗ Green tickY ✗ ✗ ✗ ✗ Green tickY ✗ ✗ Total preorder ✗ ✗ Green tickY ✗ ✗ ✗ Green tickY ✗ ✗ Total order ✗ Green tickY Green tickY ✗ ✗ ✗ Green tickY ✗ ✗ Prewellordering ✗ ✗ Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗ Well-quasi-ordering ✗ ✗ ✗ Green tickY ✗ ✗ Green tickY ✗ ✗ Well-ordering ✗ Green tickY Green tickY Green tickY ✗ ✗ Green tickY ✗ ✗ Lattice ✗ Green tickY ✗ ✗ Green tickY Green tickY Green tickY ✗ ✗ Join-semilattice ✗ Green tickY ✗ ✗ Green tickY ✗ Green tickY ✗ ✗ Meet-semilattice ✗ Green tickY ✗ ✗ ✗ Green tickY Green tickY ✗ ✗ Strict partial order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY Strict weak order ✗ Green tickY ✗ ✗ ✗ ✗ ✗ Green tickY Green tickY Strict total order ✗ Green tickY Green tickY ✗ ✗ ✗ ✗ Green tickY Green tickY Symmetric Antisymmetric Connected Well-founded Has joins Has meets Reflexive Irreflexive Asymmetric Definitions, for all a , b {\displaystyle a,b} {\displaystyle a,b} and S ≠ ∅ : {\displaystyle S\neq \varnothing :} {\displaystyle S\neq \varnothing :} a R b ⇒ b R a {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} {\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}} a R b and b R a ⇒ a = b {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} {\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}} a ≠ b ⇒ a R b or b R a {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} {\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}} min S exists {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} {\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}} a ∨ b exists {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} {\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}} a ∧ b exists {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} {\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}} a R a {\displaystyle aRa} {\displaystyle aRa} not a R a {\displaystyle {\text{not }}aRa} {\displaystyle {\text{not }}aRa} a R b ⇒ not b R a {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}} {\displaystyle {\begin{aligned}aRb\Rightarrow \\{\text{not }}bRa\end{aligned}}}
Green tickY indicates that the column's property is always true for the row's term (at the very left), while ✗ indicates that the property is not guaranteed in general (it might, or might not, hold). For example, that every equivalence relation is symmetric, but not necessarily antisymmetric, is indicated by Green tickY in the "Symmetric" column and ✗ in the "Antisymmetric" column, respectively. All definitions tacitly require the homogeneous relation R {\displaystyle R} {\displaystyle R} be transitive: for all a , b , c , {\displaystyle a,b,c,} {\displaystyle a,b,c,} if a R b {\displaystyle aRb} {\displaystyle aRb} and b R c {\displaystyle bRc} {\displaystyle bRc} then a R c . {\displaystyle aRc.} {\displaystyle aRc.} A term's definition may require additional properties that are not listed in this table.

A binary relation that is antisymmetric, transitive, and reflexive (but not necessarily total) is a partial order.

A group with a compatible total order is a totally ordered group.

There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in a betweenness relation. Forgetting the location of the ends results in a cyclic order. Forgetting both data results in a separation relation.[17]

  1. ^ a b Halmos 1968, Ch.14.
  2. ^ a b Birkhoff 1967, p. 2.
  3. ^ a b Schmidt & Ströhlein 1993, p. 32.
  4. ^ Fuchs 1963, p. 2.
  5. ^ a b c Davey & Priestley 1990, p. 3.
  6. ^ Strohmeier, Alfred; Genillard, Christian; Weber, Mats (1 August 1990). "Ordering of characters and strings". ACM SIGAda Ada Letters (7): 84. doi:10.1145/101120.101136. S2CID 38115497.
  7. ^ Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets". Pi Mu Epsilon Journal. 9 (7): 462–464. ISSN 0031-952X. JSTOR 24340068.
  8. ^ Let a < b {\displaystyle a<b} {\displaystyle a<b}, assume for contradiction that also b < a {\displaystyle b<a} {\displaystyle b<a}. Then a < a {\displaystyle a<a} {\displaystyle a<a} by transitivity, which contradicts irreflexivity.
  9. ^ If a < a {\displaystyle a<a} {\displaystyle a<a}, the not a < a {\displaystyle a<a} {\displaystyle a<a} by asymmetry.
  10. ^ This definition resembles that of an initial object of a category, but is weaker.
  11. ^ Roland Fraïssé (December 2000). Theory of Relations. Studies in Logic and the Foundations of Mathematics. Vol. 145 (1st ed.). Elsevier. ISBN 978-0-444-50542-2. Here: p. 35
  12. ^ Brian A. Davey and Hilary Ann Priestley (1990). Introduction to Lattices and Order. Cambridge Mathematical Textbooks. Cambridge University Press. ISBN 0-521-36766-2. LCCN 89009753. Here: p. 100
  13. ^ Yiannis N. Moschovakis (2006) Notes on set theory, Undergraduate Texts in Mathematics (Birkhäuser) ISBN 0-387-28723-X, p. 116
  14. ^ that is, beyond some index, all further sequence members are equal
  15. ^ Davey and Priestly 1990, Def.2.24, p. 37
  16. ^ Weyer, Mark (2002). "Decidability of S1S and S2S". Automata, Logics, and Infinite Games. Lecture Notes in Computer Science. Vol. 2500. Springer. pp. 207–230. doi:10.1007/3-540-36387-4_12. ISBN 978-3-540-00388-5.
  17. ^ Macpherson, H. Dugald (2011), "A survey of homogeneous structures", Discrete Mathematics, 311 (15): 1599–1634, doi:10.1016/j.disc.2011.01.024