Movatterモバイル変換

[0]ホーム
URL:

Jump to content
WikipediaThe Free Encyclopedia
Search

Total order

From Wikipedia, the free encyclopedia
Order whose elements are all comparable
"Linear order" redirects here; not to be confused withLinear order (linguistics).
This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(February 2016) (Learn how and when to remove this message)

Inmathematics, atotal order orlinear order is apartial order in which any two elements are comparable. That is, a total order is abinary relation≤{\displaystyle \leq } on somesetX{\displaystyle X}, which satisfies the following for alla,b{\displaystyle a,b} andc{\displaystyle c} inX{\displaystyle X}:

  1. a≤a{\displaystyle a\leq a} (reflexive).
  2. Ifa≤b{\displaystyle a\leq b} andb≤c{\displaystyle b\leq c} thena≤c{\displaystyle a\leq c} (transitive).
  3. Ifa≤b{\displaystyle a\leq b} andb≤a{\displaystyle b\leq a} thena=b{\displaystyle a=b} (antisymmetric).
  4. a≤b{\displaystyle a\leq b} orb≤a{\displaystyle b\leq a} (strongly connected, formerly called totality).

Requirements 1. to 3. just make up the definition of a partial order.Reflexivity (1.) already follows from strong connectedness (4.), but is required explicitly by many authors nevertheless, to indicate the kinship to partial orders.[1]Total orders are sometimes also calledsimple,[2]connex,[3] orfull orders.[4]

A set equipped with a total order is atotally ordered set;[5] the termssimply ordered set,[2]linearly ordered set,[3][5]toset[6] andloset[7][8] are also used. The termchain is sometimes defined as a synonym oftotally 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 alinear extension of that partial order.

Strict and non-strict total orders

[edit]

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

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

Thus, astrict total order on a setX{\displaystyle X} is astrict partial order onX{\displaystyle X} in which any two distinct elements are comparable. That is, a strict total order is abinary relation<{\displaystyle <} on somesetX{\displaystyle X}, which satisfies the following for alla,b{\displaystyle a,b} andc{\displaystyle c} inX{\displaystyle X}:

  1. Nota<a{\displaystyle a<a} (irreflexive).
  2. Ifa<b{\displaystyle a<b} then notb<a{\displaystyle b<a} (asymmetric).
  3. Ifa<b{\displaystyle a<b} andb<c{\displaystyle b<c} thena<c{\displaystyle a<c} (transitive).
  4. Ifa≠b{\displaystyle a\neq b}, thena<b{\displaystyle a<b} orb<a{\displaystyle b<a} (connected).

Asymmetry follows from transitivity and irreflexivity;[a] moreover, irreflexivity follows from asymmetry.[b]

Examples

[edit]
  • Anysubset of a totally ordered setX is totally ordered for the restriction of the order onX.
  • The unique order on the empty set,∅, is a total order.
  • Any set ofordinal numbers (more strongly, these arewell-orders).
  • IfX is any set andf aninjective function fromX to a totally ordered set thenf induces a total ordering onX by settingx1 ≤x2 if and only iff(x1) ≤f(x2).
  • Thelexicographical order on theCartesian product of a family of totally ordered sets,indexed by awell ordered set, is itself a total order.
  • The set ofreal numbers ordered by the usual "less than or equal to" (≤) or "greater than or equal to" (≥) relations is totally ordered. Hence each subset of the real numbers is totally ordered, such as thenatural numbers,integers, andrational numbers. Each of these can be shown to be the unique (up to anorder isomorphism) "initial example" of a totally ordered set with a certain property, (here, a total orderA isinitial for a property, if, wheneverB has the property, there is an order isomorphism fromA to a subset ofB):[9][citation needed]
    • The natural numbers form an initial non-empty totally ordered set with noupper bound.
    • The integers form an initial non-empty totally ordered set with neither an upper nor alower bound.
    • The rational numbers form an initial totally ordered set which isdense in the real numbers. Moreover, the reflexive reduction < is adense order on the rational numbers.
    • The real numbers form an initial unbounded totally ordered set that isconnected in theorder topology (defined below).
  • Ordered fields are totally ordered by definition. They include the rational numbers and the real numbers. Every ordered field contains an ordered subfield that is isomorphic to the rational numbers. AnyDedekind-complete ordered field is isomorphic to the real numbers.
  • The letters of the alphabet ordered by the standarddictionary order, e.g.,A <B <C etc., is a strict total order.

Chains

[edit]

The termchain is sometimes defined as a synonym for a totally ordered set, but it is generally used for referring to asubset of apartially ordered set that is totally ordered for the induced order.[1][10] 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 ofchain for referring to totally ordered subsets isZorn's lemma which asserts that, if every chain in a partially ordered setX has an upper bound inX, thenX contains at least one maximal element.[11] Zorn's lemma is commonly used withX being a set of subsets; in this case, the upper bound is obtained by proving that the union of the elements of a chain inX is inX. This is the way that is generally used to prove that avector space hasHamel bases and that aring hasmaximal ideals.

In some contexts, the chains that are considered are order isomorphic to the natural numbers with their usual order or itsopposite order. In this case, a chain can be identified with amonotone sequence, and is called anascending chain or adescending chain, depending whether the sequence is increasing or decreasing.[12]

A partially ordered set has thedescending chain condition if every descending chain eventually stabilizes.[13] For example, an order iswell founded if it has the descending chain condition. Similarly, theascending chain condition means that every ascending chain eventually stabilizes. For example, aNoetherian ring is a ring whoseideals satisfy the ascending chain condition.

In other contexts, only chains that arefinite sets are considered. In this case, one talks of afinite chain, often shortened as achain. In this case, thelength 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.[14] Thus asingleton set is a chain of length zero, and anordered pair is a chain of length one. Thedimension of a space is often defined or characterized as the maximal length of chains of subspaces. For example, thedimension of a vector space is the maximal length of chains oflinear subspaces, and theKrull dimension of acommutative ring is the maximal length of chains ofprime ideals.

"Chain" may also be used for some totally ordered subsets ofstructures that are not partially ordered sets. An example is given byregular chains of polynomials. Another example is the use of "chain" as a synonym for awalk in agraph.

Further concepts

[edit]

Lattice theory

[edit]

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

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

We then writea ≤bif and only ifa=a∧b{\displaystyle a=a\wedge b}. Hence a totally ordered set is adistributive lattice.

Finite total orders

[edit]

A simplecounting 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 awell order. Either by direct proof or by observing that every well order isorder isomorphic to anordinal one may show that every finite total order isorder isomorphic to aninitial segment of the natural numbers ordered by <. In other words, a total order on a set withk elements induces a bijection with the firstk natural numbers. Hence it is common to index finite total orders or well orders withorder type ω by natural numbers in a fashion which respects the ordering (either starting with zero or with one).

Category theory

[edit]

Totally ordered sets form afull subcategory of thecategory ofpartially ordered sets, with themorphisms being maps which respect the orders, i.e. mapsf such that ifa ≤b thenf(a) ≤f(b).

Abijectivemap between two totally ordered sets that respects the two orders is anisomorphism in this category.

Order topology

[edit]

For any totally ordered setX we can define theopen intervals

  • (a,b) = {x |a <x andx <b},
  • (−∞,b) = {x |x <b},
  • (a, ∞) = {x |a <x}, and
  • (−∞, ∞) =X.

We can use these open intervals to define atopology on any ordered set, theorder 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 ifN is the natural numbers,< is less than and> greater than we might refer to the order topology onN induced by< and the order topology onN 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 hereditarilynormal.

Completeness

[edit]

A totally ordered set is said to becomplete if every nonempty subset that has anupper bound, has aleast upper bound. For example, the set ofreal numbersR is complete but the set ofrational numbersQ is not. In other words, the various concepts ofcompleteness (not to be confused with being "total") do not carry over torestrictions. For example, over thereal numbers a property of the relation≤ is that everynon-empty subsetS ofR with anupper bound inR has aleast upper bound (also called supremum) inR. 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:

  • If the order topology onX is connected,X is complete.
  • X is connected under the order topology if and only if it is complete and there is nogap inX (a gap is two pointsa andb inX witha <b such that noc satisfiesa <c <b.)
  • X is complete if and only if every bounded set that is closed in the order topology is compact.

A totally ordered set (with its order topology) which is acomplete lattice iscompact. Examples are the closed intervals of real numbers, e.g. theunit interval [0,1], and theaffinely extended real number system (extended real number line). There are order-preservinghomeomorphisms between these examples.

Sums of orders

[edit]

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

Forx,y∈A1∪A2{\displaystyle x,y\in A_{1}\cup A_{2}},x≤+y{\displaystyle x\leq _{+}y} holds if and only if one of the following holds:
  1. x,y∈A1{\displaystyle x,y\in A_{1}} andx≤1y{\displaystyle x\leq _{1}y}
  2. x,y∈A2{\displaystyle x,y\in A_{2}} andx≤2y{\displaystyle x\leq _{2}y}
  3. x∈A1{\displaystyle x\in A_{1}} andy∈A2{\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 )} is a totally ordered index set, and for eachi∈I{\displaystyle i\in I} the structure(Ai,≤i){\displaystyle (A_{i},\leq _{i})} is a linear order, where the setsAi{\displaystyle A_{i}} are pairwise disjoint, then the natural total order on⋃iAi{\displaystyle \bigcup _{i}A_{i}} is defined by

Forx,y∈⋃i∈IAi{\displaystyle x,y\in \bigcup _{i\in I}A_{i}},x≤y{\displaystyle x\leq y} holds if:
  1. Either there is somei∈I{\displaystyle i\in I} withx≤iy{\displaystyle x\leq _{i}y}
  2. or there are somei<j{\displaystyle i<j} inI{\displaystyle I} withx∈Ai{\displaystyle x\in A_{i}},y∈Aj{\displaystyle y\in A_{j}}

Decidability

[edit]

Thefirst-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 inS2S, themonadic second-order theory ofcountable total orders is also decidable.[15]

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 theCartesian product, though the resulting order may only bepartial. Here are three of these possible orders, listed such that each order is stronger than the next:

  • Lexicographical order: (a,b) ≤ (c,d) if and only ifa <c or (a =c andb ≤d). This is a total order.
  • (a,b) ≤ (c,d) if and only ifa ≤c andb ≤d (theproduct order). This is a partial order.
  • (a,b) ≤ (c,d) if and only if (a <c andb <d) or (a =c andb =d) (the reflexive closure of thedirect product of the corresponding strict total orders). This is also a partial order.

Each of these orders extends the next in the sense that if we havex ≤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 thevector spaceRn, each of these make it anordered vector space.

See alsoexamples of partially ordered sets.

A real function ofn real variables defined on a subset ofRndefines a strict weak order and a corresponding total preorder on that subset.

Related structures

[edit]
Transitive binary relations
SymmetricAntisymmetricConnectedWell-foundedHas joinsHas meetsReflexiveIrreflexiveAsymmetric
Total,
Semiconnex		 Anti-
reflexive
Equivalence relationGreen tickY✗✗✗✗✗Green tickY✗✗
Preorder(Quasiorder)✗✗✗✗✗✗Green tickY✗✗
Partial order✗Green tickY✗✗✗✗Green tickY✗✗
Total preorder✗✗Green tickY✗✗✗Green tickY✗✗
Total order✗Green tickYGreen tickY✗✗✗Green tickY✗✗
Prewellordering✗✗Green tickYGreen tickY✗✗Green tickY✗✗
Well-quasi-ordering✗✗✗Green tickY✗✗Green tickY✗✗
Well-ordering✗Green tickYGreen tickYGreen tickY✗✗Green tickY✗✗
Lattice✗Green tickY✗✗Green tickYGreen tickYGreen tickY✗✗
Join-semilattice✗Green tickY✗✗Green tickY✗Green tickY✗✗
Meet-semilattice✗Green tickY✗✗✗Green tickYGreen tickY✗✗
Strict partial order✗Green tickY✗✗✗✗✗Green tickYGreen tickY
Strict weak order✗Green tickY✗✗✗✗✗Green tickYGreen tickY
Strict total order✗Green tickYGreen tickY✗✗✗✗Green tickYGreen tickY
SymmetricAntisymmetricConnectedWell-foundedHas joinsHas meetsReflexiveIrreflexiveAsymmetric
Definitions,
for alla,b{\displaystyle a,b} andS≠∅:{\displaystyle S\neq \varnothing :}		aRb⇒bRa{\displaystyle {\begin{aligned}&aRb\\\Rightarrow {}&bRa\end{aligned}}}aRb and bRa⇒a=b{\displaystyle {\begin{aligned}aRb{\text{ and }}&bRa\\\Rightarrow a={}&b\end{aligned}}}a≠b⇒aRb or bRa{\displaystyle {\begin{aligned}a\neq {}&b\Rightarrow \\aRb{\text{ or }}&bRa\end{aligned}}}minSexists{\displaystyle {\begin{aligned}\min S\\{\text{exists}}\end{aligned}}}a∨bexists{\displaystyle {\begin{aligned}a\vee b\\{\text{exists}}\end{aligned}}}a∧bexists{\displaystyle {\begin{aligned}a\wedge b\\{\text{exists}}\end{aligned}}}aRa{\displaystyle aRa}not aRa{\displaystyle {\text{not }}aRa}aRb⇒not bRa{\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 byGreen tickY in the "Symmetric" column and✗ in the "Antisymmetric" column, respectively.

All definitions tacitly require thehomogeneous relationR{\displaystyle R} betransitive: for alla,b,c,{\displaystyle a,b,c,} ifaRb{\displaystyle aRb} andbRc{\displaystyle bRc} thenaRc.{\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 apartial order.

Agroup with a compatible total order is atotally ordered group.

There are only a few nontrivial structures that are (interdefinable as) reducts of a total order. Forgetting the orientation results in abetweenness relation. Forgetting the location of the ends results in acyclic order. Forgetting both data results use ofpoint-pair separation to distinguish, on a circle, the two intervals determined by a point-pair.[16]

See also

[edit]

Notes

[edit]
  1. ^Leta<b{\displaystyle a<b}, assume for contradiction that alsob<a{\displaystyle b<a}. Thena<a{\displaystyle a<a} by transitivity, which contradicts irreflexivity.
  2. ^Ifa<a{\displaystyle a<a}, then nota<a{\displaystyle a<a} by asymmetry.
References
  1. ^abHalmos 1968, Ch.14.
  2. ^abBirkhoff 1967, p. 2.
  3. ^abSchmidt & Ströhlein 1993, p. 32.
  4. ^Fuchs 1963, p. 2.
  5. ^abcDavey & Priestley 1990, p. 3.
  6. ^Young AP, Modgil S, Rodrigues O.Prioritised Default Logic as Rational Argumentation(PDF). Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016). Retrieved16 January 2025.
  7. ^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.
  8. ^Ganapathy, Jayanthi (1992). "Maximal Elements and Upper Bounds in Posets".Pi Mu Epsilon Journal.9 (7):462–464.ISSN 0031-952X.JSTOR 24340068.
  9. ^This definition resembles that of aninitial object of acategory, but is weaker.
  10. ^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
  11. ^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
  12. ^Yiannis N. Moschovakis (2006)Notes on set theory,Undergraduate Texts in Mathematics (Birkhäuser)ISBN 0-387-28723-X, p. 116
  13. ^that is, beyond some index, all further sequence members are equal
  14. ^Davey and Priestly 1990, Def.2.24, p. 37
  15. ^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.
  16. ^Macpherson, H. Dugald (2011), "A survey of homogeneous structures",Discrete Mathematics,311 (15):1599–1634,doi:10.1016/j.disc.2011.01.024

Bibliography

[edit]

External links

[edit]
Key concepts
Results
Properties & Types (list)
Constructions
Topology & Orders
Related
Retrieved from "https://en.wikipedia.org/w/index.php?title=Total_order&oldid=1320898113"
Categories:
Hidden categories:
[8]ページ先頭
©2009-2026 Movatter.jp