Вступительная часть: множества, отображения, образ и прообраз

Преподаватель: Ржонсницкая Юлия Борисовна.

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

1. Язык: кванторы и связки

Кванторы: $\forall$ — «для любого» (All), $\exists$ — «существует» (Exists), $\exists!$ — «существует ровно один».

Логические связки: конъюнкция $\wedge$ («и»), дизъюнкция $\vee$ («или»), отрицание $\neg$ («не»), импликация $\Rightarrow$ («следует»), эквивалентность $\Leftrightarrow$ («тогда и только тогда»).

Определение 1. Предикат $P(x)$ — высказывание, зависящее от переменных; при подстановке конкретных значений оно становится истинным или ложным.

Запись $\forall x \in A\ \ P(x)$ читается «для любого $x$ из $A$ верно $P(x)$», а $\exists x \in A : P(x)$ — «найдётся хотя бы один $x$ из $A$, для которого верно $P(x)$».

1.1. Отрицание высказываний

Отрицание обозначается $\neg$ или чертой сверху. При отрицании кванторы меняются на противоположные, а само высказывание инвертируется:

$\neg\bigl(\exists x\ P(x)\bigr) \iff \forall x\ \neg P(x), \qquad \neg\bigl(\forall x\ P(x)\bigr) \iff \exists x\ \neg P(x).$

Словами: «не существует подходящего» — это «каждый не подходит»; «не все подходят» — это «найдётся хотя бы один, который не подходит».

Для нескольких кванторов правило применяется по цепочке:

$\neg\bigl(\forall x\ \exists y : P(x, y)\bigr) \iff \exists x\ \forall y : \neg P(x, y).$

Пример. Отрицание высказывания «$\forall x \in \mathbb{R}\ \ \exists y \in \mathbb{R} : x < y$» — это «$\exists x \in \mathbb{R}\ \ \forall y \in \mathbb{R} : x \ge y$». Первое истинно, второе ложно.

2. Множества и операции над ними

Запись $x \in A$ — «элемент $x$ принадлежит множеству $A$»; $x \notin A$ — не принадлежит. Множество не упорядочено и не содержит повторов: $\{1, 2, 3\} = \{3, 1, 2\} = \{1, 1, 2, 3\}$.

Принцип экстенсиональности. Два множества равны тогда и только тогда, когда состоят из одних и тех же элементов:

$A = B \iff \forall x\ (x \in A \Leftrightarrow x \in B).$

В аксиоматической теории множеств (ZFC) это отдельная аксиома; в курсе она используется как рабочий критерий равенства.

2.1. Подмножество и равенство

Определение 2. $A$ — подмножество $B$ ($A \subseteq B$), если каждый элемент $A$ лежит в $B$:

$A \subseteq B \iff \forall x\ (x \in A \Rightarrow x \in B).$

Равенство — два включения: $A = B \iff (A \subseteq B) \wedge (B \subseteq A)$.

Отсюда два шаблона доказательства, которыми пользуются всю лекцию:

• чтобы доказать $A \subseteq B$, берём произвольный $x \in A$ и показываем, что $x \in B$;
• чтобы доказать $A = B$, либо доказываем оба включения, либо сразу строим цепочку равносильностей $x \in A \Leftrightarrow \dots \Leftrightarrow x \in B$.

2.2. Операции

Определение 3. Пусть $A$ и $B$ — подмножества универсального множества $U$ (все множества, о которых идёт речь в задаче).

1. Пересечение: $A \cap B = \{x \in U \mid (x \in A) \wedge (x \in B)\}$ — ключевое слово «и».
2. Объединение: $A \cup B = \{x \in U \mid (x \in A) \vee (x \in B)\}$ — ключевое слово «или» (нестрогое: можно и в обоих).
3. Разность: $A \setminus B = \{x \in U \mid (x \in A) \wedge (x \notin B)\}$.
4. Симметрическая разность: $A \triangle B = (A \setminus B) \cup (B \setminus A)$ — элементы ровно одного из множеств.
5. Дополнение $A$ до $X$: $X \setminus A$; при $X = U$ обозначается $\overline{A}$.

Пример. $A = \{1, 2, 3\}$, $B = \{3, 4\}$: $A \cap B = \{3\}$, $A \cup B = \{1, 2, 3, 4\}$, $A \setminus B = \{1, 2\}$, $B \setminus A = \{4\}$, $A \triangle B = \{1, 2, 4\}$.

2.3. Таблица-переводчик «множества ↔ логика»

Именно этим переводчиком делаются почти все доказательства ниже.

3. Семейства множеств

Пусть $A$ — множество индексов, и каждому $\alpha \in A$ сопоставлено множество $Y_\alpha$. Набор $\{Y_\alpha\}_{\alpha \in A}$ называется семейством множеств. Индекс $\alpha$ — просто «номер» множества: при $A = \{1, 2, 3\}$ семейство — это три множества $Y_1, Y_2, Y_3$, при $A = \mathbb{N}$ — бесконечная последовательность $Y_1, Y_2, Y_3, \dots$

Определение 4. Объединение и пересечение семейства:

$\bigcup_{\alpha \in A} Y_\alpha = \{x \mid \exists \alpha \in A : x \in Y_\alpha\}, \qquad \bigcap_{\alpha \in A} Y_\alpha = \{x \mid \forall \alpha \in A : x \in Y_\alpha\}.$

В объединение попадают элементы хотя бы одного множества семейства, в пересечение — элементы каждого. Квантор $\exists$ отвечает за «или», квантор $\forall$ — за «и».

Примеры.

1. $Y_1 = \{1, 2\}$, $Y_2 = \{2, 3\}$, $Y_3 = \{5\}$: $\displaystyle\bigcup_{k=1}^{3} Y_k = \{1, 2, 3, 5\}$.
2. $Y_1 = \{1, 2, 3\}$, $Y_2 = \{2, 3, 4\}$, $Y_3 = \{0, 2, 5\}$: $\displaystyle\bigcap_{k=1}^{3} Y_k = \{2\}$.
3. Бесконечный пример из анализа: $Y_n = \left(-\tfrac{1}{n}, \tfrac{1}{n}\right)$, $n \in \mathbb{N}$. Интервалы вложены: $(-1, 1) \supset \left(-\tfrac12, \tfrac12\right) \supset \left(-\tfrac13, \tfrac13\right) \supset \dots$, и $\bigcap_{n=1}^{\infty} Y_n = \{0\}.$ Ноль лежит в каждом интервале; любое $x \ne 0$ выпадает из $Y_n$, как только $\tfrac1n \le |x|$. Такие бесконечные пересечения окрестностей появятся в определениях предела и замкнутости.

4. Законы де Моргана

Для двух множеств:

$\overline{A \cup B} = \overline{A} \cap \overline{B}, \qquad \overline{A \cap B} = \overline{A} \cup \overline{B}.$

Теорема 1 (де Морган для семейства). Для любого множества $X$ и семейства $\{Y_\alpha\}_{\alpha \in A}$

$X \setminus \bigcup_{\alpha \in A} Y_\alpha = \bigcap_{\alpha \in A} (X \setminus Y_\alpha), \qquad X \setminus \bigcap_{\alpha \in A} Y_\alpha = \bigcup_{\alpha \in A} (X \setminus Y_\alpha).$

Словами: «не попасть ни в одно из $Y_\alpha$» — это «не попасть в каждое по отдельности»; «не попасть во все сразу» — это «не попасть хотя бы в одно».

Доказательство первого равенства. Берём произвольный $x$ и переводим каждую строку по таблице:

$x \in X \setminus \bigcup_{\alpha \in A} Y_\alpha \iff (x \in X) \wedge \Bigl(x \notin \bigcup_{\alpha \in A} Y_\alpha\Bigr) \iff (x \in X) \wedge \neg\bigl(\exists \alpha \in A : x \in Y_\alpha\bigr)$

$\iff (x \in X) \wedge \bigl(\forall \alpha \in A : x \notin Y_\alpha\bigr) \iff \forall \alpha \in A\ \bigl((x \in X) \wedge (x \notin Y_\alpha)\bigr) \iff \forall \alpha \in A\ \ x \in X \setminus Y_\alpha \iff x \in \bigcap_{\alpha \in A} (X \setminus Y_\alpha).$

Единственный содержательный шаг — отрицание квантора $\exists$ в третьем переходе; в четвёртом мы внесли условие $x \in X$, не зависящее от $\alpha$, под квантор $\forall$. Так как цепочка верна для любого $x$, множества равны. Второе равенство доказывается так же с заменой $\forall$ на $\exists$. $\blacksquare$

Проверка на числах. $X = \{1, 2, 3, 4, 5\}$, $Y_1 = \{1, 2\}$, $Y_2 = \{2, 4\}$. Слева: $Y_1 \cup Y_2 = \{1, 2, 4\}$, $X \setminus (Y_1 \cup Y_2) = \{3, 5\}$. Справа: $X \setminus Y_1 = \{3, 4, 5\}$, $X \setminus Y_2 = \{1, 3, 5\}$, их пересечение $\{3, 5\}$. Совпадение — не случайность, а теорема.

5. Декартово произведение

Определение 5. Упорядоченная пара $(a, b)$ — пара, в которой важен порядок:

$(a, b) = (c, d) \iff (a = c) \wedge (b = d).$

В частности, $(1, 2) \ne (2, 1)$, тогда как $\{1, 2\} = \{2, 1\}$.

Определение 6. Декартово произведение множеств $A$ и $B$ — множество всех упорядоченных пар, первая координата которых лежит в $A$, а вторая — в $B$:

$A \times B = \{(x, y) \mid (x \in A) \wedge (y \in B)\}.$

Примеры.

1. $A = \{1, 2\}$, $B = \{3, 4\}$: $A \times B = \{(1, 3), (1, 4), (2, 3), (2, 4)\}$ — четыре точки. Для конечных множеств $|A \times B| = |A| \cdot |B|$.
2. $[1, 2] \times [3, 4]$ — уже не четыре точки, а прямоугольник на плоскости; $\mathbb{R} \times \mathbb{R} = \mathbb{R}^2$ — вся координатная плоскость.

Свойства.

1. В общем случае $A \times B \ne B \times A$: при $A = \{1, 2\}$, $B = \{3\}$ получаем $A \times B = \{(1, 3), (2, 3)\}$, а $B \times A = \{(3, 1), (3, 2)\}$. Между ними, впрочем, есть естественное взаимно однозначное соответствие $(a, b) \mapsto (b, a)$.
2. Дистрибутивность относительно пересечения и объединения: $A \times (B \cap C) = (A \times B) \cap (A \times C), \qquad A \times (B \cup C) = (A \times B) \cup (A \times C).$

Доказательство первого равенства. Берём произвольную пару $(a, b)$:

$(a, b) \in A \times (B \cap C) \iff (a \in A) \wedge (b \in B \cap C) \iff (a \in A) \wedge (b \in B) \wedge (b \in C)$

$\iff \bigl((a \in A) \wedge (b \in B)\bigr) \wedge \bigl((a \in A) \wedge (b \in C)\bigr) \iff \bigl((a, b) \in A \times B\bigr) \wedge \bigl((a, b) \in A \times C\bigr) \iff (a, b) \in (A \times B) \cap (A \times C).$

Для объединения в той же цепочке «и» во второй координате заменяется на «или». $\blacksquare$

6. Отображения

Определение 7. Пусть $X$, $Y$ — множества. Отображение (функция) $f : X \to Y$ — правило, которое каждому $x \in X$ сопоставляет ровно один элемент $y \in Y$; пишут $y = f(x)$.

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

Если $y = f(x)$, то $y$ называется образом точки $x$, а $x$ — прообразом точки $y$. У одной точки $y$ может быть несколько прообразов: для $f(x) = x^2$ числа $2$ и $-2$ — два прообраза числа $4$.

Определение 8. Для $f : X \to Y$:

• область определения: $\mathrm{Dom}(f) = X$;
• область прибытия (кодомен): $Y$ — множество, в которое функция объявлена действующей;
• образ отображения (область значений): $\mathrm{Im}(f) = f(X) = \{y \in Y \mid \exists x \in X : f(x) = y\}.$

Всегда $\mathrm{Im}(f) \subseteq Y$, но равенство может не выполняться.

Пример. $f : [-1, 1] \to \mathbb{R}$, $f(x) = x^2$. Область прибытия объявлена равной $\mathbb{R}$, но реально принимаются только значения из $[0, 1]$: $\mathrm{Im}(f) = [0, 1] \subsetneq \mathbb{R}$. Школьная задача «найдите область значений функции $y = x^2$ на отрезке $[-1, 1]$» — это в точности вычисление $f([-1, 1])$.

7. Образ и полный прообраз множества

Пусть $f : X \to Y$.

Определение 9. Образ множества $A \subseteq X$ при отображении $f$:

$f(A) = \{y \in Y \mid \exists x \in A : y = f(x)\}.$

Собираем все значения, которые функция принимает на элементах $A$. Запись $y \in f(A)$ не говорит, какой именно $x$ дал значение $y$, — только что хотя бы один такой $x$ существует. Из-за этого квантора в теореме об образе пересечения появится тонкость.

Определение 10. Полный прообраз множества $B \subseteq Y$ при отображении $f$:

$f^{-1}(B) = \{x \in X \mid f(x) \in B\}.$

Эквивалентная запись, ближе к лекционной: $f^{-1}(B) = \{x \in X \mid \exists y \in B : f(x) = y\}$. Полный прообраз точки — это $f^{-1}(\{y\}) = \{x \in X \mid f(x) = y\}$, множество всех её прообразов.

Примеры для $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$.

Графически: образ множества $A$ — какие «высоты» $y$ достигает график при $x \in A$; полный прообраз $B$ — какие $x$ приводят график на высоты из $B$; прообразы точки $y_0$ — абсциссы точек пересечения графика с горизонтальной прямой $y = y_0$.

8. Четыре свойства образа и прообраза

Теорема 2. Пусть $f : X \to Y$. Для любых $A, B \subseteq Y$

1. $f^{-1}(A \cup B) = f^{-1}(A) \cup f^{-1}(B)$;
2. $f^{-1}(A \cap B) = f^{-1}(A) \cap f^{-1}(B)$;

и для любых $A, B \subseteq X$

3. $f(A \cup B) = f(A) \cup f(B)$;
4. $f(A \cap B) \subseteq f(A) \cap f(B)$.

Полный прообраз дистрибутивен относительно объединения и пересечения, а образ — только относительно объединения. В пункте 4 обратное включение, вообще говоря, неверно.

8.1. Прообраз объединения и пересечения

Доказательство 1. Берём произвольный $x \in X$:

$x \in f^{-1}(A \cup B) \iff f(x) \in A \cup B \iff \bigl(f(x) \in A\bigr) \vee \bigl(f(x) \in B\bigr) \iff \bigl(x \in f^{-1}(A)\bigr) \vee \bigl(x \in f^{-1}(B)\bigr) \iff x \in f^{-1}(A) \cup f^{-1}(B).$

Доказательство 2 — та же цепочка с $\cap$ и $\wedge$ вместо $\cup$ и $\vee$. $\blacksquare$

Все переходы — определения, поэтому получаются равносильности, а значит, равенства множеств.

Проверка для $f(x) = x^2$. Пусть $A = \{1, 4\}$, $B = \{4, 9\}$. Тогда $A \cap B = \{4\}$ и $f^{-1}(A \cap B) = \{-2, 2\}$. С другой стороны, $f^{-1}(A) = \{-2, -1, 1, 2\}$, $f^{-1}(B) = \{-3, -2, 2, 3\}$, пересечение снова $\{-2, 2\}$.

8.2. Образ объединения

Доказательство 3. Берём произвольный $y \in Y$:

$y \in f(A \cup B) \iff \exists x \in A \cup B : f(x) = y \iff \bigl(\exists x \in A : f(x) = y\bigr) \vee \bigl(\exists x \in B : f(x) = y\bigr) \iff \bigl(y \in f(A)\bigr) \vee \bigl(y \in f(B)\bigr) \iff y \in f(A) \cup f(B).$

Средний переход: «существует $x$, лежащий в $A$ или в $B$» — то же самое, что «существует $x$ в $A$ или существует $x$ в $B$». Квантор существования свободно проходит через «или». $\blacksquare$

Проверка. $f(x) = x^2$, $A = \{-2, -1\}$, $B = \{0, 1, 3\}$: $f(A) = \{1, 4\}$, $f(B) = \{0, 1, 9\}$, $f(A) \cup f(B) = \{0, 1, 4, 9\} = f(A \cup B)$.

То же доказательство через полный прообраз точки

Для любого $y$ верно $y \in f(A) \iff f^{-1}(\{y\}) \cap A \ne \varnothing$: пересечение непусто ровно тогда, когда найдётся $x$, лежащий в $A$ и удовлетворяющий $f(x) = y$. Поэтому

$f(A \cup B) = \{y \mid f^{-1}(\{y\}) \cap (A \cup B) \ne \varnothing\} = \{y \mid \bigl(f^{-1}(\{y\}) \cap A\bigr) \cup \bigl(f^{-1}(\{y\}) \cap B\bigr) \ne \varnothing\}$

$= \{y \mid f^{-1}(\{y\}) \cap A \ne \varnothing \ \vee\ f^{-1}(\{y\}) \cap B \ne \varnothing\} = f(A) \cup f(B).$

Использован факт $U \cup V \ne \varnothing \iff (U \ne \varnothing) \vee (V \ne \varnothing)$. Обратите внимание: писать нужно $f^{-1}(\{y\})$, а не $f^{-1}(y)$ — обратной функции может не быть, а полный прообраз одноточечного множества есть всегда.

8.3. Образ пересечения: почему только включение

Доказательство 4. Для включения берём произвольный элемент левой части и показываем, что он лежит в правой. Пусть $y \in f(A \cap B)$. По определению образа существует один конкретный $x \in A \cap B$ с $f(x) = y$. Из $x \in A \cap B$ следует одновременно $x \in A$ и $x \in B$. Из $x \in A$ и $f(x) = y$ получаем $y \in f(A)$; из $x \in B$ и $f(x) = y$ получаем $y \in f(B)$. Значит, $y \in f(A) \cap f(B)$. $\blacksquare$

Коротко:

$y \in f(A \cap B) \Rightarrow \exists x \in A \cap B : f(x) = y \Rightarrow (x \in A) \wedge (x \in B) \Rightarrow \bigl(y \in f(A)\bigr) \wedge \bigl(y \in f(B)\bigr) \Rightarrow y \in f(A) \cap f(B).$

Почему нельзя пойти обратно. Из $y \in f(A) \cap f(B)$ мы знаем: $\exists x_1 \in A : f(x_1) = y$ и $\exists x_2 \in B : f(x_2) = y$. Но $x_1$ и $x_2$ могут быть разными, и ни один из них не обязан лежать в $A \cap B$. Квантор существования не проходит через «и»: утверждение «$\exists x$: $x \in A$ и $x \in B$» сильнее, чем «$\exists x \in A$ и $\exists x \in B$».

Когда равенство есть. Если $f$ инъективно ($f(x_1) = f(x_2) \Rightarrow x_1 = x_2$), то два «свидетеля» $x_1 \in A$ и $x_2 \in B$ обязаны совпасть, этот общий $x$ лежит в $A \cap B$, и $f(A \cap B) = f(A) \cap f(B)$ для любых $A, B \subseteq X$. Верно и обратное: если равенство выполняется для всех $A, B$, то $f$ инъективно (иначе для склеенных $x_1 \ne x_2$ берём $A = \{x_1\}$, $B = \{x_2\}$).

9. Дополнительные свойства полного прообраза

Полный прообраз согласован со всеми операциями над множествами, не только с $\cup$ и $\cap$. Для $B \subseteq Y$

$f^{-1}(Y \setminus B) = X \setminus f^{-1}(B).$

Доказательство. $x \in f^{-1}(Y \setminus B) \iff f(x) \in Y \setminus B \iff f(x) \notin B \iff x \notin f^{-1}(B) \iff x \in X \setminus f^{-1}(B)$. $\blacksquare$

Отсюда $f^{-1}(A \setminus B) = f^{-1}(A) \setminus f^{-1}(B)$, а для произвольного семейства $\{B_\alpha\}$

$f^{-1}\Bigl(\bigcup_\alpha B_\alpha\Bigr) = \bigcup_\alpha f^{-1}(B_\alpha), \qquad f^{-1}\Bigl(\bigcap_\alpha B_\alpha\Bigr) = \bigcap_\alpha f^{-1}(B_\alpha).$

Образ же с разностью не дружит: $f(A \setminus B) \ne f(A) \setminus f(B)$ в общем случае. Тот же пример $f(x) = x^2$, $A = \{-2, 2\}$, $B = \{2\}$: слева $f(\{-2\}) = \{4\}$, справа $\{4\} \setminus \{4\} = \varnothing$. Из-за этой «дисциплинированности» прообразы удобнее образов в анализе и топологии: непрерывность, например, определяется через прообразы открытых множеств.

10. Шаблоны доказательств

Если в цепочке все стрелки $\Leftrightarrow$ — доказано равенство. Если хотя бы одна только $\Rightarrow$ — доказано лишь включение, и стоит поискать контрпример к обратному.

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

1. Путать образ и полный прообраз. Образ идёт «вперёд» по стрелке функции (из $A \subseteq X$ получаем $f(A) \subseteq Y$), полный прообраз — «назад» (из $B \subseteq Y$ получаем $f^{-1}(B) \subseteq X$).
2. Считать $f^{-1}$ обратной функцией. Для множеств это обозначение полного прообраза, оно работает всегда.
3. Путать область прибытия и область значений. $\mathrm{Im}(f) \subseteq Y$, и включение бывает строгим.
4. Ставить равенство в свойстве 4 без инъективности. Контрпример: $f(x) = x^2$, $A = \{-2\}$, $B = \{2\}$.
5. Забывать, где живут множества. В $f^{-1}(B)$ множество $B$ лежит в $Y$; в $f(A)$ множество $A$ лежит в $X$.
6. Не различать «существует один и тот же $x$» и «существуют, возможно, разные $x_1$, $x_2$». Это вся логика пункта 4.
7. Переставлять кванторы $\forall$ и $\exists$ при отрицании или в определениях.

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

Пусть $f : \mathbb{R} \to \mathbb{R}$, $f(x) = x^2$.

1. Найдите $f(\{-3, -1, 2\})$.
2. Найдите $f([-2, 1])$.
3. Найдите $f^{-1}(\{9\})$.
4. Найдите $f^{-1}([0, 4])$.
5. Найдите $f^{-1}((1, 9))$.
6. Для $A = \{-2, 0\}$ и $B = \{0, 2\}$ сравните $f(A \cap B)$ и $f(A) \cap f(B)$.
7. Запишите отрицание высказывания $\forall \varepsilon > 0\ \ \exists N \in \mathbb{N}\ \ \forall n \ge N : |a_n| < \varepsilon$.
8. Найдите $\displaystyle\bigcup_{n=1}^{\infty} \left[\tfrac1n, 1\right]$ и $\displaystyle\bigcap_{n=1}^{\infty} \left[0, \tfrac1n\right]$.

Ответы

1. $\{1, 4, 9\}$.
2. $[0, 4]$: наибольшее значение достигается в точке $-2$, наименьшее — в $0$.
3. $\{-3, 3\}$.
4. $[-2, 2]$.
5. $(-3, -1) \cup (1, 3)$.
6. $A \cap B = \{0\}$, поэтому $f(A \cap B) = \{0\}$. Но $f(A) = f(B) = \{0, 4\}$, значит, $f(A) \cap f(B) = \{0, 4\}$. Включение строгое.
7. $\exists \varepsilon > 0\ \ \forall N \in \mathbb{N}\ \ \exists n \ge N : |a_n| \ge \varepsilon$.
8. $(0, 1]$ и $\{0\}$.

13. Шпаргалка