# Partial Order Relation **A [[relation]] that relates elements such that for particular pairs of elements, one precedes the other.** > [!Example] Partial Order Relation > A *partial order relation*, or a *reflexive*, *weak*, or *non-strict partial order* is a binary relation that is [[Reflexive Relation|reflexive]], [[Antisymmetric Relation|antisymmetric]], and [[Transitive Relation|transitive]]. > > That is, some binary relation $R$ on a [[set]] $X$ is a partial order relation if > $\begin{gather} > \forall x\in X:xRx \\ > \forall x,y\in X:(xRy\wedge yRx)\implies x=y \\ > \forall x,y,z\in X:(xRy\wedge yRz)\implies xRz > \end{gather}$ > ^d31142 > [!Example] Strict Partial Order Relation > A *strict partial order relation*, or a *irreflexive*, *strong*, or *strict partial order* is a binary relation that is [[Reflexive Relation#^4dc1ca|irreflexive]], [[Symmetric Relation#^bd8e50|asymmetric]], and [[Transitive Relation|transitive]]. > > That is, some binary relation $R$ on a [[set]] $X$ is a strict partial order relation if > $\begin{gather} > \forall x\in X:\neg(xRx) \\ > \forall x,y\in X:xRy\implies \neg(yRx) \\ > \forall x,y,z\in X:(xRy\wedge yRz)\implies xRz > \end{gather}$ > > As a transitive relation is asymmetric if and only if it is irreflexive, it is possible to define a strict partial order relation while *omitting either but not both* of the requirements of asymmetry and irreflexivity. A partial order relation between two elements $x$ and $y$ is typically denoted as either $x\le y$, $x\preceq y$, or $x\sqsubseteq y$. The two elements are called *comparable* and it is said that $x$ *precedes* $y$. Some sources use $x\preceq y$ or $x\sqsubseteq y$ to denote a [[Total Order Relation|total order]] and distinguish them from partial orders. Additionally, $x<y$, $x\prec y$, or $x\sqsubset y$ are used to denote that $x$ precedes $y$ and they are not equal. As such, they are commonly used to denote strict partial orders. If $x\prec y$ and if there is no third element $z$ such that $x\prec z\prec y$, then $y$ *covers* $x$. If a relation $\preceq$ is a partial order relation of a set $X$, then $X$ is referred to as a *partially ordered set* or a *poset*. This poset may be expressed as $(X,R)$ for some partial order $R$. ## Visualisation A partially ordered set is often depicted by a *Hasse diagram*. In a Hasse diagram, elements are depicted as vertices on a plane and edges are drawn from one element to another if one covers the other. An *arrow* may be used instead pointing from the former to the latter. Hasse diagrams are drawn such that if $x\preceq y$, then $x$ is drawn on a lower level than $y$. Consider the divisor relation $x\mid y$ on the set $S = \{1, 2, 3, 4, 6, 8, 9, 12, 18\}$: - an edge would be drawn from $6$ to $12$ since $6\mid 12$ and no other element in the set is divisible by $6$ yet is also a divisor of $12$. - on the contrary, an edge would *not* be drawn from $3$ to $12$ since although $3\mid 12$, it is also true that $3\mid 6$ and $6\mid 12$. ![[RelationHasseDiagram.svg|500]] > [!Example] Minimal and Maximal Element > A *minimal element* of a partially ordered set $(X,\preceq)$ is an element $x\in X$ such that there are no elements $y\in X$ where $y\preceq x$ > > On a Hasse diagram, a minimal element is an element with no edges connected to it from below. For example, $1$ is the only minimal element of the above partially ordered set. >*** > A *maximal element* of a partially ordered set $(X,\preceq)$ is an element $x\in X$ such that there are no elements $y\in X$ where $x\preceq y$. > > On a Hasse diagram, a maximal element is an element with no edges connected to it from above. For example, $8$, $9$, $12$, and $18$ are all maximal elements of the above partially ordered set. > [!Example] Least and Greatest Element > A *least element*, if it exists, of a partially ordered set $(X, \preceq)$ is an element $x\in X$ such that for all elements $y\in X$, $x\preceq y$. > > On a Hasse diagram, a least element is an element which can reach all other elements by a strictly upwards path. > *** > A *greatest element*, if it exists, of a partially ordered set $(X, \preceq)$ is an element $x\in X$ such that for all elements $y\in X$, $y\preceq x$. > > On a Hasse diagram, a greatest element is an element which can reach all other elements by a strictly downwards path. > > ![[PartialOrderRelationLeastGreatestElementHasse.svg|450]] > > In the above Hasse diagram of the partial order $\in$ on the [[power set]] of $\{x,y,z\}$, the *greatest element* is $\{x,y,z\}$ and the *least element* is the [[Set#^5f880b|empty set]] $\varnothing$.