Skip to main content

Discrete Mathematical Structures

Dan Yasaki, Sebastian Pauli

Subsection 6.1.3 Combining binary relations

Since relations are sets, we can take unions, intersections, differences, and complements of relations.
🔗

Example 6.1.3.1. Students and courses.

Let \(S\) be the set of students at UNCG, and let \(C\) be the set of courses at UNCG. Let \(T\) and \(N\) be the relations from \(S\) to \(C\text{,}\)
\begin{align*} T \amp = \{(s,c) \in S \times C \given s \text{ has taken }\}; \\ N \amp = \{(s,c) \in S \times C \given s \text{ needs }c\text{ to graduate}\}. \end{align*}
Then
\begin{align*} T \cap N \amp = \{(s,c) \in S \times C \given s \text{ has taken }c\text{ and needs }c\text{ to graduate}\};\\\\ T - N \amp = \{(s,c) \in S \times C \given s \text{ has taken }c \text{ but does not need }c \text{ to graduate}\}. \end{align*}
🔗
🔗
Like functions, we can represent relations in many ways.
🔗

Example 6.1.3.2. Relation divides.

Let \(R\) be the relation on \(\{1, 2,3,4,5,6\}\) given by \(a\,R\,b\) if and only if \(a\) divides \(b\text{.}\) Then
\begin{align*} R = \bigl\{\amp (1, 1),(1,2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), \\ \amp(2, 4),(2, 6),(3, 3), (3, 6), (4, 4), (5, 5), (6, 6) \bigr\}. \end{align*}
We can represent it graphically as
🔗
We can represent \(R\) in a table by putting an \(\times\) in the \(a\) th row and \(b\) th column if and only if \(a\) divides \(b\text{.}\)
\begin{equation*} \begin{array}{c|cccccc} R \amp 1 \amp 2 \amp 3 \amp 4 \amp 5 \amp 6 \\ \hline 1 \amp \times\amp \times\amp \times\amp \times\amp \times\amp \times\\ 2\amp \amp \times\amp \amp \times\amp\amp \times\\ 3\amp \amp \amp \times\amp \amp\amp \times\\ 4\amp\amp\amp\amp\times\\ 5\amp\amp\amp\amp\amp\times\\ 6\amp\amp\amp\amp\amp\amp\times \end{array} \end{equation*}
🔗
🔗
Like functions, we can also compose relations.
🔗

Definition 6.1.3.3.

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be sets. Suppose \(R\) is a relation from \(A\) to \(B\text{,}\) and \(S\) is a relation from \(B\) to \(C\text{.}\) The composite or composition of \(R\) and \(S\text{,}\) denoted \(S \circ R\text{,}\) is the relation from \(A\) to \(C\)
\begin{equation*} S \circ R = \{(a, c) \in A \times C \given \exists b \in B \text{ such that }a\,R\,b\text{ and }b S c\}. \end{equation*}
🔗
🔗
Three sets A and B and C are represented each by an oval. The ovals do not overlap. An arrow labeled R goes from A to B. An arrow labeled S goes from B to C. An arrow labeled the composition of S and R goes from A to C.
Figure 6.1.3.4. Composition of the two relations \(S\subseteq B\times C\) and \(R\subseteq A\times B\text{.}\)
🔗

Example 6.1.3.5. Composition of relations.

Let \(A = \{1, 2, 3\}\text{,}\) \(B = \{1, 2, 3, 4\}\text{,}\) and \(C = \{0, 1, 2\}\text{.}\) Let \(R\) be the relation from \(A\) to \(B\)
\begin{equation*} R = \{(1,1), (1,4), (2,3), (3,1), (3,4)\}, \end{equation*}
and let \(S\) be the relation from \(B\) to \(C\)
\begin{equation*} S = \{(1,0), (2,0), (3,1), (3,2), (4,1)\}. \end{equation*}
Compute the composition \(S \circ R\text{.}\)
🔗
One approach is to view this graphically.
🔗
Then
\begin{equation*} S\circ R = \{(1,0), (2,1), (2,2), (1,1), (3,0), (3,1)\}. \end{equation*}
🔗
🔗
🔗
PrevTopNext