Partial Ordering

Partial Orderings

A relation ≤ is said to be a partial ordering if the following three statements hold:

  • For all tex:$$ a $$, tex:$$ a \leq a $$ ,
  • If tex:$$ a \leq b $$ and tex:$$ b \leq a $$, tex:$$ a = b $$, and
  • If tex:$$ a \leq b $$ and tex:$$ b \leq c $$, it follows that tex:$$ a \leq c $$.

A finite collection of objects which are related with a partial ordering are said to form a directed acyclic graph. Such a finite collection may be drawn visually using a Hasse diagram.

A partial order where any two items are comparable (that is, given tex:$$ a $$ and tex:$$ b $$, either tex:$$ a \le b $$, tex:$$ a = b $$, or tex:$$ b \le a $$), this forms a linear ordering.

A partial ordering with other restrictions forms a partial ordering.

A topological ordering of a finite number of partially ordered objects is a linear ordering of the elements tex:$$ x_1, x_2, x_3, \ldots, x_n $$ such that if tex:$$ x_j \leq x_k $$ then tex:$$ j \leq k $$. A topological ordering is unique if and only if the objects are linearly ordered.

Strict Partial Ordering

A relation < is said to be a strict partial ordering if the following statements hold:

  • For all tex:$$ a $$, tex:$$ a \not\le a $$ ,
  • At most one of tex:$$ a \le b $$ or tex:$$ b \le a $$ is true,
  • If tex:$$ a \le b $$ and tex:$$ b \le c $$, it follows that tex:$$ a \le c $$,
  • There is an object tex:$$ r $$ such that tex:$$ r \le a $$ for all other objects tex:$$ a $$, and
    • If tex:$$ a \le c $$ and tex:$$ b \le c $$, either tex:$$ a = b $$ , tex:$$ a \le b $$, or tex:$$ b \le a $$.

Local Definitions

Most partial orderings are defined locally with definitions of form tex:$$ a $$ immediately precedes tex:$$ b $$.

Examples

  • The Unix directory structure with dir_a immediately preceding dir_b if dir_b is a directory within dir_a; the root of the tree is the root directory designated /.
  • Java inheritance defines a partial ordering with Class_A immediately preceding Class_B if Class_B is a subclass of Class_A; the root of the tree is the class Type.
  • Most partial organizations in society describe a partial ordering where tex:$$ a \leq b $$ if tex:$$ b $$ is a subordinate of tex:$$ b $$.
  • Given all members of the species Homo sapian, the local definition that Ann immediately precedes Bob/Barb if Ann is the mother of Bob or Barb defines a partial ordering. The root is the most recent common ancestor of all Homo sapians (see common descent).
  • Given a person tex:$$ r $$ and his or her ancestors (but not too far back), then define tex:$$ a \le b $$ if tex:$$ a $$ is a descendant of tex:$$ b $$.

References