What does it mean for transitive closure to be minimal?

Question

I don't understand what that word "minimal" has to do with anything. Can anyone explain and give an example?

Answer 1

I assume you are talking about relations.

Some basics:

• A relation $R$ on a set $A$ is, as you know, a subset of $A\times A$, so $R\subset A\times A$. Instead of $(a,b)\in R$, we often write $aRb$
• A relation is transitive if, for any three elements $a,b,c\in A$ for which $aRb, bRc$, we also have $aRc$.

---

Now, a transitive closue (let's call it $T_R$) of $R$ is the, as you say, minimal transitive relation that includes $R$. By include, I mean literally that $R$ is its subset, or in other words, $Q$ includes $R$ if, for all $a,b$ for which $aRb$, we also have $aQb$.

This means that among all of the transitive relations that include $R$, $T_R$ is the one that is the smallest set.

For example, $A\times A$ is a transitive relation that includes $R$, but there may be some smaller relations that also are transitive and include $R$.

---

For example, let $A=\{a,b,c\}$ be a two element set, and let $R=\{(a,b), (b,c)\}$.

$R$ is clearly not transitive, but the following relations (all of which include $R$) are all transitive:

• $R_1=\{(a,b), (b,c), (a,c)\}$
• $R_2=\{(a,b), (b,c), (a,c), (a,a)\}$
• $R_3=\{(a,b), (b,c), (a,c), (b,b)\}$
• $R_4=\{(a,b), (b,c), (a,c), (c,a), (c,b), (a,a), (c,c), (b,b)\}$

All of these (and some others) are transitive relations that include $R$, but only $R_1$ is the minimal transitive relation that includes $R$. In fact, any transitive relation that includes $R$ has the following properties:

1. It contains $(a,b)$ (because $R$ includes $(a,b)$)
2. It contains $(b,c)$ (because $R$ includes $(b,c)$)
3. It is transitive (by definition)
4. It contains $(a,c)$ (follows from 1,2,3)
5. It contains $R_1$ (follows from 1,2,4).