Skip to main content
edited tags; edited title
Link
Asaf Karagila
  • 396.6k
  • 46
  • 617
  • 1k

Calculate transitive closure of a setrelation

Source Link
Nubcake
  • 426
  • 1
  • 6
  • 17

Calculate transitive closure of a set

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?