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