Order and Lattices: When Things Have Rank

📍 Where we are: Part I · Logic from Scratch — Chapter 2. Sets, Relations, and Functions handed us pairs and mappings; now we watch one special kind of relation rank its own domain into a hierarchy — with a top, a bottom, and a well-defined "closest common ancestor" for any two things.

In the last chapter a relation was just a set of ordered pairs, a bag of "this is linked to that." Most relations are shapeless. But a few do something remarkable: they arrange their whole domain into a ladder, so that of any two elements you can often say which sits higher. The subclass relation does it perfectly. This chapter is about that shape, the order, and the two operations, meet and join, that make an order a machine you can compute with. They are the quiet engine under every hierarchy in this series.

We will not take "the join of two concepts is their nearest shared ancestor" on faith. We will define an order from three laws, build the full order from a handful of edges and watch the construction terminate step by step, derive the join and the meet as the unique solutions to a bounding problem, prove why adding a single bottom element is enough to complete this particular order into a lattice, and tie every one of those moves to the exact line of committed code that performs it. By the end the sentence join(professor, student) = researcher will not be a slogan; it will be a computation you can carry out by hand and check against a real program's output.

The simple version

Imagine a family tree of ideas instead of people. "Professor" and "student" both sit under "researcher," which sits under "person." Point at any two boxes and ask: what is the closest box above both? For professor and student it is researcher, their nearest shared ancestor. That question, "nearest shared ancestor," is the join; its mirror, "nearest shared descendant," is the meet. A structure where every pair has a clean answer to both is a lattice, and once you see it you see it everywhere: in class hierarchies, in confidence scores, in the geometry of the embeddings later volumes learn.

What this chapter covers

• From relation to order — the three laws (reflexive, antisymmetric, transitive), each written as a quantified statement and then verified line by line on the concept hierarchy person above researcher above professor and student.
• Building the full order — a worked trace of the reflexive-transitive closure that turns three covering edges into the nine-pair order, an ascending chain of sizes $7 \to 9 \to 9$ that halts on its own.
• Hasse diagrams — drawing an order with only its covering edges, dropping every edge that transitivity can recover.
• Bounds, joins, and meets — the join (least upper bound) as the least common subsumer, the meet (greatest lower bound) as its mirror, each derived as the unique solution to a bounding problem and each traced through the real code.
• Lattices and bounded lattices — when every pair has a join and a meet, why a meet can fail, and a short proof that for this order one bottom element ⊥ is exactly enough to repair it.
• Monotone maps and growing chains — order-preserving functions and the least upper bound of an ascending chain: the join stretched from a pair to a whole growing set, the groundwork the fixpoint chapters build on.
• Why this recurs — the subsumption order (Volume 2), the confidence lattice (Volumes 2 and 5), and box containment (Volume 3), all the same shape.

From a relation to an order: the three laws

Recall the setup from the previous chapter. A relation on a set $S$ is a subset of the Cartesian product $S \times S$, the set of all ordered pairs $(a, b)$ with $a$ and $b$ drawn from $S$. (The symbol $\in$ reads "is an element of," and $\subseteq$ reads "is a subset of," so writing $R \subseteq S \times S$ says every pair in $R$ is one of the possible pairs over $S$.) When a relation happens to obey three laws we stop calling it a relation and call it an order, and we switch to the symbol ≤. Before the symbols, the plain-language decoder: read a ≤ b here as "a is at least as specific as b," a sits below or at b in the hierarchy. So professor ≤ researcher says a professor is a special kind of researcher. Description-logic texts write the very same idea with a different symbol, professor ⊑ researcher, read "professor is subsumed by researcher"; ≤ and ⊑ are the same relation wearing two notations, and we use them interchangeably.

A partial order (mathematicians write "poset," short for partially ordered set) is a relation ≤ satisfying the following three laws, where the symbol $\forall$ reads "for all," $\land$ reads "and," and $\Rightarrow$ reads "implies" [1]:

• Reflexive: $\forall x \in S,\; x \le x$. Every concept is a special case of itself.
• Antisymmetric: $\forall a, b \in S,\; (a \le b \,\land\, b \le a) \Rightarrow a = b$. Two different concepts cannot each be below the other: no ties, no two-element cycles.
• Transitive: $\forall a, b, c \in S,\; (a \le b \,\land\, b \le c) \Rightarrow a \le c$. Below-ness carries through: a professor is a researcher, a researcher is a person, so a professor is a person.

The word "partial" is the honest part. A relation is a total order if it additionally satisfies $\forall a, b \in S,\; (a \le b) \lor (b \le a)$, where $\lor$ reads "or," meaning any two elements are comparable. The number line is total: given two distinct numbers, one is smaller. A partial order drops that demand. Some pairs are incomparable: neither $\text{professor} \le \text{student}$ nor $\text{student} \le \text{professor}$ holds, so professor and student sit side by side with neither below the other. That is not a defect; it is the whole point of a hierarchy that branches.

Building the full order from its covering edges

Our running academic world gives us a clean fragment to order. The companion file orders.py does not spell out the whole relation; it states only the covering pairs, the direct "sits immediately below" links (lines 18 to 23):

COVERS = [
    ("professor", "researcher"),
    ("student", "researcher"),
    ("researcher", "person"),
]
CONCEPTS = ["professor", "student", "researcher", "person"]

Three edges. Yet the full order ≤ has more pairs than that. It must contain every reflexive pair like ("professor", "professor"), because reflexivity demands $x \le x$, and it must contain every transitive consequence like ("professor", "person"), because $\text{professor} \le \text{researcher}$ and $\text{researcher} \le \text{person}$ force it. Building the full relation from the three edges uses the reflexive-transitive closure: start with the reflexive pairs and the covering pairs, then repeatedly add any pair that transitivity forces, until nothing new appears. The engine is relational composition, written with the small circle ∘: the composite $\le \circ \le$ contains $(a, c)$ whenever there is a middle element $b$ with $a \le b$ and $b \le c$, that is, whenever two single steps chain into one. Here is the closure loop (lines 26 to 33):

def leq_relation(covers, elements) -> set:
    """Reflexive-transitive closure of the covering pairs = the full ≤ order."""
    leq = {(x, x) for x in elements} | set(covers)
    while True:
        added = {(a, c) for (a, b) in leq for (b2, c) in leq if b == b2} - leq
        if not added:
            return leq
        leq |= added

Let us run it by hand and watch the relation grow. Write $|R|$ for the size of a relation $R$, the number of pairs it contains (the vertical bars $|\cdot|$ denote the count of elements in a set). The seed on line 28 unions the four reflexive pairs with the three covering pairs, and because those seven pairs are all distinct the seed has $|R_0| = 7$ pairs:

$$R_0 = \underbrace{\{(\text{prof},\text{prof}),\, (\text{stud},\text{stud}),\, (\text{res},\text{res}),\, (\text{pers},\text{pers})\}}_{\text{reflexive, } 4} \;\cup\; \underbrace{\{(\text{prof},\text{res}),\, (\text{stud},\text{res}),\, (\text{res},\text{pers})\}}_{\text{covers, } 3}.$$

The loop body on line 30 forms every composition $\le \circ \le$ over the current pairs and keeps only what is genuinely new (the - leq subtracts the pairs already present). On the first pass, the compositions through a shared middle element $b$ that produce a pair not already in $R_0$ are exactly two, both routed through researcher:

$$(\text{prof} \le \text{res}) \,\land\, (\text{res} \le \text{pers}) \;\Rightarrow\; \text{prof} \le \text{pers}, \qquad (\text{stud} \le \text{res}) \,\land\, (\text{res} \le \text{pers}) \;\Rightarrow\; \text{stud} \le \text{pers}.$$

So the first pass adds $\{(\text{prof},\text{pers}),\, (\text{stud},\text{pers})\}$, growing the relation to $|R_1| = 9$. On the second pass every composition lands on a pair that is already present (for instance $\text{prof} \le \text{pers}$ composed with $\text{pers} \le \text{pers}$ just gives $\text{prof} \le \text{pers}$ again), so added is empty and the function returns. The construction is a short ascending chain of sizes that reaches a fixpoint, a value the operator no longer changes:

| pass $t$ | what the loop body does | pairs added | $|R_t|$ | |---|---|---|---| | $0$ | seed: reflexive pairs ∪ covering pairs | — | $7$ | | $1$ | add transitive compositions $\le \circ \le$ | $(\text{prof},\text{pers}),\,(\text{stud},\text{pers})$ | $9$ | | $2$ | add transitive compositions $\le \circ \le$ | none | $9$ |

These are the real numbers: the seed is $7$ pairs, one pass takes it to $9$, and a confirming pass finds nothing, so the closure returns a nine-pair relation. (This is the same "grow until nothing new appears" recipe the running example uses at larger scale: its forward chaining reaches the $47$-atom model in cumulative waves of $23, 41, 47, 47$. Same machine, more edges.) The full order, all nine pairs, is most easily read as a table of ✓ marks, one row per possible lower element $a$, one column per possible upper element $b$, a ✓ exactly where $a \le b$:

$a \le b$	professor	student	researcher	person
professor	✓		✓	✓
student		✓	✓	✓
researcher			✓	✓
person				✓

Count the ticks: $3 + 3 + 2 + 1 = 9$, matching $|R_1|$ exactly. The empty cell at (professor, student) and its mirror at (student, professor) are the incomparable pair made visible.

Checking the three laws on the real relation

With the nine-pair relation in hand, verifying that it is a partial order is a direct transcription of the three laws, one Python line each (lines 43 to 48):

def is_partial_order(leq_set: set, elements) -> bool:
    reflexive = all((x, x) in leq_set for x in elements)
    antisym = all(a == b for (a, b) in leq_set if (b, a) in leq_set)
    transitive = all((a, c) in leq_set
                     for (a, b) in leq_set for (b2, c) in leq_set if b == b2)
    return reflexive and antisym and transitive

Each check reads straight off the table. Reflexivity (line 44) asks whether the four diagonal cells are ticked; they are. Antisymmetry (line 45) scans every ticked cell $(a, b)$ whose mirror $(b, a)$ is also ticked and demands $a = b$; the only mutually-ticked cells are the four diagonal ones, where $a = b$ holds by construction, so the law passes and there are no off-diagonal two-cycles. Transitivity (lines 46 to 47) reruns the composition check and confirms every chained pair is already present, for instance $(\text{prof},\text{res})$ and $(\text{res},\text{pers})$ compose to $(\text{prof},\text{pers})$, which is ticked. Running the module prints the verdict on its first line:

is a partial order: True

Hasse diagrams: drawing an order without its clutter

Drawn as arrows, the full nine-pair order is a hairball: professor points at researcher, at person, and at itself. A Hasse diagram is the tidy alternative. To define it precisely we need the strict part of the order and the covering relation. Write $a \lt b$ (strictly below) to mean $a \le b$ and $a \ne b$; this strips off the four reflexive pairs, leaving the five strict pairs. Then $a$ is covered by $b$ when $a \lt b$ and there is no intermediate $c$ with $a \lt c \lt b$: nothing sits strictly between them. A Hasse diagram draws only the covering edges, places more general concepts higher, and lets your eye recover everything else by walking upward.

The bookkeeping is exact. The full order has nine pairs; drop the four reflexive loops to get five strict pairs; of those, drop the two that a middle element bridges, $(\text{prof},\text{pers})$ and $(\text{stud},\text{pers})$, both bridged by researcher. What remains is three covering edges, exactly the three pairs in COVERS. The edge professor → person is never drawn: you can already walk there through researcher, so transitivity does the work the ink need not.

The concept hierarchy of the academic world as a Hasse diagram: only the direct edges are drawn, height encodes generality, and researcher is visibly the nearest box above both professor and student. Original diagram by the authors, created with AI assistance.

Read top to bottom and the order reads off at a glance: person is most general, professor and student most specific, researcher the hinge between them. This picture is the structure the rest of the chapter computes on.

Bounds, joins, and meets

Take two elements, $a$ and $b$. An upper bound of them is any element $x$ that sits above both, meaning $a \le x$ and $b \le x$ hold together. The least upper bound, when a single smallest one exists, is the join, written a ⊔ b (read "a join b"). Precisely, $j$ is the join of $a$ and $b$ when it is an upper bound and it is below every other upper bound: $a \le j$, $b \le j$, and $j \le x$ for every upper bound $x$. In a concept hierarchy the join has a name you will meet again and again: the least common subsumer (LCS), the most specific concept that still contains both. Mirror every word for the other operation: a lower bound sits below both, $x \le a$ and $x \le b$, and their greatest lower bound is the meet, written a ⊓ b (read "a meet b").

One fact makes both operations well-defined: when a join exists, it is unique. Suppose $j_1$ and $j_2$ were both least upper bounds of $a$ and $b$. Each is an upper bound, and each is below every upper bound, so $j_1 \le j_2$ (because $j_1$ is least and $j_2$ is an upper bound) and $j_2 \le j_1$ (symmetrically). Antisymmetry, the second law, then forces $j_1 = j_2$. So "the" join is a legitimate phrase, and the same argument makes "the" meet unique. This is exactly why the code can return a single value or None and never has to choose among rivals.

The code is that definition, almost verbatim. Upper bounds are a filter (lines 51 to 52); the join keeps only the bound that is below every other bound (lines 55 to 59):

def upper_bounds(a, b, elements):
    return [x for x in elements if leq(a, x) and leq(b, x)]


def join(a: str, b: str, elements=CONCEPTS):
    """Least upper bound (least common subsumer), or ``None`` if none is least."""
    ubs = upper_bounds(a, b, elements)
    least = [x for x in ubs if all(leq(x, y) for y in ubs)]
    return least[0] if len(least) == 1 else None

The subtlety is the middle line of join: least keeps every upper bound $x$ that is below all the upper bounds, which is the definition of "least" applied to the finite set ubs. The uniqueness we just proved has a sharp consequence for the last line. The list least can never hold two distinct elements, because two distinct elements each below the other would violate antisymmetry. So len(least) is always $0$ or $1$: it is $1$ when the least upper bound exists and $0$ when it does not. The guard if len(least) == 1 else None is therefore not a heuristic; it is the exact test "does a least upper bound exist?", and the None branch fires precisely when the answer is no. That "or None" is where the honesty lives, and the next section is where it bites.

The worked run: a join that lands, a meet that fails

Here is the whole point of the module, in three lines of real output (produced by lines 76 to 78):

join(professor, student) = researcher
meet(professor, student) = None
join(professor, person)  = person

Trace each one against the ✓ table. For join(professor, student), upper_bounds scans the four concepts and keeps those above both. Reading the professor and student rows of the table, the columns ticked in both rows are researcher and person, so ubs = ['researcher', 'person']. Now the least filter asks, of each of those, whether it lies below every element of ubs:

• researcher: $\text{researcher} \le \text{researcher}$ ✓ and $\text{researcher} \le \text{person}$ ✓, so it survives.
• person: $\text{person} \le \text{researcher}$ is false (the (person, researcher) cell is empty), so it is dropped.

least = ['researcher'], length $1$, and the function returns researcher. This is the least common subsumer at work: the upper bounds are researcher and person, but researcher is below person, so researcher is the nearest shared ancestor, exactly the hinge the Hasse diagram showed.

For join(professor, person), the professor and person rows share ticks only in the person column, so ubs = ['person'], the least filter keeps it, and the join is person. This is the easy case: person is already above professor, so the nearest thing above both is person itself.

meet(professor, student) = None is the honest failure. The mirror-image code (lines 62 to 71) filters the lower bounds and keeps their greatest:

def lower_bounds(a, b, elements):
    return [x for x in elements if leq(x, a) and leq(x, b)]


def meet(a: str, b: str, elements=CONCEPTS):
    """Greatest lower bound, or ``None`` (e.g. professor and student share no
    common sub-concept — their meet would be ⊥, which we have not added)."""
    lbs = lower_bounds(a, b, elements)
    greatest = [x for x in lbs if all(leq(y, x) for y in lbs)]
    return greatest[0] if len(greatest) == 1 else None

lower_bounds(professor, student) scans for any $x$ with $x \le \text{professor}$ and $x \le \text{student}$. Reading down the professor column, only professor is ticked; down the student column, only student. No single concept appears in both, so lbs = []. With an empty list greatest is empty too, its length is $0$, and the meet is None. There is genuinely no concept below both professor and student. Nothing in our world is simultaneously both: the professors are alice and bob, the students carol, dave, and erin, two disjoint groups, so the common lower bounds are empty and the meet does not exist. In the hierarchy's language professor ⊓ student would be the concept whose members are both, and it has none: the empty, impossible concept. The meet is not wrong; it is genuinely absent, and the code says None rather than invent an answer.

Lattices and bounded lattices: repairing the gaps

A lattice is a partial order in which every pair has both a join and a meet [1][2]. Our four-concept order is not quite one. Every pair does have a join, because you can always climb to a shared ancestor, at worst person, so it is a join-semilattice with person as its highest element. But the meet of professor and student is missing, so it fails the full lattice test.

The repair is two special elements. The top, written ⊤, sits above everything, $\forall x,\; x \le \top$; in a class hierarchy it is the universal concept "Thing." The bottom, written ⊥, sits below everything, $\forall x,\; \bot \le x$; it is the empty, unsatisfiable concept "Nothing" with no members at all. Add ⊥ beneath professor and student and their meet is no longer missing: it is ⊥, exactly the "concept with no members" we just described.

Now the careful part. A bounded lattice is a lattice that additionally carries a ⊤ and a ⊥ [2]. Mind the order of the words: it must already be a lattice before the two anchors are named. Bolting a ⊤ and ⊥ onto an arbitrary poset does not conjure the missing bounds. Two incomparable elements can share several incomparable upper bounds and still have no single least one, top or no top, so the join can fail even with ⊤ present. What rescues our order is a specific structural fact, and it is worth proving rather than asserting.

Claim. A finite join-semilattice with a bottom element ⊥ is a full lattice: every pair $a, b$ acquires a meet.

Proof. Let $L(a, b)$ be the set of common lower bounds of $a$ and $b$. It is nonempty, since $\bot \in L(a, b)$, and finite, since the whole order is. In a join-semilattice every finite nonempty set has a least upper bound, computed by folding the binary join over its elements: because ⊔ is associative and commutative, the iterated pairwise join is independent of the order in which the elements are combined, and, by induction on the (finite) size of the set, that fold equals the least upper bound of the whole set. So let $m = \bigsqcup L(a, b)$ be the join of all the common lower bounds. We show $m$ is the greatest lower bound of $a$ and $b$, in two steps. First, $m$ is itself a lower bound of $a$ and $b$. Every element of $L(a, b)$ is below $a$, so $a$ is an upper bound of the set $L(a, b)$; since $m$ is the least upper bound of that set, $m \le a$, and likewise $m \le b$. Hence $m$ is a common lower bound, $m \in L(a, b)$. Second, $m$ is the greatest such. Any common lower bound $\ell \in L(a, b)$ satisfies $\ell \le m$, because $m$ is an upper bound of the whole set $L(a, b)$. So $m$ is a lower bound that dominates every other lower bound: the greatest lower bound, the meet. $\blacksquare$

This is exactly the situation of our order. It is already a finite join-semilattice (the hierarchy is tree-shaped, so any two elements have a unique nearest ancestor, hence a well-defined join), and its top person was there from the start. Adding a single bottom ⊥ satisfies the hypothesis of the claim, so every pair now gets a meet, and the order becomes a genuine bounded lattice. The meet of professor and student, formerly None, becomes $\bigsqcup \{\bot\} = \bot$, matching the promise in the meet docstring. That is the specific reason ⊥ completes this order, not a general law that ⊤ and ⊥ complete every order. The academic-world fragment ships without that ⊥ on purpose, so meet(professor, student) returns None, showing you the gap before it shows you the patch.

Monotone maps and growing chains: the least fixpoint in miniature

So far we have joined two elements. Two further ideas let an order compute over whole growing collections, and they are the exact groundwork the next chapters build fixpoints on.

The first is a monotone map, also called an order-preserving function: a function $f$ from one ordered set $(P, \le_P)$ to another $(Q, \le_Q)$ such that $\forall a, b \in P,\; a \le_P b \Rightarrow f(a) \le_Q f(b)$. It never scrambles rank. Our world has a natural one: send each concept to its extension, the set of individuals that belong to it. Because $\text{professor} \le \text{researcher}$ and every professor is a researcher, we get $\text{members}(\text{professor}) \subseteq \text{members}(\text{researcher})$, that is $\{\text{alice}, \text{bob}\} \subseteq \{\text{alice}, \text{bob}, \text{carol}, \text{dave}, \text{erin}\}$. The map from concepts ordered by ≤ to member-sets ordered by ⊆ preserves the order: climb the concept hierarchy and the extensions can only grow, never shrink.

The second is the least upper bound of a growing set. Stretch the join from a pair to an ascending chain, a sequence $X_0 \le X_1 \le X_2 \le \cdots$ that only grows, whose least upper bound (its supremum) is the smallest element sitting above the whole chain at once.

You have already run one. The leq_relation loop, traced above, is precisely an ascending chain in the lattice of relations ordered by ⊆: each pass produces a relation containing the previous one, $R_0 \subseteq R_1 \subseteq R_2$, with the concrete sizes $7 \to 9 \to 9$ we computed (the ⊆ relates the relations; the sizes are just their integer counts). The loop halts at that chain's least upper bound, the smallest reflexive, transitive relation containing the covering pairs (the reflexive-transitive closure, whose seed $R_0$ already carries the four reflexive pairs), which is the least fixpoint of a monotone operator (the operator "add every composition"). Start at the bottom, apply a monotone operator until nothing new appears, then take the least upper bound of the growing chain: that recipe is how every reasoner in this series actually computes, and the next chapter names it outright.

Why this shape keeps coming back

The reason we spend a whole chapter on so small an idea is that this same structure, a partial order, ideally a bounded lattice, with join and meet, is load-bearing across the entire series:

• The subsumption order (Volume 2). An ontology's classes form exactly this order under ⊑, and the job of a description-logic reasoner is to compute it. The join is again the least common subsumer; asking "what is the most specific class above both A and B?" is a query an EL reasoner answers by climbing the very hierarchy we drew by hand here.
• The confidence / annotation lattice (Volumes 2 and 5). When facts carry truth values, certain, probable, unknown, contradictory, those values themselves form a lattice, and combining two pieces of evidence is a meet or a join in that lattice. Reasoning with graded truth is reasoning inside an order.
• Box containment as an order (Volume 3). When concepts are learned as regions of space, boxes, one box being inside another is the ≤ relation, geometrically, and the join of two boxes is the smallest box enclosing both: a least common subsumer made of coordinates instead of symbols. This bridge from orders to knowledge hierarchies is what formal concept analysis first mapped out [3].

That last bullet is the thesis. The join is not logic trivia; it is a contract. The symbolic reasoner computes join(professor, student) = researcher by walking edges; the neural embedding must reach the same answer by intersecting regions. When both agree, the neuro-symbolic system is coherent. When they disagree, one of them is lying.

The unsolved part

Here the join was exact and instant, because the order was tiny, hand-drawn, and handed to us as three covering pairs. Two things shatter that comfort at scale. First, in a genuinely expressive concept language the least common subsumer of two classes need not exist as any named concept: the honest answer may be an anonymous, sprawling description that grows exponentially as you compose more concepts, so "just compute the join" stops being cheap or even finite. Second, and more sharply for this series, a neural embedding places concepts in continuous space and can only approximately honor meet and join. The containment it learns by geometry may fail to honor the intended subsumption facts, leaving professor's box only partly inside researcher's, so the target relation professor ⊑ researcher is no longer preserved, or letting two concepts overlap in ways the symbolic order forbids. Whether a learned geometry can respect a lattice exactly and provably, not just on average, is one of the open questions the whole neuro-symbolic program circles back to. This chapter gives you the yardstick; later volumes measure the gap.

Why it matters

Every hierarchy you will meet in neuro-symbolic AI, the class taxonomy a reasoner walks, the confidence values a probabilistic layer combines, the boxes an embedding learns, is a partial order, and the interesting computation on any of them is a join or a meet. Getting this one abstraction right buys three payoffs: a vocabulary ("join equals least common subsumer") identical whether you do symbolic subsumption or geometric containment; a diagnostic (does my embedding's join match my reasoner's join?) for whether the two halves of a hybrid system agree; and an early warning (a meet returning None) that a hierarchy is missing its bottom. When the neural and symbolic sides respect the same order, they can be trusted to describe the same world, the entire promise this book is building toward.

Key terms

• Partial order (poset) — a relation ≤ that is reflexive, antisymmetric, and transitive; it ranks a domain while allowing incomparable pairs.
• Reflexive, antisymmetric, transitive — the three defining laws: $x \le x$; $a \le b$ and $b \le a$ force $a = b$; $a \le b$ and $b \le c$ give $a \le c$.
• Incomparable — two elements where neither is below the other (professor and student); the reason an order is "partial."
• Reflexive-transitive closure — the smallest reflexive, transitive relation containing a set of edges; built here by iterating composition until a fixpoint (sizes $7 \to 9 \to 9$).
• Relational composition (∘) — chaining two steps into one: $a \le b$ and $b \le c$ yield the composed pair $a \le c$.
• Covering pair / Hasse diagram — a direct "sits immediately below" edge ($a \lt b$ with nothing strictly between), and the diagram that draws only those edges, recovering the rest by transitivity.
• Upper / lower bound — an element above (below) both of two given elements.
• Join (⊔) / least common subsumer — the least upper bound: the most specific element above both, unique when it exists. In the concept hierarchy, join(professor, student) = researcher.
• Meet (⊓) — the greatest lower bound: the most general element below both; meet(professor, student) is absent here without a bottom.
• Lattice / join-semilattice / bounded lattice — a poset where every pair has a join and a meet; a join-semilattice has only every join; bounded adds a top ⊤ and a bottom ⊥ to a lattice.
• Top ⊤ / bottom ⊥ — the universal element above everything ("Thing") and the empty element below everything ("Nothing").
• Monotone map (order-preserving function) — a function $f$ between ordered sets with $a \le b$ implying $f(a) \le f(b)$; it never scrambles rank. Sending each concept to its set of members is one.
• Ascending chain / least upper bound of a growing set — a sequence $X_0 \le X_1 \le X_2 \le \cdots$ that only grows, and the smallest element above all of it at once: the join generalized from a pair to an unbounded sequence, and the seed of the least fixpoint.

Where this leads

We now have the shape of a hierarchy, the two operations that compute on it, and, through monotone maps and the least upper bound of a growing chain, the seed of the least fixpoint every reasoner in this series leans on. But an order tells you how concepts rank; it does not yet tell you how to combine statements into true or false conclusions. The next chapter, Propositional Logic: True, False, and What Follows, introduces the smallest complete logic, atoms joined by ∧, ∨, and ¬ (read "and", "or", "not"), and, satisfyingly, its truth values will turn out to form a bounded lattice of their own, with ⊤ and ⊥ exactly where we just put them, while forward chaining reappears as the least upper bound of a growing set of derived facts. The order does not disappear; it becomes the scaffolding truth hangs on.

---

Companion code: examples/logic/orders.py builds the concept order from its covering pairs (leq_relation), checks the three laws (is_partial_order), and computes joins and meets (join, meet). Run python3 examples/logic/orders.py to reproduce every number in this chapter: the "is a partial order: True" verdict, join(professor, student) = researcher, meet(professor, student) = None, and join(professor, person) = person.