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

Функция — это тоже множество пар

Функция $f : X \to Y$ — это отношение $f \subseteq X \times Y$ с одним дополнительным требованием: для каждого $x \in X$ существует ровно одна пара $(x, y) \in f$.

Из этого требования следуют две вещи, которые в неформальном разговоре обычно теряются:

1. функция определена на всём $X$ — не бывает «функции, которая иногда не возвращает значение»;
2. функция однозначна — один вход, один выход.

Именно поэтому «функция» в математике и function в Python — не одно и то же: питоновская функция может бросить исключение или вернуть разное при разных запусках.

$$\htmlData{k=f}{f} : \htmlData{k=dom}{X} \to \htmlData{k=cod}{Y}$$

Запись $f$$:$$X$$\to$$Y$ — это в точности аннотация типа: def f(x: X) -> Y. Читать формулу без такой аннотации — то же самое, что читать код без типов.

Три вопроса

Про любую функцию задают три вопроса, и все три — про стрелки.

не функцияфункция, но и не инъекция, и не сюръекцияинъекцияинъекция, но не сюръекция

Инъекция (injective, «вложение»): разные аргументы дают разные значения.

$f(a) = f(b) \;\Rightarrow\; a = b$

Информация не теряется: по значению можно однозначно восстановить аргумент. Хеш-функция инъективной не является — в этом весь смысл коллизий.

Сюръекция (surjective, «накрытие»): каждый элемент $Y$ достигается.

$\forall y \in Y\;\; \exists x \in X : f(x) = y$

Биекция: и то, и другое сразу. Только у биекций есть обратная функция.

Полезная проверка для конечных множеств: если $|X| > |Y|$, инъекции быть не может — это принцип Дирихле, он же pigeonhole. Если $|X| < |Y|$, не может быть сюръекции.

Композиция

$(g \circ f)(x) = g(f(x))$

Читается справа налево: сначала применяется $f$, потом $g$. Это регулярный источник ошибок, потому что записано в обратном порядке относительно выполнения.

Причина такого порядка станет очевидной в блоке 1: умножение матриц — это композиция отображений, и $AB\mathbf{x}$ означает «сначала $B$, потом $A$». Порядок в записи наследуется от $f(x)$.

Свойства наследуются приятным образом: композиция инъекций инъективна, композиция сюръекций сюръективна, композиция биекций — биекция.

Обратная функция

$f^{-1} : Y \to X$ существует тогда и только тогда, когда $f$ — биекция, и удовлетворяет

$f^{-1} \circ f = \mathrm{id}_X, \qquad f \circ f^{-1} = \mathrm{id}_Y$

Обратите внимание на обозначение: $f^{-1}$ используют и для обратной функции, и для прообраза — а прообраз определён для любой функции, не только для биекции. Это разные вещи с одинаковой записью, и следующий урок посвящён именно прообразу.

Почему это важно для ML

• Обратимость линейного отображения — это существование $A^{-1}$, и критерий формулируется как «ядро тривиально», то есть «отображение инъективно».
• Softmax — не инъекция: прибавление константы ко всем логитам не меняет результат. Отсюда и берётся трюк с вычитанием максимума для устойчивости.
• Замена переменных в интеграле требует биективности — это условие в формуле normalizing flows.