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

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 \}`

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 \}`