# Relations

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