Ordering

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.

References

Deransart, Pierre, Maluszynski, Jan. A Grammatical View of Logic Programming. MIT Press, 1993.
Doets, Kees. From Logic to Logic Programming. MIT Press, 1994.