Greatest and Maximal Elements

Hierarchies and dependencies are everywhere, from family trees to project workflows. Mathematics provides a powerful tool for understanding these structures through the concept of a partially ordered set, where some elements are related but others may be incomparable. Within these complex systems, a seemingly simple question arises: what does it mean to be "at the top"? This question uncovers a subtle but critical distinction that is often overlooked. The problem lies in defining "the top" precisely—is it a single, undisputed ruler, or one of several undefeated contenders?

This article demystifies the two key concepts used to answer this question: the ​​greatest element​​ and the ​​maximal element​​. Across the following chapters, you will gain a clear understanding of their definitions, the logical relationship between them, and the profound implications of this distinction.

First, in "Principles and Mechanisms," we will explore the formal definitions using intuitive examples, from course prerequisites to number theory, and uncover the different rules that govern finite and infinite sets. Then, in "Applications and Interdisciplinary Connections," we will see how these abstract ideas provide a powerful lens for analyzing real-world systems in computer science, biology, economics, and even the foundations of mathematics itself.

Imagine you are looking at a family tree, or perhaps the command structure of an ancient army. Some individuals are ancestors to others, some are descendants. Some officers command others, who in turn command soldiers. In mathematics, we call these structures ​​partially ordered sets​​, or ​​posets​​ for short. The "order" isn't always as simple as a straight line of numbers; some individuals might be incomparable, like two cousins who are not in a direct line of descent, or two captains who are peers.

Our journey in this chapter is to understand what it means to be "at the top" in such a structure. You might think this is simple, but as with many things in science, a question that seems simple on the surface often hides a world of beautiful and subtle ideas. We're going to explore two different notions of being "at the top": the ​​maximal​​ element and the ​​greatest​​ element.

Let's start with a familiar scenario: planning a university degree. Imagine a program with five courses, $\{C_1, C_2, C_3, C_4, C_5\}$. The rules say that $C_1$ is a prerequisite for both $C_2$ and $C_3$. In turn, $C_2$ is a prerequisite for $C_4$, and $C_3$ is a prerequisite for $C_5$. We can draw this out like a little tree. An arrow from course A to course B means "you must take A before B".

Now, which courses are "at the top"? These would be the final courses you can take, the ones that are not prerequisites for anything else. Looking at our diagram, it's clear that after you take $C_4$, there's nowhere else to go in that branch. The same is true for $C_5$. These are the "end-of-the-line" courses. In the language of order theory, $C_4$ and $C_5$ are ​​maximal elements​​. A maximal element is an element that has nothing "above" it.

This seems straightforward enough. But now, let's ask a slightly different question: Is there a single, ultimate "capstone" course that everything else leads to? A single course that is, in a sense, "above" all others? This would be what we call a ​​greatest element​​. A greatest element must be comparable to, and greater than, every other element in the set.

In our curriculum, is there a greatest element? Let's check. For a course to be the greatest, every other course must be its prerequisite (directly or indirectly). Is $C_4$ the greatest? No, because taking $C_3$ and $C_5$ has no bearing on it; they are not prerequisites for $C_4$. Is $C_5$ the greatest? No, for the same reason. There is no single course that sits atop the entire structure. So, this poset has two maximal elements, but no greatest element.

This is the fundamental distinction we must burn into our minds:

• ​​Maximal​​: A contender for the throne. Nobody can defeat them (nothing is strictly greater). There can be many contenders.
• ​​Greatest​​: The undisputed king. They have already defeated everyone (they are greater than or equal to all other elements). There can be at most one king.

Let's move from course planning to a game with numbers. Consider the set of all positive integers less than 20, that is $S = \{1, 2, \dots, 19\}$. Let's define our ordering relation not as "less than or equal to", but by ​​divisibility​​. We'll say that $a \preceq b$ if $a$ divides $b$. So, $3 \preceq 12$ because $3$ divides $12$, but $5 \not\preceq 13$.

Who are the maximal elements in this game? A number $m$ is maximal if it doesn't divide any other number in the set $S$. Think about the number 18. Are there any multiples of 18 (other than 18 itself) in the set $\{1, \dots, 19\}$? No, the next multiple is 36, which is too big. So, 18 is a maximal element. What about 17? Its next multiple is 34, also too big. So 17 is maximal. In fact, any number $m$ where $2m > 19$ will be maximal, because its smallest multiple (other than itself) will be outside the set. This means all the numbers $\{10, 11, 12, 13, 14, 15, 16, 17, 18, 19\}$ are maximal elements!. We have a whole crowd of contenders.

With so many maximal elements, can there be a greatest one? Of course not. A greatest element would have to be a multiple of every number in the set. It would have to be a multiple of 19, 18, 17, and so on. Such a number would be enormous, certainly not in our little set of numbers less than 20. So, once again, we have a posse of maximal elements but no single greatest element.

Is it possible to have a greatest element in this game? Yes, if we carefully choose our set. Let's try $S = \{2, 3, 5, 6, 10, 15, 30, 60\}$ with the same divisibility relation. Now, who is the greatest? Let's test the largest number, 60. Is it a multiple of everything else in the set? Yes! $2|60$, $3|60$, $5|60$, $6|60$, $10|60$, $15|60$, and $30|60$. Everything in the set is a divisor of 60. Therefore, 60 is the ​​greatest element​​. And if 60 is the greatest, what are the maximal elements? Well, only 60. Nothing can be "above" 60.

This leads us to a crucial insight. In the last example, the greatest element, 60, was also the only maximal element. This was no accident. It is a universal truth of all partially ordered sets: ​​If a greatest element exists, it must be the unique maximal element.​​

The proof is a lovely piece of logic. Let's call our greatest element $G$.

1. First, is $G$ a maximal element? For $G$ not to be maximal, there would have to be some other element $x$ that is strictly greater than $G$. But this is impossible! $G$ is the greatest element, meaning it's greater than or equal to everything, including this hypothetical $x$. So we would have $G \preceq x$ and $x \preceq G$. The rules of a poset (specifically, antisymmetry) demand that this can only happen if $x=G$. So no element can be strictly greater than $G$. Therefore, $G$ must be maximal.
2. Second, is it the unique maximal element? Suppose there was another maximal element, let's call it $M$. Since $G$ is the greatest element, we know that $M \preceq G$. But wait! $M$ is maximal, meaning nothing can be strictly greater than it. Since we know $M \preceq G$ and $M \neq G$ is forbidden, it must be that $M=G$. Any other supposed maximal element is just the greatest element in disguise!

So, the existence of a king, a greatest element, implies there is only one contender, who is the king himself.

We've established a one-way street: A greatest element implies a unique maximal element. Now, any good scientist asks: what about the other way around? If we survey a poset and find only a single maximal element, can we conclude it must be the greatest element?

Here, we stumble upon one of the most profound divides in mathematics: the chasm between the ​​finite​​ and the ​​infinite​​.

Let's first consider ​​finite​​ sets. Suppose you have a finite poset with a single maximal element, $m$. Pick any other element, $x$. If $x$ is not $m$, can we show that $x \preceq m$? Let's try to "climb" from $x$. If $x$ is not maximal (and we know it isn't, since $m$ is the only one), there must be some element $x_1$ such that $x \prec x_1$. If $x_1$ isn't $m$, we can do it again, finding an $x_2$ such that $x_1 \prec x_2$. We build a chain: $x \prec x_1 \prec x_2 \prec \dots$. Since the set is finite, we can't keep finding new, distinct elements forever. This climbing path must end. And where can it end? It can only end at a maximal element. Since we have only one maximal element, $m$, our path must inevitably lead to it. By transitivity, if we have a path from $x$ to $m$, then $x \preceq m$. Since we could do this for any $x$, it means $m$ is greater than or equal to everything. It is the greatest element!.

So for any finite set, the answer is a resounding yes: a unique maximal element is always the greatest element.

But what about ​​infinite​​ sets? Here, the story changes completely. Our "climbing" argument breaks down, because in an infinite set, you might be able to climb forever! Consider the set of all finite subsets of the natural numbers $\mathbb{N}=\{1, 2, 3, \dots\}$, ordered by the subset relation $\subseteq$. Pick any finite subset, say $A=\{1, 5, 10\}$. Can we find a "bigger" one? Sure, just add a number that's not in it, like $B = \{1, 5, 10, 23\}$. $B$ is also a finite set, and $A \subset B$. We can do this forever. This set has no maximal elements at all!.

To get a definitive "no" to our question, we need an even cleverer construction. Let's use the set from problem's solution: Let $S$ be the union of the natural numbers $\mathbb{N}=\{1,2,3,\dots\}$ and a single isolated element $\{x\}$. The order on $\mathbb{N}$ is the usual $\le$. The element $x$ is incomparable with every natural number.

• In this set, is there a maximal element? The natural numbers don't have one, as you can always add 1. What about $x$? Since nothing is "greater" than $x$, it is a maximal element. In fact, it's the unique maximal element.
• Now for the punchline: Is $x$ the greatest element? No! For $x$ to be the greatest, it would have to be greater than or equal to every other element. But it's not greater than or equal to 3, for instance. They are incomparable. So here we have it: an infinite set with a unique maximal element that is not the greatest element. The finite intuition fails us completely!

This exploration has revealed a rich structure, but we can push it one step further by connecting it to another field of mathematics: analysis. Consider the set of all rational numbers $x$ such that $0 \le x \le \sqrt{3}$. But wait, we restrict our world to only the rational numbers, so our set is $S = \{ x \in \mathbb{Q} \mid 0 \le x \text{ and } x^2 \le 3 \}$. Does this set have a greatest element?

We can find rational numbers that get incredibly close to $\sqrt{3}$: $1.7, 1.73, 1.732, \dots$. But we can never find a rational number that is equal to $\sqrt{3}$. So, for any rational number $q$ in our set $S$ that is close to $\sqrt{3}$, we can always find another rational number that's even closer, and still in $S$. Therefore, there is no greatest element in this set.

However, the set is clearly "bounded above" by $\sqrt{3}$. This value, $\sqrt{3}$, is what analysts call the ​​supremum​​, or the least upper bound. It is the ultimate summit, but it's a summit that lies just outside the territory of our set. A ​​greatest element​​ (or ​​maximum​​) must be a member of the set itself—a peak you can actually stand on. A ​​supremum​​ is more like the horizon—the line you can approach but never quite reach from within your current world.

And what about existence in the vastness of infinity? We saw that some infinite sets have maximal elements and some don't. Is there a master key? There is, and it is one of the most powerful and controversial tools in mathematics: ​​Zorn's Lemma​​. It gives a condition—that every ascending chain of elements has an "upper bound" somewhere in the set—which, if met, guarantees the existence of at least one maximal element, even in the most unimaginably complex infinite sets. It is the ultimate generalization of our simple "finite climbing" argument, a statement of profound faith in order.

From simple course prerequisites to the very foundations of mathematics, the quest to understand what it means to be "at the top" reveals a universe of structure, where simple questions lead to deep truths about the nature of the finite and the infinite.

We have spent some time getting to know the characters of our story: the humble maximal element and its more imperious cousin, the greatest element. A greatest element, you’ll recall, is the undisputed monarch of a set—an element greater than or equal to every other element. A maximal element is more like a local warlord; no one is greater than it, but it might not rule the entire domain. This distinction seems subtle, almost a matter of semantics. But as we are about to see, asking the simple question, "Does this system have a greatest element?" is like using a powerful lens that reveals the deep, hidden structure of systems all around us. The answer—whether it's a resounding "yes," a definitive "no," or a telling "it's complicated"—has profound consequences in fields as diverse as computer science, biology, and economics.

Let's start in the world of computers, where order is everything. Imagine you are a build system for a large software project. You have a collection of files—main.c, core.c, utils.h, and so on—and you need to compile them. The catch is that some files depend on others. For instance, main.c might need the code from core.c to be compiled first. This "must be compiled before" relationship creates a partial order on the set of files.

Now, a natural question to ask is: Is there a single file that must be compiled last? That is, does this ordered set have a greatest element? If such a file existed, it would be the final, ultimate target of the whole compilation process. But in most real-world projects, this is not the case. You might have one file that produces the main executable program, but another completely separate file that builds a suite of diagnostic tests. Neither depends on the other. They are both "final" outputs, but neither is greater than the other. They are both maximal elements, but there is no single greatest element. Likewise, there might be multiple files with no dependencies at all (like config.c and utils.h), meaning there's no single "first" file to compile, and thus no least element. The absence of a greatest element here isn't a flaw; it's a feature! It tells us that the project has multiple independent endpoints, which can perhaps even be built in parallel. The structure of the order reveals the structure of the workflow.

The search for a greatest element is also at the heart of making our computers perform reliable calculations. When solving a large system of linear equations—a task essential for everything from weather prediction to designing bridges—the popular method of Gaussian elimination can be dangerously unstable. Small rounding errors can snowball into catastrophic inaccuracies. A brilliant and simple strategy to tame this chaos is called "pivoting." At each step of the algorithm, we look at a part of our matrix and search for the entry with the largest absolute value. This is nothing more than finding the greatest element in a small, finite set of numbers! We then rearrange our equations to put this "greatest" element in a special position, the pivot position, where it can anchor the calculation and prevent errors from growing out of control. More advanced "complete pivoting" strategies expand the search to a larger submatrix, requiring more work but offering even better stability. This hunt for the greatest element is a constant, tiny act of course-correction that makes modern scientific computing possible. It’s a beautiful example of a simple, local rule—find the biggest number right here, right now—leading to a robust, global outcome.

However, nature loves to remind us that there are no silver bullets. Mathematicians have cleverly constructed special "pathological" matrices where this very strategy of always picking the local greatest element leads to the worst possible outcome: the errors grow exponentially! For one such $12 \times 12$ matrix, the size of the numbers can blow up by a factor of $2^{11}$, which is 2048. This is a sobering lesson: even the most intuitive strategy can have hidden failure modes, and understanding the dynamics of the "greatest element" is key to mapping them out.

Let’s turn from the silicon world of computers to the carbon world of biology. One of the most beautiful concepts in developmental biology is "potency"—the capacity of a cell to differentiate into other cell types. A blood stem cell is potent; it can become a red blood cell, a white blood cell, or a platelet. A neuron, on the other hand, is terminally differentiated; its fate is sealed. We have an intuitive hierarchy: a totipotent cell (like a fertilized egg) is the master of all, capable of forming an entire organism; a pluripotent cell (like an embryonic stem cell) can form any body tissue but not the extraembryonic tissues like the placenta; a multipotent cell (like the blood stem cell) is more restricted, and so on.

Can we make this beautiful, intuitive idea mathematically precise? The answer is a delightful "yes," using the language of ordered sets. Let's define one cell type as "less potent than or equal to" another if the set of its possible descendant fates is a subset of the other's. So if cell $c_2$ can become everything cell $c_1$ can become (and possibly more), we say $c_1 \preceq c_2$. This simple definition creates a partial order of potency.

Now, where does the totipotent cell fit in? By definition, it can give rise to all embryonic and extraembryonic cell types. Its set of reachable fates is the entire set of possible fates in the organism. Under our ordering, this means that for any cell type $c$ in the body, its set of fates is a subset of the totipotent cell's fates. In other words, the totipotent cell is the ​​greatest element​​ in the hierarchy of life's potential. This isn't just a clever analogy. This mathematical formalism brings extraordinary clarity, distinguishing totipotency (the true greatest element) from pluripotency (a slightly less powerful state) and giving us a rigorous framework to understand the very architecture of development.

The existence of a greatest element brought order to biology. Now let's see what its absence does in the realm of strategy and economics. Consider a simple game, like Rock-Paper-Scissors. Does Player 1 have a "best" move? A strategy that is at least as good as, or better than, any other choice, no matter what Player 2 does? Let's formalize this. We can order the strategies: strategy $A$ is "greater than or equal to" strategy $B$ if its payoff is at least as good as $B$'s against every possible move by the opponent. A "greatest element" in this ordering would be a dominant strategy—a single move that is always the best choice.

But as any child knows, Rock-Paper-Scissors has no such thing. Rock beats scissors, but loses to paper. Paper beats rock, but loses to scissors. For any choice you make, there's an opponent's choice that makes you regret it. There are maximal strategies in certain contexts, but no single greatest strategy. This lack of a greatest element is the very soul of the game! It is what creates the endless cycle, the need for bluffing, psychology, and randomness. The entire field of game theory, with its deep ideas of mixed strategies and Nash equilibria, is built upon the fascinating consequences of systems that lack a greatest element. The "solution" to the game is not to find the best move, but to find the best probability mixture of moves, precisely because no single move reigns supreme.

Finally, let's step back and admire the role our concept plays in the abstract world of pure mathematics. Here, the existence of a greatest element is tied to some of the most fundamental properties of space and structure.

In topology, there is a concept called "compactness," which is a way of generalizing the idea of a set being "closed and bounded" like the interval $[0, 1]$. It captures a notion of topological finiteness and well-behavedness. Now, consider a set that has a linear order (every two elements are comparable) and is endowed with the natural "order topology." A remarkable theorem states that if such a space is compact, it must have a greatest element and a least element. The proof is wonderfully intuitive: if there were no greatest element, you could create an "open cover" of the space with an infinite collection of rays of the form $(-\infty, b)$. Each point would be covered, but no finite collection of these rays could ever cover the whole space, because their union would always be another ray, leaving elements further "up" uncovered. This would violate compactness. So, for an ordered space to be "compact," it must be capped at both ends. Its "boundedness" is manifested as the existence of a greatest and least element.

Even the very definition of a function, a concept at the bedrock of mathematics, relies on this idea. When we define a function $f(A) = \max(A)$ that takes a non-empty, finite set of numbers $A$ and returns its maximum, we are implicitly relying on a deep truth: every non-empty, finite subset of the real numbers has a unique greatest element. This guarantee of existence and uniqueness is what makes the rule a well-defined function. It's something we take for granted, but it is a direct consequence of the orderly nature of the real numbers.

This pattern of lifting properties from simple spaces to more complex ones is a grand theme in mathematics. We can even define orders on spaces of functions themselves. If you have a set of possible states $P$ with an order, you can order the functions that map into $P$. A powerful result, which relies on the Axiom of Choice (a foundational axiom of modern mathematics), states that this large, complex function space has a maximal element if and only if the original, simple space $P$ does. The structure of the building blocks determines the structure of the edifice.

From the practicalities of compiling code to the grand strategy of life's development, from the stability of numerical algorithms to the abstract beauty of topology, the question "Is there a greatest element?" echoes through the halls of science. The answer, yes or no, is never trivial. It is a key that unlocks a deeper understanding of the system itself, revealing whether it converges to a single peak, is defined by a balance of competing forces, or stretches endlessly towards infinity.