# Partially Ordered Set

Suppose you have a collection of objects. For two of them it might be obvious that, in some sense A is bigger than B, but others might be harder to compare.

Cake tins, for example. If A can hold B, then A is clearly bigger than B. However, it may be that C can't hold D, and D can't hold C. Using the concept of "can contain", the ordering between these tins is incomplete. It is a partial ordering.

With this example in mind we have the following definition of a Partially-Ordered Set:

## Irreflexive version

A set X is partially ordered by R if:
• For elements x of X, we do not have xRx (R is irreflexive)
• We cannot have both xRy and yRx (R is anti-symmetric)
• xRy and yRz implies xRz (R is transitive)
This is intuitively like "strictly less than" - $<$

## Reflexive version

A set X is partially ordered by R if:
• For elements x of X, we do have xRx (R is reflexive)
• If xRy and yRx then x=y (R is anti-symmetric)
• xRy and yRz implies xRz (R is transitive)
This is intuitively like "less than or equal to" - $\le$