Order Theory


Order theory the concept of order when using binary relations

Pre Orders

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

Partial Orders

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

Notice that x,yA(x,y)R\exists x, y \in A \bullet (x, y) \notin R, and that’s the reason why a partial order doesn’t provide a way to determine the order of any elements of AA.

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 PX×YP \subseteq X \times Y is denoted as Ṗ=P(domP¯×Y)\dot{P} = P \cup (\overline{dom P}^{\perp} \times Y^{\perp}). The augmented complement domP¯\overline{dom P}^{\perp} is the set of all elements of XX not in PP plus the \perp 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, YY^{\perp}.

So given X={a,b,c}X = \{ a, b, c \} and Y={1,2}Y = \{ 1, 2 \}, and a partial order P={(a,1),(b,2)}P = \{ (a, 1), (b, 2) \}, domP¯={c,}\overline{dom P}^{\perp} = \{ c, \perp \}, and {c,}×Y={(c,1),(c,2),(c,),(,1),(,2),(,)}\{ c, \perp \} \times Y^{\perp} = \{ (c, 1), (c, 2), (c, \perp), (\perp, 1), (\perp, 2), (\perp, \perp) \}. Therefore Ṗ={(a,1),(b,2),(c,1),(c,2),(c,),(,1),(,2),(,)}\dot{P} = \{ (a, 1), (b, 2), (c, 1), (c, 2), (c, \perp), (\perp, 1), (\perp, 2), (\perp, \perp) \}.

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

If the order PP is total, i.e. domP=Xdom P = X, then $ = P { } Y^{} $.

Total Orders

A total order describes the order of all of the ordered pairs in a relation. RR is a total order on AA if its already a partial order, and if x,yAxRyyRx\forall x, y \in A \bullet xRy \lor yRx.

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. RR is a strict partial order on AA 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. RR is a strict total order on AA if its already a strict partial order, and if $ x, y A xRy yRx x = y $.

Special Elements

Given a binary relation RA×AR \subseteq A \times A an arbitrary element xAx \in A:

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

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

Given a partian order RR on AA, BAB \subseteq A, and xAx \in A:

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