Equivalence Relations · step 9 of 13

Equivalence closure of a relation

The equivalence closure of R is the smallest equivalence relation containing it, computed as the transitive closure of R ∪ R⁻¹ ∪ Δ. The order matters: transitivity must come last, because symmetrising after closing transitively can destroy transitivity. Its classes are exactly the connected components of the underlying undirected graph, which is what union-find algorithms compute.

Practise equivalence closure of a relation free → All Equivalence Relations subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Add the diagonalInclude (a,a) for every element to force reflexivity.
SymmetriseUnion with R⁻¹ so every arrow becomes bidirectional.
Close transitively, lastIterate adding shortcuts until nothing changes. Doing this before symmetrising gives the wrong answer.
Read off the componentsThe classes are the connected components of the graph whose edges are the pairs of R, ignoring direction.

Worked example

Find the equivalence closure of R = {(1,2),(3,4),(4,5)} on {1,2,3,4,5,6}.

Treat the pairs as undirected edges: 1–2, 3–4, 4–5, with 6 isolated.
Connected components: {1,2}, {3,4,5}, {6}.
These components are the classes of the closure.
The relation is all pairs within a component: 4 + 9 + 1 = 14 ordered pairs.

Answer. Classes {1,2}, {3,4,5}, {6} — the closure has 14 ordered pairs, and the quotient set has three elements.

Where marks get dropped

These are the specific errors that cost credit on equivalence closure of a relation questions — QED's rubric penalises each of them separately.

Closing transitively before symmetrising, which can leave the result non-transitive after the symmetric step.
Forgetting isolated elements. Element 6 relates to nothing in R but must form its own class for reflexivity.
Adding pairs that are not forced. The closure is the SMALLEST such relation, so every added pair must be justified.

Practise this until it is automatic

Unlimited fresh questions

QED generates new equivalence closure of a relation problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Equivalence Relations mastery is tracked so you know when this is exam-ready.

Equivalence closure of a relation — frequently asked questions

Why are the classes the connected components?

Because symmetrising makes the graph undirected and transitive closure connects anything joined by a path. Two elements end up related exactly when a path joins them.

What algorithm computes this efficiently?

Union-find (disjoint-set union). Each pair triggers a union operation, and with path compression the total cost is near-linear — far better than computing the transitive closure explicitly.

Does the closure always exist?

Yes, because equivalence relations are closed under intersection: the intersection of all equivalence relations containing R is itself one, and is the smallest.

The rest of Equivalence Relations

Equivalence classes, partitions and quotient sets. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make equivalence closure of a relation exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →