Question

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?

Answer 1

Answer:

a)

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

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

$R^n = R^3$   for every n>3

b)

$\left \{ (1,2),(2,3),(3,4) \right \}$

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

$R^2$ is the composite relation $R\circ R$

Let's compute it

$R^2(1)=R(R(1))=R(1)=1$

$R^2(2)=R(R(2))=R(1)=1$

$R^2(3)=R(R(3))=R(2)=1$

$R^2(4)=R(R(4))=R(3)=2$

so

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

$R^3$ is computed in a similar way,

$R^3=R\circ R^2$

So we have

$R^3(1)=R(R^2(1))=R(1)=1$

$R^3(2)=R(R^2(2))=R(1)=1$

$R^3(3)=R(R^2(3))=R(1)=1$

$R^3(4)=R(R^2(4))=R(2)=1$

And

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

From here we see that  

$R^n = R^3$

for every n>3

b)  

We must look for the missing elements that would make R transitive, and those elements are

$\left \{ (1,2),(2,3),(3,4) \right \}$