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}

Congruence modulo n:

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

It divides integers into n residue classes modulo 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.

Programmatic Equality and Hashing

If an object's equals is used as a key in collections or Maps, it must exhibit equality semantics. Java's contract requires equality to be reflexive, symmetric, transitive, and consistent; additionally, equal objects must have the same hashCode.

However, hashCode does not define an equivalence relation: different objects can collide on hash values. The correct direction 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

The partial order A on set ≤ 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).

A set containing ⊆ 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 Diagram Removal of Deducible 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.

Make join and meet operations work

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

Adding complements, the empty set, and the full set yields a Boolean algebra. In data flow analysis, abstract states are often organized into lattices, where join operations combine states from different control flow paths, and iteration converges to a fixed point.

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

The reachability relation in a directed acyclic dependency graph forms a strict partial 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.

If a file system only considers the "ancestry" relationship within a plain tree, it can form a partial order. However, with symbolic links included, cycles or multiple paths may emerge, making it no longer equivalent to the partial order of the directory tree.

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 does 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 minimal element.

References

• MIT Mathematics for Computer Science