What is a Partially Ordered Set and its Properties?

[Greg Bernhardt]

Definition/Summary

A partially ordered set, or in short, a poset, is a set A together with a relation \leq~\subseteq A\times A which is reflexive, antisymmetric, and transitive. In other words, satisfying
1)\forall x\in A,~x\leq x (the relation is reflexive)
2)\forall x,y\in A,~x\leq y~and~y\leq x\Rightarrow x=y (the relation is antisymmetric)
3)\forall x,y,z\in A,~x\leq y~and~y\leq z\Rightarrow x\leq z (the relation is transitive)

It is common to refer to a poset \left(A,\leq\right) simply as A, with the underlying relation being implicit.

Equations

Antisymmetry:

For example, a checker-board with the relation "not further from the white end" is not a poset because two different squares can be the same distance from the white end, and so the relation is not anti-symmetric.

But the same board with the relation "not further from the white end according to legal moves for an ordinary black piece" is a poset .

Totally ordered set:

A poset with the extra condition
4) \forall x,y\in A,~x\leq y~or~y\leq x
is a totally ordered set.

In other words, loosely speaking, a totally ordered set is essentially one-dimensional: it can be thought of as a line, in which any element is either one side or the other side of any other element.

Extended explanation



* This entry is from our old Library feature. If you know who wrote it, please let us know so we can attribute a writer. Thanks!

 

[fresh_42]

The extra condition is called trichotomy and a total ordering is sometimes also called linear, simple, or complete. If non empty subsets always have a smallest element, i.e. all other elements of the set are bigger, then the ordering is called well-ordered.