Partial ordering

Note to reader: this page defines $\sqsubseteq$ as the partial ordering under study, this is to try and make the concept distinct from $\le$, which the reader should have been familiar with from a young age (and thus can taint initial study)

Definition

Given a relation, $\sqsubseteq$ in $X$ (mathematically: $\sqsubseteq\subseteq X\times X$) we say $\sqsubseteq$ is a partial order if:

• The relation $\sqsubseteq$ is all 3 of the following:

	Name	Definition
1	Reflexive	$\forall x\in X[(x,x)\in\sqsubseteq]$ or equivalently $\forall x\in X[x\sqsubseteq x]$
2	Identitive (AKA: antisymmetric)	$\forall x,y\in X[((x,y)\in\sqsubseteq\wedge(y,x)\in\sqsubseteq)\implies (x=y)]$ or equivalently $\forall x,y\in X[(x\sqsubseteq y\wedge y\sqsubseteq x)\implies(x=y)]$
3	Transitive	$\forall x,y,z\in X[((x,y)\in\sqsubseteq\wedge(y,z)\in\sqsubseteq)\implies(x,z)\in\sqsubseteq]$ or equivalently $\forall x,y,z\in X[(x\sqsubseteq y\wedge y\sqsubseteq z)\implies(x\sqsubseteq z)]$

• Note: $\le$, $\preceq$ or $\subseteq$ are all commonly used for partial relations too.
  • The corresponding strict partial orderings are $<$, $\prec$ and $\subset$

Alternative definition

Alternatively, a partial order is simply a preorder that is also anti-symmetric (AKA Identitive), that is to say:

• Given a preorder in $X$, so a $\preceq$ such that $\preceq\subseteq X\times X$, then $\preceq$ is also a partial order if:
• $\forall x,y\in X[((x,y)\in\preceq\wedge(y,x)\in\preceq)\implies (x=y)]$ or equivalently
  • $\forall x,y\in X[(x\preceq y\wedge y\preceq x)\implies(x=y)]$

Induced strict partial ordering

Here, let $\preceq$ be a partial ordering as defined above, then the relation, $\prec$ defined by:

• $(x,y)\in\prec\iff[x\ne y\wedge x\preceq y]$

is a strict partial ordering

• Note: every strict partial ordering induces a partial ordering, given a strict partial ordering, $<$, we can define a relation $\le$ as:
  • $x\le y\iff[x=y\vee x<y]$ or equivalently (in relational form): $(x,y)\in\le\iff[x=y\vee (x,y)\in<]$

In fact there is a 1:1 correspondence between partial and strict partial orderings, this is why the term "partial ordering" is used so casually, as given a strict you have a partial, given a partial you have a strict.

• See Overview of partial orders for more information

See also

• Preorder - like a partial order except it need not be anti-symmetric (AKA identitive)
• Strict partial order - which induces and is induced by the same partial order, thus an equivalent statement to a partial order