What is partially ordered

1. Jul 23, 2014

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!