Overview of partial orders

Note: this page contains material intended to help the study of partial orderings and solve some common misconceptions, it is advised that someone trying to learn about (rather than reference or check something) about partial orders read this.

Definition

A partial order is a relation on a set [ilmath]X[/ilmath], which we shall call [ilmath]\mathcal{R}\subseteq X\times X[/ilmath] that is:

	Name	Definition
1	Reflexive	[ilmath]\forall x\in X[(x,x)\in\mathcal{R}][/ilmath] or equivalently [ilmath]\forall x\in X[x\mathcal{R} x][/ilmath]
2	Identitive (AKA: antisymmetric)	[ilmath]\forall x,y\in X[((x,y)\in\mathcal{R}\wedge(y,x)\in\mathcal{R})\implies (x=y)][/ilmath] or equivalently [ilmath]\forall x,y\in X[(x\mathcal{R} y\wedge y\mathcal{R} x)\implies(x=y)][/ilmath]
3	Transitive	[ilmath]\forall x,y,z\in X[((x,y)\in\mathcal{R}\wedge(y,z)\in\mathcal{R})\implies(x,z)\in\mathcal{R}][/ilmath] or equivalently [ilmath]\forall x,y,z\in X[(x\mathcal{R} y\wedge y\mathcal{R} z)\implies(x\mathcal{R} z)][/ilmath]

• Note that: there is no requirement for [ilmath](x,y)\in\mathcal{R}\iff x\mathcal{R}y[/ilmath] (if [ilmath]x\ne y[/ilmath]) this is probably why it is called a partial ordering (rather than a total ordering which is a partial ordering where all elements are comparable)
• For example:
  1. The divisor relation is a partial ordering (see Divisor partial ordering) and this is clearly not a total ordering
  2. The subset relation is a partial ordering and is clearly not a total ordering

---

TODO: References

---

Various views

Let us now write [ilmath]\mathcal{R} [/ilmath] as [ilmath]\preceq[/ilmath] and rather than [ilmath]x\mathcal{R}y[/ilmath] or [ilmath](x,y)\in\mathcal{R[/ilmath]} write [ilmath]x\preceq y[/ilmath] accordingly.

There are 2 things we must cover:

1. What does [ilmath]\succeq[/ilmath] mean?
2. What does [ilmath]\prec[/ilmath] (and [ilmath]\succ[/ilmath]) mean?

Dealing with [ilmath]x\preceq y\iff y\succeq x[/ilmath]

There are 2 views about what [ilmath]x\prec y[/ilmath] means. We'll do the strongest (most formal) first

Dual relation

Consider the relation [ilmath]\mathcal{R}^{-1} [/ilmath]

Defining [ilmath]x\preceq y\iff y\succeq x[/ilmath]

This is a bit of a cop-out but we can simply say that [ilmath]y\succeq x[/ilmath] is another way of writing [ilmath]x\preceq y[/ilmath]

Dealing with [ilmath]\prec[/ilmath] and [ilmath]\succ[/ilmath]

Define the relation: [ilmath]x \prec y\iff x\preceq y \wedge x\ne y[/ilmath]

---

TODO: Finish off page, find references

---