Partial Orderings

Partial Orderings

A partial order is a binary relation on a set that allows you to compare elements in a specific way. Unlike a total order, where any two elements must be comparable, a partial order only requires that some elements can be compared, while others may not be. Partial orderings are used in various branches of mathematics and computer science, such as in ordering tasks in scheduling or arranging sets of objects in terms of some hierarchical structure.

1. Definition of a Partial Order

A partial order on a set $A$ is a relation $\leq$ on $A$ that satisfies the following three properties:

1. Reflexivity: Every element is related to itself.

   $$\forall a \in A, \, a \leq a.$$

   This means that for every element $a \in A$, $a$ is always less than or equal to itself.

2. Antisymmetry: If $a \leq b$ and $b \leq a$, then $a = b$.

   $$\forall a, b \in A, \, \text{if} \, a \leq b \text{ and } b \leq a, \text{ then } a = b.$$

   This means that if $a$ is less than or equal to $b$ and $b$ is less than or equal to $a$, then $a$ and $b$ must be the same element.

3. Transitivity: If $a \leq b$ and $b \leq c$, then $a \leq c$.

   $$\forall a, b, c \in A, \, \text{if} \, a \leq b \text{ and } b \leq c, \text{ then } a \leq c.$$

   This means that if $a$ is less than or equal to $b$, and $b$ is less than or equal to $c$, then $a$ is less than or equal to $c$.

A partial order allows some elements of the set to be compared, but not all of them may be comparable. If two elements cannot be compared, they are said to be incomparable.

Example of Partial Order:

Consider the set $A = \{1, 2, 3, 4\}$ and the relation $\leq$ on this set. This relation is reflexive, antisymmetric, and transitive, so it is a partial order. The set $A$ with the usual less than or equal relation is an example of a partial order.

2. Hasse Diagrams

A Hasse diagram is a graphical representation of a partially ordered set (poset). In a Hasse diagram, elements are represented by vertices, and edges indicate the ordering between them. The diagram is drawn in such a way that:

• If $a \leq b$ and there is no element $c$ such that $a \leq c \leq b$, then there is an edge from $a$ to $b$.
• The diagram is drawn so that lower elements are placed below higher elements.

Example:

Let’s consider the set $A = \{1, 2, 3, 4\}$ and the relation $\leq$, where the set is ordered as follows:

The Hasse diagram for this partial order would look like this:

       4
     / | \
    2  3  1

In this diagram:

• 1 is less than 2, 3, and 4.
• 2 and 3 are less than 4, but not comparable with each other.
• 4 is the greatest element in the set.

3. Types of Partial Orders

There are several types of partial orders based on the level of comparability between elements. Two important types are total orders and strict partial orders.

Total Order (Linear Order)

A total order is a special type of partial order where every pair of elements is comparable. That is, for any two elements $a$ and $b$ in a set $A$, either $a \leq b$ or $b \leq a$.

For example, the usual "less than or equal to" ($\leq$) relation on the integers $\mathbb{Z}$ is a total order because for any two integers, one will always be less than or equal to the other.

Strict Partial Order

A strict partial order is a binary relation $<$ that satisfies:

1. Irreflexivity: $a \not< a$ for all $a \in A$.
2. Transitivity: If $a < b$ and $b < c$, then $a < c$.

For example, the usual "less than" ($<$) relation on integers $\mathbb{Z}$ is a strict partial order.

4. Example of Partial Order

Let’s consider a set of divisors of 12: $A = \{1, 2, 3, 4, 6, 12\}$, and define the relation $\leq$ by $a \leq b$ if $a$ divides $b$.

We can verify that this relation is a partial order because:

• Reflexivity: Every number divides itself.
• Antisymmetry: If $a$ divides $b$ and $b$ divides $a$, then $a = b$.
• Transitivity: If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$.

The Hasse diagram for this partial order looks like this:

      12
     /  \
    6    3
   / \   / 
  2   4 1

Here:

• 1 divides everything.
• 2 divides 4 and 6.
• 3 divides 6 and 12.
• 4 divides 12.
• 6 divides 12.
• 12 is the largest element, divisible by all others.

5. Important Concepts Related to Partial Orders

• Greatest Element: An element $g \in A$ is the greatest element of the partially ordered set if $g \geq a$ for all $a \in A$.
• Least Element: An element $l \in A$ is the least element of the partially ordered set if $l \leq a$ for all $a \in A$.
• Upper Bound: An element $u \in A$ is an upper bound of a subset $B \subseteq A$ if for all $b \in B$, $b \leq u$.
• Lower Bound: An element $l \in A$ is a lower bound of a subset $B \subseteq A$ if for all $b \in B$, $l \leq b$.
• Maximal Element: An element $m \in A$ is maximal if there is no element $a \in A$ such that $m < a$.
• Minimal Element: An element $m \in A$ is minimal if there is no element $a \in A$ such that $a < m$.

6. Summary

• A partial order is a relation that satisfies reflexivity, antisymmetry, and transitivity, allowing for partial comparisons between elements.
• A total order is a special type of partial order where every pair of elements is comparable.
• Hasse diagrams provide a visual representation of partial orders by displaying elements as vertices and the ordering relationship as edges.
• Partitions and lattices are examples of structures built upon partially ordered sets.

Partial orders are a fundamental concept in mathematics and computer science, with applications in organizing elements, scheduling tasks, data classification, and many other areas.