# Order Theory

Order theory the concept of order when using binary relations

## Pre Orders

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

## Partial Orders

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

Notice that $\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 $A$.

### 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 $P \subseteq X \times Y$ is denoted as $\dot{P} = P \cup (\overline{dom P}^{\perp} \times Y^{\perp})$. The augmented complement $\overline{dom P}^{\perp}$ is the set of all elements of $X$ not in $P$ 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, $Y^{\perp}$.

So given $X = \{ a, b, c \}$ and $Y = \{ 1, 2 \}$, and a partial order $P = \{ (a, 1), (b, 2) \}$, $\overline{dom P}^{\perp} = \{ c, \perp \}$, and $\{ c, \perp \} \times Y^{\perp} = \{ (c, 1), (c, 2), (c, \perp), (\perp, 1), (\perp, 2), (\perp, \perp) \}$. Therefore $\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 $P$ is total, i.e. $dom P = X$, then $ = P { } Y^{} $.

## Total Orders

A total order describes the order of *all* of the
ordered pairs in a relation.
$R$
is a total order on
$A$
if its already a partial order, and if
$\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.
$R$
is a strict partial order on
$A$
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.
$R$
is a strict total order on
$A$
if its already a strict partial order, and if $ x, y A xRy yRx x
= y $.

## Special Elements

Given a binary relation $R \subseteq A \times A$ an arbitrary element $x \in A$:

**Minimal**: $x$ is a minimal element of $R$ if $\lnot \exists a \in A \bullet (a, x) \in R \land a \neq x$**Maximal**: $x$ is a maximal element of $R$ if $\lnot \exists a \in A \bullet (x, a) \in R \land a \neq x$**Smallest**: $x$ is**the**smallest element of $R$ if $\forall a \in A \bullet (x, a) \in R$

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

**Largest**: $x$ is**the**largest element of $R$ if $\forall a \in A \bullet (a, x) \in R$

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

Given a partian order $R$ on $A$, $B \subseteq A$, and $x \in A$:

**Lower bound**: $x$ is a lower bound for $B$ if $\forall b \in B \bullet (x, b) \in R$

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

**Upper bound**: $x$ is a lower bound for $B$ if $\forall b \in B \bullet (b, x) \in R$**Least upper bound**: The smallest element of the upper bounds**Greatest lower bound**: The largest element of the lower bounds