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.