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

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.

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

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

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

Laboratory/Laboratory3/2method.md · 5.1 KB · updated 2026-07-31 21:59