Отношения: упорядоченные пары и сетка того, кто с кем связан
Упорядоченная пара помнит порядок: (a, b) — не то же, что (b, a). Декартово произведение A × B — сетка всех пар, а отношение — выбранное подмножество сетки. Внешние ключи, === и графы подписок — отношения; рефлексивность, симметричность и транзитивность их различают.
Джуниору досталось социальное приложение с таблицей follows(follower_id, followee_id) и баг-репортом: «в списке моих подписчиков — люди, на которых подписан я, а не те, кто подписан на меня». Запрос читал WHERE follower_id = :me — и возвращал аккаунты, на которые подписан я, потому что первая колонка — та, что подписывается. Исправление — поменять местами два имени колонок. Ничто из мира множеств к этому багу не готовило: у множества нет первого и второго, так что предыдущие два урока даже не могут выразить «Аня подписана на Бориса, а Борис на Аню — нет». Чтобы это сказать, нужна пара, в которой позиция несёт смысл — и как только появляются упорядоченные пары, «подписан на», «меньше чем», «ссылается по внешнему ключу», даже === оказываются одним и тем же математическим объектом: множеством упорядоченных пар, подмножеством сетки.
После этого урока ты можешь определить упорядоченную пару и объяснить, почему важна позиция, построить декартово произведение A × B и посчитать его размер, определить отношение как подмножество произведения, проверить свойства рефлексивности, симметричности и транзитивности, и запустить трёхэлементный разбор на конкретном отношении.
Упорядоченная пара (a, b) делает позицию значимой. В отличие от множества, где {a, b} = {b, a}, упорядоченная пара (a, b) = (c, d) только тогда, когда a = c и b = d. Значит, (1, 2) ≠ (2, 1). Упорядоченные пары — повсюду: координаты (x, y), записи «ключ–значение», строки (follower_id, followee_id). Баг из хука — это именно баг упорядоченной пары: строка (аня, борис) означает «аня подписана на бориса», и чтение колонок в обратном порядке разворачивает все стрелки графа.
Декартово произведение A × B — множество всех упорядоченных пар (a, b), где a из A, а b из B. Представьте сетку: A — метки строк, B — метки столбцов, каждая ячейка — одна пара. Количество: |A × B| = |A| · |B|. Если A = {1, 2, 3} и B = {x, y, z, w}: 3 × 4 = 12 пар. Забытое условие JOIN в SQL даёт именно эту сетку целиком.
const a = [1, 2, 3];
const b = ["x", "y", "z", "w"];
const grid = a.flatMap((m) => b.map((n) => [m, n]));
grid.length; // 12 = 3 × 4Отношение из A в B — любое подмножество A × B. Сетка перечисляет все пары, которые могут быть связаны; отношение хранит пары, которые связаны на самом деле. Чтобы сказать «a связано с b», проверяем (a, b) ∈ R — вопрос о принадлежности. Таблица follows над пользователями {аня, борис, кира} — некоторое подмножество 9-ячеечной сетки пользователи × пользователи. Пустое отношение (никто ни на кого не подписан) и полная сетка (все на всех) — оба законных крайних случая.
Три попарные проверки раскрывают характер отношения. Когда R ⊆ A × A:
- Рефлексивность — (x, x) ∈ R для всех x. «x ≤ x» — да. «x — предок себя» — нет.
- Симметричность — (x, y) ∈ R влечёт (y, x) ∈ R. Взаимная дружба — да. Follows — заведомо нет.
- Транзитивность — (x, y) ∈ R и (y, z) ∈ R влекут (x, z) ∈ R. Предок-от — да. Follows — нет.
Функция — частный случай отношения, в котором каждый элемент A фигурирует как первая координата ровно в одной паре — один выход на вход. Большинство хранимых отношений — follows, внешние ключи, теги — многие-ко-многим и функциями не являются.
Трёхэлементный разбор: A = {1, 2, 3}, R = {(1,1), (2,2), (1,2), (2,1)}.
- Рефлексивное? Нужны (1,1), (2,2), (3,3). Нет (3,3) → нерефлексивное. Достаточно одной отсутствующей диагональной пары, чтобы не пройти.
- Симметричное? (1,2) → есть (2,1) ✓; диагональные пары сами себе обратные ✓ → симметричное.
- Транзитивное? (1,2) и (2,1) требуют (1,1) ✓; (2,1) и (1,2) требуют (2,2) ✓ → транзитивное.
Это настоящая техника отладки: проверка свойств на малых отношениях подтверждает предположения до того, как на них опирается код.
▸Граничные случаи
Является ли === рефлексивным? Почти — но NaN === NaN равно false по стандарту IEEE 754, что делает === на числах нерефлексивным. Эта одна отсутствующая диагональная пара имеет реальные последствия: array.indexOf(NaN) никогда его не найдёт (indexOf использует ===), тогда как array.includes(NaN) найдёт (includes использует SameValueZero, который считает NaN равным себе).
|A| = 5 и |B| = 3. Сколько пар в A × B? Напишите число.
Одинакова ли упорядоченная пара (2, 1) с (1, 2)? Ответьте «да» или «нет».
R = {(1,1),(2,2),(3,3)} на {1,2,3}. Является ли R рефлексивным? Ответьте «да» или «нет».
R = {(1,2),(2,1)} на {1,2,3}. Является ли R рефлексивным? Ответьте «да» или «нет».
R = {(1,2),(2,3)} на {1,2,3}. Для транзитивности: (1,2) и (2,3) в R — какая пара ещё должна быть в R? Запишите как (x,y).
|A| = 3 и |B| = 4. Сколько пар в A × B, и чем именно является отношение из A в B?
Упорядоченная пара (a, b) делает позицию значимой — (a, b) ≠ (b, a). Декартово произведение A × B собирает все |A| · |B| возможных пар в сетку — 3 × 4 даёт 12, и забытое условие JOIN выдаёт именно её. Отношение — любое подмножество сетки: определение, превращающее «связан» в вопрос о принадлежности, (a, b) ∈ R. Таблицы с внешними ключами хранят отношения строка за строкой; === задаёт одно через его истинные пары. На одном множестве три попарные проверки классифицируют отношение: рефлексивное (каждая диагональная пара присутствует), симметричное (каждая стрелка обращена), транзитивное (стрелки складываются цепочкой). Трёхэлементный разбор делает проверки механическими. Функции — не общий случай, а частный: отношение, в котором каждый вход фигурирует как первая координата ровно в одной паре; большинство хранимых отношений — многие-ко-многим.
Практика
Начни сверху. Задачи идут от простого к сложному: вспомнить факт, применить к случаю, затем senior-уровень. Открой, попробуй, потом открой ответ.
Что-то непонятно?
Задай вопрос по этому уроку. Вопросы анонимны и попадают напрямую автору — урок станет лучше.