5.2 Equivalence Relations and Partial Orders: Classification, Dependencies, and Lattices

Some relationships group objects into the same category, such as "two requests have the same normalized URL"; others express sequence or containment, such as "task A must complete before task B." The former leads to equivalence relations, the latter to partial orders.

Equivalence relations produce classification

The equivalence relation ~ on the set A simultaneously satisfies:

Reflexive: a~a
Symmetry: a~b → b~a
Transitivity: a~b ∧ b~c → a~c

The equivalence class of element a:

[a]={x∈A | x~a}

For a fixed positive integer n, congruence modulo n:

a≡b (mod n) ⇔ n | (a-b)

It partitions the integers into n residue classes. For modulus 3:

[0], [1], [2]

Each integer belongs to exactly one class.

Equivalence Relations and Partitions Are Mutually Corresponding

A partition of set A is a collection of non-empty subsets that satisfies:

• The subsets are pairwise disjoint;
• Their union is A.

The equivalence classes formed by an equivalence relation constitute a partition. Conversely, given a partition, we can define:

a ~ b ⇔ a and b lie in the same subset

This relation is necessarily an equivalence relation.

Thus, "choosing representative objects" typically involves two layers:

1. Defining which objects are considered equivalent;
2. Selecting a canonical representative for each equivalence class.

URL normalization, compiler common subexpression elimination, and cache key design all perform similar tasks. Normalization functions must ensure that equivalent objects map to the same representative, while avoiding the erroneous merging of objects that are not actually equivalent.

For example, explicitly define a~b ⇔ a.casefold()==b.casefold(). A deterministic transformation at a fixed version induces reflexive, symmetric, and transitive output equality. Python 3 casefold maps German ß to ss:

words = ["Straße", "STRASSE", "strasse", "Street"]
groups = {}
for word in words:
    groups.setdefault(word.casefold(), []).append(word)
print(groups)
# {'strasse': ['Straße', 'STRASSE', 'strasse'], 'street': ['Street']}

This checks the classification induced by the chosen key, not its suitability for every application. It performs no Unicode normalization and defines no email or URL case policy. Persistent keys also need compatibility consideration when Unicode data versions change.

Programmatic Equality and Hashing

The equals method should define an equivalence relation on non-null object references. The Java 21 Object contract requires reflexivity, symmetry, transitivity, and consistency while relevant fields remain unchanged; equal objects must also have equal hash codes.

A fixed, stable hash function does induce an equivalence relation through equal hash values, but that relation is generally coarser than object equality: unequal objects can land in the same class. The required implication is:

a.equals(b) → a.hashCode() == b.hashCode()

The reverse does not hold. Treating hash values as unique identifiers may cause the merging of objects that are not actually equal.

Floating-point numbers, proxy objects, cross-type values, and mutable fields complicate equality design. Once an object is inserted into a hash collection, its state involved in equality and hashing must not be modified.

Partial Order: Allows Incomparability

A partial order ≤ on set A satisfies:

Reflexive: a ≤ a
Antisymmetric: a ≤ b ∧ b ≤ a → a = b
Transitive: a ≤ b ∧ b ≤ c → a ≤ c

(A,≤) is called a partially ordered set (poset).

Set inclusion ⊆ is a partial order. Two sets {read} and {write} are mutually non-contained, so they are incomparable. A partial order does not require that every pair of elements be comparable.

If for every pair a,b, either a≤b or b≤a holds, then the order is a total order. The standard integer ordering ≤ is a total order.

A strict partial order can be derived from:

a < b ⇔ a ≤ b ∧ a ≠ b

which is irreflexive and transitive.

Hasse Diagrams Omit Implied Edges

A finite partial order can be represented using a Hasse diagram:

• No reflexive loops are drawn;
• Edges that can be inferred via transitivity are omitted;
• Larger elements are typically placed higher in the diagram.

For the power set 𝒫({a,b}) ordered by inclusion:

      {a,b}
      /   \
    {a}   {b}
      \   /
        ∅

∅⊆{a,b} has no direct edge because it can be derived from either {a} or {b}.

Don't Confuse Minimum, Minimal, and Least Upper Bound

• Minimum element: m≤x holds for all x; if it exists, it is unique;
• Minimal element: no other element is strictly less than it; multiple such elements may exist;
• Maximum / maximal: dual definitions.

In a task dependency partial order, there may be multiple currently executable minimal tasks, yet no unique minimum task.

For the set S:

• An upper bound u satisfies that for all s∈S, we have s≤u;
• The least upper bound (join) is the smallest among all upper bounds;
• Lower bounds and the greatest lower bound (meet) are dual concepts.

The "least upper bound" is not necessarily the minimum element of S, and it may not even belong to S.

Lattices Have Join and Meet for Every Pair

If every pair of elements in a poset has a unique least upper bound and greatest lower bound, then the structure is called a lattice.

The power set forms a lattice under inclusion:

A ∨ B = A∪B   // join
A ∧ B = A∩B   // meet

On a fixed universe’s power set, adding complement, the empty set, and the universe yields a Boolean algebra. Data-flow analysis can organize abstract states in a lattice and join incoming states. On a finite-height lattice, iteration from the bottom along an ascending chain with monotone transfer functions reaches a fixed point; infinite-height domains may need widening. Being a lattice alone does not guarantee termination.

A "lattice" is not just any hierarchical structure. If any pair of elements lacks a unique join or meet, it fails to be a lattice.

Dependency Graph and Topological Order

Reachability by positive-length paths in a directed acyclic graph forms a strict partial order; including zero-length paths gives its reflexive, non-strict order. A topological sort provides a linear ordering compatible with this partial order: if a must come before b, then a appears before b in the sorted sequence.

Tasks that are incomparable can be ordered in multiple ways, so a topological order may not be unique. The detection of a cycle indicates that a strict dependency ordering is impossible; the build system should report the cycle path, rather than arbitrarily breaking an edge.

Python 3.9+ graphlib accepts a map from each node to its predecessors, the reverse of many adjacency lists. This checks dependency constraints and the last task without assuming an order between independent tasks:

from graphlib import TopologicalSorter, CycleError

predecessors = {"build": {"lint", "test"}, "lint": set(), "test": set()}
order = tuple(TopologicalSorter(predecessors).static_order())
positions = {task: i for i, task in enumerate(order)}
assert all(positions[p] < positions[task]
           for task, parents in predecessors.items() for p in parents)
print(order[-1])  # build; lint and test may appear in either order.
try:
    tuple(TopologicalSorter({"A": {"B"}, "B": {"A"}}).static_order())
except CycleError:
    print("cycle")

Strict ancestry in an ordinary tree is a strict partial order; including each node itself makes it non-strict. Following symbolic links as extra edges may introduce cycles. Multiple paths alone do not invalidate a partial order; acyclicity is the relevant condition.

Subtypes Are Often Preorders

Subtypes typically satisfy reflexivity and transitivity, but two syntactically distinct types may still be subtypes of each other. If we do not treat mutually subtype types as equivalent classes, antisymmetry need not hold based on syntactic equality. Therefore, in formal contexts, the subtype relationship is often initially called a preorder, and then quotiented over types that are interchangeable to yield a partial order.

Actual language rules also involve variance, structural versus nominal types, and null, and cannot be fully captured by a simple set-inclusion diagram.

Completion Check

1. Prove that congruence modulo 5 is an equivalence relation, and list five equivalence classes;
2. Define "case-insensitive equality" for strings, and explain how to choose a canonical representative;
3. Draw the Hasse diagram for 𝒫({a,b,c});
4. Find the join and meet of {a} and {b,c};
5. Provide two different topological orders for a dependency graph with five tasks;
6. Construct a poset with multiple minimal elements but no minimum element.

References

• MIT Mathematics for Computer Science