Operations on Relations
Since binary relations defined on a pair of sets A and B are subsets of the Cartesian product A × 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
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
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
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:
where the sum of the elements is calculated by the rules
Difference of Relations
The difference of two relations is defined as follows:
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
Then the relation differences \(R \backslash S\) and \(S \backslash R\) are given by
Symmetric Difference of Relations
The symmetric difference of two binary relations \(R\) and \(S\) is the binary relation defined as
Let \(R\) and \(S\) be relations of the previous example. Then
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
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
then the complement of \(R\) has the form
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:
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
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,
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 \(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\}.\)