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

## Properties of relations

1. What is a **binary relation on a set** $A$? How is it related to $A \times A$?
2. Define **reflexivity**. Why does checking it require the underlying set $A$ and
   not just the list of pairs?
3. Define **symmetry** and **transitivity**. For each, give a small relation that
   has the property and one that does not.
4. Is the relation $\{(1,2),(2,3)\}$ on $\{1,2,3\}$ transitive? If not, which pair
   must be added?

## Equivalence relations

5. Define an **equivalence relation**. What three properties must it have?
6. What is an **equivalence class**? Explain how an equivalence relation
   **partitions** its set.
7. A relation on $\{1,2,3\}$ contains $(1,2)$ and $(2,3)$ and is known to be an
   equivalence relation. Which other pairs **must** it contain, and why?

## Inverse and implementation

8. Define the **inverse** $R^{-1}$ of a relation $R$. What is the inverse of
   $\{(1,2),(3,4),(5,6)\}$?
9. Show that $R$ is symmetric **if and only if** $R = R^{-1}$.
10. What is the time complexity of your transitivity check? How would a hash-based
    membership test improve it?

## Tasks by hand

11. Let $A = \{1,2,3\}$ and $R = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}$. Is $R$
    reflexive? symmetric? transitive? Is it an equivalence relation? If so, list
    its equivalence classes.
12. Give the smallest relation on $\{1,2,3\}$ that contains $(1,2)$ and $(2,3)$
    and **is** an equivalence relation. List all its pairs.
13. Compute the inverse of $R = \{(1,3),(2,3),(3,1)\}$.