Partial Order Relations

Definition

A relation is a partial order relation (or partial order) iff it is reflexive, antisymmetric and transitive. $\preccurlyeq$ is used to denote a partial order relation (it replaces $R$ in $aRb$, so $a\preccurlyeq b$), read ”$a$ is curly less than or equal to $y$“

Partially Ordered Set

A set $A$ is a partially ordered set or poset with respect to a partial order relation $R$ on $A$, denoted by $(A,R)$ A set with a partial order relation defined on it can be represented $(A,R)$ and be called a poset

Hasse Diagram

Partial order relations can be represented as hasse diagrams

1. Start with a directed graph
2. Remove loops on nodes (because reflexive)
3. Arrange nodes such that all arrows are pointing up, then remove arrow heads (because antisymmetric)
4. Remove arrows that are implied by transitivity
   • If there is an arrow from $a$ to $b$ and $b$ to $c$, remove the arrow from $a$ to $c$
   • Keep repeating to remove as many arrows as possible

Example

For the “divides” relation on set $A=\{1,2,3,9,18\}$

Partial Order Relations 2024-10-05 06.21.24.excalidraw

⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’

Excalidraw Data

Text Elements

Directed Graph

Hasse Diagram

Embedded Files

200bb00677aa83342ccef1087c52e673c454aa82: image.png

acb4d4eb3d78d42155a9149398dea983c5eba8d5: image_0.png

Link to original

Formal Definition

Let $\preccurlyeq$ be a partial order on a set $A$. A Hasse diagram of $\preccurlyeq$ satisfies the following condition for all distinct $x,y,m\in A$: If $x\preccurlyeq y$ and no $m\in A$ is such that $x\preccurlyeq m\preccurlyeq y$, then $x$ is placed below $y$ with a line joining them, else no line joins $x$ and $y$

Analogy

Putting on socks and shoes (ignore reflexivity)

• left sock must go on before left shoe, same for right
• but whether the left or right sock goes on first does not matter
• whether the left shoe goes on before the right sock does not matter
• left sock $\preccurlyeq$ left shoe
• right sock $\preccurlyeq$ right shoe
• the order is “partial” because there may not be an order between certain elements
• left sock and right sock are not comparable

Common Examples

• The “divides” relation, $|$, on a set of positive integers
• $\le$ on a set of real numbers
• $\subseteq$ on a set of sets

Properties of Poset Elements

Suppose $\preccurlyeq$ is a partial order relation on a set $A$ For example, the hasse diagram of $|$ on $A=\{1,2,\dots ,10\}$

Comparability

Elements $a$ and $b$ of $A$ are said to be comparable iff either $a\preccurlyeq b$ or $b\preccurlyeq a$. Otherwise, $a$ and $b$ are noncomparable Hasse diagram: Comparable means having a path between the elements that only goes up In the example $2$ and $8$ are comparable, but $5$ and $9$ are not

Compatibility

Elements $a$ and $b$ of $A$ are said to be compatible iff there exists $c\in A$ such that $a\preccurlyeq c$ and $b\preccurlyeq c$
Hasse diagram: The elements have have a path upwards to the same elements
In the example, $1$ and $8$ , $2$ and $3$ are compatible but $3$ and $5$ are not

Maximal Element

Element $c$ of $A$ is a maximal element of $A$ iff $\forall x\in A$, either $x\preccurlyeq c$ or $x$ and $c$ are noncomparable $\forall x\in A(c\preccurlyeq x\Rightarrow c=x)$ Hasse diagram: There are no lines upward from the element In the example $6,7,8,9,10$ are the maximal elements

Minimal Element

Element $c$ of $A$ is a minimal element of $A$ iff $\forall x\in A$, either $c\preccurlyeq x$ or $x$ and $c$ are noncomparable $\forall x\in A(x\preccurlyeq c\Rightarrow c=x)$ Hasse diagram: There are no lines downward from the element In the example $1$ is the maximal elements

Largest Element

Element $c$ of $A$ is the largest element of $A$ iff $\forall x\in A(x\preccurlyeq c)$ A largest element is always also maximal Note: largest element = greatest element = maximum Hasse diagram: There is a path downwards to all other elements In the example there is no largest element

Smallest Element

Element $c$ of $A$ is the smallest element of $A$ iff $\forall x\in A(c\preccurlyeq x)$ A smallest element is always also minimal Note: smallest element = least element = minimum Hasse diagram: There is a path upwards to all other elements In the example $1$ is the smallest element

Linearisation

Creating a Total Order Relations from a partial order, without violating the partial order relation Let $\preccurlyeq$ be a partial order on a set $A$. A linearisation of $\preccurlyeq$ is a total order ${\preccurlyeq }^{\ast }$ on $A$ such that $\forall x,y\in A(x\preccurlyeq y\Rightarrow x{\preccurlyeq }^{\ast }y)$

Example

For the “divides” relation on $\{1,2,3,9,18\}$ Linearisations will include:

• $1{\preccurlyeq }^{\ast }2{\preccurlyeq }^{\ast }3{\preccurlyeq }^{\ast }9{\preccurlyeq }^{\ast }18$
• $1{\preccurlyeq }^{\ast }3{\preccurlyeq }^{\ast }2{\preccurlyeq }^{\ast }9{\preccurlyeq }^{\ast }18$
• etc.

Kahn’s Algorithm

An algorithm that takes a finite set $A$ and a partial order $\preccurlyeq$ on $A$, and outputs a linearisation ${\preccurlyeq }^{\ast }$ of $\preccurlyeq$ Informally:

1. Find the a minimal element of $A$
2. Remove the element from $A$
3. Repeat until $A=\varnothing$
4. The linearisation is the elements that were removed, in the order of removal