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

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

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:

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

2.5 Reference algorithms #

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)$.

Laboratory/Laboratory2/2method.md · 4.8 KB · updated 2026-07-31 21:14