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

Ты пользуешься функциями с девятого класса, и интуиция подсказывает: функция — это правило, по которому каждому $x$ сопоставляется $y$. Этой интуиции хватало для параболы и синуса. Но вот вопрос, на который «правило сопоставления» ответить не может: у отображения $f(x) = x^2$ есть обратное или нет? А у $f(x) = x^3$? Интуитивно кажется, что должно быть похоже — оба «просто степень», — но обратная функция существует только у одного из них. Чтобы объяснить разницу, а не просто заметить её, нужен точный язык.

Этот язык — три слова: инъекция, сюръекция, биекция. Они описывают не саму функцию, а то, как она «упаковывает» область определения в кодомен. Инъективность — это гарантия того, что коллизий не будет: разные входы никогда не дают одинаковый выход, так что по результату можно однозначно восстановить, что было на входе. Сюръективность — это гарантия того, что ни один элемент кодомена не останется «сиротой»: до каждого можно дотянуться. А биективность — это сочетание того и другого, и именно оно, а не что-то ещё, гарантирует существование обратной функции.

Различие звучит абстрактно, пока не встретишь его в коде. Softmax необратим и не может быть необратимым иначе — не потому, что кто-то плохо его спроектировал, а потому что сдвиг всех логитов на одну константу не меняет результат: это структурная неинъективность, зашитая в формулу. Автоэнкодер с узким бутылочным горлышком в принципе не может восстанавливать входы без потерь — это не следствие недообучения, а прямое следствие теоремы о ранге и дефекте, которую ты уже видел применительно к матрицам. А нормализующие потоки в генеративных моделях спроектированы как цепочки обратимых слоёв специально для того, чтобы можно было точно посчитать плотность вероятности через формулу замены переменных, — и это работает только потому, что каждый слой биективен. Три термина этого урока — не абстрактная алгебра ради алгебры, а точный словарь для разговора о том, что модель умеет восстанавливать, а что теряет навсегда.

Начнём с самого фундамента — со строгого определения того, что вообще такое функция, — а затем последовательно разберём инъективность, сюръективность, биективность и композицию, каждый раз с примерами, которые ломаются, и примерами, которые работают.

🎯 Ты узнаешь:

• Как функция строго определяется как множество упорядоченных пар — отношение с условием единственности значения — и почему это определение сильнее, чем «правило сопоставления»

• Что такое инъективность («один к одному»), как её проверять через уравнение $f(x_1) = f(x_2) \Rightarrow x_1 = x_2$ и почему это условие — основа идентифицируемости параметров в ML

• Что такое сюръективность («на»), почему она зависит от выбора кодомена и как один и тот же закон соответствия может быть сюръективным или нет в зависимости от того, куда его «целят»

• Что такое биективность, почему обратная функция существует тогда и только тогда, когда функция биективна, и как эту обратную функцию явно строить

• Как ведёт себя композиция функций: почему композиция инъекций — инъекция, композиция сюръекций — сюръекция, композиция биекций — биекция, и какие обратные утверждения при этом ложны

• Почему ReLU не инъективен, а softmax не инъективен по другой причине, и как обратимые слои нормализующих потоков (RealNVP) строятся так, чтобы обратимость была гарантирована конструктивно

• Как теорема о ранге и дефекте объясняет, почему автоэнкодер с сужением размерности не может быть инъективным, и что это значит для потери информации

История: откуда это взялось?

Долгое время «функция» означала формулу — выражение через $x$, составленное из известных операций. Такое понимание разбилось в 1807 году, когда Жозеф Фурье показал, что произвольную, в том числе разрывную и «сшитую по кускам» функцию, можно представить рядом синусов и косинусов. Стало ясно, что функция — это не обязательно формула, а нечто более общее. Точку в вопросе поставил Петер Густав Лежён Дирихле. В 1837 году в работе о рядах Фурье он сформулировал определение, которое используется до сих пор: функция — это произвольное правило, ставящее в соответствие каждому значению переменной ровно одно значение, безо всяких требований к тому, чтобы это правило задавалось формулой. В качестве иллюстрации предельной свободы такого определения Дирихле привёл функцию, равную единице на рациональных числах и нулю на иррациональных, — она не является непрерывной ни в одной точке, но по определению Дирихле это полноценная функция.

Как только функция перестала быть привязана к формуле, естественно встал вопрос о сравнении «размеров» бесконечных множеств. Ключевую роль здесь сыграл Георг Кантор. В 1870–1880-х годах он предложил сравнивать множества не подсчётом элементов (для бесконечных множеств это бессмысленно), а через существование взаимно однозначного соответствия между ними — то есть биекции. Открытие оказалось шокирующим: множество натуральных чисел, множество целых чисел и множество рациональных чисел находятся в биекции друг с другом, то есть «одинаково бесконечны», а вот множество вещественных чисел — строго «больше»: биекции с натуральными числами для него не существует. Доказательство этого факта — диагональный аргумент Кантора 1891 года — стало одним из самых known argument во всей математике; мы разберём его идею в разделе задач. Годом раньше, в 1888 году, Рихард Дедекинд в работе «Что такое числа и для чего они служат» предложил определять бесконечное множество именно через биекцию: множество бесконечно тогда и только тогда, когда существует биекция между ним и его собственным (не совпадающим с ним) подмножеством. Для конечных множеств такое невозможно в принципе — часть всегда меньше целого, — а для бесконечных это норма, и на этом парадоксе построена знаменитая притча об «Отеле Гильберта», которую мы вспомним в конце урока.

Сами слова «инъекция», «сюръекция» и «биекция» появились гораздо позже и пришли не из анализа, а из проекта по полной формализации математики. Группа французских математиков, публиковавшаяся под коллективным псевдонимом Николя Бурбаки, в середине XX века взялась переписать всю математику на строгом теоретико-множественном языке, начиная с самых оснований. В томе «Теория множеств» этого проекта функция впервые была определена не как «правило», а как объект теории множеств — множество упорядоченных пар с условием единственности, — то есть ровно так, как мы определим её в следующем разделе. Одновременно бурбакисты ввели три термина для трёх типов такого множества пар: injection, surjection, bijection. Термины оказались настолько удобными, что вытеснили более старые описательные обороты вроде «взаимно однозначное отображение на» и вошли во все языки математики, включая русский, почти без изменений.

Функция как отношение: строгое определение

Интуиция: функция — это не правило, а множество пар

Представь, что ты не объясняешь функцию человеку, а описываешь её компьютеру, который ничего не знает про «правила» и «формулы» — только про множества и пары. Как тогда сказать, что такое $f(x) = x^2$ на множестве $\{-1, 0, 1, 2\}$? Проще всего — явно выписать, что чему сопоставлено: $(-1, 1)$, $(0, 0)$, $(1, 1)$, $(2, 4)$. Это и есть функция — не формула, а сама эта коллекция пар. Формула $x^2$ — лишь удобный способ описать, какие пары входят в коллекцию, но не единственный: то же множество пар можно было бы задать таблицей, графиком или списком «если — то».

Отсюда и строгое определение: функция $f$ из множества $A$ в множество $B$ — это подмножество декартова произведения $A \times B$ (то есть набор упорядоченных пар $(a, b)$), удовлетворяющее двум условиям. Во-первых, у каждого элемента $A$ должна найтись хотя бы одна пара — иначе функция не определена на всём $A$. Во-вторых, у каждого элемента $A$ должна найтись не более одной пары — иначе результат неоднозначен, и это уже не функция, а просто отношение.

Определение: Пусть $A$ и $B$ — множества. Функцией (отображением) $f: A \to B$ называется подмножество $f \subseteq A \times B$, для которого выполнено: для каждого $a \in A$ существует единственный элемент $b \in B$ такой, что $(a, b) \in f$. Этот элемент обозначают $f(a)$. Множество $A$ называется областью определения (доменом), множество $B$ — кодоменом (областью прибытия), а множество $f(A) = \{f(a) : a \in A\} \subseteq B$ — образом (областью значений) функции $f$.

Ключевое слово здесь — «единственный». Оно превращает произвольное отношение между $A$ и $B$ в функцию. Ровно это условие обычно проверяют «вертикальным тестом» на графике: если вертикальная прямая пересекает график больше одного раза, это не функция, потому что одному $x$ отвечает два разных $y$ — нарушена единственность.

Обрати внимание и на разницу между кодоменом $B$ и образом $f(A)$. Кодомен — это то, куда функция может попасть по объявлению; образ — это то, куда она действительно попадает. Кодомен $B$ выбирают заранее, при объявлении функции, а образ $f(A)$ вычисляют апостериори. Эта разница окажется решающей уже в следующем разделе, когда речь пойдёт о сюръективности.

Разбор примеров

Пример 1. Явное конечное отношение — функция или нет?

Рассмотрим $A = \{1, 2, 3\}$, $B = \{x, y\}$ и отношение $R_1 = \{(1, x), (2, y), (3, x)\}$. Проверяем условие единственности: у $1$ есть пара $x$ и только она, у $2$ — только $y$, у $3$ — только $x$. Каждый элемент $A$ имеет ровно одну пару. Значит, $R_1$ — функция, $f(1) = x$, $f(2) = y$, $f(3) = x$.

Пример 2 (контрпример). Нарушение единственности.

Возьмём те же множества и отношение $R_2 = \{(1, x), (1, y), (2, x), (3, y)\}$. У элемента $1$ здесь две пары: $(1, x)$ и $(1, y)$. Условие единственности нарушено, и $R_2$ функцией не является — это просто отношение общего вида. На графике это выглядело бы как две точки с одинаковой абсциссой и разными ординатами: вертикальная прямая через $x = 1$ пересекла бы такой «график» дважды.

Пример 3 (контрпример). Нарушение «для каждого».

Отношение $R_3 = \{(1, x), (2, y)\}$ на тех же $A = \{1,2,3\}$, $B = \{x,y\}$ не является функцией $A \to B$: элементу $3$ не сопоставлено вообще ничего. Это распространённая путаница: $R_3$ вполне могла бы быть функцией, если бы мы объявили её областью определения множество $\{1, 2\}$, а не $\{1, 2, 3\}$. Область определения — часть объявления функции, а не то, что подбирается постфактум под имеющиеся пары.

Пример 4. Формула, не определённая всюду.

Классическая ловушка: $f(x) = \dfrac{1}{x - 2}$, если её объявить как $f: \mathbb{R} \to \mathbb{R}$, функцией в строгом смысле не является — при $x = 2$ пары не существует вовсе, знаменатель обращается в ноль. Чтобы формула стала честной функцией, нужно сузить домен: $f: \mathbb{R} \setminus \{2\} \to \mathbb{R}$. После такого сужения условие «для каждого $a$ существует пара» выполняется, и всё в порядке. Это иллюстрирует общее правило: домен функции, заданной формулой, — это множество, на котором формула вообще имеет смысл, а не весь $\mathbb{R}$ по умолчанию.

Почему это важно

Строгое определение через пары кажется избыточной формальностью, пока не понадобится точно сказать, где заканчивается функция и начинается что-то другое. В программировании функция как отображение «на каждый вход — единственный выход» — это в точности контракт чистой функции: одинаковый вход должен детерминированно давать одинаковый выход, иначе система непредсказуема. В базах данных условие единственности — это буквально определение функциональной зависимости между столбцами, на которой стоит вся теория нормализации. А в машинном обучении именно это определение отделяет модель (математическую функцию параметров и входа) от стохастического процесса генерации данных: модель обязана быть функцией, а вот сам процесс, который она приближает, может и не быть — одному и тому же входу в реальном мире может отвечать несколько разных исходов, и это уже другая, вероятностная история, где вместо $f(x)$ говорят об условном распределении $p(y \mid x)$.

Инъективность: разные входы — разные выходы

Интуиция: гардероб без потерянных номерков

Представь гардероб в театре, где каждому пальто выдают номерок. Хороший гардероб устроен так, что два разных пальто никогда не получают один и тот же номерок — иначе при возврате случится путаница: по номерку нельзя будет понять, чьё это пальто. Отображение «пальто → номерок» с этим свойством называется инъективным: разным входам всегда соответствуют разные выходы. Если, наоборот, встретить одинаковый номерок на двух разных пальто, восстановить хозяина по номерку станет невозможно — информация об исходном пальто необратимо потеряна.

Именно это и есть суть инъективности: функция ничего не «склеивает». По значению $f(a)$ всегда можно однозначно сказать, каким было $a$ — в пределах того, что $a$ вообще было в образе функции.

Определение: Функция $f: A \to B$ называется инъективной (инъекцией, взаимно однозначным отображением в $B$), если для любых $a_1, a_2 \in A$ из $f(a_1) = f(a_2)$ следует $a_1 = a_2$. Равносильная формулировка (контрапозиция): $a_1 \ne a_2 \Rightarrow f(a_1) \ne f(a_2)$ — разные элементы области определения переходят в разные элементы кодомена.

На практике удобнее доказывать инъективность именно через первую форму: предположить, что $f(a_1) = f(a_2)$, и алгебраически вывести отсюда $a_1 = a_2$. А чтобы опровергнуть инъективность, достаточно предъявить один-единственный контрпример — конкретную пару $a_1 \ne a_2$ с равными значениями.

Разбор примеров

Пример 1 (лёгкий). Линейная функция.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = 3x - 7$. Предположим $f(x_1) = f(x_2)$: $3x_1 - 7 = 3x_2 - 7 \Rightarrow 3x_1 = 3x_2 \Rightarrow x_1 = x_2$. Инъективна. Геометрически: любая невырожденная линейная функция строго монотонна, а строго монотонная функция инъективна автоматически — она либо всё время растёт, либо всё время убывает, вернуться к уже пройденному значению не может.

Пример 2 (средний, контрпример). Квадрат на всей прямой.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$. Проверим кандидатов $x_1 = 2$, $x_2 = -2$: $f(2) = 4$ и $f(-2) = 4$ — значения совпали, а $2 \ne -2$. Инъективность нарушена одним явным контрпримером. Причина видна на графике: парабола симметрична относительно оси $y$, и любая горизонтальная прямая $y = c$ при $c > 0$ пересекает её дважды.

Пример 3 (средний). Кубическая функция.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$. Предположим $x_1^3 = x_2^3$. У вещественного числа существует ровно один вещественный кубический корень (в отличие от квадратного), поэтому из равенства кубов следует равенство самих чисел: $x_1 = x_2$. Инъективна, несмотря на то, что производная $f'(x) = 3x^2$ обращается в ноль при $x = 0$ — «плоский» участок графика не превращается в горизонтальный отрезок, функция всё равно строго возрастает на всей прямой.

Пример 4 (сложный, контрпример). Кубический многочлен со «сдвигом».

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^3 - x$. Посчитаем в трёх точках: $f(-1) = -1 - (-1) = 0$, $f(0) = 0 - 0 = 0$, $f(1) = 1 - 1 = 0$. Три разных числа — $-1$, $0$, $1$ — дают одно и то же значение $0$. Не просто не инъективна, а «трижды не инъективна» в одной точке кодомена. Небольшая модификация формулы кубической функции (добавление члена $-x$) полностью разрушает свойство, которым обладала чистая $x^3$, — инъективность не наследуется автоматически при малых изменениях формулы, её нужно проверять заново.

Пример 5 (ML). Один из «встроенных» слоёв нейросети.

Слой ReLU, $f(x) = \max(0, x)$, действующий покомпонентно. Возьмём $x_1 = -1$, $x_2 = -5$: $f(-1) = 0$ и $f(-5) = 0$. Всё отрицательное «схлопывается» в ноль. ReLU не инъективен, и это структурное, а не случайное свойство: информация о том, насколько глубоко в минус ушёл вход, теряется безвозвратно. Это одна из причин, по которой ReLU нельзя напрямую использовать в обратимых слоях нормализующих потоков — мы вернёмся к этому в разделе задач.

Почему это важно

Инъективность — это математическое условие идентифицируемости: возможности однозначно восстановить причину по следствию. В статистике параметр модели называют идентифицируемым, если отображение «параметр → распределение данных» инъективно: разным значениям параметра отвечают разные наблюдаемые последствия, и, значит, по бесконечному объёму данных параметр в принципе можно восстановить точно. Если это отображение не инъективно — например, при полной мультиколлинеарности признаков в линейной регрессии, — никакой объём данных не поможет отличить одно значение параметра от другого: они дают буквально одинаковые предсказания. Такая же логика стоит за хеш-функциями (инъективность в идеале желательна, но при сжатии в конечное пространство невозможна по принципу Дирихле), за шифрованием (расшифровка требует, чтобы шифрование было инъективно — иначе несколько разных сообщений расшифровывались бы в одно) и за кодировками признаков в ML, где one-hot-подобные схемы специально строят инъективными, чтобы категорию можно было восстановить из вектора без потерь.

Сюръективность: «на» — каждый элемент кодомена достигнут

Интуиция: у каждого места в зале есть зритель

Инъективность следила за тем, чтобы не было двух пальто на один номерок. Сюръективность следит за противоположным: чтобы не осталось «пустых» номерков, до которых функция вообще не дотягивается. Представь рассадку зрителей по местам в зале: рассадка сюръективна, если каждое место кем-то занято, — неважно, свободно ли при этом несколько человек сидят рядом (это уже вопрос инъективности, к рассадке отношения не имеющий). Сюръективность — это про кодомен целиком, а не про домен: она спрашивает, «дотянулась» ли функция до каждого объявленного места назначения.

Определение: Функция $f: A \to B$ называется сюръективной (сюръекцией, отображением на $B$), если для любого $b \in B$ найдётся хотя бы один элемент $a \in A$ такой, что $f(a) = b$. Равносильно: образ функции совпадает с кодоменом, $f(A) = B$.

Здесь есть тонкость, которую легко упустить: сюръективность зависит не только от закона соответствия, но и от того, какой кодомен объявлен. Одна и та же формула $f(x) = x^2$ является сюръекцией как $\mathbb{R} \to [0, \infty)$, но не сюръекцией как $\mathbb{R} \to \mathbb{R}$ — потому что во втором случае в кодомен включили отрицательные числа, до которых квадрат никогда не дотягивается. Сюръективность — свойство не формулы, а тройки (формула, домен, кодомен).

Разбор примеров

Пример 1 (лёгкий). Линейная функция снова.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = 3x - 7$. Возьмём произвольный $y \in \mathbb{R}$ и решим уравнение относительно $x$: $3x - 7 = y \Rightarrow x = \dfrac{y + 7}{3}$. Это вещественное число существует при любом $y$, значит прообраз находится всегда. Сюръективна.

Пример 2 (средний, контрпример). Квадрат на всей прямой как кодомене.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$. Возьмём $y = -1$: уравнение $x^2 = -1$ не имеет вещественных решений. Элемент $-1 \in \mathbb{R}$ недостижим, значит функция не сюръективна как отображение в $\mathbb{R}$. Образ этой функции — $[0, \infty)$, строго меньшее множество, чем объявленный кодомен $\mathbb{R}$.

Пример 3 (средний). Тот же квадрат с честным кодоменом.

Теперь объявим кодомен корректно: $f: \mathbb{R} \to [0, \infty)$, $f(x) = x^2$. Возьмём произвольный $y \ge 0$: уравнение $x^2 = y$ разрешимо, например $x = \sqrt{y}$ — вещественное число, потому что $y \ge 0$. Прообраз найден для любого элемента кодомена. Сюръективна. Обрати внимание: формула не изменилась ни на символ, изменилось только объявление кодомена — а вывод о сюръективности перевернулся на противоположный.

Пример 4 (сложный, контрпример). Экспонента.

$g: \mathbb{R} \to \mathbb{R}$, $g(x) = e^x$. Возьмём $y = 0$: уравнение $e^x = 0$ решений не имеет — экспонента строго положительна при любом вещественном $x$, к нулю она лишь приближается на $-\infty$, но никогда его не достигает. Не сюръективна как отображение в $\mathbb{R}$. Образ функции — открытый луч $(0, \infty)$; как отображение $\mathbb{R} \to (0, \infty)$ та же формула уже сюръективна, и обратной к ней послужит натуральный логарифм.

Пример 5 (ML). One-hot-кодирование категорий.

Отображение из трёх категорий $\{\text{кот}, \text{собака}, \text{птица}\}$ в $\mathbb{R}^3$ по правилу «кот» $\mapsto (1,0,0)$, «собака» $\mapsto (0,1,0)$, «птица» $\mapsto (0,0,1)$. Возьмём вектор $(0.5,\ 0.5,\ 0) \in \mathbb{R}^3$: он не совпадает ни с одним из трёх образов, значит недостижим. Функция явно не сюръективна — её образ состоит всего из трёх точек, а кодомен $\mathbb{R}^3$ несчётен. И это нормально: от one-hot-кодирования требуется инъективность (различимость категорий), а не сюръективность — «пустое» пространство между тремя точками попросту не нужно.

Почему это важно

Сюръективность формализует вопрос «может ли модель в принципе выдать любой заявленный результат». В классификации, если последний слой сети имеет кодомен $[0, 1]$ (вероятность), а активационная функция сюръективна на этот интервал (как сигмоида, чей образ — весь открытый интервал $(0,1)$), сеть теоретически может выразить любую степень уверенности. Если бы образ был у́же объявленного диапазона, часть возможных ответов оказалась бы структурно недостижима — не из-за плохого обучения, а из-за самой архитектуры. В генеративном моделировании условие сюръективности генератора на пространство данных — это условие того, что модель способна воспроизвести любой реалистичный объект, а не только подмножество похожих друг на друга; типичная патология GAN, называемая mode collapse, — это именно потеря сюръективности: генератор перестаёт достигать целых областей распределения данных. А в численных методах разрешимость уравнения $f(x) = y$ при любом $y$ из допустимого диапазона — это в чистом виде вопрос о сюръективности $f$.

Биективность и обратная функция

Интуиция: соответствие без потерь и без дыр

Биективность — это одновременно инъективность и сюръективность: ни одна пара элементов домена не «склеена» в один выход, и ни один элемент кодомена не остался без прообраза. В результате получается идеальное соответствие один-к-одному между двумя множествами целиком: каждому элементу $A$ отвечает ровно один элемент $B$, и каждому элементу $B$ отвечает ровно один элемент $A$. Именно эта симметрия и позволяет определить обратное движение — обратную функцию, которая «отматывает» соответствие назад.

Определение: Функция $f: A \to B$ называется биективной (биекцией, взаимно однозначным соответствием между $A$ и $B$), если она одновременно инъективна и сюръективна. В этом случае для каждого $b \in B$ существует ровно один $a \in A$ с $f(a) = b$ (существование — из сюръективности, единственность — из инъективности), и можно корректно определить обратную функцию $f^{-1}: B \to A$ по правилу $f^{-1}(b) = a$, где $a$ — этот единственный прообраз.

Отсюда — центральная теорема раздела, которую стоит проговорить явно, потому что именно она объясняет, зачем всё это было нужно.

Теорема (существование обратной функции). Функция $f: A \to B$ обладает обратной функцией $f^{-1}: B \to A$ тогда и только тогда, когда $f$ биективна.

Идея доказательства. В одну сторону мы её уже фактически провели в определении: если $f$ биективна, каждому $b$ отвечает ровно один прообраз, и правило $b \mapsto a$ корректно определяет функцию. В обратную сторону: если $f^{-1}: B \to A$ существует и удовлетворяет $f^{-1}(f(a)) = a$ для всех $a$ и $f(f^{-1}(b)) = b$ для всех $b$, то из первого равенства следует инъективность $f$ (если $f(a_1) = f(a_2)$, применим $f^{-1}$ к обеим частям и получим $a_1 = a_2$), а из второго — сюръективность $f$ (для любого $b$ элемент $a = f^{-1}(b)$ является прообразом). Значит, $f$ обязана быть биективной. $\blacksquare$

Разбор примеров

Пример 1 (лёгкий). Линейная функция как биекция.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = 3x - 7$. Мы уже показали её инъективность и сюръективность выше, значит она биективна. Обратная функция строится решением $y = 3x - 7$ относительно $x$: $f^{-1}(y) = \dfrac{y+7}{3}$. Проверка: $f(f^{-1}(y)) = 3 \cdot \dfrac{y+7}{3} - 7 = y + 7 - 7 = y$. Сходится.

Пример 2 (средний, контрпример). Квадрат без ограничений не биективен.

$f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ не инъективна (пример 2 из раздела об инъективности) и не сюръективна (пример 2 из раздела о сюръективности) — она проваливает оба условия сразу, а достаточно и одного провала, чтобы обратной функции не было. Действительно, «обратная функция» квадрата в бытовом смысле, $\sqrt{y}$, обратна лишь на суженном домене: как только домен и кодомен сужены до $[0, \infty)$ (пример 3 из инъективности и сюръективности), функция становится биекцией, и $f^{-1}(y) = \sqrt{y}$ работает корректно.

Пример 3 (средний). Тригонометрическая функция на сужении.

$\sin: [-\pi/2,\ \pi/2] \to [-1, 1]$. На всей числовой прямой синус периодичен и заведомо не инъективен ($\sin 0 = \sin \pi = 0$, например). Но на отрезке $[-\pi/2, \pi/2]$ синус строго возрастает (производная $\cos x > 0$ на этом интервале), значит инъективен; а его значения на этом отрезке пробегают ровно весь $[-1, 1]$, значит сюръективен на этот кодомен. Биекция, обратная функция — $\arcsin$. Это общий приём: если функция не биективна на «естественном» домене, её можно сузить до участка строгой монотонности и получить биекцию — так определены все обратные тригонометрические функции.

Пример 4 (сложный). Линейное отображение и невырожденность матрицы.

$T: \mathbb{R}^2 \to \mathbb{R}^2$, $T(x, y) = (x + y,\ x - y)$, матрица оператора $A = \begin{pmatrix} 1 & 1 \\ 1 & -1 \end{pmatrix}$. Определитель $\det A = 1\cdot(-1) - 1\cdot 1 = -2 \ne 0$. Из линейной алгебры известно: линейный оператор с ненулевым определителем инъективен (нулевой вектор — единственное решение $Av = 0$) и одновременно сюръективен (система $Av = b$ разрешима при любом $b$) — то есть биективен. Это в точности стыкуется с уроком о собственных значениях: матрица обратима тогда и только тогда, когда $0$ не входит в её спектр, а линейное отображение с обратимой матрицей — это в точности биекция.

Пример 5 (ML). Инволюция как частный случай биекции.

$f: \mathbb{R} \setminus \{0\} \to \mathbb{R} \setminus \{0\}$, $f(x) = 1/x$. Инъективна ($1/x_1 = 1/x_2 \Rightarrow x_1 = x_2$), сюръективна (для $y \ne 0$ прообраз $x = 1/y \ne 0$ существует), значит биективна. Особенность этого примера — обратная функция совпадает с самой функцией: $f^{-1} = f$, потому что $f(f(x)) = 1/(1/x) = x$. Такие самообратные биекции называют инволюциями, и с ними приятно работать в коде: не нужно хранить отдельно прямое и обратное преобразование.

Почему это важно

Именно биективность — а не что-то более слабое — гарантирует, что преобразование можно «отменить» без потери информации. Это ровно тот критерий, вокруг которого построены нормализующие потоки (Normalizing Flows) — класс генеративных моделей вроде RealNVP и Glow. Каждый слой такой сети спроектирован заведомо биективным: это позволяет, с одной стороны, генерировать данные, применяя слои в прямом порядке к случайному шуму, а с другой — точно вычислять правдоподобие реальных данных, применяя обратные слои и формулу замены переменной в плотности вероятности, которая для необратимого преобразования математически не определена. То же требование стоит за обратимыми архитектурами (invertible residual networks, i-RevNet): обратимость слоя означает, что активации можно восстановить из более глубокого слоя, не сохраняя их в памяти при обучении, — экономия, которая имеет смысл только потому, что биективность гарантирует существование однозначного обратного пути.

Композиция функций и её свойства

Интуиция: конвейер из двух станков

Если $f: A \to B$ и $g: B \to C$ — два отображения, то их композиция $g \circ f: A \to C$, определённая как $(g \circ f)(a) = g(f(a))$, — это последовательное применение сначала $f$, потом $g$, как деталь проходит сначала через один станок конвейера, потом через следующий. Условие, которое здесь легко упустить: кодомен первой функции должен совпадать (или быть подмножеством) с доменом второй — иначе выход первого станка физически не подойдёт ко входу второго.

Определение: Пусть $f: A \to B$, $g: B \to C$. Композицией функций $f$ и $g$ называется функция $g \circ f: A \to C$, заданная правилом $(g \circ f)(a) = g(f(a))$ для всех $a \in A$.

Теорема (наследование свойств при композиции). Пусть $f: A \to B$ и $g: B \to C$.

1. Если $f$ и $g$ инъективны, то $g \circ f$ инъективна.

2. Если $f$ и $g$ сюръективны, то $g \circ f$ сюръективна.

3. Если $f$ и $g$ биективны, то $g \circ f$ биективна, и $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$.

Доказательство пункта 1. Пусть $(g \circ f)(a_1) = (g \circ f)(a_2)$, то есть $g(f(a_1)) = g(f(a_2))$. Так как $g$ инъективна, отсюда $f(a_1) = f(a_2)$. Так как $f$ инъективна, отсюда $a_1 = a_2$. Значит, $g \circ f$ инъективна.

Доказательство пункта 2. Возьмём произвольный $c \in C$. Так как $g$ сюръективна, найдётся $b \in B$ с $g(b) = c$. Так как $f$ сюръективна, найдётся $a \in A$ с $f(a) = b$. Тогда $(g \circ f)(a) = g(f(a)) = g(b) = c$. Прообраз найден для любого $c$, значит $g \circ f$ сюръективна.

Пункт 3 следует из пунктов 1 и 2: биективность — это инъективность плюс сюръективность, и обе они переносятся на композицию по отдельности. Формула для обратной функции композиции проверяется прямой подстановкой: $(f^{-1} \circ g^{-1}) \circ (g \circ f) = f^{-1} \circ (g^{-1} \circ g) \circ f = f^{-1} \circ \mathrm{id} \circ f = f^{-1} \circ f = \mathrm{id}$ — порядок при обращении композиции переворачивается, ровно как при снятии одежды: последнее надетое снимается первым.

Разбор примеров

Пример 1 (лёгкий). Композиция двух линейных биекций.

$f(x) = x + 1$, $g(x) = 2x$, обе $\mathbb{R} \to \mathbb{R}$. Считаем: $(g \circ f)(x) = g(x + 1) = 2(x+1) = 2x + 2$; а в другом порядке $(f \circ g)(x) = f(2x) = 2x + 1$. Заметь: $2x + 2 \ne 2x + 1$ — композиция функций не коммутативна, порядок станков на конвейере важен. Обе композиции при этом биективны (линейные функции с ненулевым коэффициентом при $x$), что согласуется с теоремой: обе $f$ и $g$ биективны по отдельности.

Пример 2 (средний). Явная проверка формулы для обратной композиции.

Для тех же $f, g$: $f^{-1}(x) = x - 1$, $g^{-1}(x) = x/2$. По теореме $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$, то есть $(g \circ f)^{-1}(y) = f^{-1}(g^{-1}(y)) = \dfrac{y}{2} - 1$. Проверим напрямую: решаем $y = 2x + 2$ относительно $x$ — $x = \dfrac{y - 2}{2} = \dfrac{y}{2} - 1$. Совпало.

Пример 3 (сложный, контрпример на обратное утверждение). Композиция может быть инъективна, даже когда одна из функций — нет.

Утверждение «если $g \circ f$ инъективна, то $g$ обязана быть инъективной» — ложно, и вот контрпример. Пусть $A = \{1, 2\}$, $B = \{1, 2, 3\}$, $C = \{x, y\}$. Определим $f: A \to B$ как $f(1) = 1$, $f(2) = 2$ (инъективна). Определим $g: B \to C$ как $g(1) = x$, $g(2) = y$, $g(3) = y$ — $g$ не инъективна, потому что $g(2) = g(3) = y$. Но композиция: $(g\circ f)(1) = g(1) = x$, $(g\circ f)(2) = g(2) = y$ — оба значения различны, значит $g \circ f$ инъективна. Причина в том, что «склейка» $g$ происходит на элементе $3$, который вообще не входит в образ $f$, — и композиции об этой склейке ничего не известно. При этом верно более слабое, но истинное утверждение: если $g \circ f$ инъективна, то $f$ (первая по порядку применения функция) обязана быть инъективной. Доказательство ровно повторяет шаг из теоремы: $f(a_1) = f(a_2) \Rightarrow g(f(a_1)) = g(f(a_2)) \Rightarrow$ (по инъективности $g\circ f$) $a_1 = a_2$.

Почему это важно

Свойство «композиция биекций — биекция» — это ровно то, что делает возможными глубокие обратимые архитектуры: если каждый отдельный слой нормализующего потока биективен, то и вся сеть целиком, будучи композицией десятков таких слоёв, автоматически биективна — обратимость не нужно проверять для сети целиком, достаточно спроектировать обратимым каждый кирпичик, а дальше работает теорема. Формула $(g \circ f)^{-1} = f^{-1} \circ g^{-1}$ на практике означает, что для инференса в обратную сторону слои нужно применять в обратном порядке — это буквально то, что происходит в коде при вызове .inverse() у последовательности слоёв flow-модели. А контрпример про «инъективность композиции не гарантирует инъективность каждой функции по отдельности» предостерегает от рассуждения «раз конечная сеть инъективна на практике, значит каждый слой инъективен» — это неверно, и обратный слой может маскировать неинъективность промежуточного, если она происходит на неиспользуемой части кодомена.

Практика: 30 заданий

Базовые задания (1–10)

Задание 1: Определи, является ли $f: \mathbb{R} \to \mathbb{R}$, $f(x) = 2x + 3$ инъективной, сюръективной, биективной. Если биективна — найди обратную функцию.

Задание 2: Определи, является ли $f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$ инъективной и сюръективной. Приведи конкретные числовые контрпримеры для каждого нарушенного свойства.

Задание 3: Рассмотри $f: [0, \infty) \to [0, \infty)$, $f(x) = x^2$ (тот же закон, что и в задании 2, но с суженными доменом и кодоменом). Определи тип функции.

Задание 4: Определи тип функции $f: \mathbb{Z} \to \mathbb{Z}$, $f(n) = n + 5$.

Задание 5: Определи тип функции $f: \mathbb{Z} \to \mathbb{Z}$, $f(n) = 2n$.

Задание 6: Определи тип функции $f: \mathbb{N} \to \mathbb{N}$, $f(n) = n^2$, где $\mathbb{N} = \{1, 2, 3, \dots\}$.

Задание 7: Дана функция на конечных множествах $A = \{1,2,3\}$, $B = \{a,b,c,d\}$: $f(1)=a$, $f(2)=b$, $f(3)=c$. Определи тип.

Задание 8: Дана функция $A = \{1,2,3,4\}$, $B = \{a,b,c\}$: $f(1)=a$, $f(2)=a$, $f(3)=b$, $f(4)=c$. Определи тип.

Задание 9: Определи тип функции $g: \mathbb{R} \to \mathbb{R}$, $g(x) = e^x$, а затем — тип функции $\tilde{g}: \mathbb{R} \to (0, \infty)$ с той же формулой.

Задание 10: Даны $f(x) = x + 1$ и $g(x) = 2x$, обе $\mathbb{R}\to\mathbb{R}$. Вычисли $(g\circ f)(x)$ и $(f \circ g)(x)$ и сравни их.

Средние задания (11–20)

Задание 11: Докажи, что $f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^3$ биективна, и найди обратную функцию.

Задание 12: Определи тип функции $f: \mathbb{R} \to \mathbb{R}$, $f(x) = x^3 - x$.

Задание 13: Докажи, что $f: \mathbb{R}\setminus\{0\} \to \mathbb{R}\setminus\{0\}$, $f(x) = 1/x$ биективна и найди $f^{-1}$.

Задание 14: Определи тип функции «пол» $f: \mathbb{R} \to \mathbb{Z}$, $f(x) = \lfloor x \rfloor$.

Задание 15: Рассмотри $\sin$ как отображение $\mathbb{R} \to [-1,1]$ и как отображение $[-\pi/2, \pi/2] \to [-1, 1]$. Сравни их инъективность.

Задание 16: Линейный оператор $T: \mathbb{R}^2 \to \mathbb{R}^2$, $T(x,y) = (x+y,\ x-y)$. Проверь биективность через определитель матрицы и найди $T^{-1}$.

Задание 17: Линейное отображение $T: \mathbb{R}^3 \to \mathbb{R}^2$, $T(x,y,z) = (x+y,\ y+z)$. Определи, инъективно ли оно и сюръективно ли оно.

Задание 18: На множестве $P(\{1,2\}) = \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$ определи $f(S) = \{1,2\}\setminus S$ (дополнение). Докажи, что это биекция, и опиши $f^{-1}$.

Задание 19: $A = \{1,2,3,4,5\}$, $B=\{1,2,3,4\}$. Докажи, что инъективной функции $A \to B$ не существует. Приведи пример сюръективной функции $A \to B$.

Задание 20: Пусть $f: A \to B$, $g: B \to C$, и известно, что $g \circ f$ инъективна. Докажи, что $f$ обязана быть инъективной. Приведи пример, показывающий, что при этом $g$ инъективной быть не обязана.

Продвинутые задания (21–30)

Задание 21: Докажи в общем виде: если $f: A\to B$ и $g: B\to C$ биективны, то $g\circ f$ биективна, и проверь формулу $(g\circ f)^{-1} = f^{-1}\circ g^{-1}$ на числовом примере $f(x)=x+1$, $g(x)=2x$.

Задание 22: Построй явную биекцию между $\mathbb{N}_0 = \{0,1,2,\dots\}$ и $\mathbb{Z}$ и проверь её на первых шести значениях.

Задание 23: Опиши (без полной формализации) идею диагонального аргумента Кантора, доказывающего, что биекции между $\mathbb{N}$ и $(0,1)$ не существует.

Задание 24: Сравни инъективность ReLU $f(x)=\max(0,x)$ и Leaky ReLU $f_\alpha(x) = x$ при $x\ge0$, $\alpha x$ при $x<0$ (с $\alpha=0{,}01$), обе как отображения $\mathbb{R}\to\mathbb{R}$.

Задание 25: Докажи алгебраически, что $\mathrm{softmax}: \mathbb{R}^n \to \Delta^{n-1}$ не инъективен, показав, что $\mathrm{softmax}(z) = \mathrm{softmax}(z+c\cdot\mathbf{1})$ для любой константы $c$. Проверь на числах $z=(1,2,3)$, $c=1$.

Задание 26: Линейный энкодер $E:\mathbb{R}^3\to\mathbb{R}^2$, $E(x_1,x_2,x_3) = (x_1+x_2,\ x_2+x_3)$. Найди нетривиальный вектор в ядре и объясни связь с потерей информации в автоэнкодерах.

Задание 27: Дана матрица признаков $X=\begin{pmatrix}1&1\\2&2\\3&3\end{pmatrix}$ (второй столбец — точная копия первого). Покажи, что отображение $\beta\mapsto X\beta$ не инъективно, приведя два разных вектора параметров с одинаковыми предсказаниями. Объясни, что это значит для идентифицируемости.

Задание 28: One-hot-кодирование трёх категорий в $\mathbb{R}^3$ (см. пример в разделе о сюръективности). Докажи его инъективность и объясни, почему для кодирования достаточно требовать именно инъективность, а не сюръективность.

Задание 29: Хеш-функция отображает словарь из $100\,000$ слов в $10\,000$ ячеек (приём feature hashing). Докажи с помощью принципа Дирихле, что такая функция не может быть инъективной, и оцени среднюю нагрузку на ячейку.

Задание 30: Слой связывающего преобразования (affine coupling layer) из RealNVP: вход делится на две части $x=(x_a,x_b)$, выход $y_a=x_a$, $y_b = x_b\odot\exp(s(x_a)) + t(x_a)$, где $s,t$ — произвольные (сколь угодно сложные) нейросети. Построй явную обратную формулу и объясни, почему биективность слоя гарантирована при любых $s,t$.

Частые ошибки

Ошибка 1. Путают инъективность и сюръективность местами.

Как выглядит: «функция $f(x)=x^2$ на $\mathbb{R}\to\mathbb{R}$ не сюръективна, потому что $f(2)=f(-2)$» — свойство названо неправильным именем.

Почему возникает: оба термина новые, начинаются на согласную, легко перепутать местами.

Как правильно: инъективность — про разные входы, не должно быть двух разных $x$ с одинаковым $f(x)$. Сюръективность — про весь кодомен, каждый $y$ должен быть достигнут. Мнемоника: инъекция — как инъекция шприцем, попадает в одну точку без разброса (не расщепляется), а сюръекция — сплошное покрытие кодомена.

Ошибка 2. Проверяют сюръективность, не глядя на объявленный кодомен.

Как выглядит: «$f(x)=e^x$ сюръективна, потому что принимает много разных положительных значений» — вывод сделан без учёта того, куда функция объявлена (в $\mathbb{R}$ или в $(0,\infty)$).

Почему возникает: кажется, что раз функция «активно работает» и выдаёт разнообразные значения, этого достаточно.

Как правильно: сюръективность — это сравнение образа $f(A)$ с объявленным кодоменом $B$, а не оценка «насколько активно» функция работает. Одна и та же формула сюръективна для одного кодомена и не сюръективна для другого — см. задания 2 и 3 в базовом блоке.

Ошибка 3. Считают, что у любой функции есть обратная.

Как выглядит: пишут «обратная функция для $f(x)=x^2$ — это $\sqrt{x}$» без оговорок про сужение домена и кодомена.

Почему возникает: в школе с обратными функциями работают в основном на участках, где всё уже подготовлено (степенные, показательные функции на «удобных» промежутках), и вопрос существования не поднимается явно.

Как правильно: обратная функция существует тогда и только тогда, когда исходная функция биективна — обе половины теоремы обязательны. $\sqrt{x}$ — корректная обратная функция только для суженной $f:[0,\infty)\to[0,\infty)$, $f(x)=x^2$, а не для $f:\mathbb{R}\to\mathbb{R}$.

Ошибка 4. Путают строгую монотонность с самим свойством инъективности как будто это одно и то же для всех функций.

Как выглядит: «$f(x)=x^3-x$ не монотонна, значит не инъективна» — верный вывод получен неверной логикой, которая в общем случае ломается.

Почему возникает: для функций одной вещественной переменной строгая монотонность действительно влечёт инъективность, и это удобный достаточный признак, который незаметно принимают за определение.

Как правильно: строгая монотонность — это лишь достаточное, но не необходимое условие инъективности. Существуют немонотонные инъективные функции (например, кусочно заданные так, что скачки не создают повторов). Единственный универсальный способ доказать инъективность — напрямую проверить $f(x_1)=f(x_2)\Rightarrow x_1=x_2$, а монотонность — лишь одна из полезных тактик, не подменяющая определение.

Ошибка 5. Забывают, что $|A|>|B|$ делает инъекцию невозможной, а $|A|<|B|$ — сюръекцию невозможной, только для конечных множеств.

Как выглядит: «между $\mathbb{N}$ и $\mathbb{Z}$ не может быть биекции, потому что $\mathbb{Z}$ «в два раза больше»» — рассуждение по аналогии с конечными множествами, перенесённое на бесконечные.

Почему возникает: интуиция про «часть меньше целого» твёрдо усвоена на конечных примерах и автоматически переносится дальше.

Как правильно: для бесконечных множеств сравнение по включению ничего не говорит о существовании биекции — задание 22 явно строит биекцию $\mathbb{N}_0\to\mathbb{Z}$, хотя $\mathbb{Z}$ содержит «в два раза больше» чисел в наивном смысле счёта. Это же наблюдение — определение Дедекинда для бесконечных множеств.

Ошибка 6. Считают композицию функций коммутативной.

Как выглядит: «$g\circ f$ и $f\circ g$ — одно и то же, порядок не важен, ведь и там, и там участвуют одни и те же две функции».

Почему возникает: при умножении чисел порядок не важен, и привычка автоматически переносится на композицию.

Как правильно: композиция функций в общем случае не коммутативна — задание 10 даёт явный числовой контрпример ($2x+2$ против $2x+1$). Более того, часто $f\circ g$ вообще не определена, даже если $g\circ f$ определена: нужно совпадение кодомена первой применяемой функции с доменом второй, а в обратном порядке это может не выполняться.

Ошибка 7. Из инъективности композиции $g\circ f$ делают вывод об инъективности обеих функций.

Как выглядит: «$g\circ f$ инъективна, значит и $f$, и $g$ по отдельности инъективны».

Почему возникает: кажется естественным, что свойство целого распределяется поровну между частями.

Как правильно: из инъективности $g\circ f$ гарантированно следует инъективность только первой применяемой функции $f$ (задание 20 даёт строгое доказательство), а вот $g$ может быть не инъективна — «склейки» в $g$ могут прятаться вне образа $f$, куда композиция никогда не заглядывает, и оттого остаются незамеченными.

Главное запомнить

• Функция строго — это подмножество $f \subseteq A\times B$ с условием: каждому $a\in A$ отвечает ровно один $b\in B$. Домен, кодомен и образ (область значений $f(A)\subseteq B$) — три разных понятия, и образ не обязан совпадать с кодоменом.

• Инъективность ("разные входы — разные выходы"): $f(a_1)=f(a_2)\Rightarrow a_1=a_2$. Опровергается одним числовым контрпримером; доказывается прямым алгебраическим выводом из предположения о равенстве значений.

• Сюръективность ("на", каждый элемент кодомена достигнут): $f(A) = B$. Свойство тройки (формула, домен, кодомен) — одна и та же формула может быть сюръективной на один объявленный кодомен и не сюръективной на другой.

• Биективность = инъективность + сюръективность = существование и единственность прообраза у каждого элемента кодомена.

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

• Для конечных множеств: $|A|>|B|$ делает инъекцию невозможной, $|A|<|B|$ делает сюръекцию невозможной (принцип Дирихле). Для бесконечных множеств эти правила не работают — счётное множество может быть в биекции со своим собственным подмножеством (определение Дедекинда).

• Композиция: $(g\circ f)(a)=g(f(a))$ не коммутативна. Инъективность и сюръективность сохраняются при композиции инъекций/сюръекций соответственно; композиция биекций — биекция, и $(g\circ f)^{-1}=f^{-1}\circ g^{-1}$ (порядок переворачивается).

• Обратное к «композиция сохраняет свойство» не всегда верно: из инъективности $g\circ f$ следует инъективность $f$, но не обязательно $g$.

• В ML инъективность — это условие идентифицируемости: возможности восстановить вход/параметр по выходу. Softmax и полная мультиколлинеарность признаков — примеры структурной неинъективности; one-hot-кодирование строится инъективным намеренно.

• В ML сюръективность и биективность — условия обратимости слоёв. ReLU не инъективен (необратим), Leaky ReLU биективен на $\mathbb{R}$. Нормализующие потоки строят каждый слой явно биективным (например, через связывающие преобразования RealNVP), чтобы вся сеть целиком была обратима по теореме о композиции биекций.

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

Связь с другими темами курса

Что нужно было знать до этого урока

Урок опирается на аппарат из урока 176 «Множества и операции»: декартово произведение $A\times B$, из которого строится отношение, подмножества, объединения и пересечения, которые понадобились для описания образа и кодомена. Само понятие отношения и функции как частного случая отношения — прямое продолжение теоретико-множественного языка, наработанного там же. Из курса линейной алгебры (уроки 157, 161, 167, 172) взяты матричное умножение, критерий обратимости через определитель, ранг и ядро матрицы, теорема о ранге и дефекте (следствие критерия существования решений однородной системы) — весь этот аппарат напрямую использован в примерах про линейные отображения (задания 16, 17, 26) как частный, вычислительно прозрачный случай общей теории инъекций и сюръекций. Из школьного курса — техника решения уравнений (без неё не проверить сюръективность конкретной формулы) и представление о строгой монотонности функции.

Что изучить дальше

Урок 178 «Числовые последовательности» рассматривает последовательность как частный случай функции — отображение $\mathbb{N}\to\mathbb{R}$, — и вопросы об инъективности такого отображения напрямую связаны с тем, повторяются ли члены последовательности. Дальше по курсу — понятие мощности множества и счётности, где биекция становится главным рабочим инструментом сравнения размеров бесконечных множеств (продолжение сюжета с диагональным аргументом Кантора из задания 23); теория групп, где изоморфизм — это в точности биекция, сохраняющая структуру операции; и математический анализ, где непрерывность плюс строгая монотонность на отрезке — стандартный способ получать биекции и обратные функции (как в примере с $\arcsin$), а обратная функция дифференцируема по теореме о производной обратной функции.

Где это нужно в жизни

💻 Программирование. Хеш-таблицы и хеш-функции — примеры сознательно неинъективных отображений (сжатие большого пространства ключей в малое число ячеек), где важно управлять частотой и последствиями коллизий, а не пытаться получить невозможную инъективность. Криптографические примитивы — шифрование должно быть инъективным (иначе расшифровка неоднозначна), а хорошие хеш-функции для паролей — намеренно необратимыми (сюръективными на выход, но без эффективного способа найти прообраз).

🤖 ML/AI. Нормализующие потоки (RealNVP, Glow, NICE) строятся из явно биективных связывающих слоёв, что даёт точное вычисление правдоподобия через формулу замены переменных. Идентифицируемость параметров моделей (линейная регрессия при мультиколлинеарности, факторный анализ, независимый компонентный анализ) — прямое следствие инъективности отображения «параметр → предсказание». Автоэнкодеры и любое сжатие размерности структурно неинъективны при уменьшении числа измерений — потеря информации гарантирована теоремой о ранге и дефекте, а не браком обучения.

📊 Data Science. One-hot- и label-кодирование категориальных признаков проектируются инъективными, чтобы декодирование было однозначным; feature hashing, наоборот, намеренно жертвует инъективностью ради фиксированной размерности признакового пространства. Проверка ранга матрицы признаков перед обучением линейной модели — это прямая проверка инъективности отображения параметров в предсказания.

🔬 Наука. В физике обратимые (биективные) преобразования координат лежат в основе канонических преобразований в механике; необратимые процессы (энтропия растёт) моделируются как неинъективные отображения фазового пространства во времени. В криптографии RSA и другие асимметричные схемы шифрования используют так называемые trapdoor-перестановки — биекции, которые легко вычислить в одну сторону и почти невозможно обратить без секретного ключа.

Интересные факты

• Притча об «Отеле Гильберта», придуманная Давидом Гильбертом для популяризации идей Кантора: отель с бесконечным числом занятых номеров всегда может принять ещё одного гостя — достаточно попросить каждого постояльца переселиться из номера $n$ в номер $n+1$, освобождая номер $1$. Это не фокус, а прямая иллюстрация биекции между $\mathbb{N}$ и $\mathbb{N}\setminus\{1\}$ — собственным подмножеством самого себя, ровно как в определении бесконечного множества по Дедекинду и в задании 22 этого урока.

• Теорема Кантора — Бернштейна — Шрёдера утверждает: если между множествами $A$ и $B$ существуют инъекции в обе стороны ($f:A\to B$ и $g:B\to A$, обе инъективны), то между $A$ и $B$ обязательно существует и биекция — даже если ни одна из исходных инъекций сама биекцией не была. Теорему независимо доказали Феликс Бернштейн и Эрнст Шрёдер на рубеже 1897–1898 годов (свой вариант доказательства позже предложил и Дедекинд); она превращает сравнение мощностей множеств в задачу, для которой достаточно найти два «однонаправленных» вложения вместо одного явного взаимно однозначного соответствия.

• Термины «инъекция», «сюръекция» и «биекция» не восходят к классическому анализу XIX века — их ввела в середине XX века группа французских математиков, публиковавшаяся под коллективным псевдонимом Николя Бурбаки, в рамках проекта по полной аксиоматизации математики на теоретико-множественном языке. До этого математики обходились описательными оборотами вроде «взаимно однозначное соответствие», и по сей день это словосочетание используют как синоним биекции.

• Диагональный аргумент Кантора (задание 23) применяется далеко за пределами теории множеств: похожая логика лежит в основе теоремы Гёделя о неполноте и доказательства неразрешимости проблемы остановки в теории вычислимости Тьюринга — в обоих случаях строится объект, который по построению не может совпасть ни с одним элементом предполагаемого полного списка.

Лайфхаки и полезные трюки

1. Проверяй инъективность через уравнение, а не через график, если формула алгебраическая. Предположи $f(x_1)=f(x_2)$ и попробуй алгебраически вывести $x_1=x_2$. Если на каком-то шаге приходится делить на выражение, которое может обнулиться, или извлекать корень чётной степени — скорее всего, инъективность нарушена именно там, и стоит поискать контрпример рядом с этим местом.

2. Строгая монотонность — самый быстрый достаточный признак инъективности на $\mathbb{R}$. Если производная не меняет знак (или равна нулю лишь в изолированных точках, как у $x^3$ в нуле), функция инъективна автоматически — не нужно решать уравнение $f(x_1)=f(x_2)$ вручную.

3. Для сюръективности реши уравнение $f(x)=y$ относительно $x$ и проверь, при каких $y$ решение существует. Полученное множество допустимых $y$ — это и есть образ функции. Сюръективность на объявленный кодомен — это в точности вопрос «содержится ли кодомен целиком в этом множестве».

4. Для конечных множеств сначала сравни мощности, прежде чем строить отображение. $|A|>|B|$ сразу исключает инъекцию, $|A|<|B|$ сразу исключает сюръекцию — не нужно перебирать варианты, принцип Дирихле даёт ответ мгновенно (задания 7, 8, 19).

5. Если формула не даёт биекцию на естественном домене — сузь домен до участка монотонности. Так строятся все обратные тригонометрические функции ($\arcsin$, $\arccos$, $\arctan$) и обратный квадратный корень: не меняй формулу, поменяй объявление домена и кодомена.

6. Для линейных отображений между конечномерными пространствами биективность — это про определитель или ранг, а не про алгебраические выкладки с $x_1, x_2$. Квадратная матрица с ненулевым определителем задаёт биекцию; отображение из пространства большей размерности в пространство меньшей — никогда не инъективно, из меньшей в большую — никогда не сюръективно (теорема о ранге и дефекте, знакомая по линейной алгебре).

7. В коде на Python/NumPy проверяй обратимость слоя эмпирически перед тем, как полагаться на неё в проде. Пропусти случайный тензор через слой и его заявленную обратную функцию: np.allclose(inverse(forward(x)), x). Это не заменяет математическое доказательство биективности, но быстро ловит опечатки в формуле обратного преобразования — как в задании 30.

8. Помни, что композиция инъекций и сюръекций сохраняет свойство только в направлении «частные функции → композиция», а не наоборот. Прежде чем делать вывод о свойствах отдельных слоёв по свойству всей сети, вспомни контрпример из задания 20: инъективность целого не гарантирует инъективность каждой части.

Три термина этого урока — тонкий, но мощный инструмент: они превращают расплывчатое «функция обратима» в точное, проверяемое условие, которое можно доказать уравнением или опровергнуть одним числовым контрпримером. В следующий раз, когда увидишь слой нейросети, хеш-функцию или кодировку признаков, задай себе не вопрос «работает ли это», а вопрос «что теряется при этом отображении, а что — нет» — и три слова, разобранные сегодня, дадут на него точный ответ.