Функции: инъекции, сюръекции, биекции

Каждый раз когда возникает ошибка «хеш-коллизия» или «duplicate key» в базе данных, за этим стоит математика функций. SHA-256 стойкий не потому что «хорошо написан» - а потому что его кодомен настолько велик, что принцип Дирихле вступает в силу лишь при астрономическом числе попыток.

• **Хеш-таблицы (HashMap):** open addressing и chaining - две стратегии борьбы с неизбежными коллизиями при load factor > 0.7
• **Криптография (AES, RSA):** функции шифрования обязаны быть биекциями - иначе дешифровка невозможна математически
• **Базы данных (UNIQUE constraint):** гарантия инъективности для выбранных колонок на уровне схемы
• **Парадокс дней рождения:** основа birthday attack на хеш-функции и причина обязательного соления паролей

Предварительные знания

• Relations and Partial Orders

Функция: область, кодомен, образ

Функция f: A → B - это бинарное отношение на A × B такое, что каждому элементу a ∈ A сопоставлен ровно один элемент f(a) ∈ B. Важно различать три понятия: область определения (domain) A, кодомен (codomain) B, и образ (image) f(A) = {f(a) | a ∈ A}.

**Три разных понятия:** - **Domain (область):** откуда берём аргументы - A - **Codomain (кодомен):** куда отображаем - B (объявленный тип возвращаемого значения) - **Image (образ):** куда реально попадаем - f(A) ⊆ B (может быть строгим подмножеством)

Различие образа и кодомена критично в системах типов. В TypeScript function f(): number не значит, что f вернёт любое число - возможно только подмножество. Зависимые типы (Idris, Agda) позволяют задать точный образ в сигнатуре.

Две функции f, g: A → B равны (f = g), если f(a) = g(a) для всех a ∈ A - независимо от того, как они объявлены внутри. Но инъективность и сюръективность зависят от кодомена, поэтому его нужно явно указывать.

Инъекция, сюръекция, биекция

Три вида функций различаются тем, как они «покрывают» кодомен и насколько «уникально» отображают область. Это фундаментальные свойства, определяющие обратимость и сравнение мощностей множеств.

**Три определения:** - **Инъекция (one-to-one):** f(a) = f(b) ⟹ a = b. Разные входы - разные выходы, нет коллизий. - **Сюръекция (onto):** ∀b ∈ B ∃a ∈ A: f(a) = b. Каждый элемент кодомена достигается. - **Биекция:** одновременно инъекция и сюръекция. Взаимно однозначное соответствие.

Хеш-функции в идеале должны быть инъективными (нет коллизий), но для конечного кодомена ({0..2³²-1}) и бесконечной области (все строки) инъекция математически невозможна. MD5 и SHA-256 - это не инъекции, но их коллизионная стойкость является вычислительной аппроксимацией инъективности.

Принцип Дирихле: если |A| > |B| и f: A → B, то f не может быть инъекцией. Именно поэтому хеш-таблица с 1000 ячейками и 1001 ключом гарантированно имеет коллизию - независимо от качества хеш-функции.

Композиция и обратная функция

Если f: A → B и g: B → C, то их композиция (g ∘ f): A → C определена как (g ∘ f)(a) = g(f(a)). Сначала применяем f, затем g. Обратная функция f⁻¹: B → A существует тогда и только тогда, когда f - биекция.

**Свойства композиции:** - Если f и g инъективны, то g ∘ f инъективна - Если f и g сюръективны, то g ∘ f сюръективна - Если f и g биективны, то g ∘ f биективна и (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹

В теории категорий функции - это морфизмы, а композиция - основная операция. Функторы, монады (Promise, Maybe, IO) - это обобщения функций, сохраняющие структуру композиции. Свойство (g ∘ f)⁻¹ = f⁻¹ ∘ g⁻¹ используется в криптографии для дешифровки составных шифров.

Принцип Дирихле (Pigeonhole)

Принцип Дирихле: если n+1 объект распределить по n ящикам, хотя бы в одном ящике окажется не менее двух объектов. Формально: если |A| > |B|, то не существует инъекции f: A → B.

**Обобщённый принцип:** если kn+r объектов (0 < r ≤ n) распределить по n ящикам, хотя бы в одном окажется ≥ k+1 объектов. Это нижняя граница: гарантия существования «переполненного» ящика.

«Парадокс дней рождения»: в группе из 23 человек вероятность совпадения дней рождения > 50%. Это применение принципа Дирихле с вероятностной оценкой. Именно поэтому хеши паролей нужно солить - без соли birthday attack работает против всей базы данных одновременно.

Задача LeetCode 287 «Find the Duplicate Number» - доказательство существования дубликата через Дирихле: n+1 число в диапазоне [1..n], значит два числа совпадут. Нахождение дубликата за O(1) памяти - цикл Флойда на графе функции.

Ключевые идеи

• **Функция f: A → B** - однозначное отображение; domain, codomain, image - три разные вещи
• **Инъекция** (no collisions): f(a)=f(b) ⟹ a=b; невозможна при |A| > |B|
• **Сюръекция** (onto): image = codomain, каждый элемент B достигается
• **Биекция** = инъекция + сюръекция: существует f⁻¹, |A| = |B|; обязательна для шифрования
• **Принцип Дирихле:** |A| > |B| гарантирует коллизию - основа анализа безопасности хешей

Связанные темы

Функции связывают множества и лежат в основе большинства математических структур:

• Отношения — Функция - частный случай бинарного отношения с дополнительным условием однозначности
• Модулярная арифметика — RSA использует биективные функции в кольце ℤₙ; хеш-таблицы используют x mod n как сюръекцию
• Комбинаторика — Подсчёт инъекций - это перестановки (P(n,k)); биекций - n!; сюръекций - числа Стирлинга

Вопросы для размышления

• Функция Python hash() - инъекция или нет? Почему при перезапуске Python хеши строк меняются (PYTHONHASHSEED)? Что это говорит о практической vs математической инъективности?
• В TypeScript тип (x: number) => number описывает кодомен, но не образ. Как branded types или newtype-паттерн позволяют сузить кодомен до реального образа? Приведите пример с UserId vs number.
• OAuth access token generation должна быть инъективной. Почему? Что произойдёт если два пользователя получат одинаковый токен? Какие техники гарантируют уникальность?

Связанные уроки

• plt-06-lambda-calculus