Partial Order

Overview

A binary relation $R$ on set $A$ is a non-strict partial order on $A$ iff it is reflexive on $A$, antisymmetric, and transitive. In other words, a non-strict partial order is an antisymmetric preorder.

If $R$ is instead irreflexive on $A$, it is a strict partial order.

Hasse Diagrams

Let $⟨P,\le ⟩$ be a poset. For distinct $a,b\in P$, we say $b$ covers $a$ if $a\le b$ and there does not exist any distinct third element $x$ such that $a\le x\le b$.

A Hasse diagram is a directed graph that encodes a finite poset $⟨P,\le ⟩$. It consists of a vertex for each element of $P$, with a directed edge (usually oriented upwards) from $a\in P$ to $b\in P$ whenever $b$ covers $a$.