Calculus

Set Theory

Set Theory Logo

Binary Relations

Definition of a Binary Relation

Recall that a Cartesian product of two sets \(A\) and \(B\) is the set of all possible ordered pairs \(\left( {a,b} \right),\) where \(a \in A\) and \(b \in B:\)

\[A \times B = \left\{ {\left( {a,b} \right) \mid a \in A \text{ and } b \in B} \right\}.\]

To trace the relationship between the elements of two or more sets (or between the elements on the same set), we use a special mathematical structure called a relation.

A binary relation \(R\) from set \(A\) to set \(B\) is a subset of the Cartesian product \(A \times B:\)

\[R \subseteq A \times B.\]

If \(R \subseteq A \times B\) is a binary relation and \(\left( {a,b} \right) \in R,\) we say \(a\) is related to \(b\) by \(R.\) It is denoted by \(aRb\) (infix notation).

If \(R \subseteq A \times B\) and \(A = B,\) the binary relation \(R\) is called a homogeneous binary relation defined on the set \(A.\)

Let \(R \subseteq A \times B\) be a binary relation defined on a pair of sets \(A\) and \(B.\) The set of all \(a \in A\) such that \(aRb\) for at least one \(b \in B\) is called the domain of the binary relation \(R.\) The set of all \(b \in B\) such that \(aRb\) for at least one \(a \in A\) is called the codomain (also referred to as image or range) of the binary relation \(R.\)

Examples of Binary Relations

  1. The relation “greater than”, denoted by \(\gt,\) on the set \(A = \left\{ {1,2,3} \right\}.\)

    The Cartesian square of the set \(A\) is given by \[{{A^2} = \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}\kern0pt{\left.{\left( {1,3} \right),\left( {2,1} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,3} \right),}\right.}\kern0pt{\left.{\left( {3,1} \right),\left( {3,2} \right),}\right.}\kern0pt{\left.{\left( {3,3} \right)} \right\}.}\] We find all pairs \(\left( {a,b} \right)\) where \(a \gt b.\) This yields: \[{R_1} = \left\{ {\left( {2,1} \right),\left( {3,1} \right),\left( {3,2} \right)} \right\}.\]
  2. The relation “two numbers have the same parity” on the set \(B = \left\{ {2,3,4} \right\}.\)

    The Cartesian square of the set \(B\) consists of \(9\) ordered pairs: \[{n\left( {{B^2}} \right) = n\left( {B \times B} \right) }={ n\left( B \right) \times n\left( B \right) }={ 3 \times 3 }={ 9.}\] The relation \(R_2\) contains the pairs of numbers of the same parity (either both are even or both are odd): \[{{R_2} = \left\{ {\left( {2,2} \right),\left( {2,4} \right),}\right.}\kern0pt{\left.{\left( {4,2} \right),\left( {4,4} \right),\left( {3,3} \right)} \right\}.}\]
  3. The divisibility relation on the set of natural numbers.

    The divisibility relation , denoted by \(a \mid b\;\) (“\(a\) divides \(b\)”), on the set \(\mathbb{N}\) is defined if and only if there is some \(n \in \mathbb{N}\) such that \(a \times n = b.\) Obviously, this relation contains an infinite number of elements. Examples of the elements of the relation: \[{{R_2} = \left\{ {\left( {1,2} \right),\left( {3,6} \right),}\right.}\kern0pt{\left.{\left( {4,12} \right),\left( {7,28} \right),\left( {11,44} \right), \ldots } \right\}.}\] Examples of ordered pairs that do not belong to the divisibility relation: \[{\left( {2,1} \right),\left( {6,3} \right),\left( {3,5} \right),}\kern0pt{\left( {7,11} \right),\left( {11,7} \right), \ldots }\]
  4. We can also use binary relations to trace relationships between people or between any other objects. Examples of binary relations between people:

    Family relations (like “brother” or “sister-brother” relations), the relation “is the same age as”, the relation “lives in the same city as”, etc.

Representation of Binary Relations

There are many ways to specify and represent binary relations. Some of which are as follows:

  • Listing Tuples (Roster Method)
  • Set Builder Notation
  • Relation as a Matrix
  • Relation as a Directed Graph
  • Relation as an Arrow Diagram
  • Relation as a Cartesian Plane Graph

Listing Tuples (Roster Method)

A binary relation can be represented with an explicit list of its tuples (ordered pairs).

Consider the set \(A = \left\{ {1,2,5,6,10} \right\}\) and the binary relation \(aRb\) on \(A.\) The relation \(aRb\) is defined if and only if \(a – b\) is odd. We specify the relation \(aRb\) by listing all its ordered pairs \(\left( {a,b} \right):\)

\[{R = \left\{ {\left( {1,2} \right),\left( {1,6} \right),}\right.}\kern0pt{\left.{\left( {1,10} \right),\left( {2,1} \right),}\right.}\kern0pt{\left.{\left( {2,5} \right),\left( {5,2} \right),}\right.}\kern0pt{\left.{\left( {5,6} \right),\left( {5,10} \right),}\right.}\kern0pt{\left.{\left( {6,1} \right),\left( {6,5} \right),}\right.}\kern0pt{\left.{\left( {10,1} \right),\left( {10,5} \right)} \right\}.}\]

Defining a Relation Using Set Builder Notation

Since a relation is a set, we can describe a relation by set builder method.

Let \(A = \left\{ {1,2,3,4} \right\}\) and \(B = \left\{ {3,4,5,6} \right\}\). Consider the relation \(aRb\) defined in set builder form as

\[R = \left\{ {\left( {a,b} \right) \mid a + b \le 6} \right\}.\]

In roster form, this relation is written as

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

Relation as a Matrix

If \(R \subseteq X \times Y\) is a binary relation between the sets \(X\) and \(Y,\) where

\[{X = \left\{ {{x_1}, \ldots ,{x_n}} \right\},\;\;}\kern0pt{Y = \left\{ {{y_1}, \ldots ,{y_m}} \right\},}\]

then \(R\) can be represented by the logical \(n \times m\) matrix \(M = \left[{a_{ij}}\right]\) whose \(\left({i,j}\right)-\)entry is given by

\[ {a_{ij}} = \begin{cases} 1, &\left({x_i},{y_j}\right) \in R\\ 0, &\left({x_i},{y_j}\right) \notin R \end{cases}. \]

The logical matrix \(M\) is also called the binary matrix, relation matrix, Boolean matrix, adjacency matrix, or zero-one matrix. If \(X = Y,\) then \(m = n,\) and the matrix \(M\) is square.

Suppose the binary relation \(R = \left\{ {\left( {x,y} \right) \mid x \gt y} \right\}\) is defined on the set \(X = \left\{ {5,6,7,8} \right\}.\) In matrix form, the relation \(R\) is represented as follows:

Logical matrix for the binary relation x is greater than y
Figure 1.

Relation as a Directed Graph

A binary relation on a finite set can also be represented using a directed graph (a digraph for short).

A directed graph consists of a set vertices and a set of edges directed from one vertex to another. The edges are also called arrows or directed arcs.

If a binary relation \(R\) is defined on a set \(A,\) then the elements of the set \(A\) are represented by vertices, and the ordered pairs of the relation \(R\) are represented by the directed edges.

Suppose we are given a set \(A\) and a binary relation \(R:\)

\[A = \left\{ {1,2,3,4,5} \right\},\]

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

The relation \(R\) on \(A\) is represented by its digraph as follows:

Digraph of a binary relation of the set A={1,2,3,4,5}.
Figure 2.

Relation as an Arrow Diagram

A binary relation \(R\) from set \(A\) to set \(B\) can be depicted using an arrow diagram.

Consider two sets:

\[{A = \left\{ {a,b,c,d,e} \right\},\;\;}\kern0pt{B = \left\{ {1,2,3,4,5,6} \right\}.}\]

Suppose that the relation \(R\) between \(A\) and \(B\) is given in roster form:

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

We can visualize the relation \(R\) by the arrow diagram:

Representation of relation between sets A and B using an arrow diagram.
Figure 3.

Relation as a Cartesian Plane Graph

To represent a binary relation graphically, we can plot the ordered pairs of the relation as points on a coordinate plane. For example, the relation \(R\) between sets \(A\) and \(B\) from the previous example is displayed on the Cartesian plane as follows:

Representation of relation between sets A and B using an arrow diagram.
Figure 4.

Solved Problems

Click or tap a problem to see the solution.

Example 1

The binary relation “less than or equal to” is defined on the set \(A = \left\{ {0,2,5,7} \right\}.\) Represent it in roster form.

Example 2

The binary relation “greater than” is defined on the set \(B = \left\{ {\large{\frac{2}{3}}\normalsize, \large{\frac{4}{7}}\normalsize, \large{\frac{5}{8}}\normalsize, \large{\frac{{11}}{{17}}}\normalsize} \right\}.\) Represent it in roster form.

Example 3

Let \(A = \left\{ {1,3,4,5,7} \right\}.\) Represent the relation \(R = \left\{ {\left( {a,b} \right) \mid \left| {a – b} \right| \lt 2} \right\}\) on the set \(A\) in matrix form.

Example 4

Let \(A = \left\{ {1,2,3,4,5,6} \right\}.\) Represent the divisibility relation on the set \(A\) as a matrix.

Example 5

The relation \(R\) on the set \(C = \left\{ {0,1,2,3} \right\}\) is given by the matrix \[M = \left[ {\begin{array}{*{20}{c}} 1&0&1&1\\ 0&1&0&1\\ 0&1&0&0\\ 0&1&0&1 \end{array}} \right].\] Represent \(R\) using a digraph.

Example 6

Let \(B = \left\{ {2,4,5,7,8,9} \right\}.\) A relation \(R\) on the set \(B\) is defined as follows: \[R = \left\{ {\left( {a,b} \right) \mid 2 \mid \left( {a + b} \right)} \right\}.\] Draw the digraph of \(R.\)

Example 1.

The binary relation “less than or equal to” is defined on the set \(A = \left\{ {0,2,5,7} \right\}.\) Represent it in roster form.

Solution.

We list all ordered pairs that satisfy the relation definition:

\[{R = \left\{ {\left( {0,0} \right),\left( {0,2} \right),}\right.}\kern0pt{\left.{\left( {0,5} \right),\left( {0,7} \right),}\right.}\kern0pt{\left.{\left( {2,2} \right),\left( {2,5} \right),}\right.}\kern0pt{\left.{\left( {2,7} \right),\left( {5,5} \right),}\right.}\kern0pt{\left.{\left( {5,7} \right),\left( {7,7} \right)} \right\}.}\]

Example 2.

The binary relation “greater than” is defined on the set \(B = \left\{ {\large{\frac{2}{3}}\normalsize, \large{\frac{4}{7}}\normalsize, \large{\frac{5}{8}}\normalsize, \large{\frac{{11}}{{17}}}\normalsize} \right\}.\) Represent it in roster form.

Solution.

Given that

\[{\frac{2}{3} \approx 0.666,\;\;}\kern0pt{\frac{4}{7} \approx 0.571,\;\;}\kern0pt{\frac{5}{8} = 0.625,\;\;}\kern0pt{\frac{{11}}{{17}} \approx 0.647,}\]

we list the elements of the set \(B\) in increasing order:

\[B = \left\{ {\frac{4}{7},\frac{5}{8},\frac{{11}}{{17}},\frac{2}{3} }\right\}.\]

Now we can build the ordered pairs satisfying the relation “greater than”:

\[{R = \left\{ {\left( {\frac{5}{8},\frac{4}{7}} \right),}\right.}\kern0pt{\left.{\left( {\frac{{11}}{{17}},\frac{4}{7}} \right),}\right.}\kern0pt{\left.{\left( {\frac{2}{3},\frac{4}{7}} \right),}\right.}\kern0pt{\left.{\left( {\frac{{11}}{{17}},\frac{5}{8}} \right),}\right.}\kern0pt{\left.{\left( {\frac{2}{3},\frac{5}{8}} \right),}\right.}\kern0pt{\left.{\left( {\frac{2}{3},\frac{{11}}{{17}}} \right)} \right\}.}\]

Example 3.

Let \(A = \left\{ {1,3,4,5,7} \right\}.\) Represent the relation \(R = \left\{ {\left( {a,b} \right) \mid \left| {a – b} \right| \lt 2} \right\}\) on the set \(A\) in matrix form.

Solution.

The logical matrix \(M\) represents all ordered pairs \({\left( {a,b} \right)}\) on the set \(A.\) If an element of the matrix (an ordered pair) satisfies the condition \({\left| {a – b} \right| \lt 2},\) it is labeled by \(1.\) If not, it is labeled by \(0.\)

Logical matrix representing the relation R={(a,b)||a-b|<2} on the set A={1,3,4,5,7}.
Figure 5.

Example 4.

Let \(A = \left\{ {1,2,3,4,5,6} \right\}.\) Represent the divisibility relation on the set \(A\) as a matrix.

Solution.

The \(\left({i,j}\right)-\)entry of the logical matrix is set to be equal to \(1,\) if the element of the \(i\text{th}\) row divides the element of the \(j\text{th}\) column. Otherwise, the \(\left({i,j}\right)-\)entry is zero.

Divisibility relation on the set A = {1,2,3,4,5,6} as a logical matrix.
Figure 6.

Example 5.

The relation \(R\) on the set \(C = \left\{ {0,1,2,3} \right\}\) is given by the matrix \[M = \left[ {\begin{array}{*{20}{c}} 1&0&1&1\\ 0&1&0&1\\ 0&1&0&0\\ 0&1&0&1 \end{array}} \right].\] Represent \(R\) using a digraph.

Solution.

The digraph contains \(4\) nodes and \(8\) directed edges. The number of nodes is equal to the cardinality of the set \(C,\) and the number of edges is equal to the number of matrix elements with value \(1.\)

Digraph of a binary relation on the set A={0,1,2,3}.
Figure 7.

Example 6.

Let \(B = \left\{ {2,4,5,7,8,9} \right\}.\) A relation \(R\) on the set \(B\) is defined as follows: \[R = \left\{ {\left( {a,b} \right) \mid 2 \mid \left( {a + b} \right)} \right\}.\] Draw the digraph of \(R.\)

Solution.

To satisfy the divisibility condition \({2 \mid \left( {a + b} \right)},\) the sum of the components \(a\) and \(b\) must be even. Hence, the relation \(R\) includes the following ordered pairs:

\[{R = \left\{ {\left( {2,2} \right),\left( {2,4} \right),}\right.}\kern0pt{\left.{\left( {2,8} \right),\left( {4,2} \right),}\right.}\kern0pt{\left.{\left( {4,4} \right),\left( {4,8} \right),}\right.}\kern0pt{\left.{\left( {5,5} \right),\left( {5,7} \right),}\right.}\kern0pt{\left.{\left( {5,9} \right),\left( {7,5} \right),}\right.}\kern0pt{\left.{\left( {7,7} \right),\left( {7,9} \right),}\right.}\kern0pt{\left.{\left( {8,2} \right),\left( {8,4} \right),}\right.}\kern0pt{\left.{\left( {8,8} \right),\left( {9,5} \right),}\right.}\kern0pt{\left.{\left( {9,7} \right),\left( {9,9} \right)} \right\}.}\]

The directed graph of the divisibility relation looks as follows:

Digraph of a divisibility relation on the set A ={2,4,5,7,8,9}.
Figure 8.