Partial Order and Hasse Diagram

1. Introduction to Relations

Before diving into partial orders, let's establish the foundational concept of relations and their properties.

Definition: Binary Relation

A binary relation $R$ on a set $A$ is a subset of $A \times A$ . We write $aRb$ (or $a \sim b$ ) to mean $(a,b) \in R$ .

Key Properties of Relations

Reflexivity: A relation $R$ on set $A$ is reflexive if for every element $a \in A$ , we have $aRa$ .

Example: " $=$ " on real numbers (every number equals itself)
Counter-example: " $<$ " on real numbers (no number is less than itself)

Antisymmetry: A relation $R$ on set $A$ is antisymmetric if for all $a, b \in A$ , if $aRb$ and $bRa$ , then $a = b$ .

Example: " $\leq$ " on real numbers (if $a \leq b$ and $b \leq a$ , then $a = b$ )
Counter-example: "loves" relation among people (mutual love doesn't imply identity)

Transitivity: A relation $R$ on set $A$ is transitive if for all $a, b, c \in A$ , if $aRb$ and $bRc$ , then $aRc$ .

Example: "ancestor of" relation (if $A$ is ancestor of $B$ and $B$ is ancestor of $C$ , then $A$ is ancestor of $C$ )
Counter-example: "is friend of" relation (friend of friend isn't necessarily a friend)

Symmetry: A relation $R$ on set $A$ is symmetric if for all $a, b \in A$ , if $aRb$ then $bRa$ .

Example: "is married to" relation
Counter-example: "is parent of" relation

2. Partial Orders: Definition and Properties

Definition: Partial Order (Poset)

A partial order (or partially ordered set, abbreviated as poset) is a set $P$ together with a binary relation $\preceq$ that satisfies three properties:

Reflexivity: For all $a \in P$ , $a \preceq a$
Antisymmetry: For all $a, b \in P$ , if $a \preceq b$ and $b \preceq a$ , then $a = b$
Transitivity: For all $a, b, c \in P$ , if $a \preceq b$ and $b \preceq c$ , then $a \preceq c$

We denote a partially ordered set as $(P, \preceq)$ or simply $P$ when the relation is clear from context.

Strict Partial Order

The strict partial order associated with $\preceq$ is the relation $\prec$ defined by: $a \prec b$ if and only if $a \preceq b$ and $a \neq b$

This relation is:

Irreflexive: No element is related to itself
Asymmetric: If $a \prec b$ , then not $b \prec a$
Transitive: If $a \prec b$ and $b \prec c$ , then $a \prec c$

Comparability

Two elements $a$ and $b$ in a poset are comparable if either $a \preceq b$ or $b \preceq a$ (or both, in which case $a = b$ ). Elements that are not comparable are called incomparable.

3. Examples of Partial Orders

Example 1: Divisibility on Natural Numbers

Let $N = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12\}$ and define $a \preceq b$ if $a$ divides $b$ .

Verification:

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

Relations:

$1 \preceq$ everything (1 divides all numbers)
$2 \preceq 4, 6, 8, 10, 12$
$3 \preceq 6, 9, 12$
$4 \preceq 8, 12$
$6 \preceq 12$

Incomparable pairs: $(2,3)$ , $(2,5)$ , $(3,4)$ , $(3,5)$ , $(4,5)$ , $(4,6)$ , $(4,9)$ , etc.

Example 2: Subset Relation on Power Set

Let $A = \{a, b, c\}$ and consider $\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}$ with the subset relation $\subseteq$ .

Structure:

$\emptyset \subseteq$ all sets
$\{a\} \subseteq \{a,b\}, \{a,c\}, \{a,b,c\}$
$\{b\} \subseteq \{a,b\}, \{b,c\}, \{a,b,c\}$
$\{c\} \subseteq \{a,c\}, \{b,c\}, \{a,b,c\}$
$\{a,b\}, \{a,c\}, \{b,c\} \subseteq \{a,b,c\}$

Incomparable pairs: $(\{a\}, \{b\})$ , $(\{a\}, \{c\})$ , $(\{b\}, \{c\})$ , $(\{a,b\}, \{a,c\})$ , $(\{a,b\}, \{b,c\})$ , $(\{a,c\}, \{b,c\})$

Example 3: Lexicographic Order on Strings

Consider the set of strings $\{a, aa, ab, b, ba, bb\}$ with lexicographic ordering (dictionary order).

Order: $a \preceq aa \preceq ab \preceq b \preceq ba \preceq bb$

This is actually a total order since every pair of elements is comparable.

Example 4: Information Order on Partial Functions

Let $X = \{1, 2, 3\}$ and $Y = \{a, b\}$ . Consider partial functions from $X$ to $Y$ , ordered by information content: $f \preceq g$ if $\text{dom}(f) \subseteq \text{dom}(g)$ and $f(x) = g(x)$ for all $x \in \text{dom}(f)$ .

Example functions:

$f_1$ : undefined everywhere
$f_2$ : $1 \mapsto a$
$f_3$ : $2 \mapsto b$
$f_4$ : $1 \mapsto a, 2 \mapsto b$
$f_5$ : $1 \mapsto a, 3 \mapsto a$

Relations: $f_1 \preceq$ everything, $f_2 \preceq f_4$ , $f_2 \preceq f_5$ , $f_3 \preceq f_4$ , but $f_2$ and $f_3$ are incomparable.

4. Special Elements in Partial Orders

Minimal and Maximal Elements

An element $a$ is minimal if there is no element $b$ such that $b \prec a$
An element $a$ is maximal if there is no element $b$ such that $a \prec b$

Note: A poset may have multiple minimal/maximal elements, or none at all.

Least and Greatest Elements

An element $a$ is the least element (or minimum) if $a \preceq b$ for all $b$ in the poset
An element $a$ is the greatest element (or maximum) if $b \preceq a$ for all $b$ in the poset

Note: If they exist, least and greatest elements are unique.

Lower and Upper Bounds

For a subset $S$ of a poset $P$ :

An element $a \in P$ is a lower bound of $S$ if $a \preceq s$ for all $s \in S$
An element $a \in P$ is an upper bound of $S$ if $s \preceq a$ for all $s \in S$

Infimum and Supremum

For a subset $S$ of a poset $P$ :

The infimum (or greatest lower bound, glb) of $S$ is the greatest element among all lower bounds of $S$
The supremum (or least upper bound, lub) of $S$ is the least element among all upper bounds of $S$

Example: In the divisibility poset on $\{1,2,3,4,5,6,12\}$ :

$\inf(\{4,6\}) = 2$ (greatest common divisor)
$\sup(\{4,6\}) = 12$ (least common multiple)

5. Hasse Diagrams: Construction and Interpretation

Definition and Purpose

A Hasse diagram is a graphical representation of a finite partially ordered set that eliminates redundant information by showing only the "covering" relations.

Covering Relation

Element $a$ covers element $b$ (written $b \lessdot a$ ) if:

$b \prec a$ ( $b$ is strictly less than $a$ )
There is no element $c$ such that $b \prec c \prec a$

Construction Rules for Hasse Diagrams

Vertices: Each element of the poset is represented by a vertex
Edges: Draw an edge between $a$ and $b$ if one covers the other
Vertical arrangement: If $a \prec b$ , place $a$ below $b$
Transitivity elimination: Don't draw edges for relations that follow from transitivity
No self-loops: Reflexivity is implicit
Direction: Lower elements are "less than" higher elements

Step-by-Step Construction Example

Poset: Divisibility on $\{1, 2, 3, 4, 6, 12\}$

Step 1: List all relations

$1|1, 1|2, 1|3, 1|4, 1|6, 1|12$
$2|2, 2|4, 2|6, 2|12$
$3|3, 3|6, 3|12$
$4|4, 4|12$
$6|6, 6|12$
$12|12$

Step 2: Identify covering relations

$1 \lessdot 2$ ( $1 < 2$ , no element between)
$1 \lessdot 3$ ( $1 < 3$ , no element between)
$2 \lessdot 4$ ( $2 < 4$ , no element between)
$2 \lessdot 6$ ( $2 < 6$ , no element between)
$3 \lessdot 6$ ( $3 < 6$ , no element between)
$4 \lessdot 12$ ( $4 < 12$ , no element between)
$6 \lessdot 12$ ( $6 < 12$ , no element between)

Step 3: Draw the diagram

Divisibility poset diagram

Reading Hasse Diagrams

To determine if $a \preceq b$ : Check if there's an upward path from $a$ to $b$ .

Examples using the divisibility diagram above:

$1 \preceq 12$ ? Yes (path: $1 \to 2 \to 4 \to 12$ or $1 \to 3 \to 6 \to 12$ )
$2 \preceq 6$ ? Yes (direct path: $2 \to 6$ )
$4 \preceq 6$ ? No (no upward path from 4 to 6)

6. Advanced Examples and Applications

Example 1: Boolean Algebra B₃

Consider the Boolean algebra of subsets of a 3-element set $\{x, y, z\}$ .

Elements: All 8 subsets of $\{x, y, z\}$ Relation: Subset inclusion $\subseteq$

Boolean Algebra B₃ Hasse Diagram

Properties:

Least element: $\emptyset$
Greatest element: $\{x,y,z\}$
Every pair has a unique inf and sup
Complemented (every element has a complement)

Operations:

Join ( $\vee$ ): $\{x\} \vee \{y\} = \{x,y\}$
Meet ( $\wedge$ ): $\{x,y\} \wedge \{x,z\} = \{x\}$
Complement: $\overline{\{x\}} = \{y,z\}$

Example 2: Non-Distributive Lattices

Diamond and Pentagon Lattices

The Diamond lattice $M_3$ and Pentagon lattice $N_5$ are fundamental examples of non-distributive lattices. These are the smallest lattices that fail the distributive property.

Diamond $M_3$ failure: $a \wedge (b \vee c) = a \wedge 1 = a$ $(a \wedge b) \vee (a \wedge c) = 0 \vee 0 = 0$ Since $a \neq 0$ , distributivity fails.

Pentagon $N_5$ failure: Similarly demonstrates non-distributivity and is also non-modular.

Example 3: Partition Lattice

Consider all partitions of the set $\{1, 2, 3, 4\}$ ordered by refinement.

Partitions:

$\{\{1,2,3,4\}\}$ (coarsest)
$\{\{1,2,3\}, \{4\}\}$ , $\{\{1,2,4\}, \{3\}\}$ , $\{\{1,3,4\}, \{2\}\}$ , $\{\{2,3,4\}, \{1\}\}$
$\{\{1,2\}, \{3,4\}\}$ , $\{\{1,3\}, \{2,4\}\}$ , $\{\{1,4\}, \{2,3\}\}$ , $\{\{1,2\}, \{3\}, \{4\}\}$ , $\{\{1,3\}, \{2\}, \{4\}\}$ , $\{\{1,4\}, \{2\}, \{3\}\}$ , $\{\{2,3\}, \{1\}, \{4\}\}$ , $\{\{2,4\}, \{1\}, \{3\}\}$ , $\{\{3,4\}, \{1\}, \{2\}\}$
$\{\{1\}, \{2\}, \{3\}, \{4\}\}$ (finest)

Refinement relation: $P_1 \preceq P_2$ if every block of $P_1$ is contained in some block of $P_2$ .

Example 4: Young Diagrams

Young diagrams (used in representation theory) form a partial order under inclusion.

Example Young diagrams for partitions of 4:

Young diagrams for partitions of 4

Ordering: $\lambda \preceq \mu$ if the Young diagram of $\lambda$ fits inside the Young diagram of $\mu$ .

Example 5: Dominance Order on Permutations

Consider permutations of $\{1, 2, 3\}$ with the weak order.

Permutations: $123, 132, 213, 231, 312, 321$

Covering relations (via adjacent transpositions):

$123 \lessdot 132$ (swap positions 2,3)
$123 \lessdot 213$ (swap positions 1,2)
$132 \lessdot 312$ (swap positions 1,2)
$132 \lessdot 231$ (swap positions 1,3)
$213 \lessdot 231$ (swap positions 2,3)
$213 \lessdot 312$ (swap positions 1,3)
$231 \lessdot 321$ (swap positions 1,2)
$312 \lessdot 321$ (swap positions 2,3)

Permutation Weak Order on S₃

Inversion Table Interpretation: Each permutation can be characterized by its inversion count. The covering relations correspond to adding exactly one inversion via adjacent transposition.

Geometric Interpretation: This poset corresponds to regions in the braid arrangement, with maximal chains corresponding to reduced expressions in the symmetric group.

Example 6: Ideal Lattice in Ring Theory

In the ring $\mathbb{Z}_{12} = \mathbb{Z}/12\mathbb{Z}$ , consider the lattice of ideals ordered by inclusion.

Ideals: $(0), (1), (2), (3), (4), (6), (12)$ where $(n)$ represents the ideal generated by $n$ .

Relations:

$(12) \subseteq (6) \subseteq (3) \subseteq (1)$
$(12) \subseteq (6) \subseteq (2) \subseteq (1)$
$(12) \subseteq (4) \subseteq (2) \subseteq (1)$
$(0) \subseteq$ everything

Example 7: Formal Concept Analysis

Given a formal context $\mathcal{K} = (G, M, I)$ where $G$ is a set of objects, $M$ is a set of attributes, and $I \subseteq G \times M$ :

Example Context: | Objects | Attribute 1 | Attribute 2 | Attribute 3 | |---------|-------------|-------------|-------------| | Object A | ✓ | ✗ | ✓ | | Object B | ✓ | ✓ | ✗ | | Object C | ✗ | ✓ | ✓ |

Galois Connection: For $A \subseteq G$ and $B \subseteq M$ :

$A' = \{m \in M : \forall g \in A, (g,m) \in I\}$
$B' = \{g \in G : \forall m \in B, (g,m) \in I\}$

Formal Concepts: Pairs $(A, B)$ where $A' = B$ and $B' = A$

The set of all formal concepts forms a complete lattice called the concept lattice.

7. Comparing Partial Orders

Order Isomorphism

Two posets $(P, \preceq_P)$ and $(Q, \preceq_Q)$ are order isomorphic if there exists a bijection $f: P \to Q$ such that: $a \preceq_P b$ if and only if $f(a) \preceq_Q f(b)$

Order Embedding

A function $f: P \to Q$ between posets is an order embedding if: $a \preceq_P b$ if and only if $f(a) \preceq_Q f(b)$

Chain and Antichain

A chain is a totally ordered subset (all elements are comparable)
An antichain is a subset where no two distinct elements are comparable

Dilworth's Theorem: In any finite poset, the maximum size of an antichain equals the minimum number of chains needed to cover the poset.

Chains and Antichains Visualization

Width and Height

The width of a poset is the size of its largest antichain
The height of a poset is the size of its longest chain minus 1

8. Real-World Applications

Real-World Applications

Software Version Control

Git commits form a partial order where commit $A \preceq$ commit $B$ if $A$ is an ancestor of $B$ . Merge operations create elements with multiple immediate predecessors.

Example: Consider commits $c_1, c_2, c_3, c_4$ where:

$c_1$ is the initial commit
$c_2$ and $c_3$ branch from $c_1$
$c_4$ merges $c_2$ and $c_3$

This creates the poset: $c_1 \prec c_2, c_3 \prec c_4$

Task Dependencies in Project Management

In project management, tasks form a partial order where task $A \preceq$ task $B$ if $A$ must be completed before $B$ can begin. Critical path analysis finds maximal chains.

Example Project Tasks:

$T_1$ : Requirements gathering
$T_2$ : Database design
$T_3$ : UI design
$T_4$ : Backend implementation
$T_5$ : Frontend implementation
$T_6$ : Integration testing

Dependencies: $T_1 \prec T_2, T_3$ and $T_2 \prec T_4$ and $T_3 \prec T_5$ and $T_4, T_5 \prec T_6$

Information Systems and Query Specificity

In databases, queries can be ordered by specificity. A more specific query provides a subset of results from a less specific query.

Example SQL queries on employee database:

$Q_1$ : SELECT * FROM employees
$Q_2$ : SELECT * FROM employees WHERE department = 'Engineering'
$Q_3$ : SELECT * FROM employees WHERE department = 'Engineering' AND salary > 100000

Order: $Q_3 \prec Q_2 \prec Q_1$ (more specific queries return subsets)

Concurrency Theory and Causality

Events in concurrent systems form a partial order where $A \preceq B$ if event $A$ causally precedes event $B$ . Incomparable events represent potentially simultaneous occurrences.

Lamport's Happens-Before Relation: For events $e_1, e_2$ in a distributed system: $e_1 \to e_2$ if:

$e_1$ and $e_2$ are in the same process and $e_1$ occurs before $e_2$
$e_1$ is a send event and $e_2$ is the corresponding receive event
There exists $e_3$ such that $e_1 \to e_3$ and $e_3 \to e_2$ (transitivity)

Concept Hierarchies in Knowledge Representation

In ontologies and knowledge graphs, concepts form partial orders where $A \preceq B$ if concept $A$ is more specific than concept $B$ .

Example Taxonomy: $\text{Golden Retriever} \prec \text{Dog} \prec \text{Mammal} \prec \text{Animal} \prec \text{Living Thing}$

Multiple inheritance: $\text{Platypus} \prec \text{Mammal}, \text{Egg-laying Animal}$

Preference Modeling in Decision Theory

Consumer preferences often form partial orders where incomparable elements represent different trade-offs.

Example: Smartphone preferences based on (price, performance, battery life)

Phone A: ($800, high performance, average battery)
Phone B: ($600, average performance, excellent battery)
Phone C: ($400, low performance, poor battery)

Relations: $C \prec A$ and $C \prec B$ , but $A$ and $B$ are incomparable (different trade-offs)

Security Classification Lattices

Security classifications form lattices where information can flow from lower to higher classification levels.

Example Military Classification:

Levels: Unclassified $\prec$ Confidential $\prec$ Secret $\prec$ Top Secret
Compartments: Need-to-know basis creates additional partial order structure
Clearance: Person can access information at their level and below

Resource Allocation in Distributed Systems

Resource allocations form partial orders based on availability and priority.

Example Computing Resources:

Allocation $A_1$ : 2 CPUs, 4GB RAM
Allocation $A_2$ : 4 CPUs, 2GB RAM
Allocation $A_3$ : 4 CPUs, 4GB RAM

Relations: $A_1 \prec A_3$ and $A_2 \prec A_3$ , but $A_1$ and $A_2$ are incomparable

Basic Exercises

Exercise 1: Determine which of the following relations on $\{1, 2, 3, 4\}$ are partial orders:

a) $R_1 = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,3), (1,3)\}$

b) $R_2 = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (3,4)\}$

c) $R_3 = \{(1,1), (2,2), (3,3), (4,4), (1,2), (1,3), (1,4), (2,4), (3,4)\}$

Exercise 2: For the poset of divisors of 24, find:

a) All maximal elements

b) All minimal elements

c) The greatest element (if it exists)

d) The least element (if it exists)

Exercise 3: Draw the Hasse diagram for:

a) The poset of divisors of 30

b) The poset $\mathcal{P}(\{a,b\})$ ordered by $\subseteq$

c) The poset $\{1,2,3,4,5,6\}$ with $a \preceq b$ iff $a|b$

Intermediate Exercises

Exercise 4: In the lattice of subsets of $\{1,2,3,4\}$ , find:

a) $\{1,2\} \vee \{2,3\}$

b) $\{1,2\} \wedge \{2,3\}$

c) $\{1,3\} \vee \{2,4\}$

d) $\{1,2,3\} \wedge \{2,3,4\}$

Exercise 5: Prove that in any poset, if a greatest element exists, then it is unique.

Exercise 6: Given the poset with Hasse diagram:

a) Which elements are comparable to $b$ ?

b) What are $\sup(\{b,c\})$ and $\inf(\{b,c\})$ ?