Calculus

Set Theory

Set Theory Logo

Operations on Relations

Since binary relations defined on a pair of sets \(A\) and \(B\) are subsets of the Cartesian product \(A \times B,\) we can perform all the usual set operations on them.

Let \(R\) and \(S\) be two relations over the sets \(A\) and \(B,\) respectively.

Intersection of Relations

The intersection of the relations \(R \cap S\) is defined by

\[{R \cap S }={ \left\{ {\left( {a,b} \right) \mid aRb \text{ and } aSb} \right\},}\]

where \(a \in A\) and \(b \in B.\)

For example, let \(R\) and \(S\) be the relations “is a friend of” and “is a work colleague of” defined on a set of people \(A\) (assuming \(A = B\)). Their intersection \(R \cap S\) will be the relation “is a friend and work colleague of“.

If the relations \(R\) and \(S\) are defined by matrices \({M_R} = \left[ {{a_{ij}}} \right]\) and \({M_S} = \left[ {{b_{ij}}} \right],\) the matrix of their intersection \(R \cap S\) is given by

\[{M_{R \cap S}} = {M_R} * {M_S} = \left[ {{a_{ij}} * {b_{ij}}} \right],\]

where the product operation is performed as element-wise multiplication.

Union of Relations

Similarly, the union of the relations \(R \cup S\) is defined by

\[{R \cup S }={ \left\{ {\left( {a,b} \right) \mid aRb \text{ or } aSb} \right\},}\]

provided \(a \in A\) and \(b \in B.\)

For example, the union of the relations “is less than” and “is equal to” on the set of integers will be the relation “is less than or equal to“.

If the relations \(R\) and \(S\) are defined by matrices \({M_R} = \left[ {{a_{ij}}} \right]\) and \({M_S} = \left[ {{b_{ij}}} \right],\) the union of the relations \(R \cup S\) is given by the following matrix:

\[{M_{R \cup S}} = {M_R} + {M_S} = \left[ {{a_{ij}} + {b_{ij}}} \right],\]

where the sum of the elements is calculated by the rules

\[{0 + 0 = 0,\;\;}\kern0pt{1 + 0 = 0 + 1 = 1,\;\;}\kern0pt{1 + 1 = 1.}\]

Difference of Relations

The difference of two relations is defined as follows:

\[{R \backslash S }={ \left\{ {\left( {a,b} \right) \mid aRb \text{ and not } aSb} \right\},}\]

\[{S \backslash R }={ \left\{ {\left( {a,b} \right) \mid aSb \text{ and not } aRb} \right\},}\]

where \(a \in A\) and \(b \in B.\)

Suppose \(A = \left\{ {a,b,c,d} \right\}\) and \(B = \left\{ {1,2,3} \right\}.\) The relations \(R\) and \(S\) have the form

\[{R = \left\{ {\left( {a,1} \right),\left( {b,2} \right),\left( {c,3} \right),\left( {d,1} \right)} \right\},\;\;}\kern0pt{S = \left\{ {\left( {a,1} \right),\left( {b,1} \right),\left( {c,1} \right),\left( {d,1} \right)} \right\}.}\]

Then the relation differences \(R \backslash S\) and \(S \backslash R\) are given by

\[{R\backslash S = \left\{ {\left( {b,2} \right),\left( {c,3} \right)} \right\},\;\;}\kern0pt{S\backslash R = \left\{ {\left( {b,1} \right),\left( {c,1} \right)} \right\}.}\]

Symmetric Difference of Relations

The symmetric difference of two binary relations \(R\) and \(S\) is the binary relation defined as

\[{R \,\triangle\, S = \left( {R \cup S} \right)\backslash \left( {R \cap S} \right),\;\;\text{or}\;\;}\kern0pt{R \,\triangle\, S = \left( {R\backslash S} \right) \cup \left( {S\backslash R} \right).}\]

Let \(R\) and \(S\) be relations of the previous example. Then

\[{R \,\triangle\, S }={ \left\{ {\left( {b,2} \right),\left( {c,3} \right)} \right\} }\cup{ \left\{ {\left( {b,1} \right),\left( {c,1} \right)} \right\} }={ \left\{ {\left( {b,1} \right),\left( {c,1} \right),\left( {b,2} \right),\left( {c,3} \right)} \right\}.}\]

Complement of a Binary Relation

Suppose that \(R\) is a binary relation between two sets \(A\) and \(B.\) The complement of \(R\) over \(A\) and \(B\) is the binary relation defined as

\[\bar R = \left\{ {\left( {a,b} \right) \mid \text{not } aRb} \right\},\]

where \(a \in A\) and \(b \in B.\)

For example, let \(A = \left\{ {1,2} \right\},\) \(B = \left\{ {1,2,3} \right\}.\) If a relation \(R\) between sets \(A\) and \(B\) is given by

\[R = \left\{ {\left( {1,2} \right),\left( {1,3} \right),\left( {2,2} \right),\left( {2,3} \right)} \right\},\]

then the complement of \(R\) has the form

\[\bar R = \left\{ {\left( {1,1} \right),\left( {2,1} \right)} \right\}.\]

Converse of a Binary Relation

Let \(R\) be a binary relation on sets \(A\) and \(B.\) The converse relation or transpose of \(R\) over \(A\) and \(B\) is obtained by switching the order of the elements:

\[{R^T} = \left\{ {\left( {b,a} \right) \mid aRb} \right\},\]

where \(a \in A,\) \(b \in B.\)

So, if \(R = \left\{ {\left( {1,2} \right),\left( {1,3} \right),\left( {1,4} \right)} \right\},\) then the converse of \(R\) is

\[{R^T} = \left\{ {\left( {2,1} \right),\left( {3,1} \right),\left( {4,1} \right)} \right\}.\]

If a relation \(R\) is defined by a matrix \(M,\) then the converse relation \(R^T\) will be represented by the transpose matrix \(M^T\) (formed by interchanging the rows and columns). For example,

\[{M = \left[ {\begin{array}{*{20}{c}} 1&0&0\\ 0&1&0\\ 1&1&0 \end{array}} \right],\;\;}\kern0pt{{M^T} = \left[ {\begin{array}{*{20}{c}} 1&0&1\\ 0&1&1\\ 0&0&0 \end{array}} \right].}\]

Sometimes the converse relation is also called the inverse relation and denoted by \(R^{-1}.\)

Empty, Universal and Identity Relations

A relation \(R\) between sets \(A\) and \(B\) is called an empty relation if \(\require{AMSsymbols}{R = \varnothing.}\)

The universal relation between sets \(A\) and \(B,\) denoted by \(U,\) is the Cartesian product of the sets: \(U = A \times B.\)

A relation \(R\) defined on a set \(A\) is called the identity relation (denoted by \(I\)) if \(I = \left\{ {\left( {a,a} \right) \mid \forall a \in A} \right\}.\)

Properties of Combined Relations

When we apply the algebra operations considered above we get a combined relation. The original relations may have certain properties such as reflexivity, symmetry, or transitivity. The question is whether these properties will persist in the combined relation? The table below shows which binary properties hold in each of the basic operations.

Properties of operations on binary relations
Figure 1.

Solved Problems

Click or tap a problem to see the solution.

Example 1

The relations \(R = \left\{ {\left( {0,2} \right),\left( {1,0} \right),\left( {1,2} \right),\left( {2,0} \right)} \right\}\) and \(S = \left\{ {\left( {1,0} \right),\left( {1,1} \right),\left( {1,2} \right),\left( {2,2} \right)} \right\}\) are defined on the set \(A = \left\{ {0,1,2} \right\}.\) Find the union of \(R\) and \(S\) in matrix form.

Example 2

The relations \(R = \left\{ {\left( {a,a} \right),\left( {b,a} \right),}\right.\) \(\left.{\left( {c,c} \right),\left( {b,d} \right),} \right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {d,a} \right),\left( {d,c} \right)} \right\}\) and \(S = \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {c,a} \right),} \right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {d,a} \right),\left( {d,b} \right)} \right\}\) are defined on the set \(B = \left\{ {a,b,c,d} \right\}.\) Find the intersection of \(R\) and \(S\) in matrix form.

Example 3

Let \(A = \left\{ {1,2,3} \right\}.\) The relation \(R\) on set \(A\) is defined by the digraph.
Digraph of a relation on a set of 3 elements.
Find the combined relation \(\overline {R^T} \backslash R,\) where \(\overline {R^T}\) denotes the complement of the converse relation.

Example 4

Let \(B = \left\{ {a,b,c,d} \right\}.\) The relation \(S\) on set \(B\) is defined by the digraph.
Digraph of a relation on a set of 4 elements
Find the combined relation \(\overline {S \cap {S^T}},\) where \({S^T}\) denotes the converse relation of \(S.\)

Example 5

Prove that the symmetric difference of two reflexive relations is irreflexive.

Example 6

Prove that the union of two antisymmetric relations need not be antisymmetric.

Example 1.

The relations \(R = \left\{ {\left( {0,2} \right),\left( {1,0} \right),\left( {1,2} \right),\left( {2,0} \right)} \right\}\) and \(S = \left\{ {\left( {1,0} \right),\left( {1,1} \right),\left( {1,2} \right),\left( {2,2} \right)} \right\}\) are defined on the set \(A = \left\{ {0,1,2} \right\}.\) Find the union of \(R\) and \(S\) in matrix form.

Solution.

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

\[{R = \left\{ {\left( {0,2} \right),\left( {1,0} \right),\left( {1,2} \right),\left( {2,0} \right)} \right\},}\;\; \Rightarrow {{M_R} = \left[ {\begin{array}{*{20}{c}} 0&0&1\\ 1&0&1\\ 1&0&0 \end{array}} \right];}\]

\[{S = \left\{ {\left( {1,0} \right),\left( {1,1} \right),\left( {1,2} \right),\left( {2,2} \right)} \right\},}\;\; \Rightarrow {{M_S} = \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 0&0&1 \end{array}} \right].}\]

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

\[{{M_{R \cup S}} = {M_R} + {M_S} }={ \left[ {\begin{array}{*{20}{c}} 0&0&1\\ 1&0&1\\ 1&0&0 \end{array}} \right] }+{ \left[ {\begin{array}{*{20}{c}} 0&0&0\\ 1&1&1\\ 0&0&1 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&0&1\\ 1&1&1\\ 1&0&1 \end{array}} \right].}\]

The answer can be represented in roster form:

\[{R \cup S }={ \left\{ {\left( {0,2} \right),\left( {1,0} \right),}\right.}\kern0pt{\left.{\left( {1,1} \right),\left( {1,2} \right),}\right.}\kern0pt{\left.{\left( {2,0} \right),\left( {2,2} \right)} \right\}.}\]

Example 2.

The relations \(R = \left\{ {\left( {a,a} \right),\left( {b,a} \right),}\right.\) \(\left.{\left( {c,c} \right),\left( {b,d} \right),} \right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {d,a} \right),\left( {d,c} \right)} \right\}\) and \(S = \left\{ {\left( {a,b} \right),\left( {b,a} \right),\left( {c,a} \right),} \right.\) \(\kern-2pt\left.{\left( {c,d} \right),\left( {d,a} \right),\left( {d,b} \right)} \right\}\) are defined on the set \(B = \left\{ {a,b,c,d} \right\}.\) Find the intersection of \(R\) and \(S\) in matrix form.

Solution.

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

\[{R = \left\{ {\left( {a,a} \right),\left( {b,a} \right),\left( {b,d} \right),}\right.}\kern0pt{\left.{\left( {c,c} \right),\left( {c,d} \right),}\right.}\kern0pt{\left.{\left( {d,a} \right),\left( {d,c} \right)} \right\},}\;\; \Rightarrow {{M_R} = \left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 1&0&0&1\\ 0&0&1&1\\ 1&0&1&0 \end{array}} \right];}\]

\[{S = \left\{ {\left( {a,b} \right),\left( {b,a} \right),}\right.}\kern0pt{\left.{\left( {c,a} \right),\left( {c,d} \right),}\right.}\kern0pt{\left.{\left( {d,a} \right),\left( {d,b} \right)} \right\},}\;\; \Rightarrow {{M_S} = \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 1&0&0&0\\ 1&0&0&1\\ 1&1&0&0 \end{array}} \right].}\]

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

\[{{M_{R \cap S}} = {M_R} * {M_S} }={ \left[ {\begin{array}{*{20}{c}} 1&0&0&0\\ 1&0&0&1\\ 0&0&1&1\\ 1&0&1&0 \end{array}} \right] }*{ \left[ {\begin{array}{*{20}{c}} 0&1&0&0\\ 1&0&0&0\\ 1&0&0&1\\ 1&1&0&0 \end{array}} \right] }={ \left[ {\begin{array}{*{20}{c}} 0&0&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 1&0&0&0 \end{array}} \right].}\]

Converting back to roster form, we obtain

\[R \cap S = \left\{ {\left( {b,a} \right),\left( {c,d} \right),\left( {d,a} \right)} \right\}.\]

Example 3.

Let \(A = \left\{ {1,2,3} \right\}.\) The relation \(R\) on set \(A\) is defined by the digraph.
Digraph of a relation on a set of 3 elements.
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.

Converse of the relation R with edges in the opposite direction.

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

\[\overline{R^T} = U\backslash {R^T}.\]

Complementary relation for the converse relation of R.

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

An example of combined relation on a set of 3 elements

In roster form, the answer is written as

\[\overline {{R^T}} \backslash R = \left\{ {\left( {1,1} \right),\left( {2,3} \right),\left( {3,2} \right)} \right\}.\]

Example 4.

Let \(B = \left\{ {a,b,c,d} \right\}.\) The relation \(S\) on set \(B\) is defined by the digraph.
Digraph of a relation on a set of 4 elements
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.

Converse relation S^T - example 2

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

Intersection of the original relation S and its converse S^T

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

The complement of the intersection of two relations.

Example 5.

Prove that the symmetric difference of two reflexive relations is irreflexive.

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

\[R \,\triangle\, S = \left( {R \backslash S} \right) \cup \left( {S \backslash R} \right).\]

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.

Example 6.

Prove that the union of two antisymmetric relations need not be antisymmetric.

Solution.

We can prove this by means of a counterexample.

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

\[{R = \left\{ {\left( {1,2} \right),\left( {2,2} \right)} \right\},\;\;}\kern0pt{S = \left\{ {\left( {1,1} \right),\left( {2,1} \right)} \right\}.}\]

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

\[{R \cup S }={ \left\{ {\left( {1,2} \right),\left( {2,2} \right)} \right\} }\cup{ \left\{ {\left( {1,1} \right),\left( {2,1} \right)} \right\} }={ \left\{ {\left( {1,1} \right),\left( {1,2} \right),\left( {2,1} \right),\left( {2,2} \right)} \right\}.}\]

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.