Maximal, Minimal Elements and Bounds

In abstract algebra, Zorn's Lemma — a direct descendant of the maximal-element existence question — is used to prove that every nonzero ring with unity has a maximal ideal, and that every vector space has a basis; both proofs hinge on finding a maximal (not merely large) element in a suitably ordered collection. In linear programming and optimization, feasible regions form posets under componentwise comparison, and Pareto-optimal solutions in multi-objective optimization are precisely the maximal elements of the feasibility poset under a dominance order — a setting where, exactly as in Example 1, there are typically many incomparable optimal points rather than one greatest solution. In database theory and computer science, the "skyline query" problem in query optimization asks a database to return exactly the maximal elements of a dataset under a multi-attribute dominance relation, directly instantiating this chapter's maximal-versus-greatest distinction at scale. In lattice theory itself, requiring every pair of elements to have a supremum and infimum inside the poset is precisely the definition of a Lattice, making this chapter's careful sup/inf machinery the immediate prerequisite for that entire theory. In cryptography and access-control models, security clearances are frequently modeled as a poset of "clearance levels" where the absence of a greatest element (several incomparable top-secret compartments) is intentional, preventing any single credential from dominating all others.

Ask the tutor: Can you show me why Zorn's Lemma needs "every chain has an upper bound" instead of just "the poset is finite"?

Picture a Hasse Diagram: elements drawn as dots, with $x \prec y$ shown by placing $y$ above $x$ and drawing an edge when the relation is covering (nothing sits strictly between them). Maximal elements are exactly the dots with no edges leaving upward — the "local peaks" of the diagram, of which there can be many side by side. A greatest element, if it exists, is a single dot connected upward (via some chain of edges) to every other dot in the diagram — the unique apex of the whole picture. The four proper divisors of $60$ other than $60$ itself and $1$ — say restrict to $S = \{2,3,4,5,6,10,12,15,20,30\}$ ordered by divisibility — illustrate the gap between "maximal" and "greatest" sharply: $12, 20, 30$ are each maximal (no other element of $S$ is a multiple of them within $S$), yet none of the three divides another, so $S$ has no greatest element at all. Bounds and suprema live one level of abstraction higher: they are statements about a subset relative to the whole poset, and the bounding element need not be a member of the subset. In the poset of positive integers under divisibility, the subset $\{4, 6\}$ has upper bounds $12, 24, 36, \ldots$ — none of which is $4$ or $6$ — and the least of these upper bounds is $12 = \operatorname{lcm}(4,6)$, the supremum.

Example 1 (a genuinely asymmetric divisibility poset). Let $P = \{2, 3, 4, 6, 8, 9, 12, 18, 24, 36\}$, ordered by divisibility ($x \preceq y$ iff $x \mid y$). We locate every extremal notion for the whole set $P$ and for a designated subset. Maximal elements of $P$. Check each candidate for a strictly larger multiple still inside $P$:

• $24$: is $24$ a proper divisor of anything else in $P$? The only larger elements are $36$, and $24 \nmid 36$ (since $36/24 = 1.5$). So $24$ is maximal.
• $36$: no element of $P$ exceeds $36$, so $36$ is maximal automatically.
• $18$: is $18 \mid 36$? Yes, $36 = 2 \cdot 18$. So $18$ is not maximal.
• $12$: $12 \mid 24$ ($24 = 2\cdot 12$) and $12\mid 36$ ($36=3\cdot12$), so $12$ is not maximal.
• Checking the rest ($2,3,4,6,8,9$) similarly, each divides some larger element of $P$ (e.g. $8 \mid 24$, $9\mid 18$, etc.), so none is maximal.

Hence $P$ has exactly two maximal elements: $24$ and $36$. Since $24 \nmid 36$ and $36 \nmid 24$, they are incomparable, so by Theorem: Uniqueness of greatest/least (c)–(contrapositive), $P$ cannot have a greatest element — a set with a greatest element has a unique maximal element, but $P$ has two. Minimal elements of $P$. The candidates $2$ and $3$ divide nothing smaller in $P$ and nothing in $P$ divides them except themselves, so both are minimal; every other element (e.g. $4 = 2\cdot 2$) is divisible by $2$ or $3$, hence not minimal. So $P$ has two minimal elements: $2$ and $3$, and again no least element. Bounds and sup/inf of a subset. Let $S = \{4, 6, 9\} \subseteq P$. Search $P$ for upper bounds, i.e. elements divisible by all of $4, 6, 9$: we need divisibility by $\operatorname{lcm}(4,6,9) = 36$. Checking $P$, the only element divisible by $36$ is $36$ itself. So $36$ is the only upper bound of $S$ lying in $P$, hence trivially the least one:

For lower bounds of $S$ in $P$: we need elements of $P$ dividing all of $4,6,9$ simultaneously. The only common divisor of $4, 6, 9$ is $1$, which is not in $P$. So $S$ has no lower bound in $P$ at all, and in particular $\inf S$ does not exist in $P$ — a concrete illustration that bounds can fail to exist even in a finite poset, because the ambient set $P$ (not just $S$) may simply omit the needed element.

Example 2 (a poset of subsets, illustrating bounds that exist but lie strictly outside the subset). Let $U = \{1,2,3,4,5\}$ and let $P = \mathcal P(U) \setminus \{\emptyset, U\}$ (all subsets of $U$ except the empty set and $U$ itself), ordered by inclusion $\subseteq$. This $P$ is a genuinely large, asymmetric poset (30 elements). Consider

Upper bounds of $S$ in $P$. An upper bound $B \in P$ must satisfy $\{1,2\}\subseteq B$, $\{1,3\}\subseteq B$, $\{2,3\}\subseteq B$ simultaneously, forcing $\{1,2,3\} \subseteq B$. The smallest set satisfying this is $B_0 = \{1,2,3\}$ itself, which is in $P$ (it is neither $\emptyset$ nor $U$). Other upper bounds exist too: $\{1,2,3,4\}$, $\{1,2,3,5\}$, and $\{1,2,3,4,5\}=U$ is excluded from $P$, so the upper bounds of $S$ inside $P$ are exactly $\{1,2,3\}, \{1,2,3,4\}, \{1,2,3,5\}$. Is $B_0=\{1,2,3\}$ the least of these under $\subseteq$? Yes: $\{1,2,3\} \subseteq \{1,2,3,4\}$ and $\{1,2,3\}\subseteq\{1,2,3,5\}$, and no other upper bound is smaller. So

and notably $\sup S \notin S$ — the supremum of a subset need never belong to the subset itself, which is the precise reason sup/inf are defined via bounds in the ambient poset $P$ rather than as a special case of "greatest element of $S$." Lower bounds of $S$ in $P$. A lower bound $L$ must satisfy $L \subseteq \{1,2\}$, $L \subseteq \{1,3\}$, $L \subseteq \{2,3\}$ simultaneously. The intersection of these three sets is $\emptyset$, so $L \subseteq \emptyset$, forcing $L = \emptyset$ — but $\emptyset \notin P$ by construction. Hence $S$ has no lower bound in $P$, so $\inf S$ does not exist, exactly as in Example 1 but now for a structural (not just numerical) reason: the poset was deliberately built by deleting the one element ($\emptyset$) that would have served as the bound. This pair of examples shows the same phenomenon from two angles — arithmetic (divisibility) and combinatorial (set inclusion) — and demonstrates that the non-existence of a bound is not a pathology of infinite posets; it can happen in a 10- or 30-element finite poset the moment the ambient set is not "closed downward/upward enough."