Order Theory

Partially Ordered Set

A partially ordered set (poset) consists of a set together with a binary relation that indicates that, for certain pairs of elements in the set, one of the elements precedes the other.

These relations are called partial orders to reflect the fact that not every pair of elements of a poset need be related: for some pairs, it may be that neither element precedes the other in the poset.

Partial orders generalize the more familiar total orders, in which every pair is related.

A finite poset can be visualized through its Hasse diagram, which depicts the ordering relation between certain pairs of elements and allows one to reconstruct the whole partial order structure.

Partially Order Formal Definition

A partial order is a binary relation "≤" over a set P which is reflexive, antisymmetric, and transitive,
i.e., for all a, b, and c in P, we have that:

a ≤ a (reflexivity);
if a ≤ b and b ≤ a then a = b (antisymmetry);
if a ≤ b and b ≤ c then a ≤ c (transitivity).

Example

The set of subsets of a given set (its power set) ordered by inclusion.

Total Order Formal Definition

If X is totally ordered under ≤, then the following statements hold for all a, b and c in X:

a ≤ a (reflexivity);
If a ≤ b and b ≤ a then a = b (antisymmetry);
If a ≤ b and b ≤ c then a ≤ c (transitivity);
a ≤ b or b ≤ a (totality).

Contrast with a partial order, which has a weaker form of the third condition (it only requires reflexivity, not totality). A relation having the property of "totality" means that any pair of elements in the set of the relation are mutually comparable under the relation. Totality implies reflexivity, that is, a ≤ a. Thus a total order is also a partial order.