# Totally Ordered Set

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

## References

### 2020a

• (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Total_order 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 $X$ , 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 $\leq$ is a total order on a set $X$ if the following statements hold for all $a, b$ and $c$ in $X$ :
• Antisymmetry: If $a \leq b$ and $b \leq a$ then $a = b$ ;
• Transitivity: If $a \leq b$ and $b \leq c$ then $a \leq c$ ;
• Connexity: $a \leq b$ or $b \leq a$ .
Antisymmetry eliminates uncertain cases when both $a$ precedes $b$ and $b$ precedes $a$[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.

### 2020b

• (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Total_order#Chains 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.