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 / iii

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$.