Question

Problem 3

For two relations R₁ and R₂ on a set A, we define the composition of R₂ after R₁ as

R₂°R₁ = { (x, z) ∈ A×A | (∃ y)( (x, y) ∈ R₁ ∧ (y, z) ∈ R₂ )}

Recall that the inverse of a relation R, denoted R ^-1, on a set A is defined as:

R ^-1 = { (x, y) ∈ A×A | (y, x) ∈ R)}

1. Suppose R = { (1, 1), (1, 2), (3, 3), (3, 4) }.
   1. What is R ^-1?
   2. What is R °R ^-1?

2. Let R be an arbitrary relation on a set A.

   1. Is R °R ^-1 reflexive?
   2. Is R °R ^-1 symmetric?
   3. Is R °R ^-1 transitive?

   For each of these,

   • if the answer is yes, give a justification of why R °R ^-1 must have the property for every relation R on set A.
   • if the answer is no, give a counter-example, i.e., give an R, show what R ^-1 and R °R ^-1 are, and show why the property is not true.

Answer 1