# 3. Classroom tasks and solutions / Аудиторні задачі та розв'язання > **Source of tasks.** The problems below are taken **exactly** from the > practical-class assignment for this topic (relations and their properties); > only the wording has been cleaned up and translated to English. Each task is > followed by a **complete worked solution**. The theory used is in > [2method.md](2method.md); recall the core properties — **reflexive (R)**, > **irreflexive (Ir)**, **symmetric (S)**, **antisymmetric (A)**, **asymmetric > (As)**, **transitive (T)** — and that a "no" is always justified by a **witness** > pair. ## Task 1 — Classify relations on $\{1,2,3,4\}$ **For each relation on the set $\{1,2,3,4\}$, decide whether it is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, and transitive.** **Summary of verdicts** (✓ = has the property, ✗ = does not): | Relation | Refl. | Irrefl. | Sym. | Antisym. | Asym. | Trans. | |---|:--:|:--:|:--:|:--:|:--:|:--:| | **(a)** $\{(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)\}$ | ✗ | ✗ | ✗ | ✗ | ✗ | ✓ | | **(b)** $\{(1,1),(1,2),(2,1),(2,2),(3,3),(4,4)\}$ | ✓ | ✗ | ✓ | ✗ | ✗ | ✓ | | **(c)** $\{(2,4),(4,2)\}$ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | | **(d)** $\{(1,2),(2,3),(3,4)\}$ | ✗ | ✓ | ✗ | ✓ | ✓ | ✗ | | **(e)** $\{(1,1),(2,2),(3,3),(4,4)\}$ | ✓ | ✗ | ✓ | ✓ | ✗ | ✓ | | **(f)** $\{(1,3),(1,4),(2,3),(2,4),(3,1),(3,4)\}$ | ✗ | ✓ | ✗ | ✗ | ✗ | ✗ | **Justifications.** - **(a)** Not reflexive — missing $(1,1),(4,4)$. Not symmetric — has $(2,4)$ but not $(4,2)$. Not antisymmetric — has both $(2,3)$ and $(3,2)$. Transitive — every first coordinate is $2$ or $3$, and $(2,c),(3,c)$ are present for all the $c$ that occur, so each 2-step chain has its shortcut (e.g. $(2,3),(3,4)\Rightarrow(2,4)$ ✓). - **(b)** Reflexive — all of $(1,1),(2,2),(3,3),(4,4)$ present. Symmetric — the only off-diagonal pairs are $(1,2)$ and $(2,1)$, and both are present. Not antisymmetric — $(1,2)$ and $(2,1)$ with $1\neq 2$. Transitive — e.g. $(1,2),(2,1)\Rightarrow(1,1)$ ✓, and all such shortcuts are present. - **(c)** Not reflexive — no diagonal pairs. Symmetric — $(2,4)$ and $(4,2)$ both present. Not antisymmetric — same two pairs, $2\neq 4$. Not transitive — $(2,4),(4,2)\Rightarrow(2,2)$, which is **missing**. - **(d)** Not reflexive — no diagonal pairs. Not symmetric — $(1,2)$ present but $(2,1)$ absent. Antisymmetric — no pair has its reverse, so the condition holds vacuously. Not transitive — $(1,2),(2,3)\Rightarrow(1,3)$ is missing. - **(e)** This is the **identity** relation. Reflexive, symmetric, antisymmetric, and transitive all hold — there are no off-diagonal pairs to violate anything. (It is both an equivalence relation and a partial order.) - **(f)** Not reflexive — no diagonal pairs. Not symmetric — $(1,4)$ present, $(4,1)$ absent. Not antisymmetric — $(1,3)$ and $(3,1)$ with $1\neq 3$. Not transitive — $(2,3),(3,1)\Rightarrow(2,1)$ is missing. **Irreflexive, asymmetric, antitransitive.** *Irreflexive* is read straight off the diagonal (no self-loops): (c), (d), (f) qualify; the rest carry at least one loop. *Asymmetric* $=$ irreflexive $+$ antisymmetric, so only **(d)** $\{(1,2),(2,3),(3,4)\}$ is asymmetric — and it is moreover **antitransitive**, since its only 2-step chains $(1,2),(2,3)$ and $(2,3),(3,4)$ have **no** shortcut ($(1,3),(2,4)\notin R$). ## Task 2 — Relations on the integers, defined by a rule **Determine whether the relation $R$ on the set of all integers $\mathbb{Z}$ is reflexive, irreflexive, symmetric, antisymmetric, asymmetric, and/or transitive, where $(x,y)\in R$ if and only if:** **Summary of verdicts:** | Rule for $(x,y)\in R$ | Refl. | Irrefl. | Sym. | Antisym. | Asym. | Trans. | |---|:--:|:--:|:--:|:--:|:--:|:--:| | **(a)** $x \neq y$ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | | **(b)** $xy \ge 1$ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | | **(c)** $x = y+1$ or $x = y-1$ | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | | **(g)** $x = y^2$ | ✗ | ✗ | ✗ | ✓ | ✗ | ✗ | | **(h)** $x \ge y^2$ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | **Justifications.** - **(a) $x \neq y$.** Not reflexive: $x \neq x$ is false. Symmetric: $x\neq y$ gives $y\neq x$. Not antisymmetric: $1\neq 2$ and $2\neq 1$ both hold with $1\neq 2$. Not transitive: $1\neq 2$ and $2\neq 1$, but $1\neq 1$ is false. - **(b) $xy \ge 1$.** Not reflexive: $0\cdot 0 = 0 \not\ge 1$. Symmetric: $xy = yx$. Not antisymmetric: $2\cdot 3\ge 1$ and $3\cdot 2\ge 1$ with $2\neq 3$. Transitive: $xy\ge 1$ forces $x,y$ to share a sign, so if also $yz\ge 1$ then $x,z$ share that sign and $xz\ge 1$. - **(c) $x = y\pm 1$** (i.e. $|x-y| = 1$). Not reflexive: $|x-x| = 0 \neq 1$. Symmetric: $|x-y| = |y-x|$. Not antisymmetric: $(1,2)$ and $(2,1)$ both satisfy it with $1\neq 2$. Not transitive: $(1,2),(2,1)\Rightarrow(1,1)$, but $|1-1| = 0 \neq 1$. - **(g) $x = y^2$.** Not reflexive: $x = x^2$ only for $x\in\{0,1\}$, not all $x$. Not symmetric: $(9,3)\in R$ since $9 = 3^2$, but $(3,9)\notin R$ since $3 \neq 9^2$. Antisymmetric: $x=y^2$ and $y=x^2$ force $x = x^4$, so $x\in\{0,1\}$ and then $y=x$. Not transitive: $(16,4)$ and $(4,2)$ are in $R$, but $16 \neq 2^2 = 4$. - **(h) $x \ge y^2$.** Not reflexive: $x \ge x^2$ fails already at $x=2$ ($2\not\ge 4$). Not symmetric: $(9,3)\in R$ ($9\ge 9$) but $(3,9)\notin R$ ($3\not\ge 81$). Antisymmetric: $x\ge y^2$ and $y\ge x^2$ force $x\ge y^2\ge x^4$, so $x\in\{0,1\}$ and $y=x$. Transitive: if $x\ge y^2$ and $y\ge z^2$, then $y^2 \ge z^4 \ge z^2$, so $x \ge y^2 \ge z^2$. ## Task 3 — The inverse of a relation **Let $R = \{(a,b) \mid a \mid b\}$ be the "divides" relation on the set of positive integers. Find $R^{-1}$.** **Solution.** The inverse reverses every pair: $$R^{-1} = \{(b,a) \mid (a,b)\in R\} = \{(b,a) \mid a \mid b\}.$$ Renaming the dummy variables ($a\leftrightarrow b$) states it in the usual order: $$R^{-1} = \{(a,b) \mid b \mid a\}.$$ In words, $R^{-1}$ is the **"is a multiple of"** relation: $a\,R^{-1}\,b$ holds exactly when $a$ is a multiple of $b$. ## Task 4 — Operations on the relations $<$ and $=$ **Given $A = \{0,1,2,3\}$ and the two relations $<$ and $=$ on $A$: represent each as a set of ordered pairs, and find their union, intersection, difference, and complement.** **Solution.** As sets of pairs (the universe is $A\times A$, with $|A\times A| = 16$ pairs): $$<\ =\ \{(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)\}, \qquad {=}\ =\ \{(0,0),(1,1),(2,2),(3,3)\}.$$ - **Union** — every pair in $<$ or in $=$; this is exactly the relation $\le$: $$<\ \cup\ {=}\ =\ \{(0,0),(0,1),(0,2),(0,3),(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)\}.$$ - **Intersection** — no pair is both "less than" and "equal": $$<\ \cap\ {=}\ =\ \varnothing.$$ - **Difference** — since the two relations are disjoint, removing $=$ changes nothing: $<\ \setminus\ {=}\ =\ <$ (and symmetrically ${=}\setminus{<}\ =\ {=}$). - **Complement** (relative to $A\times A$) — the pairs **not** in each relation: $$\overline{<}\ =\ \{(a,b) : a \ge b\}\ =\ \{(0,0),(1,0),(1,1),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2),(3,3)\}\ (=\ \ge),$$ $$\overline{=}\ =\ \{(a,b) : a \neq b\}\ (12\ \text{pairs}).$$ ## Task 5 — A relation given by a matrix (doubles teams) **Given the set of table-tennis players $P = \{\text{Bob}, \text{Sam}, \text{Tom}, \text{Paul}\}$, define the relation "to play in the same doubles team" by a matrix, and check its properties.** **Solution.** A doubles arrangement splits the four players into two teams of two; take **Team 1 $= \{$Bob, Sam$\}$** and **Team 2 $= \{$Tom, Paul$\}$** (any pairing works the same way). "Same team" includes each player with themselves, so $$R = \{(\text{Bob},\text{Bob}),(\text{Sam},\text{Sam}),(\text{Tom},\text{Tom}), (\text{Paul},\text{Paul}),(\text{Bob},\text{Sam}),(\text{Sam},\text{Bob}), (\text{Tom},\text{Paul}),(\text{Paul},\text{Tom})\}.$$ As a Boolean matrix (order Bob, Sam, Tom, Paul): | $M_R$ | Bob | Sam | Tom | Paul | |:--:|:--:|:--:|:--:|:--:| | **Bob** | 1 | 1 | 0 | 0 | | **Sam** | 1 | 1 | 0 | 0 | | **Tom** | 0 | 0 | 1 | 1 | | **Paul** | 0 | 0 | 1 | 1 | **Properties.** Reflexive — the diagonal is all $1$ (everyone is on their own team). Symmetric — the matrix equals its transpose (if $x$ is Sam's teammate, Sam is $x$'s). **Not** antisymmetric — Bob and Sam are related both ways with $\text{Bob}\neq\text{Sam}$. Transitive — the two $2\times 2$ blocks of $1$s are closed under chaining. Reflexive $+$ symmetric $+$ transitive means $R$ is an **equivalence relation**; its equivalence classes are the two teams $\{$Bob, Sam$\}$ and $\{$Tom, Paul$\}$ — a **partition** of $P$. ![The doubles "same team" relation: two clusters (equivalence classes) with mutual arrows and self-loops](img/task5_teams.png) ## Task 6 — One relation, three representations (divisibility) **Given $A = \{1,2,3,4\}$ and the relation $x\,R\,y$ meaning "$x$ divides $y$" ($x \mid y$, i.e. $y$ is a multiple of $x$), present $R$ as (1) ordered pairs, (2) a matrix, and (3) a directed graph, and determine its properties and type.** **Solution.** **(1) Ordered pairs.** Test $x \mid y$ for all $x,y\in\{1,2,3,4\}$ (note $1$ divides everything, and every number divides itself): $$R = \{(1,1),(1,2),(1,3),(1,4),(2,2),(2,4),(3,3),(4,4)\}.$$ **(2) Matrix** ($M_{xy} = 1$ iff $x \mid y$): | $M_R$ | 1 | 2 | 3 | 4 | |:--:|:--:|:--:|:--:|:--:| | **1** | 1 | 1 | 1 | 1 | | **2** | 0 | 1 | 0 | 1 | | **3** | 0 | 0 | 1 | 0 | | **4** | 0 | 0 | 0 | 1 | **(3) Directed graph.** A self-loop at every node (since $x \mid x$), plus arrows $1\to 2$, $1\to 3$, $1\to 4$ and $2\to 4$: ![Directed graph of the divisibility relation on {1,2,3,4}: loops on all nodes, with arrows 1→2, 1→3, 1→4 and 2→4](img/task6_digraph.png) **Properties and type.** Reflexive — every $(x,x)$ is present ($x \mid x$). **Not** symmetric — $(1,2)\in R$ but $(2,1)\notin R$ ($1\mid 2$ but $2\nmid 1$). Antisymmetric — if $x\mid y$ and $y\mid x$ for positive integers then $x=y$, so no two distinct elements are related both ways. Transitive — if $x\mid y$ and $y\mid z$ then $x\mid z$ (e.g. $1\mid 2$ and $2\mid 4$ give $1\mid 4$ ✓). Being reflexive, antisymmetric, and transitive, $R$ is a **partial order** — the **divisibility order** on $\{1,2,3,4\}$.