Лекция 6. Функции и отображения

Функция — частный случай бинарного отношения: такое отношение между $A$ и $B$, в котором у каждого элемента $A$ ровно одна пара. На лекции 4 мы изучали свойства отношений на одном множестве, теперь — отношения «из $A$ в $B$», которые ведут себя как функции. Главные сюжеты занятия: какие функции можно «обратить» и почему из большего множества в меньшее нельзя отобразить без склеек.

1. Функция

1.1. Функция как сопоставление

Определение 1. Пусть $A$ и $B$ — множества. Функция $f\colon A \to B$ сопоставляет каждому элементу $a \in A$ ровно один элемент $b \in B$:

$\forall a \in A\ \exists!\, b \in B\ \ f(a) = b.$

Слова «функция» и «отображение» здесь синонимы. Квантор $\exists!$ читается «существует ровно один» (лекция 2).

1.2. Функция как отношение

Определение 2. Бинарное отношение $f \subseteq A \times B$ называется функцией из $A$ в $B$, если выполнены два условия:

• тотальность слева: $\forall a \in A\ \exists b \in B\ \ (a, b) \in f$ — у каждого $a$ есть хотя бы одна пара;
• функциональность: $(a, b_1) \in f \wedge (a, b_2) \in f \to b_1 = b_2$ — у каждого $a$ не больше одной пары.

Вместе условия дают «ровно одну пару», то есть определение 1. Запись $f(a) = b$ означает $(a, b) \in f$.

1.3. Тождественная функция и композиция

Определение 3. Тождественная функция на $A$ — это $\mathrm{id}_A\colon A \to A$, $\mathrm{id}_A(a) = a$. Как отношение это диагональ $\{(a, a) \mid a \in A\}$.

Определение 4. Композиция функций $f\colon A \to B$ и $g\colon B \to C$ — функция $g \circ f\colon A \to C$,

$(g \circ f)(a) = g(f(a)).$

Сначала применяется $f$, потом $g$ — читаем справа налево. Композиция ассоциативна: $h \circ (g \circ f) = (h \circ g) \circ f$, обе части переводят $a$ в $h(g(f(a)))$. Тождественная функция ничего не меняет: $f \circ \mathrm{id}_A = f$ и $\mathrm{id}_B \circ f = f$.

1.4. Домен и кодомен

Определение 5. Для $f\colon A \to B$ множество $A$ называется доменом (областью определения) $f$, а $B$ — кодоменом (областью прибытия).

Кодомен — часть функции: $x \mapsto x^2$ как функция $\mathbb R \to \mathbb R$ и как функция $\mathbb R \to [0, +\infty)$ — это разные функции, и ниже у них будут разные свойства. Кодомен не обязан состоять только из значений $f$: множество реально принимаемых значений — образ $f(A)$, и в общем случае $f(A) \subseteq B$.

2. Образ и прообраз

Определение 6. Пусть $f\colon A \to B$.

• Для $X \subseteq A$ образ $X$ — множество значений на элементах $X$: $f(X) = \{y \mid \exists x \in X\ \ f(x) = y\} = \{f(x) \mid x \in X\}.$
• Для $Y \subseteq B$ прообраз $Y$ — множество элементов, которые попадают в $Y$: $f^{-1}(Y) = \{x \in A \mid \exists y \in Y\ \ f(x) = y\} = \{x \in A \mid f(x) \in Y\}.$

3. Тотальные и частичные функции

Определение 7. Функция $f\colon A \to B$ тотальна, если она определена для всех $a \in A$. Частичная функция определена лишь на некотором подмножестве $A$; её записывают $f\colon A \rightharpoonup B$.

Частичная функция — отношение, у которого есть функциональность, но может не быть тотальности слева. Всё, что выше и ниже называется просто «функцией», — тотальные функции.

4. Инъекция

Определение 8. Функция $f\colon A \to B$ инъективна, если разные элементы переходят в разные:

$\forall a_1, a_2 \in A\ \ f(a_1) = f(a_2) \to a_1 = a_2.$

Равносильная форма (контрапозиция): $a_1 \ne a_2 \to f(a_1) \ne f(a_2)$. На схеме — в каждый элемент $B$ входит не больше одной стрелки.

Чтобы доказать инъективность, берут $f(a_1) = f(a_2)$ и выводят $a_1 = a_2$. Чтобы опровергнуть — предъявляют два разных элемента с одинаковым значением.

4.1. Левая обратная

Теорема 1 (левая обратная). Пусть $A \ne \varnothing$. Функция $f\colon A \to B$ инъективна тогда и только тогда, когда существует $g\colon B \to A$ такая, что $g \circ f = \mathrm{id}_A$.

Такую $g$ называют левой обратной к $f$: она стоит слева в композиции и «отменяет» $f$.

Доказательство. $(\Leftarrow)$ Пусть $f(a_1) = f(a_2)$. Применим $g$: $a_1 = g(f(a_1)) = g(f(a_2)) = a_2$.

$(\Rightarrow)$ Зафиксируем какой-нибудь $a_0 \in A$ — здесь нужна непустота $A$. Определим $g$:

• если $b \in f(A)$, то по инъективности есть ровно один $a$ с $f(a) = b$; положим $g(b) = a$;
• если $b \notin f(A)$, положим $g(b) = a_0$.

Тогда $g(f(a)) = a$ для любого $a \in A$, то есть $g \circ f = \mathrm{id}_A$. $\blacksquare$

Левая обратная обычно не единственна: значения на $B \setminus f(A)$ выбираются произвольно.

4.2. Монотонность и инъективность

Теорема 2. Если $f\colon \mathbb R \to \mathbb R$ строго возрастает, то $f$ инъективна.

Доказательство. Пусть $a_1 \ne a_2$, без ограничения общности $a_1 < a_2$. Из строгого возрастания $f(a_1) < f(a_2)$, значит $f(a_1) \ne f(a_2)$. $\blacksquare$

То же верно для строго убывающих функций. Обратное неверно: $f(x) = \dfrac{1}{x}$ при $x \ne 0$ и $f(0) = 0$ — биекция $\mathbb R \to \mathbb R$ (она обратна сама себе), но не монотонна на $\mathbb R$: $f(-1) = -1 < f(1) = 1$, а $f(1) = 1 > f(2) = \dfrac12$.

5. Сюръекция

Определение 9. Функция $f\colon A \to B$ сюръективна, если каждый элемент $B$ — значение $f$:

$\forall b \in B\ \exists a \in A\ \ f(a) = b.$

Равносильно: $f(A) = B$, образ совпадает с кодоменом. На схеме — в каждый элемент $B$ входит хотя бы одна стрелка.

5.1. Правая обратная

Теорема 3 (правая обратная). Пусть $B \ne \varnothing$. Функция $f\colon A \to B$ сюръективна тогда и только тогда, когда существует $g\colon B \to A$ такая, что $f \circ g = \mathrm{id}_B$.

Доказательство. $(\Leftarrow)$ Для любого $b \in B$ положим $a = g(b)$; тогда $f(a) = f(g(b)) = b$.

$(\Rightarrow)$ Для каждого $b \in B$ множество $f^{-1}(\{b\})$ непусто по сюръективности. Выберем в нём по одному элементу и назовём его $g(b)$. Тогда $f(g(b)) = b$, то есть $f \circ g = \mathrm{id}_B$. $\blacksquare$

Для бесконечного $B$ одновременный выбор элемента из каждого $f^{-1}(\{b\})$ опирается на аксиому выбора. Правая обратная тоже обычно не единственна: из каждого прообраза можно взять любой элемент.

6. Биекция

Определение 10. Функция $f$ биективна (взаимно однозначна), если она одновременно инъективна и сюръективна: каждый $b \in B$ имеет ровно один прообраз.

Теорема 4. У биекции $f\colon A \to B$ есть ровно одна обратная функция $f^{-1}\colon B \to A$, то есть функция с

$f^{-1} \circ f = \mathrm{id}_A, \qquad f \circ f^{-1} = \mathrm{id}_B.$

Доказательство. Существование. Для каждого $b \in B$ ровно один $a$ с $f(a) = b$: хотя бы один по сюръективности, не больше одного по инъективности. Положим $f^{-1}(b) = a$. Обе композиции тождественны по построению.

Единственность. Пусть $g$ и $h$ — две обратные. По ассоциативности композиции

$g = g \circ \mathrm{id}_B = g \circ (f \circ h) = (g \circ f) \circ h = \mathrm{id}_A \circ h = h. \ \blacksquare$

Та же выкладка показывает больше: если у $f$ есть левая обратная $g$ и правая обратная $h$, то $g = h$. А по теоремам 1 и 3 функция с двусторонней обратной инъективна и сюръективна. Итог: $f$ обратима $\iff$ $f$ биекция.

7. Принцип Дирихле

Теорема 5 (принцип Дирихле). Пусть $A$ и $B$ — конечные множества и $|A| > |B|$. Тогда не существует инъективной функции $f\colon A \to B$.

Иначе говоря, любая функция из большего конечного множества в меньшее склеивает хотя бы два элемента: найдутся $a_1 \ne a_2$ с $f(a_1) = f(a_2)$. Классическая формулировка — «если $n + 1$ кролика сидят в $n$ клетках, то в какой-то клетке хотя бы два кролика».

Доказательство. Пусть $f$ инъективна. Тогда $f$ — биекция между $A$ и $f(A)$, поэтому $|f(A)| = |A|$. Но $f(A) \subseteq B$, значит $|A| = |f(A)| \le |B|$ — противоречие с $|A| > |B|$. $\blacksquare$

Для конечных множеств одинаковой мощности из тех же соображений получается полезное следствие: если $|A| = |B|$, то $f\colon A \to B$ инъективна $\iff$ сюръективна $\iff$ биективна. Для бесконечных множеств это неверно: $n \mapsto 2n$ на $\mathbb N$ инъективна, но не сюръективна.

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

• Забывать про кодомен. «Функция $x^2$ сюръективна» — бессмысленное утверждение, пока не сказано, в какое множество она действует.
• Путать прообраз $f^{-1}(Y)$ с обратной функцией. Прообраз есть всегда, обратная функция — только у биекции.
• Доказывать инъективность, проверяя «$a_1 = a_2 \to f(a_1) = f(a_2)$». Это верно для любой функции; нужна обратная импликация.
• Считать, что отношение с парой у каждого $a$ — уже функция. Нужна ещё функциональность: у $a$ не должно быть двух разных пар.
• Путать порядок в композиции: $g \circ f$ — сначала $f$, потом $g$. Левая обратная к инъекции — $g \circ f = \mathrm{id}_A$, правая к сюръекции — $f \circ g = \mathrm{id}_B$.
• Применять принцип Дирихле в обратную сторону: из $|A| \le |B|$ не следует, что любая $f\colon A \to B$ инъективна, — только что инъективная существует.

Мини-тренажёр

1. Является ли отношение $\{(1, a), (2, b), (3, a), (2, c)\}$ функцией из $\{1, 2, 3\}$ в $\{a, b, c\}$? Почему?
2. Для $f\colon \mathbb Z \to \mathbb Z$, $f(n) = n \bmod 3$ (остаток от $0$ до $2$) найдите $f(\{1, 2, 3, 4\})$ и $f^{-1}(\{0\})$.
3. Инъективна ли, сюръективна ли $f\colon \mathbb Z \to \mathbb Z$, $f(n) = 2n$? А $g\colon \mathbb Z \to \mathbb Z$, $g(n) = n + 5$?
4. Постройте левую обратную к $f\colon \{1, 2\} \to \{a, b, c\}$, $f(1) = a$, $f(2) = c$. Сколько всего таких левых обратных?
5. Постройте правую обратную к $f\colon \{1, 2, 3\} \to \{a, b\}$, $f(1) = a$, $f(2) = b$, $f(3) = b$. Сколько их всего?
6. Сколько существует биекций $\{1, 2, 3\} \to \{a, b, c\}$? А инъекций $\{1, 2, 3, 4\} \to \{a, b, c\}$?
7. В классе $30$ учеников. Докажите, что хотя бы двое празднуют день рождения в один день недели в этом году, а среди любых $367$ людей двое родились в один день года.

Ответы

1. Нет: у $2$ две пары, $(2, b)$ и $(2, c)$, — нарушена функциональность.
2. $f(\{1, 2, 3, 4\}) = \{1, 2, 0, 1\} = \{0, 1, 2\}$. $f^{-1}(\{0\}) = \{\dots, -3, 0, 3, 6, \dots\} = 3\mathbb Z$.
3. $f(n) = 2n$ инъективна ($2n_1 = 2n_2 \Rightarrow n_1 = n_2$), но не сюръективна: нечётные числа не достигаются. $g(n) = n + 5$ — биекция, обратная $g^{-1}(m) = m - 5$.
4. $g(a) = 1$, $g(c) = 2$, а $g(b)$ — любое из $\{1, 2\}$. Значит, левых обратных две.
5. $g(a) = 1$ обязательно, $g(b) \in \{2, 3\}$. Правых обратных две: $g(b) = 2$ или $g(b) = 3$.
6. Биекций $3! = 6$. Инъекций из $4$ элементов в $3$ нет — по принципу Дирихле.
7. Функция «ученик $\mapsto$ день недели дня рождения» действует из $30$ элементов в $7$, $30 > 7$, поэтому не инъективна. Аналогично $367 > 366$ дней даже в високосном году.

Шпаргалка