let R and S be relations on a set A Define the composition S

let R and S be relations on a set A Define the composition S o R Define, recursively, R^N for any positive integer N Prove the following statement: there is an R-path of length N between members a and b of set A, if and only if (a, b) R^N Write down a finite formula for the transitive closure of R. Suppose that the set A is {1, 2, 3,4} and that R defined on A is R = {(1, 2), (1,3), (2,3), (2,4), (3,1)}, calculate R^2

Solution

(a) The composition SoR can be defined when the codomain of R is Domain of S. and it is S(R).

(b) R^N is R(R(R(R(R(R...R))))...)) N times composition.

(e) A = {1,2,3,4}, R = {(1,2),(1,3),(2,3),(2,4),(3,1)}

R² = {(1,3),(1,1),(2,1),(3,2),(3,3)}