# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it develops the theory of the work's theme —
binary relations on a set and their properties — together with algorithms for the
tasks in [4task.md](4task.md). No outside material is required.

## 2.1 Relations on a set

A **binary relation on a set** $A$ is a subset $R \subseteq A \times A$ of ordered
pairs. We write $(a, b) \in R$ (or $a\,R\,b$) to mean "$a$ is related to $b$." The
three properties below each quantify over the elements of $A$ or the pairs of $R$.

## 2.2 Reflexivity

$R$ is **reflexive** if **every** element is related to itself:

$$\forall a \in A : (a, a) \in R.$$

To check it, verify that the pair $(a, a)$ is present for each $a \in A$. Note
this needs the underlying set $A$, not just the pair list — a missing $(a,a)$ is
what makes a relation non-reflexive. Example: on $\{1,2,3\}$ the relation
$\{(1,1),(2,2),(3,3)\}$ is reflexive.

![Digraph of a reflexive relation: every node carries a self-loop](img/reflexive.png)

## 2.3 Symmetry

$R$ is **symmetric** if every pair's reverse is also present:

$$(a, b) \in R \ \Rightarrow\ (b, a) \in R.$$

Example: $\{(1,2),(2,1),(3,3)\}$ is symmetric — $(1,2)$ is matched by $(2,1)$, and
$(3,3)$ is its own reverse.

![Digraph of a symmetric relation: every arrow is matched by its reverse](img/symmetric.png)

## 2.4 Transitivity

$R$ is **transitive** if related pairs can be chained:

$$(a, b) \in R \ \text{and}\ (b, c) \in R \ \Rightarrow\ (a, c) \in R.$$

Example: $\{(1,2),(2,3),(1,3)\}$ is transitive — the only chain, $(1,2)$ then
$(2,3)$, is closed by $(1,3)$.

![Digraph of a transitive relation: a path a to b to c is closed by a direct a to c edge](img/transitive.png)

## 2.5 Antisymmetry, irreflexivity, and asymmetry

Three further properties complete the classification and lead to **partial orders**.

- $R$ is **antisymmetric** if the only way to have both $(a,b)$ and $(b,a)$ is
  $a=b$:
  $$(a,b)\in R \ \text{and}\ (b,a)\in R \ \Rightarrow\ a=b.$$
  Equivalently, no two **distinct** elements are related both ways. This is *not*
  the negation of symmetry — the identity relation is **both**, and many relations
  are **neither**. Example: $\le$ on numbers, or $\{(1,2),(1,3),(2,3)\}$.
- $R$ is **irreflexive** if **no** element is related to itself:
  $\forall a\in A:(a,a)\notin R$ — the diagonal is empty. (Not the same as "not
  reflexive": a relation can be neither reflexive nor irreflexive.)
- $R$ is **asymmetric** if $(a,b)\in R \Rightarrow (b,a)\notin R$; equivalently,
  asymmetric $=$ irreflexive $+$ antisymmetric. A strict order such as $<$ is the
  archetype.

## 2.6 Equivalence relations

$R$ is an **equivalence relation** if it is reflexive, symmetric, **and**
transitive. An equivalence relation splits $A$ into disjoint **equivalence
classes** $[a] = \{x \in A : (a, x) \in R\}$: every element belongs to exactly one
class, and two elements are related precisely when they share a class.

For instance, on $\{1, 2, 3\}$ the relation
$\{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ is an equivalence relation with classes
$\{1, 2\}$ and $\{3\}$. **Beware:** if a relation relates $1$ to $2$ and $2$ to
$3$, transitivity *forces* $1$ to be related to $3$ (and, with symmetry, $3$ to
$1$) — otherwise it is **not** an equivalence relation.

**Partial orders.** A relation that is reflexive, **antisymmetric**, and transitive
is a **partial order** (for example $\le$ on numbers, or $\subseteq$ on sets); unlike
an equivalence relation it need not relate every pair — where an equivalence relation
*groups* elements into classes, a partial order *ranks* them.

## 2.7 The inverse relation

The **inverse** of $R$ reverses every pair:

$$R^{-1} = \{(b, a) : (a, b) \in R\}.$$

For example, the inverse of $\{(1,2),(3,4),(5,6)\}$ is $\{(2,1),(4,3),(6,5)\}$. A
relation is symmetric exactly when $R = R^{-1}$.

## 2.8 Algorithms

Below, `member(R, p)` tests whether pair `p` is in the relation (a list scan).

```text
function isReflexive(R, A):
    for a in A:
        if not member(R, (a, a)): return false
    return true

function isSymmetric(R):
    for (a, b) in R:
        if not member(R, (b, a)): return false
    return true

function isTransitive(R):
    for (a, b) in R:
        for (c, d) in R:
            if b == c and not member(R, (a, d)): return false
    return true

function isAntisymmetric(R):
    for (a, b) in R:
        if a != b and member(R, (b, a)): return false
    return true

function isEquivalence(R, A):
    return isReflexive(R, A) and isSymmetric(R) and isTransitive(R)

function isPartialOrder(R, A):
    return isReflexive(R, A) and isAntisymmetric(R) and isTransitive(R)

function inverse(R):
    result ← empty list
    for (a, b) in R:
        append (b, a) to result
    return result
```

## 2.9 Complexity

With a list-based `member` (cost $O(|R|)$): `isReflexive` is
$O(|A|\cdot|R|)$, `isSymmetric` and `isAntisymmetric` are $O(|R|^2)$, and `isTransitive` is
$O(|R|^3)$ (a pair of nested loops over $R$, each inner test scanning $R$).
Storing the pairs in a hash set reduces `member` to $O(1)$, giving
$O(|A|)$, $O(|R|)$, and $O(|R|^2)$ respectively. `inverse` is $O(|R|)$.