# What does it mean for transitive closure to be minimal?

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

• I assume you are talking about relations?
– 5xum
Apr 29, 2016 at 9:53
• If the relation is on a set $X$, then $X^2$ is transitive. Usually, you don't want this to be the transitive closure. In fact, there may be a lot of relations inbetween $R$ and $X^2$ that are transitive as well.
– HSN
Apr 29, 2016 at 9:56

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).
• Thanks, but I already know all this. I just don't understand why it is that if I have a transitive relation R, I can't just take away one element and have an even smaller one. I still don't understand what minimal means here, that's why I asked for an example, so someone could show that a certain relation can't be any smaller or something. Apr 29, 2016 at 10:03
• @paulpaul1076 I gave an example. The point is if you have a transitive relation $R$, and you take away one element, the resulting relation may not be transitive any more. In fact, that's the whole point of transitive closures: It's such a relation from which nothing can be taken away.
– 5xum
Apr 29, 2016 at 10:05