∎ QED
Relations · step 7 of 13

Powers Rⁿ & reachability

Define R¹ = R and Rⁿ⁺¹ = R∘Rⁿ. The point of this definition is a clean graph reading: (a,b) ∈ Rⁿ exactly when there is a path of length exactly n from a to b in the digraph of R. Reachability — the existence of a path of any positive length — is therefore the union of all the powers, which is precisely the transitive closure.

Practise powers rⁿ & reachability 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.

  1. Compute powers by chainingTo get Rⁿ⁺¹, follow each pair of Rⁿ by one more R-step. Working with the matrix is usually quicker.
  2. Read length exactlyRⁿ requires a path of length exactly n, not at most n. A shorter path does not qualify unless a cycle lets you pad it.
  3. Stop at n = |A|On an n-element set, any reachable pair is joined by a path of length at most n − 1, so higher powers add nothing new to reachability.
  4. Union for reachabilityR⁺ = R ∪ R² ∪ … ∪ R^n. Adding the identity gives R*, which allows the empty path.

Worked example

For R = {(1,2),(2,3),(3,1)} on {1,2,3}, compute R², R³ and determine which pairs are reachable.

  1. R²: 1→2→3 gives (1,3); 2→3→1 gives (2,1); 3→1→2 gives (3,2). So R² = {(1,3),(2,1),(3,2)}.
  2. R³: extend each R² pair by one R-step: (1,3)+(3,1) → (1,1); similarly (2,2) and (3,3). So R³ = Δ.
  3. R⁴ = R∘R³ = R, so the powers cycle with period 3.
  4. Union R ∪ R² ∪ R³ covers all nine pairs.

Answer. R² = {(1,3),(2,1),(3,2)}, R³ is the identity, and every element reaches every element — the digraph is a 3-cycle, so it is strongly connected.

Where marks get dropped

These are the specific errors that cost credit on powers rⁿ & reachability questions — QED's rubric penalises each of them separately.

Practise this until it is automatic

Unlimited fresh questions

QED generates new powers rⁿ & reachability 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.

Powers Rⁿ & reachability — frequently asked questions

What is R⁰?

By convention the identity relation Δ, representing paths of length zero. That is what makes R* = R⁰ ∪ R⁺ the reflexive-transitive closure.

How does this relate to adjacency matrix powers?

Identically. Over Boolean arithmetic, entry (i,j) of Mⁿ is 1 iff a length-n path exists; over ordinary integer arithmetic it counts how many such paths there are.

Why stop at n = |A|?

Any path longer than |A| − 1 edges repeats a vertex and so contains a removable cycle. Removing them leaves a simple path of length at most |A| − 1 between the same endpoints.

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 powers rⁿ & reachability 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 →