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
A:
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]