What separates a maximal version from a maximum version in a store ordered by 'is an ancestor of'?
answer
- nothing above it versus above everything
- there can be several tops
- uniqueness is the giveaway
- finite orders always have a maximal element
- maximum implies maximal, never the reverse
basics
~20 sA maximal version has nothing above it. A maximum version is above everything. A store can hold several maximal versions at once — concurrent heads — but a maximum, when one exists, is unique and dominates every other version.
solid answer
~40 sIn a poset, `x` is **maximal** when no element is strictly above it, and `x` is **maximum** (or greatest) when every element is below or equal to it. Maximum is by far the stronger claim: it implies maximal, it implies comparability with everything, and it forces uniqueness — two maxima would have to sit above each other, which antisymmetry forbids. A finite non-empty order always has at least one maximal element, and may have no maximum at all. That is why "give me the latest version" is an ambiguous request in an ancestry order: it is well defined only when the heads form a single element. With two maximal heads, the system must either return both or apply a merge rule; picking one and calling it the latest quietly discards the other branch.
go deeper
Learn the two words apart: maximal means nothing is above it, maximum means it is above everything. Only the second one has to be unique.
Explain why a maximum is unique — two of them would have to sit above each other, and antisymmetry forbids that — and why several maximal elements are perfectly ordinary.
Show what multiple heads mean operationally: they are the conflict signal, and any API promising a single 'latest' in a branching order is deciding something it should be surfacing.
Treat it as an interface question. Guaranteeing a maximum means guaranteeing a merge or a coordination point somewhere; decide who owns that cost before the contract promises a single answer.
## Two words one letter apart Take a set of versions ordered by `x <= y` meaning "`x` is an ancestor of `y`, or is `y` itself". Two definitions sit on top of that relation: - **Maximal**: `x` is maximal when there is no `y` in the set with `x < y`. Nothing is strictly above it. - **Maximum** (also *greatest*): `x` is maximum when `y <= x` for **every** `y` in the set. It is above everything. The difference is the quantifier. Maximal is a statement about what is missing above `x`; maximum is a statement about `x`'s relation to every other element. In a total order the two coincide, which is why the words feel interchangeable to anyone who has only ever ordered numbers. | | Maximal | Maximum | |---|---|---| | Definition | nothing strictly above it | above or equal to everything | | How many can exist | any number | at most one | | Comparable with all others | not necessarily | yes, by definition | | Exists in a finite non-empty order | always at least one | only sometimes | | Implies the other | no | yes — a maximum is maximal | ## Why a maximum is unique Suppose `a` and `b` are both maximum. Then `b <= a` because `a` is above everything, and `a <= b` because `b` is. Antisymmetry says two elements that precede each other are the same element, so `a = b`. Uniqueness is not a convention; it falls straight out of the axiom. Maximal elements get no such argument. Two maximal elements are simply incomparable: neither is above the other, and nothing is above either. ## Which one is guaranteed In a **finite non-empty** poset there is always at least one maximal element. Start anywhere and keep stepping strictly upwards; transitivity and antisymmetry forbid ever revisiting an element, and the set is finite, so the walk must stop — and it can only stop where nothing lies above. Drop finiteness and even that guarantee goes: an unbounded increasing chain has no maximal element at all. A maximum, by contrast, is never guaranteed. Two versions branched from a common ancestor and never merged are both maximal and neither is maximum, so the order simply has no greatest element. ## Reading it off a Hasse diagram A **Hasse diagram** draws a finite poset with elements as nodes, greater elements higher on the page, and a line only for each *covering* pair — `x` below `y` with nothing strictly between them. Edges implied by transitivity are left out because transitivity already supplies them. On such a picture: - a **maximal** element is any node with no line rising out of it; - a **maximum** exists only when there is exactly one such node **and** every other node has an upward path to it; - several top nodes means several maximal elements and no maximum. ## The mirror image, and well-foundedness Everything above dualises. `x` is **minimal** when nothing is strictly below it, and **minimum** (*least*) when it is below everything; the same uniqueness argument applies. That direction carries one more idea worth naming. An order is **well-founded** when every non-empty subset has at least one minimal element — equivalently, when no infinite strictly descending chain exists. Well-foundedness is a much weaker demand than having a minimum: it asks only that you cannot descend forever, not that all the descents converge on a single bottom element. Finite orders are automatically well-founded; infinite ones may or may not be, and the distinction is what separates an order you can always "bottom out" in from one you cannot. ## Where the distinction bites - **"Fetch the latest" is under-specified** in any branching order. The API must decide: one maximal element chosen by a rule, all of them, or a merged result. - **A conflict is exactly a second maximal element.** Counting heads is the detection mechanism, not an afterthought. - **Choosing arbitrarily among maximal heads loses data** — the discarded branch contained work that the kept one never incorporated. - **A maximum can be manufactured** by adding an element above the heads, which is what a merge does: it turns two maximal elements into a single one above both.
- Can a finite non-empty partial order have no maximal element at all?No. Step strictly upwards from any element; antisymmetry and transitivity mean you can never revisit one, and finiteness means the walk must stop. It can only stop at an element with nothing above it. Infinite orders lose this guarantee — an unbounded increasing chain has no maximal element.
- What does it mean for an order to be well-founded, and how does that differ from having a minimum?Well-founded means every non-empty subset has a minimal element, equivalently that no infinite strictly descending chain exists. A minimum is far stronger: a single element below everything. An order can be well-founded with many incomparable minimal elements and no minimum among them.
- A store reports two maximal versions. What does it owe the caller?Either both heads, so the caller can apply domain knowledge, or a deterministic combined value if the order supports one. What it must not do is return one head as "the latest": that silently drops a branch, and the caller has no way to learn that a second head existed.
saying these in an interview costs you the question
- Says a partial order has at most one maximal element
- Assumes a maximal element sits above every other element
- Uses 'the latest version' as though a maximum always exists
- Picks one maximal head arbitrarily and calls the conflict resolved
- Confuses minimal with minimum when reasoning in the other direction