Функции и отображения в абстрактной алгебре

В абстрактной алгебре функция — это не просто школьная история типа y = x². Это основной язык, через который математика говорит: “один объект переходит в другой объект по некоторому правилу”. (Да-да, вино переходит в уксус, а Мюнхгаузен — в Феофила.)

То есть функция описывает не только вычисление, но и связь между множествами, структурами, группами, кольцами, полями и так далее. Если множества (sets) — это “объекты”, то функции (functions / mappings) — это “стрелки” между объектами.

Что такое функция

Пусть есть два множества: A и B. Функция или отображение (function / mapping) из A в B записывается так:

f : A -> B

Читается: f — функция из A в B.

Это значит, что каждому элементу a из множества A функция f сопоставляет ровно один элемент b из множества B. То есть для каждого input должен быть один output.

Domain, codomain, range, image

Если есть функция:

f : A -> B

то:

• A — область определения (domain);
• B — целевое множество / кодомен (codomain);
• f(a) — образ элемента a (image of a);
• множество всех реально достигаемых значений — это образ функции (image / range).

Пример:

f : R -> R
f(x) = x²

Здесь:

domain = R
codomain = R

Но реально функция x² выдаёт только неотрицательные числа:

image = [0, +∞)

То есть image не всегда совпадает с codomain.

Запись f(a) = b и f: a -> b

Если функция f отправляет элемент a в элемент b, пишут:

f(a) = b

Иногда пишут так:

f : a -> b

Разница в следующем. Такая запись говорит, между какими множествами работает функция:

f : A -> B

А вот такая говорит, что конкретно происходит с отдельным элементом:

a -> b

Например:

f : Z -> Z
x -> x²

Это значит: функция из integers в integers, которая отправляет x в x².

Главное условие функции: один input — один output

Функция обязана дать каждому элементу domain ровно один output.

Например, вот это функция:

f(1) = 2
f(2) = 4
f(3) = 6

Потому что каждый input имеет один output.

А вот это уже не функция:

f(1) = 2
f(1) = 5

Потому что один и тот же input 1 получил два разных output.

Well-defined function — корректно определённая функция

Определение well-defined function является довольно важным:

Функция должна зависеть от самого элемента, а не от того, как именно этот элемент записан.

Дело в том, что иногда один и тот же объект можно записать по-разному. Например, rational number или по-простому дробь:

1/2 = 2/4 = 3/6

Всё это разные записи, но очевидно они представляют один и тот же элемент из множества rational numbers.

Теперь допустим, что кто-то пытается определить вот такую функцию:

f(a/b) = a + b

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

1/2 = 2/4

То есть 1/2 и 2/4 являются разными записями одного и того же элемента. Но при этом значения-то выходят разные:

f(1/2) = 1 + 2 = 3
f(2/4) = 2 + 4 = 6

То есть получилось, что:

f(1/2) != f(2/4)

Выходит, эта функция зависит от конкретной записи дроби, а не от самого рационального числа. Про такую штуку говорят: not well-defined.

Как проверить well-defined

Чтобы проверить, что правило действительно задаёт well-defined функцию, надо сделать так:

предположить, что x1 = x2
доказать, что f(x1) = f(x2)

То есть если два выражения обозначают один и тот же объект, функция обязана дать один и тот же результат.

Для rational numbers это выглядело бы так:

если a/b = c/d,
то надо доказать f(a/b) = f(c/d)

Для нашего “плохого” примера из раздела выше это не работает:

f(a/b) = a + b

Потому что:

1/2 = 2/4

но:

1 + 2 != 2 + 4

Почему well-defined важно для quotient structures

Это особенно важно для quotient-конструкций. Например, в modular arithmetic есть классы:

[2] = [7] = [12]

Все они обозначают один и тот же equivalence class modulo 5.

Если мы определяем функцию на классах:

F([a]) = что-то

то надо проверить:

если [a] = [b],
то F([a]) = F([b])

Иначе функция будет зависеть от выбора представителя класса (representative), а это плохо.

То же самое с операциями:

[a] + [b] = [a+b]

Надо убедиться, что если взять других представителей того же класса, результат не изменится как класс.

Например modulo 5:

[2] = [7]
[4] = [9]

Тогда:

[2] + [4] = [6] = [1]

Потому что 6 mod 5 = 1.

и:

[7] + [9] = [16] = [1]

Потому что 16 mod 5 = 1. Мы получили один и тот же класс, значит эта операция well-defined.

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

Пусть есть функции:

f : A -> B
g : B -> C

Тогда можно составить их в своего рода цепочку. Это и есть композиция функций (composition of functions):

g ∘ f : A -> C

Она определяется так:

(g ∘ f)(a) = g(f(a))

Читается: “сначала применяем f, потом применяем g”.

Это важный момент: композиция читается именно справа налево. То есть:

g ∘ f

значит:

сначала делаей f, потом g

Пример композиции

Пусть:

f(x) = x + 1
g(x) = 2x

Тогда:

(g ∘ f)(x) = g(f(x))

Сначала делаем:

f(x) = x + 1

Потом:

g(x + 1) = 2(x + 1)

Значит:

(g ∘ f)(x) = 2x + 2

Учтите, что композиция функций обычно не коммутативна.

Ассоциативность композиции

Пусть есть функции:

α : A -> B
β : B -> C
γ : C -> D

Тогда мы можем записать:

γ ∘ (β ∘ α) = (γ ∘ β) ∘ α

Это называется ассоциативность (associativity).

Смысл простой: “если порядок функций один и тот же, то скобки не важны”.

Можно писать просто:

γ ∘ β ∘ α

Но порядок всё равно читается справа налево:

сначала α
потом β
потом γ

При этом ассоциативность не означает, что можно менять функции местами. Скобки можно двигать, порядок — нет.

One-to-one function / Injective function

Функция:

f : A -> B

называется one-to-one или injective, если верно следующее:

f(a1) = f(a2) => a1 = a2

Говоря по-человечески: “если outputs одинаковые, значит inputs тоже были одинаковые”.

Или эквивалентно:

a1 != a2 => f(a1) != f(a2)

То есть разные inputs дают разные outputs. Или, говоря иначе, injective function не “склеивает” разные элементы.

Пример функции injective

Рассмотрим функцию:

f : Z -> Z
f(x) = x³

Она является injective.

Почему?

Если имеем:

x³ = y³

следовательно:

x = y

Других вариантов быть не может: разные integers не могут дать один и тот же куб.

Пример not injective

Функция:

f : Z -> Z
f(x) = x²

не является injective.

Потому что:

f(2) = 4
f(-2) = 4

Разные inputs дали одинаковый output. Короче, на выходе одно и то же, а на входе было разное.

Или другой пример с модулем:

f : Z -> N
f(x) = |x|

Эта функция тоже не injective, потому что:

|-2| = 2
|2| = 2

Onto function / Surjective function

Функция вида:

f : A -> B

называется onto или surjective, если каждый элемент B является образом хотя бы одного элемента A.

Формально: “for every b ∈ B, there exists a ∈ A such that f(a) = b”. По-человечески: “функция покрывает всё целевое множество B”. Или иначе: в B нет элементов, в которые никто не попал.

Пример функции onto

Функция:

f : R -> R
f(x) = x³

является onto.

Почему?

Потому что для любого real number b можно взять кубический корень:

x = ∛b

Тогда:

x³ = b

То есть любой real number достигается.

Пример not onto

Функция:

f : Z -> Z
f(x) = x³

не является onto. Обратите внимание, что тут речь идёт именно о domain/codomain целых чисел, в отличие от примера выше, где использовались все вещественные числа (R).

Так что почему же эта функция не является onto? Потому что не каждое целое число (из множества Z) является кубом целого числа.

Например 2 не является кубом никакого integer. Нет такого x ∈ Z, что:

x³ = 2

Одна формула — разные свойства

Свойства функции зависят не только от формулы, но и от domain/codomain.

Формула вполне может быть одна и та же, например:

x -> x³

Но при этом domain/codomain может быть разный:

Z -> Z : тогда наша функция injective, но not onto
R -> R : тогда функция injective и onto

Потому что, как уже объяснено выше, в R есть кубический корень для любого real number, а в Z нет кубического корня, например, для числа 2.

Примеры

Рассмотрим примеры функций и разных domain/codomain. Попробуем разобраться какими они являются.

1. x -> x³, из Z в Z

f : Z -> Z
f(x) = x³

• one-to-one / injective: yes
• onto / surjective: no

Почему not onto? Потому что 2 не является кубом никакого integer.

2. x -> x³, из R в R

f : R -> R
f(x) = x³

• one-to-one / injective: yes
• onto / surjective: yes

Почему onto? Потому что у каждого real number есть real cube root.

3. x -> |x|, из Z в N

f : Z -> N
f(x) = |x|

Обратите внимание, что comain тут именно N (натуральные числа)!

Эта функция:

• one-to-one / injective: no
• onto / surjective: yes

Почему not injective?

|-2| = |2| = 2

Почему onto? Потому что любой nonnegative integer n равен:

|n|

4. x -> x², из Z в Z

f : Z -> Z
f(x) = x²

• one-to-one / injective: no
• onto / surjective: no

Почему not injective?

(-2)² = 2² = 4

Почему not onto? Потому что отрицательные integers вообще не достигаются, и 2 тоже не является квадратом какого-либа целого числа.

Bijective function / Bijection

Функция называется bijective или bijection (биекция), если она одновременно:

• injective / one-to-one;
• surjective / onto.

То есть удовлетворяются оба условия:

• different inputs give different outputs
• every target element is hit

По-человечески: “идеальное соответствие один-к-одному между элементами A и B”. Каждый элемент A уходит в уникальный элемент B, и каждый элемент B получает ровно один элемент из A.

Inverse function

Если функция:

α : A -> B

является bijective, то у неё есть обратная функция (inverse function):

α⁻¹ : B -> A

Она как бы “отменяет” действие α.

Если:

α(s) = t

то:

α⁻¹(t) = s

То есть α отправила s в t; α⁻¹ возвращает t обратно в s.

Почему для inverse нужны injective и surjective

Чтобы обратная функция существовала нормально, нужны оба свойства.

Surjective нужно для существования

Если функция не onto (есть элемент b ∈ B, в который никто не попал), то непонятно, что делать со случаем:

α⁻¹(b)

Ведь его просто неоткуда вернуть.

Injective нужно для единственности

Если функция не injective, то разные элементы могли попасть в один b.

Например:

α(a1) = b
α(a2) = b

где:

a1 != a2

Тогда непонятно, куда должна вернуть обратная функция:

α⁻¹(b)

в a1 или в a2?

Поэтому:

• onto даёт, что обратное значение существует;
• injective даёт, что оно единственное.

Формулы для inverse

Если:

α : A -> B

bijective, то:

α⁻¹ ∘ α = id_A

и:

α ∘ α⁻¹ = id_B

Где id_A и id_B — identity functions.

Identity function — это функция, которая ничего не меняет:

id_A(a) = a

То есть сначала применили функцию, потом отменили её через α⁻¹, и в итоге вернулись туда же.

Важно: α⁻¹ — это не 1/α

Запись:

α⁻¹

для функции означает inverse function. Это не обязательно “единица, делённая на α”.

Как известно, в школьной алгебре запись x⁻¹ часто означает:

1/x

Но для функции:

f⁻¹

означает именно обратное отображение, которое отменяет f.

Например:

f(x) = x + 1

Тогда обратная будет:

f⁻¹(x) = x - 1

А вовсе не:

1 / (x + 1)

Теорема про функции

Пусть имеется:

α : A -> B
β : B -> C
γ : C -> D

Тогда выполняются следующие базовые факты.

1. Композиция ассоциативна

γ ∘ (β ∘ α) = (γ ∘ β) ∘ α

Скобки здесь не важны, если порядок функций не меняется.

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

Если функции α и β являются one-to-one / injective, то:

β ∘ α

тоже являются one-to-one / injective.

Короче, если ни первая, ни вторая функция не “склеивают” элементы, то их цепочка тоже не склеит элементы.

Короткое доказательство:

Пусть:

(β ∘ α)(a1) = (β ∘ α)(a2)

Тогда:

β(α(a1)) = β(α(a2))

Так как β injective:

α(a1) = α(a2)

Так как α injective:

a1 = a2

Значит β ∘ α injective.

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

Если функции α и β являются onto / surjective, то:

β ∘ α

тоже будет onto / surjective.

Короче, если первый шаг покрывает весь промежуточный слой, а второй покрывает весь финальный слой, то и вся цепочка покрывает финальный слой.

Короткое доказательство: надо показать, что любой элемент c ∈ C достигается.

Так как β является onto, то для любого c ∈ C найдётся b ∈ B, такое что:

β(b) = c

Так как α onto, для этого b ∈ B найдётся a ∈ A, такое что:

α(a) = b

Тогда:

(β ∘ α)(a) = β(α(a)) = β(b) = c

Значит β ∘ α является onto.

4. Функция bijective имеет inverse

Если функция:

α : A -> B

является one-to-one и onto, то существует:

α⁻¹ : B -> A

такая что:

α⁻¹ ∘ α = id_A

и:

α ∘ α⁻¹ = id_B

То есть inverse function действительно отменяет исходную функцию в обе стороны.

Связь с крипто-сферой

Для crypto и zk это важно.

Hash functions

Hash function обычно не injective, если domain больше codomain.

Например, если входов бесконечно много, а outputs фиксированной длины, то коллизии неизбежны. Короче, разные inputs могут дать один hash.

Finite fields

В finite fields функции и операции должны быть well-defined.

Например, когда мы говорим:

F_p = Z/pZ

мы работаем с equivalence classes.

Значит операции типа:

[a] + [b] = [a+b]

должны не зависеть от выбора representatives.

Polynomial maps

В zk часто возникают polynomial functions над finite fields:

f : F_p -> F_p

или более общо:

f : F_p^n -> F_p

Там важно понимать:

• domain;
• codomain;
• image;
• injective или нет;
• можно ли обратить отображение;
• не склеиваются ли разные witnesses.

Смысл всего этого безобразия

Функции — это не просто вычислительные правила. В абстрактной алгебре функции — это язык связей между структурами.

Сначала мы учимся понимать обычные mappings:

f : A -> B

Потом смотрим:

• Теряют ли они информацию (injective?).
• Покрывают ли всё целевое множество (surjective?).
• Можно ли их обратить (bijective? inverse exists?).
• Можно ли их соединять (composition?)

И дальше на этом языке строятся уже настоящие алгебраические звери типа изоморфизма.