Question

Please explain "Composition of Relations".

Answer 1

Suppose that we have three sets A, B and C. A relation R defined from A to B, and a relation S defined from B to C. We can now define a new relation known as the composition of R and S, written as S o R. This new relation is defined as follows:


If a is an element in A and c is an element in C, then a(S o R)c, if and only if, there exists some element b in B, such that aRb and bSc. This means that, we have a relation S o R from a to c, if and only if, we can reach from a to c in two steps; i.e. from a to b related by R and from b to c related by S. In this manner, relation S o R can be interpreted as R followed by S, since this is the order in which the two relations need to be considered, first R then S.

Calculating Composition of Relations:
To compute S o R, we will first find the 2nd's of R (i.e., the b's) and let them be the 1st's (the a's) in S. In other words, R is computed 1st, then S i.e., it is right to left, not left to right.

Properties of Composition of Relations:

1. Let A, B, C and D be sets, R a relation from A to B, S a relation from B to C and T is a relation from C to D, then, T o (S o R) = (T o S) o R
2. Consider R be a relation from A to B and S is a relation from B to C. Then, if A is any subset of A, we have (S o R)(A) = S(R(A))
3. Let A, B and C are three sets, or a relation from A to B, and S a relation from B to C. Then, (S o R) inverse = R inverse o S inverse.
4. A transitive closure of a relation R is the smallest transitive relation containing R, where a relation R is said to be transitive, if for every (a; b) belonging to R and (b; c) belonging to R, there is a (a; c) belonging to R.