Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 38 · Equivalence and Order

Extremal Elements, Bounds and Lattices

Learn minimal and maximal elements, least and greatest elements, upper bounds, supremum and infimum, and lattices, with divisibility and subset examples.

In an ordered set we often want to talk about "the biggest", "the smallest" and "the best common upper limit". In a total order such as the real numbers these ideas are simple. In a partial order they split into several related notions, and the differences matter. This lesson gives precise definitions and shows how they lead to lattices, which are posets where any two elements have a best upper bound and a best lower bound.

Throughout, (A, ≼) is a poset and S ⊆ A is a subset.

Maximal, minimal, greatest, least

  • m ∈ S is a maximal element of S if nothing in S is strictly above it: there is no s ∈ S with m ≺ s.
  • m ∈ S is a greatest element (or maximum) of S if every s ∈ S satisfies s ≼ m.
  • Minimal and least (minimum) are defined the same way, upside down.

The difference is subtle: maximal means "nothing above me", greatest means "I am above everything". A greatest element is always maximal. The reverse can fail when elements are incomparable.

Example. In ({2, 3, 4, 6, 12, 18}, divides), which elements are maximal? Both 12 and 18 have nothing in the set above them (neither divides the other, and no other element is a multiple of them). So there are two maximal elements and no greatest element. The minimal elements are 2 and 3 (neither divides the other), and there is no least element. Total orders are simpler: maximal = greatest.

If a greatest element exists it is unique: if m and m' were both greatest, m ≼ m' and m' ≼ m, so m = m' by antisymmetry.

Python Find extremal elements

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Upper and lower bounds, supremum and infimum

An upper bound of S in A is an element u ∈ A with s ≼ u for all s ∈ S. The bound need not belong to S. A lower bound is defined the other way.

The supremum (least upper bound, written sup S or ⋁ S) is the least element of the set of upper bounds, if it exists. The infimum (greatest lower bound, inf S or ⋀ S) is the greatest element of the set of lower bounds.

Example 1. In (ℝ, ≤), let S = (0, 1), the open interval. Its upper bounds are all numbers ≥ 1, so sup S = 1, even though 1 ∉ S. The set S has no maximum, but it has a supremum. Its infimum is 0.

Example 2. In (ℕ⁺, divides), the upper bounds of {4, 6} are the common multiples 12, 24, 36, .... The least of them (in divisibility order, which here is also numerical order) is 12 = lcm(4, 6). The lower bounds are the common divisors 1, 2, and the greatest is 2 = gcd(4, 6). So in the divisibility order, supremum is lcm and infimum is gcd.

Example 3. In (P(X), ⊆), sup {S, T} = S ∪ T and inf {S, T} = S ∩ T.

Lattices

A poset is a lattice if every two elements a, b have a supremum a ∨ b (the join) and an infimum a ∧ b (the meet).

The three examples above are lattices:

Lattice Join a ∨ b Meet a ∧ b
(ℝ, ≤) max(a, b) min(a, b)
(ℕ⁺, divides) lcm(a, b) gcd(a, b)
(P(X), ⊆) A ∪ B A ∩ B

This is why ∪ and ∩, ∨ and ∧, max and min, and lcm and gcd have such similar laws: they are all joins and meets of lattices. Joins and meets are commutative, associative and obey the absorption laws a ∨ (a ∧ b) = a and a ∧ (a ∨ b) = a.

Not every poset is a lattice. Take the poset with elements a, b below both c and d (a "bowtie"): the pair {c, d} has two lower bounds a and b, but neither is the greatest, so c ∧ d does not exist.

flowchart BT
    a["a"] --> c["c"]
    a --> d["d"]
    b["b"] --> c
    b --> d

Not a lattice: c and d have two lower bounds, a and b, with no greatest among them.

Python Compute join and meet in divisibility

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Well-ordered sets: a first look

A total order is a well-order if every non-empty subset has a least element. (ℕ, ≤) is a well-order: any non-empty set of natural numbers has a smallest member. (ℤ, ≤) and ([0, 1], ≤) are not: the integers have no least element, and the open interval (0, 1) has no least element either. Well-orders are what make proofs by induction possible, and they are extended far beyond the natural numbers when you study ordinals later in this track.

Python Does every subset have a least element?

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. In ({2, 3, 4, 6, 12, 18}, divides), which elements are maximal?

    Nothing in the set is a proper multiple of 12 or of 18, so both are maximal. Neither is greatest.
  2. 2. In (ℕ⁺, divides), what is the supremum of {4, 6}?

    The supremum is the least common multiple: lcm(4, 6) = 12.
  3. 3. What is sup of the open interval (0, 1) in (ℝ, ≤)?

    The upper bounds are the numbers ≥ 1; the least is 1.
  4. 4. Which is a well-order?

    Every non-empty set of natural numbers has a least element; the others have subsets without one.

Summary

  • Maximal means "nothing above"; greatest means "above everything". Greatest implies maximal and is unique if it exists.
  • Upper and lower bounds need not lie in the subset; the supremum is the least upper bound, the infimum the greatest lower bound.
  • A lattice has joins and meets for all pairs: max/min, lcm/gcd and ∪/∩ are examples.
  • A well-order is a total order in which every non-empty subset has a least element.

Next: Cardinality and Bijections