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

This section is **self-contained**: it collects all the theory needed for the
theme — binary relations, their representations, properties, operations, and
types — together with the techniques used to solve the tasks in
[3classroom.md](3classroom.md). No outside material is required.

## 2.1 What a relation is

A **binary relation** $R$ from a set $A$ to a set $B$ is any **subset of the
Cartesian product** $A \times B$ — that is, any set of ordered pairs $(a,b)$ with
$a \in A$ and $b \in B$. When $(a,b) \in R$ we say "$a$ is related to $b$" and
write $a\,R\,b$; otherwise $a \not\!R\,b$.

Most of this work concerns a **relation on a set** $A$: a subset of $A \times A$.
Because $A \times A$ has $|A|^2$ pairs, there are $2^{|A|^2}$ different relations
on $A$. Two special relations recur:

- the **identity (equality)** relation $\{(a,a) : a \in A\}$ — every element
  related only to itself;
- the **empty** relation $\varnothing$ and the **universal** relation
  $A \times A$.

## 2.2 Three ways to represent a relation

The same relation can be written in three interchangeable forms; a task may ask
for any of them.

- **Ordered pairs** — list the members of $R$, e.g. $R = \{(1,2),(2,3),(1,3)\}$.
- **Boolean matrix** $M_R$ — an $|A|\times|A|$ grid with $M_{ij} = 1$ exactly when
  $(a_i, a_j) \in R$, and $0$ otherwise. Rows are the "from" element, columns the
  "to" element.
- **Directed graph (digraph)** — draw a node for each element of $A$ and an arrow
  $a \to b$ for each pair $(a,b) \in R$. A pair $(a,a)$ becomes a **self-loop**.

For example, $R = \{(1,1),(1,2),(2,3)\}$ on $\{1,2,3\}$ has the matrix
$\begin{smallmatrix}1&1&0\\0&0&1\\0&0&0\end{smallmatrix}$ and a digraph with a loop
at $1$ and arrows $1\to 2$, $2\to 3$.

## 2.3 The core properties

Let $R$ be a relation on a set $A$. The properties tested throughout this work are:

| Property | Definition | In the digraph | In the matrix $M_R$ |
|---|---|---|---|
| **Reflexive** | $(a,a) \in R$ for **every** $a \in A$ | a self-loop at **every** node | the whole diagonal is $1$ |
| **Irreflexive** | $(a,a) \notin R$ for **every** $a \in A$ | **no** self-loops anywhere | the whole diagonal is $0$ |
| **Symmetric** | $(a,b)\in R \Rightarrow (b,a)\in R$ | every arrow has a reverse | $M_R$ is symmetric ($M_{ij}=M_{ji}$) |
| **Antisymmetric** | $(a,b)\in R$ and $(b,a)\in R \Rightarrow a=b$ | no two **distinct** nodes joined both ways | no $i \neq j$ with $M_{ij}=M_{ji}=1$ |
| **Asymmetric** | $(a,b)\in R \Rightarrow (b,a)\notin R$ | no reverse arrow **and** no self-loop | zero diagonal **and** no mirror pair |
| **Transitive** | $(a,b),(b,c)\in R \Rightarrow (a,c)\in R$ | every 2-step path $a\to b\to c$ has a shortcut $a\to c$ | the $1$s of the Boolean $M_R^2$ are already $1$ in $M_R$ |
| **Antitransitive** | $(a,b),(b,c)\in R \Rightarrow (a,c)\notin R$ | **no** 2-step path has a shortcut | wherever $M_R^2$ has a $1$, $M_R$ has a $0$ |

![Small digraphs illustrating the reflexive, symmetric, antisymmetric, and transitive properties](img/method_properties.png)

Three cautions that decide many exercises:

- **Reflexive and irreflexive are *not* opposites.** A relation can be **neither** —
  e.g. $\{(1,1)\}$ on $\{1,2\}$ has a loop at $1$ (so not irreflexive) but misses the
  loop at $2$ (so not reflexive).
- **Antisymmetric is *not* "not symmetric."** They are different conditions. The
  identity relation is **both** symmetric and antisymmetric; many relations are
  **neither**. Antisymmetry only forbids a *2-cycle between distinct elements* —
  self-loops $(a,a)$ never violate it. **Asymmetric** is the stronger cousin:
  asymmetric $=$ irreflexive $+$ antisymmetric (a strict order such as $<$ is the
  archetype).
- **A "no" needs a witness.** To *disprove* a property, exhibit one concrete
  offending pair (or missing pair): e.g. "not transitive because $(1,2),(2,3)\in
  R$ but $(1,3)\notin R$."

## 2.4 Operations on relations

Since relations are **sets** of pairs, the set operations apply directly. For
relations $R$ and $S$ on $A$:

| Operation | Definition |
|---|---|
| **Union** | $R \cup S = \{(a,b) : (a,b)\in R \ \text{or}\ (a,b)\in S\}$ |
| **Intersection** | $R \cap S = \{(a,b) : (a,b)\in R \ \text{and}\ (a,b)\in S\}$ |
| **Difference** | $R \setminus S = \{(a,b) : (a,b)\in R \ \text{and}\ (a,b)\notin S\}$ |
| **Complement** | $\overline{R} = (A\times A)\setminus R = \{(a,b) : (a,b)\notin R\}$ |
| **Inverse** | $R^{-1} = \{(b,a) : (a,b)\in R\}$ |

The **complement** is taken relative to the universe $A \times A$ (all $|A|^2$
possible pairs), so always know how large $A \times A$ is. The **inverse** simply
**reverses every pair** (reverses every arrow in the digraph, transposes the
matrix): if $R$ means "$a$ divides $b$", then $R^{-1}$ means "$a$ is a multiple of
$b$."

*(A related construction, used later, is **composition** $S \circ R = \{(a,c) :
(a,b)\in R \text{ and } (b,c)\in S \text{ for some } b\}$ — "follow $R$, then
$S$." It is not needed for this work.)*

## 2.5 Types of relation

Certain combinations of properties have names and great importance:

- **Equivalence relation** — **reflexive + symmetric + transitive**. It models a
  notion of "sameness" and splits $A$ into disjoint **equivalence classes** (a
  **partition**): each element lies in exactly one class of things related to it.
  Examples: equality, "same remainder mod $n$", "on the same team."
- **Partial order** — **reflexive + antisymmetric + transitive**. It models a
  consistent "$\le$" in which some elements may be **incomparable**. Examples:
  $\le$ on numbers, $\subseteq$ on sets, and **divisibility** $a \mid b$ on the
  positive integers.

Recognising a type is just checking the three defining properties and naming the
result.

## 2.6 Working checklist

- To classify a relation, test the **six properties one at a time**; for each,
  either argue it holds *for all* required pairs, or give **one counterexample**.
- Watch the two traps: *reflexive* needs $(a,a)$ for **every** $a$ (a single
  missing loop kills it); *antisymmetric* is about **distinct** elements only.
- For a relation defined by a **formula** on the integers, test a property by
  reasoning about the formula (e.g. "$xy=yx$, so the relation $xy\ge 1$ is
  symmetric") and disprove it with a **specific small pair**.
- For an **operation** task, write both relations as pairs first, then combine;
  for a **complement**, remember the universe is $A\times A$.
- To find a **type**, check reflexive + (symmetric ⇒ equivalence) or
  (antisymmetric ⇒ partial order), together with transitive.