Ordering

Main Index Foundation of mathematics Relations
Subject Index
comment on the page

Ordering relation

Order theory studies various kinds of binary relations that capture the intuitive notion of ordering expressed usually using phrases "less than" or "precedes".

A partial ordering (or simply ordering) of the set is a binary relation, say , which is

reflexive: for every ,

transitive: if and , then ,

antisymmetric: if and , then ,

A set with a partial order defined on it is called a partially ordered set, just an ordered set. A partially ordered set is also called a poset. This term was coined by Garrett Birkhoff [1] . A partially ordered set endowed with partial ordering is denoted by .

If in addition at least one of the relations

holds for all , then we say that the ordering relation is total. These orders are also called linear orders or chains. For instance, the divisibility relation between natural numbers is not total.

A partial ordering can be visually represented by the so-called Hasse diagrams. For instance, the name linear orders or chains comes from the fact that the elements of a linearly ordered set can be visually arranged along a straight line.

A preorder is a binary relation that is reflexive and transitive, but not necessarily antisymmetric. Each preorder on a set induces an order relation in the following way:

define an equivalence relation , where if and ,
identify all elements that are equivalent with respect to .

Thus obtained set of equivalence class is often denoted by .

An element of a partially ordered set is called

the least element if for all elements ,

a minimal element, if implies for all elements ,

the greatest element if for all elements ,

a maximal element, if implies for all elements .

The least element is the only minimal element of a poset, but generally a poset may have more minimal elements. Similarly, the greatest element is the only maximal element of a poset, but a poset may have more maximal elements

A well-ordering on a set is an ordering on such that every non-empty subset of set contains a minimal element, that is, there exists an element in each non-empty subset such that for each .