Skip to content

Chapter 8: Partially Ordered Set, Totally Ordered Set, Hasse Diagram, Well Ordered Set

1. Partially Ordered Set (Poset)

Definition

A partially ordered set (or poset) is a set (P) with a relation (\leq) that is:

  1. Reflexive: (a \le a) for all (a \in P)
  2. Antisymmetric: (a \le b \text{ and } b \le a \Rightarrow a = b)
  3. Transitive: (a \le b \text{ and } b \le c \Rightarrow a \le c)

[ (P, \le) ]

Example 1: Divisibility

Let (P = {1,2,3,6}) and (a \le b) if (a \mid b).

  • Reflexive: 2 divides 2 ✅
  • Antisymmetric: 2 divides 6 and 6 divides 2 ❌ → no, correct only if equal
  • Transitive: 2 divides 6, 6 divides 6 → 2 divides 6 ✅

This is a poset.

Example 2: Subset Relation

(P = { {a}, {a,b}, \emptyset}) (\subseteq) is a poset:

  • Reflexive: (A \subseteq A) ✅
  • Antisymmetric: (A \subseteq B) and (B \subseteq A \Rightarrow A = B) ✅
  • Transitive: (A \subseteq B \subseteq C \Rightarrow A \subseteq C) ✅

2. Totally Ordered Set (Chain)

Definition

A totally ordered set (or chain) is a poset where every pair of elements is comparable:

[ \forall a,b \in P, \text{ either } a \le b \text{ or } b \le a ]

Example

  • ( \mathbb{Z} ) with (\le)
  • {1,2,3,4} with usual ≤

3. Hasse Diagram

Definition

A Hasse diagram is a graphical representation of a poset that:

  • Omits loops and edges implied by transitivity
  • Draws smaller elements lower and larger elements higher

Construction Rules

  1. Place all elements as vertices
  2. Draw an edge (a \to b) if (a < b) and there is no c such that (a < c < b)
  3. No arrows: edges go upward
  4. Reflexive edges omitted

Example

Poset: (P = {1,2,3,6}) with divisibility.

  • 1 divides 2,3,6
  • 2 divides 6
  • 3 divides 6

Hasse diagram:

   6
  / \
 2   3
  \ /
   1

4. Maximal, Minimal, Greatest, Least Elements

Definitions

  • Maximal element: No element is greater than it in the poset
  • Minimal element: No element is less than it
  • Greatest element: Greater than all elements
  • Least element: Less than all elements

Note: Greatest/least are unique; maximal/minimal may not be unique.

Example

Poset: {1,2,3,6} with divisibility

  • Maximal: 6 ✅
  • Minimal: 1 ✅
  • Greatest: 6 ✅
  • Least: 1 ✅

5. Well-Ordered Set

Definition

A poset is well-ordered if it is totally ordered and every non-empty subset has a least element.

Example

  • (\mathbb{N}) with ≤ is well-ordered
  • (\mathbb{Z}) with ≤ is not well-ordered (no least element for (\mathbb{Z}) as subset of negatives)

6. Applications in Computer Science

  • Task scheduling (dependencies → poset)
  • Data hierarchy (file system structure)
  • Database query optimization
  • Topological sorting of DAGs
  • Partial order reduction in concurrent systems

Comments