Partial Ordering Relations

---

Partial Ordering Relations

---

1. Definition of a Partial Order

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

1. Reflexive: For all $a \in A$, $a \leq a$.
2. Antisymmetric: For all $a, b \in A$, if $a \leq b$ and $b \leq a$, then $a = b$.
3. Transitive: For all $a, b, c \in A$, if $a \leq b$ and $b \leq c$, then $a \leq c$.

A relation $\leq$ on a set $A$ is a partial order if it satisfies these three conditions.

---

2. Example of a Partial Order

Consider the set $A = \{1, 2, 3\}$ and the relation $\leq$ defined on $A$ by:

$$R = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$$

We check the three conditions for partial order:

• Reflexive: Every element is related to itself, i.e., $(1, 1), (2, 2), (3, 3) \in R$.
• Antisymmetric: If $(1, 2)$ and $(2, 1)$ were both in $R$, we would need $1 = 2$, but that is not the case. Thus, the relation is antisymmetric.
• Transitive: For example, if $(1, 2)$ and $(2, 3)$ are in $R$, then $(1, 3)$ must also be in $R$, which it is. This holds for all pairs.

Thus, $R$ is a partial order.

---

3. Total Order vs. Partial Order

A total order (also called linear order) is a special case of a partial order where every pair of elements is comparable. That is, for any two elements $a$ and $b$ in the set $A$, either $a \leq b$ or $b \leq a$ holds.

A partial order does not require that every pair of elements be comparable, meaning there may exist pairs $a$ and $b$ for which neither $a \leq b$ nor $b \leq a$ holds.

Example of a Total Order:

For the set $A = \{1, 2, 3\}$, the relation $\leq$ on $A$ defined by:

$$R = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$$

is also a total order because any two elements are comparable (for any $a, b \in A$, either $a \leq b$ or $b \leq a$).

Example of a Partial Order (Not a Total Order):

Consider the set $B = \{1, 2, 3\}$ and the relation $\leq$ defined by:

$$R = \{(1, 1), (2, 2), (3, 3), (1, 2)\}$$

This is a partial order because:

• It is reflexive, antisymmetric, and transitive.
• However, it is not a total order because $2$ and $3$ are not comparable under this relation (neither $2 \leq 3$ nor $3 \leq 2$ holds).

---

4. Hasse Diagram for Partial Order

A Hasse diagram is a graphical representation of a partial order relation. It simplifies the relation by omitting redundant edges (edges that can be inferred via transitivity). In a Hasse diagram:

• The elements of the set are represented as vertices.
• An edge from vertex $a$ to vertex $b$ indicates $a \leq b$, and this edge is drawn only if no other element $c$ exists such that $a \leq c \leq b$.

Example:

For the set $A = \{1, 2, 3\}$ with the relation $\leq$ (partial order), the Hasse diagram looks like:

   3
   |
   2
   |
   1

This diagram reflects the order $1 \leq 2 \leq 3$.

---

5. The Greatest and Least Elements

In a partially ordered set:

• The least element (also called the minimum element) is an element $m$ such that for all $x$ in the set, $m \leq x$.
• The greatest element (also called the maximum element) is an element $M$ such that for all $x$ in the set, $x \leq M$.

For the set $A = \{1, 2, 3\}$ with the relation $\leq$, the least element is 1, and the greatest element is 3.

---

6. Upper and Lower Bounds

In a partially ordered set:

• An element $u$ is an upper bound of a subset $S \subseteq A$ if for all $x \in S$, $x \leq u$.
• An element $l$ is a lower bound of a subset $S \subseteq A$ if for all $x \in S$, $l \leq x$.

For example, in the set $A = \{1, 2, 3\}$, if $S = \{1, 2\}$, then:

• The upper bound of $S$ is 3, because $2 \leq 3$.
• The lower bound of $S$ is 1, because $1 \leq 1$ and $1 \leq 2$.

---

7. Antisymmetry and the Partial Order Property

The antisymmetric property is crucial for distinguishing partial orders from other relations. This property ensures that:

• If two elements are related in both directions, they must be equal.
• This prevents any "cyclic" or "non-strict" order in the set, which would break the concept of a partial order.

---

Summary of Properties for Partial Order:

• Reflexive: Every element is comparable to itself.
• Antisymmetric: If $a \leq b$ and $b \leq a$, then $a = b$.
• Transitive: If $a \leq b$ and $b \leq c$, then $a \leq c$.

---