Relations · step 5 of 13

Reflexive & transitive closures

The closure of R with respect to a property is the smallest relation containing R that has it. Reflexive closure adds exactly the missing loops: R ∪ Δ. Transitive closure R⁺ adds shortcut pairs until no new ones appear, and equals the union of all positive powers of R. The word "smallest" is load-bearing — adding extra pairs gives a relation with the property but not the closure.

Practise reflexive & transitive closures free → All 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.

Reflexive closure — add the diagonalR ∪ {(a,a) : a ∈ A}. Nothing else is needed, and nothing else may be added.
Symmetric closure — add the reversesR ∪ R⁻¹. Again exactly the missing pairs.
Transitive closure — iterateRepeatedly add (a,c) whenever (a,b) and (b,c) are present, including pairs added in earlier rounds. Stop when a full pass adds nothing.
Verify minimalityEvery added pair must be forced by the property. If you can delete a pair and still have the property while containing R, you added too much.

Worked example

On {1,2,3,4} let R = {(1,2),(2,3),(3,4)}. Find the transitive closure R⁺.

Round 1: (1,2) and (2,3) force (1,3); (2,3) and (3,4) force (2,4).
Now R has {(1,2),(2,3),(3,4),(1,3),(2,4)}.
Round 2: (1,3) and (3,4) force (1,4).
Round 3: no new chains produce anything absent, so we stop.

Answer. R⁺ = {(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)} — exactly the pairs (i,j) with i < j.

Where marks get dropped

These are the specific errors that cost credit on reflexive & transitive closures questions — QED's rubric penalises each of them separately.

Stopping after one pass. Newly added pairs create new chains, so iteration must continue until a pass changes nothing.
Adding loops to the transitive closure. (a,a) belongs only if a genuine cycle through a exists — transitive closure is not reflexive by default.
Confusing the transitive closure R⁺ with the reflexive-transitive closure R*. The second is R⁺ ∪ Δ.

Practise this until it is automatic

Unlimited fresh questions

QED generates new reflexive & transitive closures 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 Relations mastery is tracked so you know when this is exam-ready.

Reflexive & transitive closures — frequently asked questions

Why is R⁺ the union of the powers of R?

Because (a,b) ∈ Rⁿ exactly when a path of length n runs from a to b, and transitivity is precisely the requirement that every path has a direct edge. Uniting over all n ≥ 1 collects them all.

How many rounds are needed on an n-element set?

At most n − 1, since the longest simple path has n − 1 edges. Warshall’s algorithm computes the closure in O(n³) without iterating to a fixed point.

Is there an antisymmetric closure?

No. Antisymmetry is not preserved under unions, so there is generally no smallest antisymmetric relation containing R — closures exist only for properties closed under intersection.

The rest of Relations

Properties of relations, composition, and representations. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make reflexive & transitive closures 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 →