Множества и отношения — формальный слой

ОБЯЗАТЕЛЬНОДЛЯ НОВИЧКОВ

Архитектору Инженеру

Прикладные примеры множеств, отношений и матриц — в дискретной математике. Здесь — формальные определения из курса теории множеств: зачем нужны индукция, мощность и порядки при доказательстве корректности программ и схем данных.

---

Функции и биекции

Функция f : A → B каждому a ∈ A ставит в соответствие единственный f(a) ∈ B.

Свойство	Смысл	В IT
Инъекция	разные аргументы → разные значения	ключ без коллизий
Сюръекция	каждый элемент B достижим	покрытие кодов ошибок
Биекция	инъекция + сюръекция	взаимно однозначное кодирование, изоморфизм структур

Если между конечными множествами A и B есть биекция, то |A| = |B|. Сравнение мощностей бесконечных множеств (счётные и несчётные) объясняет, почему «перечислить все вещественные числа списком» принципиально отличается от перечисления целых.

---

Математическая индукция

Чтобы доказать свойство P(n) для всех n ∈ ℕ:

1. База: P(0) (или P(k) с некоторого k).
2. Шаг: для любого n из P(n) следует P(n+1).

Тогда P(n) верно для всех n ≥ начального значения. Полная индукция: доказывают P(n) из того, что P(m) верно для всех m < n — удобно для разборов по структуре дерева или рекурсивных типов.

// Инвариант цикла — частый вид индукции на практике
// После k итераций: сумма[0..k-1] = acc

база: k = 0, acc = 0  — верно
шаг: если после k верно, то после k+1 acc увеличивается на a[k] — верно

Тот же шаблон лежит в доказательстве корректности for и в анализе рекурсии (высота стека ≤ глубина вызовов).

---

Мощность конечных и перечислимых множеств

|A| = n для конечного A. Булеан P(A) всех подмножеств имеет мощность 2^n — источник экспоненциального перебора конфигураций в тестах и feature flags.

Для бесконечных множеств сравнивают существование биекции на ℕ (счётность). Множество строк над конечным алфавитом (при фиксированной длине или с ограничением) часто конечно или счётно; множество всех подпрограмм на языке Тьюринг-полном — несчётно — см. границы вычислений.

---

Порядки и изоморфизм

Частичный порядок (A, ⩽) рефлексивен, антисимметричен, транзитивен. Линейный порядок — любые два элемента сравнимы.

Любой конечный частичный порядок изоморфен семейству подмножеств A, упорядоченному по включению ⊆. В коде тот же смысл у иерархии пакетов Java, вложенных каталогов и решёток прав доступа.

Топологическая сортировка DAG (ориентированный ациклический граф порядка) — линейное расширение частичного порядка; без циклов в графе зависимостей задач.

---

Матрицы отношений (кратко)

На конечном A = {a₁,…,aₙ} отношение R ⊆ A² задаётся матрицей (rᵢⱼ) из 0 и 1. Композиция отношений связана с умножением матриц (с учётом булевого ∨ вместо +). Для эквивалентности матрицу приводят к блочно-диагональному виду — см. 32.

---

Дальше: реляционная алгебра и таблицы → дискретная математика (прикладная) → графы — углубление.

---