Suppose R and S are relations on the set X Provide a proof o

Suppose R and S are relations on the set X. Provide a proof or a counterexample for each of the following statements. (a) [R is transitive] rightarrow [R^-1 is transitive] (b) [R and S are symmetric] rightarrow [R S is symmetric] (c) [R is symmetric] rightarrow [ R\' is antisymmetric] (d) [ R and S are transitive] rightarrow [ R S is transitive] e) [R and S are antisymmetric] rightarrow is [R S is antisymmetric]

Solution

(a) Let x, y, z X and let R be transitive and let x R y and y R z. Then, y R^-1x and z R^-1y. Since R is transitive, therefore, x R z, therefore, z R^-1x. Thus , if z R^-1y and y R^-1x, then zR^-1x . This means that R^-1 is transitive

(b) Let ( x , y ) R S , then ( x , y) R and (x , y) S so that x R y and x S y. Since R and S are symmetric, we have y R x and y S x. This implies that y (R S ) x which proves that R S is symmetric.

(c) Let X = { a,b, c} and let R = { (a,b), (b,a)}   and let a b , a c and b c. Then R ‘ = { (a,a), (a,c), (b,b), (b,c), (c,a), (c,b), (c,c)} Now, obviously, R is symmetric. However R’ is not antisymmetric as ( a,c), (c,a) R’ , but c a.

(d) Let A={x,y,z}. Suppose that R={(x,y)} and S={(y,z)}.R and S are both transitive by default.However, RS is not transitive because (x,z) is not a member of RS.

(e) Let R(a,b) if a < b and S(a,b) if a > b Both R and S are anti symmetric but R U S = {(a,b): a = b} which is symmetric