4.2 Extremal Elements: Maximal, Minimal, Greatest, Least & Bound Invariants

Back to Discrete Mathematics Notes

📚Module 04: Posets & Lattice TheoryTopic 4.2: Extremal Elements: Maximal, Minimal, Bounds, LUB & GLB⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Mountain Peaks vs The Tallest Building

Imagine surveying mountain peaks and city skylines:

1. Maximal Elements (Local Summits): In a rugged mountain range, every peak that has no higher ground immediately above it is a maximal element. A mountain range can have hundreds of distinct maximal peaks. None of them is necessarily higher than the others; they are simply local summits!
2. The Greatest Element (Global Champion): Mount Everest! It is higher than every single other point on Earth. If a global champion exists, there can only ever be one, and it must be universally comparable to everything.
3. Upper Bounds & The Least Upper Bound (LUB / Join): You and a friend want to meet at an airport that both of you can reach without backtracking. The set of all airports reachable by both travelers forms the Upper Bounds. The airport that requires the fewest layovers is the Least Upper Bound (LUB / Supremum).
4. The Lattice Standard: A partial order where any two elements have a unique consensus ceiling (LUB) and a unique consensus floor (GLB).

💻 Bridging to Computer Science: Least Common Ancestor, Semantics & Type Systems

In computer systems:

• Git Merge Base: In version control, finding the common ancestor commit of two divergent branches is finding the Greatest Lower Bound (GLB / Meet) in the commit poset!
• Type Systems & Subtyping: In compilers (e.g., TypeScript or Java), finding the common supertype of two classes (e.g., Cat and Dog $\to$ Animal) is computing their Least Upper Bound (LUB).
• Static Program Analysis (Abstract Interpretation): Compilers represent variable intervals as lattices where program branch merges compute the Join ($\vee$) of abstract states.

📑Table of Contents

• 🏔️ Extremal Elements: Maximal, Minimal, Greatest & Least
  • Extremal Elements Diagnostic Comparison
  • The 5 Golden Invariants of Extremal Elements
  • Archetypal Extremal Evaluation Matrix
• 🎯 Upper Bounds, Lower Bounds, LUB & GLB
• 🏛️ The Lattice Foundation
  • Canonical Examples of Lattices
• 📝 Step-by-Step Worked Examples
  • Example 1: Finding Bounds and Extremal Elements in a Hasse Diagram
  • Example 2: Analyzing Divisor Lattices D24 and D30
• 🎯 Exam & Interview Pitfall Check

---

🏔️ Extremal Elements: Maximal, Minimal, Greatest & Least

A common source of confusion in discrete mathematics is the distinction between maximal and greatest elements.

Extremal Elements Diagnostic Comparison

Classification	Formal Poset Definition	Graphical Hasse Invariant	Existence & Multiplicity
Maximal Element(s)	$m \in A$ such that $\nexists x \in A$ with $m \lt x$	A node with zero outgoing upward edges (a local ceiling).	Can have zero, one, or multiple elements.
Greatest Element ($\mathbf{1}$)	$g \in A$ such that $\forall x \in A, \; x \le g$	A single master summit reachable by an upward path from every node.	At most one element ($0$ or $1$). Strictly unique when it exists!
Minimal Element(s)	$m \in A$ such that $\nexists x \in A$ with $x \lt m$	A node with zero incoming downward edges (a local floor).	Can have zero, one, or multiple elements.
Least Element ($\mathbf{0}$)	$l \in A$ such that $\forall x \in A, \; l \le x$	A single universal base that leads by an upward path to every node.	At most one element ($0$ or $1$). Strictly unique when it exists!

📐Theorem 4.1: Uniqueness of Greatest and Least Elementstheorem

In any partially ordered set $(A, \le)$:

1. If a greatest element exists, it is strictly unique.
2. If a least element exists, it is strictly unique.

Proof of Uniqueness for Greatest Element: Suppose $g_1$ and $g_2$ are both greatest elements in $(A, \le)$:

• Since $g_1$ is a greatest element, $\forall x \in A, x \le g_1$. Setting $x = g_2$ yields $g_2 \le g_1$.
• Since $g_2$ is a greatest element, setting $x = g_1$ yields $g_1 \le g_2$.
• By the Antisymmetry Axiom of posets, $g_2 \le g_1 \land g_1 \le g_2 \implies g_1 = g_2$. Therefore, a poset can never contain multiple greatest elements! The exact same logic applies to least elements.

The 5 Golden Invariants of Extremal Elements

The following 5 properties are classical benchmarks tested in discrete mathematics and competitive examinations:

1. At Most One Greatest and Least: Every finite Hasse diagram contains either exactly one or zero greatest elements, and either exactly one or zero least elements ($\le 1$).
2. Greatest Implies Maximal: If a greatest element exists, it is guaranteed to be a maximal element (in fact, the only maximal element).
3. Least Implies Minimal: If a least element exists, it is guaranteed to be a minimal element (the only minimal element).
4. Single Maximal in Connected Posets: If a finite connected Hasse diagram has only one maximal element, that element is automatically the Greatest element.
5. Single Minimal in Connected Posets: If a finite connected Hasse diagram has only one minimal element, that element is automatically the Least element.

Archetypal Extremal Evaluation Matrix

To see these invariants in action, consider how extremal elements evaluate across standard Hasse diagram topologies:

Diagram Topology	Minimal Elements	Least Element ($\mathbf{0}$)	Maximal Elements	Greatest Element ($\mathbf{1}$)
Single Diamond ($a \to \{b, c\} \to d$)	$\{a\}$	$a$	$\{d\}$	$d$
Crossed Double Diamond (Two Tops & Bottoms)	$\{a, b\}$	$\emptyset$ (None)	$\{e, f\}$	$\emptyset$ (None)
Branching Y-Tree ($a \to b \to \{c, d\}$)	$\{a\}$	$a$	$\{c, d\}$	$\emptyset$ (None)
Disjoint Chains ($a - b$ and $c - d$)	$\{a, c\}$	$\emptyset$ (None)	$\{b, d\}$	$\emptyset$ (None)

★ Boolean Algebra (B₂)

Single Diamond: Single universal bottom (least a) and single universal summit (greatest d).

✓ Unique Least, Multiple Maximal

Branching Y-Tree: Unique least element a, but multiple maximal peaks {c, d}.

✓ Multiple Min & Multiple Max

Crossed Double Diamond: Multiple minimal {a, b} and multiple maximal {e, f}.

---

🎯 Upper Bounds, Lower Bounds, LUB & GLB

Let $(A, \le)$ be a poset, and let $S \subseteq A$ be any arbitrary subset.

📖Definition 4.4: Bounds of a Subsetdefinition

1. Upper Bound: An element $u \in A$ is an upper bound of $S$ if: $$\forall s \in S, \quad s \le u$$ (Notice: $u$ does NOT need to belong to $S$!).
2. Lower Bound: An element $l \in A$ is a lower bound of $S$ if: $$\forall s \in S, \quad l \le s$$
3. Least Upper Bound (LUB / Supremum / Join $\vee$): An element $x \in A$ is the LUB of $S$ (written $\text{LUB}(S)$ or $\bigvee S$) if:
   • $x$ is an upper bound of $S$, and
   • If $u$ is any other upper bound of $S$, then $x \le u$.
4. Greatest Lower Bound (GLB / Infimum / Meet $\wedge$): An element $y \in A$ is the GLB of $S$ (written $\text{GLB}(S)$ or $\bigwedge S$) if:
   • $y$ is a lower bound of $S$, and
   • If $l$ is any other lower bound of $S$, then $l \le y$.

Uniqueness Invariant: If $\text{LUB}(S)$ or $\text{GLB}(S)$ exists, it is strictly unique!

---

🏛️ The Lattice Foundation

📖Definition 4.5: Latticedefinition

A partially ordered set $(L, \le)$ is called a Lattice if and only if every pair of elements $a, b \in L$ has both:

1. A unique Least Upper Bound (Join): $$a \vee b = \text{LUB}(a, b)$$
2. A unique Greatest Lower Bound (Meet): $$a \wedge b = \text{GLB}(a, b)$$

If for even a single pair $\{a, b\} \subseteq L$, either the Join or the Meet fails to exist, $(L, \le)$ is NOT a lattice!

Semi-Lattice Classifications:

• Join Semi-Lattice: A poset where every pair possesses a unique Join ($a \vee b$), but some pairs may lack a Meet.
• Meet Semi-Lattice: A poset where every pair possesses a unique Meet ($a \wedge b$), but some pairs may lack a Join (e.g. a rooted tree or branching $Y$-poset).
• Lattice: A poset that is simultaneously both a Join Semi-Lattice and a Meet Semi-Lattice!

Architecture Flow

Lattice Structural Verification Pipeline

Systematic multi-phase checklist to determine if a finite Hasse diagram is a valid lattice

⚓Check 1

Universal Extremes Test

Must have exactly ONE maximal element (greatest 1) and ONE minimal element (least 0). Multiple tops or bottoms ⟹ NOT a lattice!

→

Pass: Single Top & Bottom

🔼Check 2

Pairwise Upper Bounds

For every incomparable pair {a, b}, calculate the set of upper bounds. The set must possess a single unique minimum (LUB).

→

Pass: Unique LUB

🔽Check 3

Pairwise Lower Bounds

For every incomparable pair {a, b}, calculate the set of lower bounds. The set must possess a single unique maximum (GLB).

Canonical Examples of Lattices

1. Divisor Poset $(D_n, \mid)$:

   • For any integer $n \ge 1$, the set $D_n$ of all positive divisors of $n$ under divisibility is always a lattice!
   • Join (LUB): $a \vee b = \text{lcm}(a, b)$
   • Meet (GLB): $a \wedge b = \gcd(a, b)$
   • Least element: $1$; Greatest element: $n$.

2. Power Set Poset $(\mathcal{P}(S), \subseteq)$:

   • The power set of any set $S$ under set inclusion is always a lattice!
   • Join (LUB): $A \vee B = A \cup B$
   • Meet (GLB): $A \wedge B = A \cap B$
   • Least element: $\emptyset$; Greatest element: $S$.

3. Totally Ordered Set (Chain):

   • Any linearly ordered set $(\mathbb{R}, \le)$ is a lattice!
   • Join: $a \vee b = \max(a, b)$; Meet: $a \wedge b = \min(a, b)$.

---

📝 Step-by-Step Worked Examples

Example 1: Finding Bounds and Extremal Elements in a Hasse Diagram

Problem Statement: Consider a poset $A = \{a, b, c, d, e, f, g\}$ whose covering relations are:

$$a \prec c, \quad b \prec c, \quad c \prec d, \quad c \prec e, \quad d \prec f, \quad e \prec f, \quad e \prec g$$

1. Find all maximal and minimal elements.
2. Does the poset have a greatest or least element?
3. For subset $S = \{a, b\}$, find all lower bounds, upper bounds, $\text{GLB}(S)$, and $\text{LUB}(S)$.
4. Determine whether this poset is a lattice.

Step-by-Step Solution:

1. Step 1: Maximal & Minimal Elements

   • Minimals (no element below them): $a$ and $b$.
   • Maximals (no element above them): $f$ and $g$.

2. Step 2: Greatest & Least Elements

   • Greatest element: Requires an element $x$ such that $\forall y \in A, y \le x$. Since there are two maximal elements ($f$ and $g$) that are mutually incomparable, neither is above the other. No greatest element exists.
   • Least element: Requires an element $x$ such that $\forall y \in A, x \le y$. There are two minimal elements ($a$ and $b$) with no element below them. No least element exists.

3. Step 3: Bounds for $S = \{a, b\}$

   • Upper Bounds of $\{a, b\}$: Elements that are $\ge a$ AND $\ge b$. Both paths merge at $c$, so the upper bounds are $\{c, d, e, f, g\}$.
   • LUB($\{a, b\}$): The least element among $\{c, d, e, f, g\}$. Since $c$ divides/precedes all of $\{d, e, f, g\}$, $\text{LUB}(S) = c$.
   • Lower Bounds of $\{a, b\}$: Elements that are $\le a$ AND $\le b$. Since $a$ and $b$ are distinct minimals with nothing below them, no element is below both. Lower bounds = $\emptyset$.
   • GLB($\{a, b\}$): Since the set of lower bounds is empty, $\text{GLB}(S)$ does not exist.

4. Step 4: Lattice Verification

   • Since $\text{GLB}(a, b)$ does not exist, the poset fails the lattice condition immediately!
   • (Also, having multiple maximal elements $f, g$ and multiple minimal elements $a, b$ without universal extremes prevents it from being a finite lattice).
   • Conclusion: NOT a lattice.

Key Takeaway: If a finite poset has more than one maximal element or more than one minimal element, it can never be a lattice!

---

Example 2: Analyzing Divisor Lattices D24 and D30

Problem Statement: Let $D_{24}$ be the set of positive divisors of $24$: $\{1, 2, 3, 4, 6, 8, 12, 24\}$ under divisibility.

1. Compute $6 \vee 8$ (Join) and $6 \wedge 8$ (Meet).
2. Is $(D_{24}, \mid)$ a lattice?

Step-by-Step Solution:

1. Step 1: Computing Join ($6 \vee 8$)

   • In a divisibility lattice, Join is the Least Common Multiple: $$6 \vee 8 = \text{lcm}(6, 8) = 24$$
   • Since $24 \in D_{24}$, the Join exists and is $24$.

2. Step 2: Computing Meet ($6 \wedge 8$)

   • In a divisibility lattice, Meet is the Greatest Common Divisor: $$6 \wedge 8 = \gcd(6, 8) = 2$$
   • Since $2 \in D_{24}$, the Meet exists and is $2$.

3. Step 3: Lattice Classification

   • For any positive integer $n$, every pair of divisors $a, b$ has $\gcd(a, b) \in D_n$ and $\text{lcm}(a, b) \in D_n$ (since both $a \mid n$ and $b \mid n \implies \text{lcm}(a, b) \mid n$).
   • Therefore, $(D_{24}, \mid)$ is guaranteed to be a lattice!

Key Takeaway: Every divisor set $(D_n, \mid)$ is always a lattice with $0 = 1$ and $1 = n$.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Can an element be both a maximal element and a minimal element in the same poset? Key Focus Points: Yes! Any completely isolated element $x$ in a poset (an element that is incomparable to every other element) is simultaneously a maximal element (nothing is strictly greater than $x$) and a minimal element (nothing is strictly less than $x$).

Question 2: If a finite poset has a single unique maximal element, is it guaranteed to be a lattice? Key Focus Points: No! A single maximal element only guarantees a unique greatest element ($1$). The poset could still have multiple minimal elements (no $0$), or internal pairs of elements could have multiple minimal upper bounds, destroying unique Joins.

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing "Upper Bound" with "LUB" Why it fails: A subset can have many upper bounds. For example, if two nodes have upper bounds $\{d, e, f\}$, neither $d$ nor $e$ is necessarily the LUB unless one is below the other. If $d \parallel e$, no unique least upper bound exists, and LUB is undefined!

Trap 2: Assuming the LUB must belong to the subset Why it fails: In subset $S = \{a, b\}$, the $\text{LUB}(a, b)$ is usually an element strictly above both $a$ and $b$ (i.e., $\text{LUB}(S) \notin S$). Only when $a \le b$ does $\text{LUB}(a, b) = b \in S$.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic4.1 Partial Orders, Strict Partial Orders & Hasse Diagram ConstructionNext Topic →4.3 Lattices, Distributive & Complemented Lattices, and Boolean Algebras