Is transitive closure defined uniquely?

Question

I'm encountering questions where I'm required to find a transitive closure (and the questions seem to suggest that there is only one), but I probably don't understand something in the definition, because I don't see why is it required that there be only one minimal transitive relation which is a superset of the one I'm asked to find a closure for. Consider this example: $A=\{1, 2, 3, 4\}$. $M$ is the set of all relations over $A$, then, for example, let some particular relation in $M$ be $R=\{(1,1)\}$. I can complete it to a transitive relation by either $R^{+}=\{(1, 1), (2, 3), (4, 3)\}$ or it could be $R^{+}=\{(1, 1), (2, 3), (4, 2)\}$. In other words, I could complete $R$ in such a way that there is never a situation when there are enough members to build a triple needed for transitivity.

Am I wrong thinking that $R^{+}$ will be a transitive closure? All examples I found so far assume that $R$ already connects all elements of its domain. Is it a requirement?

Answer 1

The transitive closure of a binary relation $R$ is the intersection of all transitive binary relations that extend $R$.

To say that $S$ extends $R$ means that for all $x,y$ in the domain, if $aRb$ and $aSb$.

The intersection $T$ of a set of binary relations is defined by saying that for all $x,y$ in the domain, $xTy$ if and only if for every binary relation $S$ in the given set of binary relations we have $xSy$.

So here's an exercise:

• Show that this intersection is a transitive binary relation.
• Show that every transitive binary relation that extends $R$ also extends this intersection.

That tells you that it's the unique minimal one.

Answer 2

Your relation $R$ is already transitive, so it is its own transitive closure. It appears that what you’re misunderstanding is the notion of transitivity. A relation $R$ on a set $A$ is transitive if it satisfies the following condition:

if $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, then $\langle a,c\rangle\in R$.

It says absolutely nothing about $\langle a,c\rangle$ if there is no $b\in A$ such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$.

To say the same thing differently, in order to show that $R$ is not transitive, you must find elements $a,b,c\in A$, not necessarily distinct, such that $\langle a,b\rangle\in R$ and $\langle b,c\rangle\in R$, but $\langle a,c\rangle\notin R$. This is not possible in the case of your example, so your relation $R$ is transitive.