# 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:

• Any re­la­tion satis­fy­ing 1-3 is a par­tial or­der, and the cor­re­spond­ing set is a poset. A to­tal or­der is a spe­cial kind of par­tial or­der defined by also satis­fy­ing 4.

• So effec­tively all or­der re­la­tions are par­tial or­der re­la­tions?