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; recall the core properties — reflexive ®, 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):

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:

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

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

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

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

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\}$.

Practical/Practical2/3classroom.md · 10.2 KB · updated 2026-07-31 21:57