Question

For the following statements, provide a proof if the statement is true or give a counterexample if the statement is false S and R are binary relations over the same domain

a)if S and R are both anti-symetric,then SoR is anti-symmetric
b)If S and R are both Symmetric,then SoR is symmetric
c)If S and R are both transitive,then SoR is transitive
d)If S and R are both symmetric,then SUR is symmetric
e)If S and R are both transitive, then SUR is transitive.

Answer 1

The statements about binary relations being anti-symmetric, symmetric and transitive when composed or united were analyzed. It was shown that S∘R is anti-symmetric if S and R are, but S∘R is not always symmetric or transitive if S and R are. S∪ R is symmetric, but not always transitive when S and R are transitive.

Step-by-step explanation:

For a student asking about properties of binary relations, we explore following claims:a) If S and R are both anti-symmetric, then S∘R is anti-symmetric: True. For any (x,y) and (y,x) in S∘R, if x≠y then it cannot be that (x,y) and (y,x) are both in S and R, or else either S or R would not be anti-symmetricb) If S and R are both symmetric, then S∘R is symmetric: False. Counterexample: S={(a,b)}, R={(b,a)}. S∘R={(a,a)} is not symmetric because (b,a) is not in S∘R.

c) If S and R are both transitive, then S∘R is transitive: False. Counterexample: S={(a,b)}, R={(b,c), (c,a)}. S∘R contains (a,c) and (c,a) but not (a,a).d) If S and R are both symmetric, then S∪ R is symmetric: True. Symmetry in S and R individually ensures thatfor all (x,y) in S or R, the pair (y,x) is also in S or R, thus in S∪ R.e) If S and R are both transitive, then S∪ R is transitive: False. Counterexample: S={(a,b), (b,c)}, R={(a,c)}. S∪ R is {(a,b), (b,c), (a,c)}, which is not transitive because (a,b) and (b,c) are in S∪ R, but (a,c) is not.