Partial Orders

Definition

A relation $R$ on a set $A$ is a partial order if it is:

1. Reflexive: $\forall a \in A: aRa$
2. Antisymmetric: $\forall a, b \in A: (aRb \land bRa) \rightarrow a = b$
3. Transitive: $\forall a, b, c \in A: (aRb \land bRc) \rightarrow aRc$

A set with a partial order is called a partially ordered set or poset, written $(A, \preceq)$.

Examples

Divisibility on $\mathbb{Z}^+$

$a \mid b$ (a divides b) is a partial order.

Subset Relation

$A \subseteq B$ on a power set $\mathcal{P}(S)$.

Less Than or Equal ($\leq$)

$\leq$ on $\mathbb{R}$ is a partial order (actually a total order).

Lexicographic Order

For strings: compare character by character.

Comparability

In a poset $(A, \preceq)$:

• $a$ and $b$ are comparable if $a \preceq b$ or $b \preceq a$
• $a$ and $b$ are incomparable if neither $a \preceq b$ nor $b \preceq a$

In $(\mathcal{P}(\{1,2,3\}), \subseteq)$:

• $\{1\}$ and $\{1, 2\}$ are comparable ($\{1\} \subseteq \{1,2\}$)
• $\{1\}$ and $\{2\}$ are incomparable

Total Orders

A partial order is a total order (or linear order) if every pair is comparable: $\forall a, b \in A: a \preceq b \lor b \preceq a$

Examples:

• $\leq$ on $\mathbb{R}$ — total order
• $\subseteq$ on $\mathcal{P}(S)$ — NOT total (unless $|S| \leq 1$)

Hasse Diagrams

A visual representation of a finite poset:

1. Draw elements as points
2. Draw line from $a$ (lower) to $b$ (higher) if $a \prec b$ with no element between
3. Omit reflexive loops and transitive edges

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

        12
       /  \
      4    6
      |   /|
      2  3 |
       \ | /
         1

Special Elements

Maximal and Minimal

• $a$ is maximal if $\neg\exists b \in A: a \prec b$ (nothing above it)
• $a$ is minimal if $\neg\exists b \in A: b \prec a$ (nothing below it)

A poset can have multiple maximal/minimal elements.

Greatest and Least

• $a$ is the greatest element (maximum) if $\forall b \in A: b \preceq a$
• $a$ is the least element (minimum) if $\forall b \in A: a \preceq b$

A poset has at most one greatest/least element.

Upper and Lower Bounds

For subset $S \subseteq A$:

• $u$ is an upper bound of $S$ if $\forall s \in S: s \preceq u$
• $l$ is a lower bound of $S$ if $\forall s \in S: l \preceq s$

Least Upper Bound (LUB) / Supremum

The least upper bound of $S$, written $\sup(S)$ or $\text{lub}(S)$, is the smallest upper bound.

Greatest Lower Bound (GLB) / Infimum

The greatest lower bound of $S$, written $\inf(S)$ or $\text{glb}(S)$, is the largest lower bound.

Lattices

A poset $(L, \preceq)$ is a lattice if every pair of elements has:

• A least upper bound (join): $a \lor b = \text{lub}(\{a, b\})$
• A greatest lower bound (meet): $a \land b = \text{glb}(\{a, b\})$

Examples

• $(\mathcal{P}(S), \subseteq)$ with $A \lor B = A \cup B$ and $A \land B = A \cap B$
• $(\mathbb{Z}^+, \mid)$ with $a \lor b = \text{lcm}(a,b)$ and $a \land b = \gcd(a,b)$

Well-Ordering

A poset $(A, \preceq)$ is well-ordered if:

1. It is a total order
2. Every non-empty subset has a least element

Examples

• $(\mathbb{N}, \leq)$ — well-ordered
• $(\mathbb{Z}, \leq)$ — NOT well-ordered (no least element)
• $(\mathbb{Q}^+, \leq)$ — NOT well-ordered ($\{x \in \mathbb{Q} \mid x > 0\}$ has no least element)

Well-Ordering Theorem

Every set can be well-ordered (equivalent to Axiom of Choice).

Topological Sorting

Given a partial order on a finite set, a topological sort is a total order consistent with the partial order.

Algorithm

1. Find a minimal element
2. Remove it and add to sorted list
3. Repeat until empty

Example

For tasks with dependencies, topological sort gives a valid execution order.

Chains and Antichains

• A chain is a totally ordered subset
• An antichain is a set of pairwise incomparable elements

Dilworth's Theorem

In a finite poset, the minimum number of chains needed to cover all elements equals the maximum size of an antichain.