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

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

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.

Practical/Practical2/2method.md · 6.5 KB · updated 2026-08-01 20:18