# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects all the theory of the work's
theme — ordered pairs, the Cartesian product, and binary relations — together
with practical guidance for carrying out the tasks in [4task.md](4task.md). No
outside material is required.

## 2.1 Ordered pairs and the Cartesian product

An **ordered pair** $(a, b)$ is two objects taken in a definite order: $a$ is the
first component, $b$ the second. Unlike a set, **order matters** and repetition
is meaningful:

$$(a, b) = (c, d) \iff a = c \ \text{and}\ b = d.$$

Thus $(1, 2) \neq (2, 1)$, whereas $\{1, 2\} = \{2, 1\}$.

The **Cartesian product** of sets $A$ and $B$ is the set of *all* ordered pairs
whose first component comes from $A$ and second from $B$:

$$A \times B = \{(a, b) : a \in A \ \text{and}\ b \in B\}.$$

Its size is the product of the sizes:

$$|A \times B| = |A| \cdot |B|.$$

For example, $\{1, 2\} \times \{a, b\} = \{(1,a), (1,b), (2,a), (2,b)\}$, which
has $2 \cdot 2 = 4$ elements. In general $A \times B \neq B \times A$: the pairs
$(1, a)$ and $(a, 1)$ are different. If either factor is empty, the product is
empty.

![Cartesian product A × B laid out as a grid of all six ordered pairs](img/cartesian.png)

## 2.2 Binary relations

A **binary relation** from $A$ to $B$ is any **subset** $R \subseteq A \times B$.
When $(a, b) \in R$ we say "$a$ is related to $b$." If $A = B$ we call $R$ a
relation **on** $A$.

![A binary relation R as a subset of A × B, shown by arrows from A to B](img/relation_subset.png)

Because a relation is just a set of ordered pairs, everything from set theory
applies to it. Two consequences used in this work:

- **Validity.** A list of ordered pairs is a valid relation for $A$ and $B$
  exactly when every pair $(a, b)$ in it satisfies $a \in A$ **and** $b \in B$ —
  i.e. the list is a subset of $A \times B$. This is what `isRelationValid`
  checks.
- **Counting.** Since $A \times B$ has $|A|\cdot|B|$ elements, the number of
  distinct relations from $A$ to $B$ is $2^{|A|\cdot|B|}$ (every subset is a
  relation).

## 2.3 Relations defined by a predicate

A relation is most often described not by listing pairs but by a **predicate** —
a condition $P(a, b)$ that each pair either satisfies or not:

$$R = \{(a, b) \in A \times B : P(a, b)\}.$$

To build $R$ you walk over the candidate pairs and keep those for which
$P(a, b)$ holds. Typical predicates are "$a$ divides $b$", "$a < b$", or "$a$ and
$b$ have the same parity." The predicate itself decides the fine print — for
instance whether the pair $(a, a)$ is allowed.

Two of this work's tasks are exactly this pattern:

- **`findRelations`** applies a predicate to pairs drawn from a **single** set
  (a relation *on* that set);
- **`filteredCartesianProduct`** applies a predicate to pairs of a **product**
  $A \times B$, keeping only those that pass.

Both are the same idea — form the candidate pairs, then filter by $P$.

## 2.4 Representing pairs and products without built-in types

Represent an **ordered pair** as a fixed two-element structure (a 2-tuple or a
length-2 array $[a, b]$), and a **product / relation** as a list of such pairs.
The membership test from Laboratory Work 1 — scan a list and compare — is reused
to check whether a component belongs to a set:

```text
function contains(S, x):
    for y in S:
        if y == x: return true
    return false
```

## 2.5 Reference algorithms

```text
function cartesianProduct(A, B):
    R ← empty list
    for a in A:
        for b in B:
            append (a, b) to R
    return R

function isRelationValid(relation, A, B):
    for (a, b) in relation:
        if not contains(A, a) or not contains(B, b):
            return false                 # a pair lies outside A × B
    return true

function findRelations(A, P):            # relation on A defined by predicate P
    R ← empty list
    for a in A:
        for b in A:
            if P(a, b): append (a, b) to R
    return R

function filteredCartesianProduct(A, B, P):
    R ← empty list
    for a in A:
        for b in B:
            if P(a, b): append (a, b) to R
    return R
```

The predicate `P(a, b)` is supplied by the caller; whether it admits the pair
$(a, a)$ is part of its definition, so `findRelations` does not special-case it.

## 2.6 Size and complexity

- `cartesianProduct` produces $|A|\cdot|B|$ pairs and runs in
  $O(|A|\cdot|B|)$ — this is optimal, since the output itself has that size.
- `isRelationValid` costs $O(|R|\cdot(|A| + |B|))$ with a list-based membership
  test (each pair triggers two scans); a hash-based membership test would reduce
  this to $O(|R|)$.
- `findRelations` evaluates the predicate on all $|A|^2$ ordered pairs, so it is
  $O(|A|^2 \cdot c_P)$ where $c_P$ is the cost of one predicate call; likewise
  `filteredCartesianProduct` is $O(|A|\cdot|B| \cdot c_P)$.