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