5
$\begingroup$

I am trying to understand how to calculate the transitive closure of a set and I have read several times the definition of the transitive closure but I still cannot understand some answers I see when doing questions.

From my definition, the transitive closure of a set $ R^+ $ is the smallest set that is transitive and contains R.

In this question I am doing , I am required to calculate the transitive closure of this set:

$ R = \{ (1,2),(2,3),(3,4),(4,1) \} $

My approach was to start with one pair and keep on adding the missing transitive pairs until I could find no more. This proved to be somewhat exhausting as I think I had written down about 15+ pairs before I thought that I must be doing something wrong. So I check the answer and it is given like this:

$ R o \{ (1,3),(2,4),(3,1),(4,2) \} o \{ (1,4),(2,1),(3,2),(4,3) \} o \{ (1,1),(2,2),(3,3),(4,4) \} $

The answer does not explain how they arrived at this answer which extremely unhelpful to me. I only managed to understand that the last composition is the reflexive set of { 1,2,3,4} but I don't know where the rest is coming from?

I also worked out the final composition which turned out to be $R^+ = \{ (1,3),(2,4),(3,1),(4,2) \}$ however I don't see how this contains R? Maybe my understanding is incorrect but does R have to be a subset of $R^+$?

Finally I drew the graph but that did not help me understand any better as there were more questions arising from this too.

Can someone please explain to me how we calculate the transitive closure of this set (and in general any set given like this) with a simple approach?

$\endgroup$
2
$\begingroup$

Lets recall the definition of transitivity. A relation $R \subseteq A \times A$ on $A$ is called transitive, if we have $$(a,b),(b,c) \in R \Rightarrow (a,c)$$ for all $a,b,c \in A$.

Your initial set is $R = \{(1,2),(2,3),(3,4),(4,1)\}$. The way you described your approach is basically the way to go. Just go through the set and if you find some $(a,b),(b,c)$ in it, add $(a,c)$.

The way the answer is given is a little bit confusing because it already tries to be explanatory :) The thing is, that they mean unions $\cup$ instead of compositions $\circ$. BUT they are writing it as a union to emphasize the steps taken in order to arrive at the solution:

  1. Step: Look at $R$. Since $(1,2),(2,3) \in R$, we need to add $(1,3)$ to the set. Analogously we have to add $(2,4),(3,1)$ and $(4,2)$. Lets call this new set $R_1$.
  2. Step: Now we have $R \subset R_1$, but $R_1$ is not yet transitive because $(1,3),(3,4) \in R_1$ but $(1,4)\notin R_1$. Hence, we have to add $(1,4)$ to $R_1$ and so on...

If we keep going we end up with the complete relation $R^+ = A \times A$ where $A = \{1,2,3,4\}$, i.e. $R^+$ contains ALL possible pairs of $1,2,3,4$.

By the way: I really like the idea to visualize the relation as a graph.

$\endgroup$
  • $\begingroup$ So what is the quickest way to compute the transitive closure , I am still unsure approaching this even though I've read your answer. Yes I also saw in notes before that the maximum possible number of pairs would we have to possibly add would be the cardinality of the set. I think I am confusing myself now; is {(1,3),(2,4),(3,1),(4,2)} transitive? We are missing (1,1) and (2,2)... $\endgroup$ – Nubcake Apr 30 '15 at 12:37
  • $\begingroup$ Unfortunately there is no very efficient way other than to add pairs iteratively. However, your example is very nice. The set $\{(1,3),(2,4),(3,1),(4,2)\}$ is not relative because it is missing $(1,1),(2,2)$. However, if we add those pairs, we arrive at the transitive closure $\{(1,3),(2,4),(3,1),(4,2),(1,1),(2,2)\}$ $\endgroup$ – GenericNickname Apr 30 '15 at 12:47
  • $\begingroup$ @GenericNickname You meant to say "is not reflexive" $\endgroup$ – drhab Apr 30 '15 at 12:51
  • $\begingroup$ @drhab actually I meant "is not transitive" - seems my mind wandered off for a sec there :) $\endgroup$ – GenericNickname Apr 30 '15 at 12:52
  • $\begingroup$ But if I keep on adding pairs like I was doing before, I would end up with a set containing all possible pairs of A x A? That wouldn't be the transitive closure of the set then would it? Also , (3,3) is also missing right? Why didn't the answer given the "transitive closure" then? Sorry but I'm still confused , why is R+ transitive? We are missing quite a lot of pairs. It's turning out like we need to add all possible pairs to make it transitive. $\endgroup$ – Nubcake Apr 30 '15 at 12:55
0
$\begingroup$

It can be shown that the transitive closure of a relation R on A which is a finite set is union of iteration R on itself |A| times. Hence the matrix representation of transitive closure is joining all powers of the matrix representation of R from 1 to |A|. In this example computing Powers of A from 1 to 4 and joining them together successively ,produces a matrix which has 1 at each entry. So the transitive closure is the full relation on A given by A x A.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.