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

  • $\begingroup$ I assume you are talking about relations? $\endgroup$
    – 5xum
    Apr 29, 2016 at 9:53
  • $\begingroup$ 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. $\endgroup$
    – HSN
    Apr 29, 2016 at 9:56

1 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).
  • $\begingroup$ 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. $\endgroup$
    – Pavel
    Apr 29, 2016 at 10:03
  • $\begingroup$ @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. $\endgroup$
    – 5xum
    Apr 29, 2016 at 10:05

You must log in to answer this question.

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