Operations on Relations

Solved Problems

Solution.

First we convert the relations \(R\) and \(S\) from roster to matrix form:

By adding the matrices \(M_R\) and \(M_S\) we find the matrix of the union of the binary relations:

The answer can be represented in roster form:

Solution.

The relations \(R\) and \(S\) are represented in matrix form as follows:

To find the intersection \(R \cap S,\) we multiply the corresponding elements of the matrices \(M_R\) and \(M_S\). This operation is called Hadamard product and it is different from the regular matrix multiplication. So, we have

Converting back to roster form, we obtain

Example 3.

Let \(A = \left\{ {1,2,3} \right\}.\) The relation \(R\) on set \(A\) is defined by the digraph.

Find the combined relation \(\overline {R^T} \backslash R,\) where \(\overline {R^T}\) denotes the complement of the converse relation.

Solution.

To get the converse relation \(R^T,\) we reverse the edge directions.

The complementary relation \(\overline{R^T}\) can be determined as the difference between the universal relation \(U\) and the converse relation \(R^T:\)

Now we can find the difference of the relations \(\overline {{R^T}} \backslash R:\)

In roster form, the answer is written as

Example 4.

Let \(B = \left\{ {a,b,c,d} \right\}.\) The relation \(S\) on set \(B\) is defined by the digraph.

Find the combined relation \(\overline {S \cap {S^T}},\) where \({S^T}\) denotes the converse relation of \(S.\)

Solution.

The converse relation \(S^T\) is represented by the digraph with reversed edge directions.

Find the intersection of \(S\) and \(S^T:\)

The complementary relation \(\overline {S \cap {S^T}} \) has the form

Solution.

Let \(R\) and \(S\) be relations defined on a set \(A.\)

Since \(R\) and \(S\) are reflexive we know that for all \(a \in A,\) \(\left( {a,a} \right) \in R\) and \(\left( {a,a} \right) \in S.\)

The difference of the relations \(R \backslash S\) consists of the elements that belong to \(R\) but do not belong to \(S\). Hence, \(R \backslash S\) does not contain the diagonal elements \(\left( {a,a} \right),\) i.e. it is irreflexive.

Similarly, we conclude that the difference of relations \(S \backslash R\) is also irreflexive.

By definition, the symmetric difference of \(R\) and \(S\) is given by

So we need to prove that the union of two irreflexive relations is irreflexive. Suppose that this statement is false. If the union of two relations is not irreflexive, its matrix must have at least one \(1\) on the main diagonal. This is only possible if either matrix of \(R \backslash S\) or matrix of \(S \backslash R\) (or both of them) have \(1\) on the main diagonal. However this contradicts to the fact that both differences of relations are irreflexive. Thus the proof is complete.

We conclude that the symmetric difference of two reflexive relations is irreflexive.

Solution.

We can prove this by means of a counterexample.

Consider the set \(A = \left\{ {0,1} \right\}\) and two antisymmetric relations on it:

Compose the union of the relations \(R\) and \(S:\)

We get the universal relation \(R \cup S = U,\) which is always symmetric on an non-empty set. Hence, \(R \cup S\) is not antisymmetric.