Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 68 ยท Sets, Relations and Functions

Equivalence Relations and Partial Orders

Equivalence classes and partitions, partial and total orders, Hasse diagrams drawn with matplotlib, lattices and topological sorting, all in Python.

Of the many relations you can write down, two families do most of the work in mathematics and computing. Equivalence relations say "these things are the same for my purposes": same remainder, same file type, same connected component. Partial orders say "this comes before or below that": divisibility, subset inclusion, task dependencies.

Both families are defined by combinations of the properties from Relations. In this lesson you will see how an equivalence relation splits a set into classes, how a partial order can be drawn as a compact Hasse diagram, and how a dependency graph is turned into a valid order of work with a topological sort.

Equivalence relations

A relation is an equivalence relation if it is reflexive, symmetric and transitive. Familiar examples: equality; "has the same birthday as"; "is congruent to modulo 5"; "is in the same group as".

The central fact is that an equivalence relation chops its set into pieces. The equivalence class of an element a is the set of everything related to a: [a] = {x : x R a}. Two key properties follow from the three axioms:

  • Every element belongs to its own class (reflexivity).
  • Two classes are either identical or completely disjoint.

So the classes form a partition of the set, exactly as defined in Power Sets and Cartesian Products. The correspondence also runs backwards: any partition defines an equivalence relation (relate two elements when they sit in the same block). Equivalence relations and partitions are two descriptions of the same structure.

The classic example is congruence modulo n. On the integers, a โ‰ก b (mod 3) splits everything into three classes: multiples of 3, numbers one above a multiple of 3, and numbers two above. Clock arithmetic is built on this idea, as you will see in Modular Arithmetic.

Python Equivalence classes of congruence mod 3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The helper classes works because of the two class properties above: it only has to compare a new element with one representative of each existing class.

Equivalence relation

Reflexive a is related to a.
Symmetric Related both ways.
Transitive Chains collapse.

Together they split the set into classes.

1 / 2

Partial orders

A relation is a partial order if it is reflexive, antisymmetric and transitive. A set together with a partial order is called a partially ordered set, or poset. Typical posets:

  • Numbers under โ‰ค.
  • Positive integers under divisibility: 3 divides 12, so 3 comes "below" 12.
  • Subsets of a set under โІ.
  • Tasks under "must happen before".

The word partial matters. Two elements a and b are comparable if a โ‰ค b or b โ‰ค a. In a partial order some pairs can be incomparable: under divisibility, neither 4 divides 6 nor 6 divides 4. When every pair is comparable the order is total (or linear), like the usual โ‰ค on numbers: you can always line the elements up on a single line.

A few vocabulary items for an element x of a poset:

  • Minimal element: nothing is strictly below it. Maximal: nothing is strictly above it.
  • Least element: below everything. Greatest: above everything. A least or greatest element, if it exists, is unique; minimal and maximal elements may be many.
  • Element y covers x if x < y and nothing sits strictly between them.

Hasse diagrams

The full list of pairs of a partial order is cluttered: it has self-loops and all the shortcuts implied by transitivity. A Hasse diagram removes the clutter. Draw one dot per element, place smaller elements lower, and draw a line only between an element and the elements that cover it. Because the direction is always upward, no arrowheads are needed, and reflexive and transitive pairs can be read off from the picture.

The program below draws the divisors of 12 ordered by divisibility. It computes the covering pairs and assigns each element a height equal to the length of the longest chain below it.

Python A Hasse diagram of the divisors of 12

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The diagram shows 1 at the bottom (the least element) and 12 at the top (the greatest). 4 and 6 are incomparable, and so are 2 and 3: they sit side by side with no upward path joining them. Reading "is there a path going up from a to b?" answers "does a divide b?".

Total orders and linear extensions

Python's sorted needs a total order, so every pair must be comparable. With only a partial order, you cannot sort directly, but you can often extend it: a linear extension is a total order that respects all the original relationships. For tasks with prerequisites, a linear extension is a valid schedule.

Lattices, briefly

In some posets every pair of elements has a best common lower bound and a best common upper bound. The meet a โˆง b is the greatest element below both; the join a โˆจ b is the least element above both. A poset where all meets and joins exist is a lattice.

The divisors of 12 form a lattice: the meet of two divisors is their greatest common divisor, and the join is their least common multiple. The meet of 4 and 6 is 2, and their join is 12. Subsets of a set under inclusion form a lattice too, with intersection as meet and union as join. Lattices reappear as Boolean algebras in Boolean Algebra and Logic Circuits.

Topological ordering

A topological sort puts the elements of a poset (or any directed acyclic graph) into a line so that if a must come before b, then a appears earlier in the list. The standard method, Kahn's algorithm, repeatedly takes an element with no remaining prerequisites, outputs it and removes it.

Python Scheduling with a topological sort

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The order is not unique: "shower" and "make coffee" could swap, and every valid list is a different linear extension of the same partial order. When tasks contain a cycle ("a before b before a") there is no valid order at all, because a partial order cannot contain such a loop; the algorithm detects it when some tasks never become ready.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which set of properties defines an equivalence relation?

    Equivalence relations are reflexive, symmetric and transitive. The first option describes a partial order.
  2. 2. Two distinct equivalence classes of the same relation...

    If two classes shared an element, transitivity and symmetry would force every member of one to be related to every member of the other, making the classes identical. So different classes never overlap.
  3. 3. In the divisibility order on {1, 2, 3, 4, 6, 12}, which pair is incomparable?

    3 does not divide 4 and 4 does not divide 3, so neither element is below the other. Every other listed pair has one dividing the other.
  4. 4. What does a Hasse diagram leave out compared with the full relation?

    It draws only the covering pairs, with smaller elements lower. Self-loops and shortcut edges are implied, and direction is shown by height.
  5. 5. When does a topological ordering of tasks not exist?

    A cycle such as a before b before a cannot be arranged in a line. Incomparable tasks are fine, since they can go in either order.

Summary

  • An equivalence relation is reflexive, symmetric and transitive; its classes partition the set, and every partition defines an equivalence relation.
  • Congruence modulo n is the standard example, with n classes of integers.
  • A partial order is reflexive, antisymmetric and transitive; elements may be incomparable, and a total order has no incomparable pairs.
  • A Hasse diagram draws only the covering pairs, with smaller elements lower; divisors under divisibility form a lattice with gcd as meet and lcm as join.
  • A topological sort lists elements so prerequisites come first; it exists exactly when there is no cycle, and it is not unique.

Next: Functions and Cardinality, where a relation assigns each input exactly one output.