Partially Ordered Set

AllPages
RecentChanges
Links to this page
Edit this page
Search
Entry portal
Advice For New Users

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$


Links to this page / Page history / Last change to this page
Recent changes / Edit this page (with sufficient authority)
All pages / Search / Change password / Logout