# 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),\left( {1,3} \right),\left( {2,1} \right),\left( {2,2} \right),\left( {2,3} \right),\left( {3,1} \right),\left( {3,2} \right),\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),\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),\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),\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),\left( {1,10} \right),\left( {2,1} \right),\left( {2,5} \right),\left( {5,2} \right),\left( {5,6} \right),\left( {5,10} \right),\left( {6,1} \right),\left( {6,5} \right),\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),\left( {1,5} \right),\left( {2,3} \right),\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\},\;\;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),\left( {1,3} \right),\left( {3,3} \right),\left( {3,5} \right),\left( {4,1} \right),\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\},\;\;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),\left( {b,1} \right),\left( {c,6} \right),\left( {d,1} \right),\left( {d,2} \right),\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:

See solved problems on Page 2.