Given the relation R = {(1,1), (2,1), (3,2), (4,3)}. Determine R^2, R^3, ... Which elements are missing to make a transitive closure of R?

Accepted Solution

Answer:a)[tex]R^2=\left \{ (1,1),(2,1),(3,1),(4,2) \right \}[/tex][tex]R^3=\left \{ (1,1),(2,1),(3,1),(4,1) \right \}[/tex][tex]R^n = R^3[/tex]   for every n>3b) [tex]\left \{ (1,2),(2,3),(3,4) \right \}[/tex]Step-by-step explanation:a) From the definition of the relation we see that R(1) = 1, R(2) = 1, R(3) = 2 and R(4) = 3 [tex]R^2[/tex] is the composite relation [tex]R\circ R[/tex] Let's compute it [tex]R^2(1)=R(R(1))=R(1)=1[/tex] [tex]R^2(2)=R(R(2))=R(1)=1[/tex] [tex]R^2(3)=R(R(3))=R(2)=1[/tex] [tex]R^2(4)=R(R(4))=R(3)=2[/tex] so [tex]R^2=\left \{ (1,1),(2,1),(3,1),(4,2) \right \}[/tex] [tex]R^3[/tex] is computed in a similar way, [tex]R^3=R\circ R^2[/tex] So we have [tex]R^3(1)=R(R^2(1))=R(1)=1[/tex] [tex]R^3(2)=R(R^2(2))=R(1)=1[/tex] [tex]R^3(3)=R(R^2(3))=R(1)=1[/tex] [tex]R^3(4)=R(R^2(4))=R(2)=1[/tex] And [tex]R^3=\left \{ (1,1),(2,1),(3,1),(4,1) \right \}[/tex] From here we see that  [tex]R^n = R^3[/tex] for every n>3 b)  We must look for the missing elements that would make R transitive, and those elements are [tex]\left \{ (1,2),(2,3),(3,4) \right \}[/tex]