Order relation

An or­der re­la­tion (also called an or­der or or­der­ing) is a bi­nary re­la­tion \(\le\) on a set \(S\) that can be used to or­der the el­e­ments in that set.

An or­der re­la­tion satis­fies the fol­low­ing prop­er­ties:

  1. For all \(a \in S\), \(a \le a\). (the re­flex­ive prop­erty)

  2. For all \(a, b \in S\), if \(a \le b\) and \(b \le a\), then \(a = b\). (the an­ti­sym­met­ric prop­erty)

  3. For all \(a, b, c \in S\), if \(a \le b\) and \(b \le c\), then \(a \le c\). (the tran­si­tive prop­erty)

A set that has an or­der re­la­tion is called a par­tially or­dered set (or “poset”), and \(\le\) is its par­tial or­der.

To­tal­ity of an order

There is also a fourth prop­erty that dis­t­in­guishes be­tween two differ­ent types of or­ders:

  1. For all \(a, b \in S\), ei­ther \(a \le b\) or \(b \le a\) or both. (the to­tal prop­erty)

The to­tal prop­erty im­plies the re­flex­ive prop­erty, by set­ting \(a = b\).

If the or­der re­la­tion satis­fies the to­tal prop­erty, then \(S\) is called a to­tally or­dered set, and \(\le\) is its to­tal or­der.

Well-ordering

A fifth prop­erty that ex­tends the idea of a “to­tal or­der” is that of the well-or­der­ing:

  1. For ev­ery sub­set \(X\) of \(S\), \(X\) has a least el­e­ment: an el­e­ment \(x\) such that for all \(y \in X\), we have \(x \leq y\).

Well-or­der­ings are very use­ful: they are the or­der­ings we can perform in­duc­tion over. (For more on this view­point, see the page on struc­tural in­duc­tion.)

Derived relations

The or­der re­la­tion im­me­di­ately af­fords sev­eral other re­la­tions.

Re­v­erse order

We can define a re­verse or­der \(\ge\) as fol­lows: \(a \ge b\) when \(b \le a\).

Strict order

From any poset \((S, \le)\), we can de­rive a strict or­der \(<), which dis­al­lows equal­ity. For \(a, b \in S\), \(a < b\) when \(a \le b\) and \(a \neq b\). This strict or­der is still an­ti­sym­met­ric and tran­si­tive, but it is no longer re­flex­ive.

We can then also define a re­verse strict or­der \(>\) as fol­lows: \(a > b\) when \(b \le a\) and \(a \neq b\).

Incomparability

In a poset that is not to­tally or­dered, there ex­ist el­e­ments \(a\) and \(b\) where the or­der re­la­tion is un­defined. If nei­ther \(a \leq b\) nor \(b \leq a\) then we say that \(a\) and \(b\) are in­com­pa­rable, and write \(a \parallel b\).

Cover relation

From any poset \((S, \leq)\), we can de­rive an un­der­ly­ing cover re­la­tion \(\prec\), defined such that for \(a, b \in S\), \(a \prec b\) when­ever the fol­low­ing two con­di­tions are satis­fied:

  1. \(a < b\).

  2. For all \(s \in S\), \(a \leq s < b\) im­plies that \(a = s\).

Sim­ply put, \(a \prec b\) means that \(b\) is the small­est el­e­ment of \(S\) which is strictly greater than \(a\). \(a \prec b\) is pro­nounced ”\(a\) is cov­ered by \(b\)”, or ”\(b\) cov­ers \(a\)”, and \(b\) is said to be a cover of \(a\).

Parents: