Order Theory

Order theory the concept of order when using binary relations

Pre Orders

A relation on is called a preorder of if its reflexive and transitive.

Partial Orders

A partial order describes the order of some of the ordered pairs in a relation. is a partial order on if its reflexive, transitive, and antisymmetric. A partial order is also a preorder.

Notice that , and that’s the reason why a partial order doesn’t provide a way to determine the order of any elements of .

Totalising a Partial Order

A partial order is totalized by calculating its augment set, and associating every element that is not in the partial order’s domain with every element of the augmented target.

The totalized version of is denoted as . The augmented complement is the set of all elements of not in plus the element (the augmented symbol is applied to the result of the complement operation). Each element is then associated with every element of the augmented target, .

So given and , and a partial order , , and . Therefore .

Notice that the totalized version behaves as specified when used within the partial order domain. Anything outside that is considered undefined. The role of is to ensure that undefinedness is propagated through relational composition.

If the order is total, i.e. , then .

Total Orders

A total order describes the order of all of the ordered pairs in a relation. is a total order on if its already a partial order, and if .

Strict Partial Orders

A strict partial order describes the order of some of the ordered pairs in a relation, but making sure that pairs consisting of the same element, and mirrored pairs are omitted. is a strict partial order on if its irreflexive, transitive, and asymmetric (which assumes the relation is antisymmetric as well). Keep in mind a strict partial order is not a partial order.

Strict Total Orders

A strict total order extends a strict partial order to describe the order of all of the ordered pairs in a relation. is a strict total order on if its already a strict partial order, and if .

Special Elements

Given a binary relation an arbitrary element :

• Minimal: is a minimal element of if

• Maximal: is a maximal element of if

• Smallest: is the smallest element of if

Note that the smallest element is also a minimal element. Since a total order describes the ordering of all possible elements, then if is a total order and is a minimal element, then its also the smallest one.

• Largest: is the largest element of if

Note that the largest element is also a maximal element. Since a total order describes the ordering of all possible elements, then if is a total order and is a maximal element, then its also the largest one.

Given a partian order on , , and :

• Lower bound: is a lower bound for if

Note that the smallest element of is a lower bound that is also an element of .

• Upper bound: is a lower bound for if

• Least upper bound: The smallest element of the upper bounds
• Greatest lower bound: The largest element of the lower bounds