6. Control questions and tasks / Контрольні запитання і завдання #

Relations and representations #

1. Define a binary relation on a set $A$. How many different relations are there on a set with $n$ elements, and why?
2. Describe the three representations of a relation — ordered pairs, Boolean matrix, directed graph — and how each pair $(a,b)$ appears in each. What is a self-loop in the digraph?
3. Write the relation $R = \{(1,1),(1,3),(2,2),(3,1)\}$ on $\{1,2,3\}$ as a Boolean matrix and as a directed graph.

The four properties #

4. State the definitions of reflexive, symmetric, antisymmetric, and transitive. For each, say how it shows up in the matrix and in the digraph.
5. Explain why antisymmetric is not the same as “not symmetric.” Give a relation that is both symmetric and antisymmetric, and one that is neither.
6. To disprove that a relation is transitive, what exactly must you exhibit? Illustrate with the relation $\{(1,2),(2,3)\}$ on $\{1,2,3\}$.
7. Is the empty relation on a non-empty set reflexive? Symmetric? Antisymmetric? Transitive? Justify each answer.

Operations and inverse #

8. Define $R \cup S$, $R \cap S$, $R \setminus S$, $\overline{R}$, and $R^{-1}$ for relations on $A$. Relative to what universe is $\overline{R}$ taken?
9. For the divides relation $R = \{(a,b)\mid a\mid b\}$ on the positive integers, describe $R^{-1}$ in words. What does reversing every arrow of the digraph do?
10. Let $A = \{0,1,2\}$. Write the relations $<$ and $=$ as pairs, and compute $<\cup\,{=}$, $<\cap\,{=}$, and $\overline{<}$ (relative to $A\times A$).

Types of relation #

11. Define an equivalence relation and a partial order in terms of the four properties. Give one everyday example of each.
12. Why does an equivalence relation produce a partition of the set? What are the equivalence classes of the “same doubles team” relation from Task 5?
13. Show that the divisibility relation on $\{1,2,3,4\}$ (Task 6) is a partial order but not an equivalence relation. Which single property separates the two types here?

Tasks by hand #

14. Classify $\{(1,1),(1,2),(2,1),(2,2),(3,3)\}$ on $\{1,2,3\}$ by all four properties, justifying every “no” with a witness pair.
15. On $\mathbb{Z}$, let $(x,y)\in R$ iff $x + y$ is even. Decide whether $R$ is reflexive, symmetric, antisymmetric, and transitive, and name its type.

Practical/Practical2/6questions.md · 2.5 KB · updated 2026-07-31 21:14