Let $A = \{a, b, c, d\}$ be a set which represents $4$ friends and $B = \{e, f, g\}$ a set which represents $3$ friends. Let ordered pairs, for example $(a, e)$, represent that person $a$ knows person $e$. Furthermore, we know that person $a$ knows person $e$, person $a$ knows $g$, person $b$ knows $f$, person $c$ knows $e$, person $c$ knows $f$ and person $c$ knows $g$.
It is naturally to start thinking about all the possibilities of knowing, i. e. set
$$A \times B = \{ (a, e), (a, f), (a, g), (b, e), (b, f), (b, g), (c, e), (c, f), (c, g), (d, e), (d, f), (d, g)\}.$$
If we observe only people who know each other, we actually observe a set
$$R = \{ (a, e), (a, g), (b, f), (c, e), (c, f), (c, g)\}.$$
Therefore, obviously $R \subseteq A \times B$. This motivates the following definition.
Binary relations
Definition: Let $A$ and $B$ be non – empty sets. Binary relation (or simply relation) between sets $A$ and $B$ is every subset $$R\subseteq A \times B. $$ If $(a, b) \in R$, we say that $a$ is related to $b$ by $R$ and denote by $aRb$.
If $A \neq B$, we say that $R$ is heterogeneous relation.
If $A = B$, we say that $R$ is homogeneous relation.
Definition: Let $A$ be non – empty set. Diagonal relation (or identity relation) on set $A$ is homogeneous binary relation
$$I_{A} = \{(a, a) \in A^{2} : a \in A\} \subseteq A^{2}.$$ Sometimes it is denoted by $id_{A}$ or $\triangle _{A}$.
Definition: Let $A$ and $B$ be non – empty sets and $R \subseteq A \times B$.
Domain of relation $R$ is a set
$$D(R) = \{a \in A: (\exists b \in B) (a, b) \in R\}\subseteq A.$$
Range of relation $R$ is a set
$$K(R) = \{b \in B: (\exists a \in A) (a, b) \in R\} \subseteq B.$$
Example 1: Let $R$ be the relation ”less than” between sets $A$ and $B$, where $A = \{3, 5, 7, 9\}$ and $B = \{2, 6, 8, 10\}$. Find the domain and range of $R$.
Solution:
$$R = \{(3, 6), (3, 8), (3, 10), (5, 6), (5, 8), (5, 10), (7, 8), (7, 10), (9, 10)\}$$
$$D(R) = \{3, 5, 7, 9\} = A$$
$$K(R) = \{6, 8, 10\}$$
Definition: Let $R \subseteq A \times B$ be a non – empty relation.
Converse relation (or reverse relation) of relation $R$ is relation $R^{-1}\subseteq B \times A$ defined by
$$R^{-1} = \{(b, a) \in B \times A: (a, b) \in R\}.$$
Definition: Let $R \subseteq A \times B$ be a relation.
The complementary relation of relation $R$ is relation
$$R^{C} = \{(a, b) \in A \times B: (a, b) \notin R\}.$$
Definition: Let $A, B$ and $C$ be non – empty sets and $R \subseteq A \times B$, $S \subseteq B \times C$ relations.
Composition of relations $R$ and $S$ is a relation $S \circ R \subseteq A \times C$ defined by
$$S \circ R \subseteq A \times C = \{(a, c) \in A \times C : (\exists b \in B) (a, b) \in R \land (b, c) \in S\}.$$
Example 2: Let $A = \{1, 2, 3\}, B = \{a, b\}$ and $C = \{x, y\}$ be the sets and $R \subseteq A \times B, S \subseteq B \times C$ relations defined by
$$R = \{(1, a), (2, b), (3, a), (3, b )\}$$
$$S = \{(a, y), (b, x)\}.$$
Find $R^{-1}, S^{C}$ and $S \circ R$.
Solution:
$$A \times B = \{(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)\}$$
$$B \times C = \{(a, x), (a, y), (b, x), (b, y)\}$$
$$R^{-1} = \{(a, 1), (b, 2), (a, 3), (b, 3)\}$$
$$S^{C} = \{(a, x), (b, y)\}$$
$$S \circ R = \{(1, y), (2, x), (3, y), (3, x)\}$$
Properties of relations
Theorem: Let $R$ and $S$ be relations. Composition of relations is not commutative, i.e. $$S \circ R \neq R \circ S.$$
Theorem: Let $R \subseteq A \times B, S \subseteq B \times C$ and $Z \subseteq C \times D$ be relations. Composition of relations is associative, i.e. $$Z \circ (S \circ R) = (Z \circ S) \circ R.$$
Proposition: Let $A$ and $B$ be non – empty sets and $R \subseteq A \times B$. Then
$$R \circ I_{A} = R$$
$$I_{B} \circ R = R,$$
i.e. identity relation is a neutral element for composition.
Lemma: Let $A$ and $B$ be non – empty sets and $R,S \subseteq A \times B$. Then
1) $R \subseteq S \Rightarrow R^{-1} \subseteq S^{-1}$
2) $(R \cup S)^{-1} = R^{-1} \cup S^{-1}$
3) $(R \cap S)^{-1} = R^{-1} \cap S^{-1}$
4) $(R^{-1})^{-1} = R.$
