Homepage

# 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 \in A \exists y \in A ((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$$.

## 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 \in A \forall y \in A (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 $$\forall x \in A \forall y \in A (xRy \lor yRx \lor 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 ((a, x) \in R \land a \neq x)$$

• Maximal: $$x$$ is a maximal element of $$R$$ if $$\lnot \exists a \in A ((x, a) \in R \land a \neq x)$$

• Smallest: $$x$$ is the smallest element of $$R$$ if $$\forall a \in A ((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 ((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 ((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 ((b, x) \in R)$$

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