Partial order

A partial order on a set $P$ is a relation $\le\,\subseteq P\times P$ such that for all $a,b,c\in P$:

• (Reflexive) $a\le a$.
• (Antisymmetric) If $a\le b$ and $b\le a$, then $a=b$.
• (Transitive) If $a\le b$ and $b\le c$, then $a\le c$.

The pair $(P,\le)$ is called a partially ordered set (poset). Here $P\times P$ is the Cartesian product of $P$ with itself.

A partial order does not require that every pair of elements be comparable; when comparability holds for all pairs, one has a total order . Many notions in order theory, such as upper bounds and lower bounds , are defined relative to a partial order.

Examples:

• On the power set $\mathcal P(X)$ of a set $X$, define $A\le B$ iff $A\subseteq B$ (the subset relation).
• On $\mathbb{N}$ (the natural numbers ), define $a\preceq b$ iff $a\mid b$ (divisibility). This is a partial order but not a total order.