# Calculus

## Set Theory # 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:

#### 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:

#### 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:

#### 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:

## 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.$$

### 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.

### 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.$$

### 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: