Skip to content

Partial Orders#

Definition: Partial Order

Let \(A\) be a set.

A partial order of \(A\) is a relation \(R \subseteq A \times A\) which is reflexive, transitive and asymmetric.

Notation

Partial orders are usually denoted by \(\le\) instead of \(R\).

Definition: Strict Partial Order

Let \(A\) be a set.

A strict partial order of \(A\) is a relation \(R \subseteq A \times A\) which is irreflexive, transitive and antisymmetric.

Notation

Partial orders are usually denoted by \(\lt\) instead of \(R\).

Boundedness#

Definition: Boundedness

Let \(S\) be a partially ordered set and let \(T\) be subset of \(S\).

We say that \(T\) is:

  • bounded below if there exists some \(l \in S\) such that \(l \le t\) for all \(t \in T\). Any such \(l\) is called a lower bound of \(T\);
  • bounded above if there exists some \(u \in S\) such that \(t \le u\) for all \(t \in T\). Any such \(u\) is called an upper bound of \(T\);
  • bounded if it is both bounded above and bounded below.

Definition: Infimum

Let \(S\) be a partially ordered set, let \(T \subseteq S\) be bounded below and let \(L\) be the set of all lower bounds of \(T\).

The infimum of \(T\) is the smallest lower bound of \(T\) (if such exists):

\[ \inf T \le l \qquad \forall l \in L \]

Definition: Supremum

Let \(S\) be a partially ordered set, let \(T \subseteq S\) be bounded above and let \(U\) be the set of all upper bounds of \(T\).

The supremum of \(T\) is the greatest upper bound of \(T\) (if such exists):

\[ u \le \sup T \qquad \forall u \in U \]

Total Orders#

Definition: Total Order

Let \(A\) be a set.

A total order of \(A\) is a partial order of \(A\) in which any two elements are comparable:

\[ a \le b \text{ or } b \le a \qquad \forall a,b \in A \]

Definition: Strict Total Order

Let \(A\) be a set.

A strict total order of \(A\) is a strict partial order of \(A\) in which any two elements are comparable:

\[ a \lt b \text{ or } b \lt a \qquad \forall a,b \in A \]