Partial order: a relation that is reflexive, antisymmetric and transitive.

Examples:

• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x\geq y$,
• The relation $R$ on the collection of alls sets where $xRy$ if $x\subseteq y$,
• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x\vert y$.

Equivalence relation: a relation that is reflexive, symmetric and transitive.

Examples:

• The relation $R$ on $\mathbb{Z}$ where $xRy$ if $x-y$ is divisible by 5.
• The relation $R$ on the set of all people where $xRy$ if $x$ and $y$ have the same age.

A relation $R$ on a set $A$ can be represented as a directed graph $G_R=(A,E)$ as follows:

The vertices of $G_R$ are the elements of $A$
The edge set $E=\{ (a,b)\in A\times A\vert aRb\}$.

A relation $R$ on a set $A=\{ a_1,a_2,\dots, a_n\}$ can be represented by an $n\times n$ relation matrix $A$ as follows:

$$A_{i,j}=\left\{ \begin{array}{ll} 1&\mbox{if $a_iRa_j$}\\ 0&\mbox{otherwise} \end{array}\right.$$

Note that the relation matrix of $R$ is the adjacency matrix of the directed graph representing $R$.

Partial Orders

Given a partial order $R$ on a set $A$:

An element $x\in A$ is maximal if

$$\forall_{a\in A} xRa\rightarrow x=a.$$

An element $x\in A$ is minimal if

$$\forall_{a\in A} aRx\rightarrow x=a.$$

An element $x\in A$ is a greatest element if

$$\forall_{a\in A} aRx.$$

An element $x\in A$ is a least element if

$$\forall_{a\in A} xRa.$$

Let $B\subseteq A$.

An element $x\in A$ is a lower bound of $B$ if

$$\forall_{b\in B} xRb.$$

An element $x$ is a greatest lower bound (glb) of $B$ if $x$ is a lower bound of $B$, and for every lower bound $x'$ of $B$, $x'Rx$.

Let $B\subseteq A$.

An element $x\in A$ is a upper bound of $B$ if

$$\forall_{b\in B} bRx.$$

An element $x$ is a least upper bound (lub) of $B$ if $x$ is an upper bound of $B$, and for every upper bound $x'$ of $B$, $xRx'$.