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

## Ordered pairs and the Cartesian product

1. What is an **ordered pair**? State the condition under which $(a,b) = (c,d)$,
   and explain why $(1,2) \neq (2,1)$ while $\{1,2\} = \{2,1\}$.
2. Define the **Cartesian product** $A \times B$. What is $|A \times B|$ in terms
   of $|A|$ and $|B|$?
3. Is $A \times B = B \times A$ in general? When are they equal?
4. What is $A \times \varnothing$? Justify your answer from the definition.

## Relations

5. Define a **binary relation** from $A$ to $B$. What does it mean for a relation
   to be a relation **on** a set $A$?
6. Exactly what does `isRelationValid(relation, A, B)` verify? Phrase your answer
   using the words *subset* and $A \times B$.
7. How many distinct relations exist from $A$ to $B$? Why? *(Hint: a relation is
   any subset of $A \times B$.)*
8. What does it mean to define a relation by a **predicate** $P(a,b)$? Write the
   set-builder form of such a relation.

## Implementation and complexity

9. How do you represent an ordered pair and a whole relation without using a
   built-in tuple/set type? How are two pairs compared for equality?
10. What is the time complexity of `cartesianProduct`? Why can it not be faster
    than $O(|A|\cdot|B|)$?
11. What is the cost of `isRelationValid` with a list-based membership test, and
    how would a hash-based test change it?
12. In `findRelations`, who decides whether the pair $(a,a)$ is included — the
    algorithm or the predicate? Explain.

## Tasks by hand

13. Compute $A \times B$ for $A = \{1,2\}$ and $B = \{x, y\}$. How many pairs do
    you get?
14. List the relation "$a < b$" **on** the set $A = \{1,2,3\}$ (pairs $(a,b)$
    with $a,b \in A$ and $a < b$). How many pairs are there?
15. Let $A = \{2, 3\}$ and $B = \{6, 8, 9\}$. Using the predicate "$a$ divides
    $b$", list the pairs of $A \times B$ that satisfy it.