Totally Ordered Set

Jump to: navigation, search

A Totally Ordered Set is a Set that is paired with a Total Order Relation.



  • (Wikipedia, 2020) ⇒ Retrieved:2020-2-15.
    • In mathematics, a total order, simple order, linear order, connex order, or full order is a binary relation on some set [math] X [/math] , which is antisymmetric, transitive, and a connex relation. A set paired with a total order is called a chain,a totally ordered set,a simply ordered set,or a linearly ordered set.Formally, a binary relation [math] \leq [/math] is a total order on a set [math] X [/math] if the following statements hold for all [math] a, b [/math] and [math] c [/math] in [math] X [/math] :
      • Antisymmetry: If [math] a \leq b [/math] and [math] b \leq a [/math] then [math] a = b [/math] ;
      • Transitivity: If [math] a \leq b [/math] and [math] b \leq c [/math] then [math] a \leq c [/math] ;
      • Connexity: [math] a \leq b [/math] or [math] b \leq a [/math] .
Antisymmetry eliminates uncertain cases when both [math] a [/math] precedes [math] b [/math] and [math] b [/math] precedes [math] a [/math][1]. A relation having the connex property means that any pair of elements in the set of the relation are comparable under the relation. This also means that the set can be diagrammed as a line of elements, giving it the name linear. The connex property also implies reflexivity, i.e., aa. Therefore, a total order is also a (special case of a) partial order, as, for a partial order, the connex property is replaced by the weaker reflexivity property. An extension of a given partial order to a total order is called a linear extension of that partial order.
  1. Nederpelt, Rob (2004). Logical Reasoning: A First Course. Texts in Computing. 3 (3rd, Revised ed.). King's College Publications. ISBN 0-9543006-7-X.


  • (Wikipedia, 2020) ⇒ Retrieved:2020-2-15.
    • The term chain is a synonym for a totally ordered set, but the term is often used to mean a totally ordered subset of some partially ordered set, for example in Zorn's lemma [1].
      • An ascending chain is a totally ordered set having a (unique) minimal element, while a descending chain is a totally ordered set having a (unique) maximal element.
      • Given a set S with a partial order ≤, an infinite descending chain is an infinite, strictly decreasing sequence of elements x1 > x2 > .... [2] As an example, in the set of integers, the chain −1, −2, −3, ... is an infinite descending chain, but there exists no infinite descending chain on the natural numbers, as every chain of natural numbers has a minimal element. If a partially ordered set does not possess any infinite descending chains, it is said to satisfy the descending chain condition. Assuming the axiom of choice, the descending chain condition on a partially ordered set is equivalent to requiring that the corresponding strict order is well-founded. A stronger condition, that there be no infinite descending chains and no infinite antichains, defines the well-quasi-orderings. A totally ordered set without infinite descending chains is called well-ordered.
      • See also Ascending chain condition for this notion.
      • The height of a poset denotes the cardinality of its largest chain in this sense.

        For example, consider the set of all subsets of the integers, partially ordered by inclusion. Then the set {In : n is a natural number}, where In is the set of natural numbers below n, is a chain in this ordering, as it is totally ordered under inclusion: If nk, then In is a subset of Ik.

  1. Paul R. Halmos (1968). Naive Set Theory. Princeton: Nostrand. Here: Chapter 14
  2. Yiannis N. Moschovakis (2006) Notes on set theory, Undergraduate Texts in Mathematics (Birkhäuser), p. 116