Calculus

Set Theory

Set Theory Logo

Binary Relations

Solved Problems

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),\left( {0,5} \right),\left( {0,7} \right),\left( {2,2} \right),\left( {2,5} \right),\left( {2,7} \right),\left( {5,5} \right),\left( {5,7} \right),\left( {7,7} \right)} \right\}.\]

Example 2.

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

Solution.

Given that

\[\frac{2}{3} \approx 0.666,\;\;\frac{4}{7} \approx 0.571,\;\;\frac{5}{8} = 0.625,\;\;\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),\left( {\frac{{11}}{{17}},\frac{4}{7}} \right),\left( {\frac{2}{3},\frac{4}{7}} \right),\left( {\frac{{11}}{{17}},\frac{5}{8}} \right),\left( {\frac{2}{3},\frac{5}{8}} \right),\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),\left( {2,8} \right),\left( {4,2} \right),\left( {4,4} \right),\left( {4,8} \right),\left( {5,5} \right),\left( {5,7} \right),\left( {5,9} \right),\left( {7,5} \right),\left( {7,7} \right),\left( {7,9} \right),\left( {8,2} \right),\left( {8,4} \right),\left( {8,8} \right),\left( {9,5} \right),\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.
Page 1 Page 2