Partial Orders

Partial Orders

A partial order is a binary relation that generalizes the concept of ordering elements, but unlike a total order, it does not necessarily compare all pairs of elements. A partial order is a relation that satisfies certain properties, which allow elements to be compared in a structured way, but there may still be pairs of elements that are not comparable.

Definition of Partial Order

A relation $R$ on a set $A$ is a partial order if it satisfies three key properties:

1. Reflexivity:

For every element $a \in A$, the pair $(a, a)$ must be in the relation $R$. In other words, every element is related to itself.

$$\forall a \in A, (a, a) \in R$$

2. Antisymmetry:

For all $a, b \in A$, if $(a, b) \in R$ and $(b, a) \in R$, then $a = b$. This means that if two elements are related in both directions, they must be the same element.

$$\forall a, b \in A, \text{ if } (a, b) \in R \text{ and } (b, a) \in R, \text{ then } a = b$$

3. Transitivity:

For all $a, b, c \in A$, if $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$. This property means that if $a$ is related to $b$, and $b$ is related to $c$, then $a$ is also related to $c$.

$$\forall a, b, c \in A, \text{ if } (a, b) \in R \text{ and } (b, c) \in R, \text{ then } (a, c) \in R$$

---

Example of Partial Order: Set Inclusion

Consider the set $A = \{\{1\}, \{2\}, \{1, 2\}, \emptyset\}$ and define the relation $R$ on $A$ by set inclusion (i.e., $A \subseteq B$ means $A$ is a subset of $B$).

• Reflexive: Every set is a subset of itself.
• Antisymmetric: If $A \subseteq B$ and $B \subseteq A$, then $A = B$.
• Transitive: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Thus, the subset relation is a partial order.

The Hasse Diagram:

A Hasse diagram is a way to visually represent a partial order, where each element is represented as a point, and the order is represented by edges connecting points. In this case, the Hasse diagram of the set inclusion relation would look like this:

       {1, 2}
      /     \
   {1}       {2}
      \     /
      ∅

• The set $\emptyset$ is related to all other sets.
• The set $\{1, 2\}$ is related to both $\{1\}$ and $\{2\}$, but there is no direct relation between $\{1\}$ and $\{2\}$.

---

Comparison with Total Orders

A total order is a special case of partial order in which every pair of elements is comparable. In other words, for any two elements $a$ and $b$ in the set $A$, either $(a, b) \in R$ or $(b, a) \in R$ must hold.

For example, the less than or equal to relation $\leq$ on the set of real numbers $\mathbb{R}$ is a total order because for any two real numbers $x$ and $y$, one of $x \leq y$ or $y \leq x$ must hold. A partial order, on the other hand, does not require that every pair of elements be comparable.

---

Partially Ordered Set (Poset)

A partially ordered set, or poset, is a set $A$ equipped with a partial order relation $R$. A poset is typically denoted as $(A, R)$.

Example: Poset of Divisibility

Consider the set of positive integers $A = \{1, 2, 3, 4, 6, 12\}$ with the divisibility relation $|$, where $a | b$ means that $a$ divides $b$.

This is a partial order because:

• Reflexive: Every number divides itself.
• Antisymmetric: If $a$ divides $b$ and $b$ divides $a$, then $a = b$.
• Transitive: If $a$ divides $b$ and $b$ divides $c$, then $a$ divides $c$.

The Hasse diagram of the divisibility relation is:

        12
       /  \
     6     4
    / \   /
   2   3 1

Here, 1 divides everything, 2 divides 4 and 6, 3 divides 6, and 6 divides 12.

---

Upper and Lower Bounds

In a poset, we often talk about upper bounds and lower bounds of subsets of elements.

• Upper Bound: An element $u$ in $A$ is an upper bound of a subset $S \subseteq A$ if for every element $s \in S$, $s \leq u$.
• Lower Bound: An element $l$ in $A$ is a lower bound of a subset $S \subseteq A$ if for every element $s \in S$, $l \leq s$.

Additionally:

• Greatest Element (Supremum): The greatest element of a set $S$ in a poset is an element $g$ such that $g$ is an upper bound of $S$, and there is no other element greater than $g$.
• Least Element (Infimum): The least element of a set $S$ in a poset is an element $l$ such that $l$ is a lower bound of $S$, and there is no other element smaller than $l$.

---

Example: Partially Ordered Set of Subsets

Consider the set $A = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$ with the subset relation (i.e., $\subseteq$). This is a poset, and we can find bounds:

• The least element is $\emptyset$, because it is a subset of all other sets.
• The greatest element is $\{1, 2\}$, because it contains all the other sets.

---

Summary of Properties of Partial Orders

Property	Definition
Reflexive	For every $a \in A$, $(a, a) \in R$
Antisymmetric	If $(a, b) \in R$ and $(b, a) \in R$, then $a = b$
Transitive	If $(a, b) \in R$ and $(b, c) \in R$, then $(a, c) \in R$

Conclusion

A partial order is a relation that helps us compare elements of a set in a structured way, allowing some elements to be comparable while leaving others unrelated. The three key properties—reflexivity, antisymmetry, and transitivity—form the foundation of this ordering. A partially ordered set (poset) is a set equipped with a partial order, and it has many applications in mathematics, computer science, and other fields where hierarchical or partial relationships exist.