Calculate transitive closure of a relation

Question

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?

Answer 1

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.

Answer 2

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.