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 (a, b), where a ∈ A and b ∈ 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)

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:

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),\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:

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\},\;\;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:

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:

Graphical representation of relation between sets A and B.
Figure 4.

See solved problems on Page 2.

Page 1 Page 2