Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Discrete mathematics, continuous mathematics and probability / 2 / b

Using the wiki convention that paths follow the written order of the binary relations, composition of relations isSome treatments reverse the naming convention; stating it explicitly avoids ambiguity. The powers of the single relation $R$ below are the same under either convention.

A pair belongs to $R\circ R$ exactly when two successive $R$ steps connect its endpoints. The chain $a\to b\to c\to d$ has two such length-two paths, $a\to b\to c$ and $b\to c\to d$. HenceThis applies composition of relations directly; no other middle element gives a pair.

The relation powers are $R^2=\{(a,c),(b,d)\}$, $R^3=\{(a,d)\}$, and $R^i=\varnothing$ for $i\ge 4$. For $k=1$, $(a,b),(b,c)\in T$ but $(a,c)\notin T$, so transitivity fails. For $k=2$, $(a,c),(c,d)\in T$ but $(a,d)\notin T$, so it still fails.

For $k=3$, $T$ consists of every pair in which the first endpoint precedes the second in $a,b,c,d$. Composing any two such pairs again gives such a pair, so $T$ is transitive. Thus the smallest $k$ is $3$; this $T$ is the transitive closure of a relation $R$.