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

Разбираемся, что такое функция строго, и учимся отличать инъекцию, сюръекцию и биекцию — ключ к понятию «столько же элементов».

Функция f: A → B — это правило, которое каждому элементу множества A сопоставляет ровно один элемент множества B.

Зачем нужен строгий взгляд на функции

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

Функция — это особое отношение

Функция f: A → B — это отношение из A в B (подмножество A × B) с одним дополнительным требованием: каждому элементу A соответствует ровно один элемент B. Не ноль, не два — ровно один. Множество A называют областью определения, B — областью значений (кодоменом). То, что реально получается на выходе, — образ: { f(a) | a ∈ A }. Образ — это подмножество кодомена, и оно может быть меньше всего B.

Пример: f(x) = x² на целых числах. Область определения — все целые, кодомен — тоже целые, но образ — только неотрицательные квадраты {0, 1, 4, 9, ...}. Значит, не каждый элемент кодомена «достигается».

Три ключевых свойства

Разберём интуицию на «рассадке». Представь: A — гости, B — стулья, функция сажает каждого гостя на стул. Инъекция — никакие два гостя не сидят на одном стуле (стульев хватило, склейки нет). Сюръекция — каждый стул занят (пустых нет). Биекция — каждый гость на своём стуле и каждый стул занят ровно одним гостем: гостей ровно столько же, сколько стульев.

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

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

Если f — биекция, у неё есть обратная функция f⁻¹, которая «отматывает назад»: f⁻¹(f(a)) = a. Обратная существует только у биекций — это и есть математический смысл «обратимости». Шифр, который можно расшифровать, — биекция. Хеш, который нельзя обратить, — не биекция (он склеивает разные входы в одинаковые выходы, и информация теряется).

Проверяем перебором на Python

Для конечных множеств свойства функции легко проверить: вычислим все значения и посмотрим на образы. Напишем универсальный анализатор.

def analyze(f, domain, codomain):
    images = [f(x) for x in domain]
    injective = len(set(images)) == len(images)   # нет повторов на выходе
    surjective = set(images) == set(codomain)      # покрыт весь кодомен
    return injective, surjective, injective and surjective

dom = [0, 1, 2, 3]
cod = [0, 1, 2, 3]

inj, sur, bij = analyze(lambda x: (x + 1) % 4, dom, cod)
print("f(x) = (x+1) mod 4:",
      "инъекция" if inj else "не инъекция,",
      "сюръекция" if sur else "не сюръекция,",
      "БИЕКЦИЯ" if bij else "не биекция")

inj, sur, bij = analyze(lambda x: x % 2, dom, [0, 1])
print("g(x) = x mod 2 в {0,1}:",
      "инъекция" if inj else "не инъекция,",
      "сюръекция" if sur else "не сюръекция")

Вывод:

f(x) = (x+1) mod 4: инъекция сюръекция БИЕКЦИЯ
g(x) = x mod 2 в {0,1}: не инъекция, сюръекция

Функция f(x) = (x+1) mod 4 — биекция: это «сдвиг по кругу», он переставляет 4 элемента без потерь, поэтому обратим. А g(x) = x mod 2 склеивает чётные в 0, нечётные в 1 — это не инъекция (повторы на выходе есть), хотя сюръекция (оба значения 0 и 1 достигаются). Идея «посчитать len(set(images)) против len(images)» — стандартный способ за одну строку проверить инъективность.

Композиция функций

Функции можно композировать: (g ∘ f)(x) = g(f(x)) — сначала применяем f, потом g. Полезные факты, которые стоит запомнить: композиция двух инъекций — инъекция; композиция двух сюръекций — сюръекция; значит, композиция двух биекций — снова биекция. Композиция — это математическая модель «конвейера» преобразований данных, который вы строите в любом пайплайне обработки.

Топологическая сортировка: порядок из частичного порядка

Частичный порядок постоянно встречается в программировании как набор зависимостей: «задача A должна быть выполнена до задачи B». Возникает практический вопрос: можно ли выстроить все задачи в одну линию (линейный порядок) так, чтобы ни одна зависимость не нарушилась? Это называется топологической сортировкой частичного порядка.

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

Типичные ошибки

• Путать кодомен и образ. Сюръективность зависит от того, что объявлено кодоменом. f(x) = x² сюръективна на «неотрицательные», но не сюръективна на «все числа».
• Думать, что у любой функции есть обратная. Обратная существует только у биекций. У не-инъекции «обратить» нельзя — непонятно, из какого входа пришли.
• Считать, что инъекция = сюръекция. Это независимые свойства. Бывает инъекция без сюръекции, сюръекция без инъекции, и только их сочетание — биекция.

Итог

• Функция сопоставляет каждому входу ровно один выход; это отношение с условием однозначности.
• Инъекция «не склеивает», сюръекция «покрывает весь кодомен», биекция — и то, и другое.
• Биекция между конечными множествами означает «в них поровну элементов» — основа счёта.
• Обратная функция существует только у биекций — это и есть обратимость.