PlanetMath: total order

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (191)
Orphanage
Unclass'd
Unproven (496)
Corrections (10)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

total order

(Definition)

A totally ordered set (or linearly ordered set) is a poset $(T,\leq)$ which has the property of comparability:

for all $x,y\in T$ , either $x\leq y$ or $y \leq x$ .

In other words, a totally ordered set is a set

with a binary relation $\leq$ on it such that the following hold for all $x,y,z\in T$ :

$x\leq x$ . (reflexivity)
If $x\leq y$ and $y\leq x$ , then . (antisymmetry)
If $x\leq y$ and $y\leq z$ , then $x\leq z$ . (transitivity)
Either $x\leq y$ or $y \leq x$ . (comparability)

The binary relation $\leq$ is then called a total order or a linear order (or total ordering or linear ordering). A totally ordered set is also sometimes called a chain, especially when it is considered as a subset of some other poset. If every nonempty subset of has a least element, then the total order is called a well-order.

Some people prefer to define the binary relation as a total order, rather than $\leq$ . In this case, is required to be transitive and to obey the law of trichotomy. It is straightforward to check that this is equivalent to the above definition, with the usual relationship between and $\leq$ (that is, $x\leq y$ if and only if either or ).

A totally ordered set can also be defined as a lattice $(T,\lor,\land)$ in which the following property holds:

for all $x,y\in T$ , either $x\land y=x$ or $x\land y=y$ .

Then totally ordered sets are distributive lattices.

"total order" is owned by yark. [ full author list (2) | owner history (1) ]

(view preamble)

Other names:

linear order, total ordering, linear ordering

Also defines:

totally ordered set, linearly ordered set, comparability, totally ordered, linearly ordered, chain, totally-ordered set, linearly-ordered set, totally-ordered, linearly-ordered

Keywords:

transitivity, reflexivity, antisymmetry, binary relation

Attachments:: ordered group (Definition) by pahio
dense total order (Definition) by mps

Log in to rate this entry.
(view current ratings)

Cross-references: lattice, law of trichotomy, least element, subset, transitivity, antisymmetry, reflexivity, binary relation, poset
There are 161 references to this entry.

This is version 17 of total order, born on 2001-10-06, modified 2007-11-04.
Object id is 124, canonical name is TotalOrder.
Accessed 45045 times total.

Classification:

AMS MSC:

06A05 (Order, lattices, ordered algebraic structures :: Ordered sets :: Total order)

Pending Errata and Addenda

None.[ View all 4 ]

Discussion

forum policy

No messages.

Interact