0
$\begingroup$

I understand the standard definition that the transitive closure of a relation $R$ on a set $S$ is the smallest relation $T$ on S such that $T$ is transitive and $R\subset T$.

My question is: what does ‘smallest’ mean here? I’m pretty sure this doesn’t refer to cardinality of sets as that definition will be quickly rendered useless for infinite sets. My professor didn’t expand on this and I can’t seem to find anything online. Could some give a clear definition of a transitive closure and the proper meaning of ‘smallest’. I would really appreciate that!

$\endgroup$

1 Answer 1

4
$\begingroup$

"Smallest" in this case means with respect to the partial ordering defined by $\subseteq$, with the relations seen as subsets of $S\times S$. It means that any transitive relations on $S$ that contains $R$ will also all contain $T$.

One should, of course, prove that such a "smallest" relation exists. The easiest way is probably to show that any intersection of transitive relations on $S$ is still transitive, and let $T$ be the intersection of all transitive relations that contain $R$.

One could also build this $T$ up from $R$ by starting with $R$. Then for any triple $x,y,z\in S$ such that $(x,y)\in R$ and $(y,z)\in R$, include $(x,z)$ in $T$, and then repeat until you have a transitive relation.

This is likely where the name "transitive closure" comes from: Start with $R$, which isn't necessarily transitive, and then "close it" with respect to transitivity by adding only the bare minimum of elements you need to satisfy transitivity. Many other so-called closures in math also work this way (such as topological closure and algebraic closure): Intuitively it's about adding elements as necessary until the desired property holds, but formally it's defined as "the smallest such that ..."

As an example, consider the set $S=\{a,b,c,d\}$ with $$R=\{ (a,b),(b,c)\\ (c,d), (b,a)\}$$ To construct the transitive closure, we could note:

  • we have $(a,b)$ and $(b,c)$, so we need $(a,c)$
  • we have $(a,b)$ and $(b,a)$, so we need $(a,a)$ and $(b,b)$
  • we have $(b,c)$ and $(c,d)$, so we need $(b,d)$

and so on. This finally yields (I believe) $$ T=\left\{\begin{array}{ccc} (a,a),&(a,b),&(a,c),\\ (a,d),&(b,a),&(b,b),\\ (b,c),&(b,d),&(c,d) \end{array}\right\} $$ Now for the more abstract approach. Consider a transitive relation $T_1\supseteq R$. And look at any pair in $T$. Clearly any pair that is in $R$ must be in $T_1$. What about the elements of $T\setminus R$? For instance, does $T_1$ contain $(a,a)$? It has to, because it's transitive and it contains $(a,b)$ and $(b,a)$. Every single element of $T\setminus R$ must be in $T_1$ by a similar argument. So we must have $T\subseteq T_1$.

$\endgroup$
4
  • $\begingroup$ Thanks for answering! I’m gonna take some time to think about it. $\endgroup$
    – Seeker
    Aug 21, 2022 at 12:18
  • $\begingroup$ Could you maybe expand on the part about smallest means with respect to the partial order. Maybe with an example $\endgroup$
    – Seeker
    Aug 21, 2022 at 12:20
  • $\begingroup$ @Newuser I tried making an example. $\endgroup$
    – Arthur
    Aug 21, 2022 at 13:54
  • $\begingroup$ Thanks a lot! It really helps $\endgroup$
    – Seeker
    Aug 21, 2022 at 19:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .