An binary relation
`R`

on a set `S`

is called an *ordering* on `S`

if `R`

is

- reflexive:
`∀s∈S sRs`

, - transitive:
`∀s,t,u∈S sRt∧tRu⇒sRu`

- antisymmetric:
`∀s,t∈S sRt∧tRs⇒s=t`

.

The the element `s∈S`

is a *maximal* element of `S`

if `¬∃t∈S, s≠t∧sRt`

.

The the element `s∈S`

is a *minimal* element of `S`

if `¬∃t∈S, s≠t∧tRs`

.

The the element `s∈S`

is the *greatest* element of `S`

if `∀t∈S tRs`

.

Note we can have several maximal elements but only one greatest element.

The elements `s,t∈S`

are called *comparable* if `sRt∨tRs`

.
Otherwise they are called *incomparable*.
The ordering `R`

is called *total* if all elements of `S`

are comparable.
Otherwise the ordering is called *partial*.

Doets defines the partial ordering as a relation `R`

on a set `S`

as being one which is both

- irreflexive:
`∀s∈S ¬sRs`

, and - transitive:
`∀s,t,u∈S sRt∧tRu⇒sRu`

He then goes on to define a *linear ordering* as one for which `∀s,t∈S`

such that `s≠t, sRt∨tRs`

.
Note that all linear orderings of the same finite set are isomorphic.

A well-founded linear ordering is called a *well-ordering*.

Deransart, Pierre, Maluszynski, Jan. *A Grammatical View of Logic Programming.* MIT Press, 1993.

Doets, Kees. *From Logic to Logic Programming.* MIT Press, 1994.

Copyright © 2014 Barry Watson. All rights reserved.