Математический анализ 1. Лекция 1

О курсе

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

Основное обучение происходит на решении задач. Занятие устроено так: сначала лекция, затем приём задач из листочков ассистентами, только очно. Дедлайнов по листочкам нет, сдавать можно в течение всего семестра, поэтому над задачами стоит думать где угодно, не только раз в неделю. Даже нерешённая задача, над которой думали, делает своё дело: узнать решение после этого совсем не то же самое, что узнать его сразу. Постарайтесь не подменять собственное думание интернетом, искусственным интеллектом или соседом; это примерно одно и то же.

Зачёт по листочкам: барьер ставится оптимистично в $80%$ закрытых клеточек, на практике граница съезжает к $65$ – $70%$ ; пустых листочков быть не должно. Затем письменный экзамен в начале декабря: $7$ – $10$ задач на четыре часа; при наличии зачёта по листочкам оценка за экзамен становится оценкой за курс.

Если лекции слушать не получается, читайте книги.

Совет

В. А. Зорич. Математический анализ, два тома, нужны оба. Выдающийся учебник; после каждой главы есть подборка задач, и тот, кто прорешает их все, будет знать анализ лучше многих. В начале первого тома есть и список аксиом теории множеств.
С. М. Львовский. Математический анализ – курс, прочитанный в Независимом университете и изданный в виде короткой, очень лаконичной книги; с задачами и примерами экзаменов НМУ.
И. А. Виноградова, С. Н. Олехник, В. А. Садовничий. Задачи и упражнения по математическому анализу – задачник, издание после 2017 года. Отличается от других сборников тем, что перед каждой главой есть краткая теория и разбор основных задач, в том числе трудных, так что по нему можно учиться самостоятельно: прочитать, что нужно знать, пройти вслед за разбором с ручкой и бумагой, затем взять похожую задачу и решить самому.
К. Куратовский, А. Мостовский. Теория множеств – для тех, кому интересно, как теория множеств строится из аксиом.

Множества

Изложение анализа, как и всей математики, зиждется на языке теории множеств, поэтому начинаем с множеств и функций, почти от самых корней.

Что такое множество, мы не знаем. Слова «совокупность», «набор», «коллекция», «собрание объектов, называемых элементами» это просто много похожих слов, а не определение. Мы не будем определять ни множество, ни то, что может быть его элементом. Есть множество $A$ , есть элемент $a$ и есть значок $a \in A$ .

О чём мы договариваемся сразу: $a \in A$ – это высказывание. В любой ситуации, с которой мы столкнёмся, должно быть возможно сказать, истинно оно или ложно. Если мы оказываемся в ситуации, когда этого сказать нельзя, это противоречит нашей изначальной договорённости.

Определение (Подмножество, равенство). $A \subset B$ , если для всякого $a \in A$ выполнено $a \in B$ :

A \subset B ⟺ \forall a (a \in A \Rightarrow a \in B) .

$A = B$ , если $A \subset B$ и $B \subset A$ .

Значок $\subset$ здесь нестрогий: включение допускает совпадение. Если нужно подчеркнуть, что множества не равны, пишут $A ⊊ B$ .

Определение (Пустое множество). Пустое множество $\emptyset$ – это множество, для которого высказывание $x \in \emptyset$ всегда ложно, что бы ни подставить вместо $x$ .

Существует ли такое множество, не вопрос: в нашей игре оно есть. Слово «ничего» понимается всеобъемлюще. Когда в школе пишут « $x \in \emptyset$ » вместо «корней нет», это не ошибка, это просто ложное высказывание для всех $x$ .

Два способа задать множество

Перечисление: ${a, b, c}$ .
Указание свойства: ${x ∣ P (x)}$ : есть высказывание $P$ с буквой $x$ ; если оно истинно, $x$ лежит в множестве, если ложно, то нет.

Обоими способами мы пользуемся в обыденной жизни, не думая, что это множества: список слушателей курса задан перечислением; «кто посещает Независимый университет? Любители математики» задано указанием свойства. Казалось бы, всё естественно, но на этом пути сразу возникают трудности.

Парадокс Рассела

Осознана эта трудность была в начале XX века. Рассмотрим множество, заданное свойством:

Y = {x ∣ x \in / x} .

Тем, кто спросит, бывает ли вообще $x \in x$ : если не бывает, только лучше: тогда свойство всегда истинно, и проблемы в этом нет. Множество вполне может быть элементом другого множества: скажем, ${1, {1, 2}}$ есть законное множество, заданное перечислением.

Зададимся вопросом: истинно ли высказывание $Y \in Y$ ?

Если истинно, то $Y$ удовлетворяет свойству, то есть $Y \in / Y$ .
Если ложно, то $Y \in / Y$ , значит, $Y$ удовлетворяет свойству и должен лежать в $Y$ .

Мы ничего плохого не делали (завели множество так, как предписано) и попали ровно в ту ситуацию, в которую договорились не попадать: не можем сказать про высказывание $Y \in Y$ , истинно оно или ложно.

Причина парадокса во всеобщности: мы захотели рассмотреть все возможные объекты $x$ , а что такое «всё на свете», не очень понятно. Скажете: ну и не надо всего на свете, давайте только то, что нужно. Но мы ровно так и определяем нужные вещи. Объединение

A \cup B = {x ∣ x \in A или x \in B}

имеет ту же форму: все возможные $x$ , для которых что-то выполнено, и оно ничем априори не безопаснее, чем множество $Y$ . А объединением мы пользуемся постоянно. С пересечением и разностью такой проблемы нет: можно писать

A \cap B = {x \in A ∣ x \in B}, A ∖ B = {x \in A ∣ x \in / B},

пробегая уже не все объекты, а только элементы $A$ . В объединении так не выкрутишься.

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

Замечание. Из тех аксиом, которые действительно что-то создают «из ниоткуда», всего несколько: аксиома пары, аксиома объединения, аксиома степени (множество всех подмножеств) и аксиома бесконечности. Выделять свойством можно, но только внутри уже имеющегося множества. Ниже, после теорем Кантора–Бернштейна и Кантора, мы увидим, как это правило спасает от парадокса Рассела.

Упорядоченная пара и декартово произведение

Чтобы кроме множеств обсуждать функции, нужна ещё одна операция, а для неё понятие упорядоченной пары. По-простому это набор из двух элементов, где сказано, кто первый, а кто второй. Но мы только что оставили неопределённым само множество, и вводить ещё «первый» и «второй» (то есть числа $1$ и $2$ , которых у нас пока нет) не хочется. Выход придумали специалисты.

Определение (Упорядоченная пара по Куратовскому).

(x, y) = {{x}, {x, y}} .

Упражнение. Проверить, что если $(x, y) = (a, b)$ , то $x = a$ и $y = b$ . В этом и состоит упорядоченность: два таких множества совпадают не только тогда, когда совпадают составы, но именно $x$ совпадает с $a$ , а $y$ с $b$ . Хорошее переборное упражнение для тех, кто хочет проверить, понимает ли он, что значит «два множества равны».

Определение (Декартово произведение).

X \times Y = {(x, y) ∣ x \in X, y \in Y} .

Как это воспринимать? Это табличка: по одной стороне отложены $x$ , по другой $y$ , в клеточках стоят пары $(x, y)$ . Кто видел декартову систему координат на плоскости, тот визуализировал декартово произведение двух прямых как плоскость.

Пример (визуализации произведений). Задача с творческим подходом: любая разумная, естественная визуализация подойдёт: геометрический объект, задаваемый двумя параметрами, один из которых бегает по первому множеству, а другой по второму.

Прямая $\times$ отрезок – бесконечная полоса.
Прямая $\times$ окружность – цилиндр.
Окружность $\times$ окружность – тор.
Сфера декартовым произведением в естественном смысле не является.

Если сопоставлять множества биективно (отрезок биективен прямой), то любой континуум изобразит что угодно, поэтому речь именно о наглядных интерпретациях. За всеми этими картинками стоит одно и то же, табличка.

Функции

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

В школе (и в XIX веке) говорили так: функция это правило, закон, сопоставление, которое каждому $x \in X$ сопоставляет единственный $y \in Y$ , обозначаемый $f (x)$ . За функцией закрепляется график

Γ_{f} = {(x, y) \in X \times Y ∣ y = f (x)} .

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

\forall x \in X \exists! y \in Y : (x, y) \in Γ.

График функции это когда над каждым $x$ ровно один $y$ . Возникает хорошая мысль: не плодить слова, а так и сказать.

Определение (Функция). Функция $f : X \to Y$ – это подмножество $Γ \subset X \times Y$ такое, что для каждого $x \in X$ существует ровно один $y \in Y$ , для которого $(x, y) \in Γ$ . Запись $y = f (x)$ есть не что иное, как другой способ записать, что $(x, y) \in Γ$ .

TikZ diagram — Функция как подмножество $Γ \subset X \times Y$ : вертикальная прямая над каждой точкой $x \in X$ пересекает $Γ$ ровно один раз.

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

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

Замечание (функции нескольких переменных). А где здесь «одна переменная»? Кто такой $X$ , не сказано, это может быть что угодно, хоть $R^{10}$ . Функция десяти переменных это функция $R^{10} \to R$ ; переменные это просто кодировка точки $x$ , не больше и не меньше. В этом и фишка абстрактного языка, который часто ругают за оторванность от примеров: выучив определение функции один раз, вы знаете, что такое функция любого числа переменных.

Композиция

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

Определение (Композиция). Если $f : X \to Y$ и $g : Y \to Z$ , то определена функция $g \circ f : X \to Z$ ,

(g \circ f) (x) = g (f (x)) .

На языке графиков:

Γ_{g \circ f} = {(x, z) \in X \times Z ∣ \exists y \in Y : (x, y) \in Γ_{f}, (y, z) \in Γ_{g}} .

Выглядит как схоластика, но это буквально то, как строят график композиции вручную: рисуют отдельно график $f$ , отдельно график $g$ , берут $x$ , смотрят, как меняется $y$ , а потом по этому $y$ смотрят, как меняется $z$ . Строить графики руками полезное упражнение, хотя машина делает это лучше вас: так понимаешь, как устроены функции.

Теорема (Ассоциативность композиции).

h \circ (g \circ f) = (h \circ g) \circ f .

Доказательство. Подаём на вход $x$ и раскрываем определения:

(h \circ (g \circ f)) (x) = h ((g \circ f) (x)) = h (g (f (x))),

((h \circ g) \circ f) (x) = (h \circ g) (f (x)) = h (g (f (x))) .

Получилось одинаково.

Это доказательство очень понятное, но неудовлетворительное. Не оставляет ли вас беспокойство, что доказательство свелось к тому, что две записи побуквенно совпали? Так много чего «одинакового» можно доказать. На самом деле мы должны были доказать, что график левой части совпадает с графиком правой.

Упражнение. Проделать доказательство на языке графиков и увидеть, где именно происходит доказательство. Расписав обе части, вы получите две логические формулы с квантором «существует $y$ такое, что …, и существует $z$ такое, что …», которые внешне будут выглядеть по-разному: по-разному расставлены скобки и кванторы. Момент доказательства это проверка, что от переписывания формулы её истинность не меняется, то есть сверка таблиц истинности.

Замечание. То же самое относится к правилам действий с множествами: формулам де Моргана, дистрибутивности $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ и прочим. Кто доказывал их кругами Эйлера или смотрел на строгое доказательство вскользь, тот наверняка помнит ощущение «чудное доказательство: написали одну и ту же фразу два раза, и доказалось». Так не могло быть. В этот момент возникли два высказывания, и истинность одного надо честно вывести из истинности другого. На начальном этапе это полезно проделать; это немного занудно, поэтому на доске мы этого делать не будем, для жизни хватает и доказательства выше.

Инъекции, сюръекции, биекции

Функций «самих по себе» не бывает, мы всегда выделяем в них подклассы.

Определение (Инъекция, сюръекция, биекция). Функция $f : X \to Y$ называется

инъекцией, если для всех $x_{1}, x_{2} \in X$ из $x_{1} \neq = x_{2}$ следует $f (x_{1}) \neq = f (x_{2})$ ;
сюръекцией, если для всякого $y \in Y$ найдётся $x \in X$ такой, что $y = f (x)$ ;
биекцией, если $f$ – инъекция и сюръекция.

Запомнить легко. Инъекция есть вложение: точки не склеиваются, $X$ скопирован в $Y$ как есть, все точечки сохранились. Сюръекция есть наложение, накрытие: образы точек $X$ закрыли весь $Y$ . Биекция это и то и другое: точки $X$ и $Y$ выставлены друг против друга, «стенка на стенку». Синоним: взаимно однозначное соответствие. Это наш первый способ говорить, что два множества «одинаковые»: можно перевесить ярлыки и получить из одного множества другое.

Казалось бы, зачем на вашу голову придумывать эти понятия? Оказывается, без них не обойтись.

Теорема (Об обратной функции). Если $f : X \to Y$ – биекция, то правило, сопоставляющее каждому $y \in Y$ такой $x \in X$ , что $y = f (x)$ , является функцией из $Y$ в $X$ . Эта функция обозначается $f^{- 1}$ , называется обратной и является биекцией.

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

Почему $f^{- 1}$ – биекция? Она не может склеить два $y$ : тогда из одного $x$ вырастали бы два $y$ , а $f$ функция. Она сюръективна: каждому $x$ соответствует $y = f (x)$ .

Обратите внимание, что все «так как» здесь на самом деле «тогда и только тогда». Если хотеть, чтобы, развернув все стрелочки в обратную сторону, мы снова получили функцию, инъективность и сюръективность необходимы. Слова «функция» и «биекция» оказываются отражениями друг друга: быть биекцией для $f$ то же самое, что быть функцией для обратного соответствия; быть функцией для $f$ то же, что быть биекцией для обратного.

Пример (обратные функции из школы). Так и рождались обратные функции в школе. $x^{2}$ не инъективна: оставили инъективную ветку на $[0, + \infty)$ , которая является биекцией на $[0, + \infty)$ , и взяли обратную: арифметический $x$ . Сам синус плохой: оставили кусочек на $[- π /2, π /2]$ , который есть биекция на $[- 1, 1]$ , и получили арксинус. Полноценная обратная функция (а не «обратная справа» или «слева» в каких-то хитрых смыслах) строится только к биекции, потому что это синонимы.

Группы и биекции

Чтобы осознать ещё одну роль биекций, потребуются общие алгебраические определения.

Определение (Множество с операцией, группа). $M$ – множество с операцией $*$ , если задана функция $* : M \times M \to M$ , то есть паре элементов $(a, \tilde{a})$ функционально сопоставлен элемент $a * \tilde{a} \in M$ , какой угодно, хоть все пары в один элемент.

Множество с операцией $(M, *)$ называется группой, если

операция ассоциативна: $(a * b) * c = a * (b * c)$ ;
существует единица $e \in M$ : $e * a = a * e = a$ для всех $a$ ;
для каждого $a \in M$ существует обратный $a^{- 1}$ : $a * a^{- 1} = a^{- 1} * a = e$ .

Зачем придумана группа? Чтобы решать уравнения, самое первое уравнение, которое учила решать Марья Ивановна. Чтобы найти $x$ из $5 x = 10$ , нужно умножить на обратное к пятёрке, переставить скобочки (ассоциативность), знать, что $5^{- 1} \cdot 5$ даст единицу и что умножение на неё ничего не меняет. Как ни странно, это ровно свойства из определения, и только они: минимум, чтобы решать уравнения.

Пример (группы). $(Z, +)$ ; $(Q ∖ {0}, \cdot)$ ; группа движений плоскости, биективных преобразований, сохраняющих расстояние, одна из важнейших групп в геометрии; перестановки. Очень часто элементы группы воспринимаются как действующие на каком-то множестве: перестановки переставляют элементы, движения двигают точки плоскости. Оказывается, так можно думать всегда; к этому мы сейчас придём.

Определение (Подгруппа, изоморфизм). $N \subset M$ – подгруппа, если $N$ сама является группой относительно той же операции.

Группы $(M_{1}, *_{1})$ и $(M_{2}, *_{2})$ изоморфны, если существует биекция $f : M_{1} \to M_{2}$ , сохраняющая операцию:

f (x *_{1} y) = f (x) *_{2} f (y) .

Изоморфные группы отличаются только названиями элементов. Группа симметрий правильного треугольника и группа перестановок трёх элементов отличаются лишь визуально: любая симметрия треугольника это перестановка его вершин, и всё.

Пример (группа биекций). Важнейший пример группы:

Bij (X) = {f : X \to X ∣ f - биекция}

с операцией композиции. Композиция ассоциативна (доказано выше); единица это тождественное отображение $id_{X}$ , $x \mapsto x$ ; у каждой биекции есть обратная, которая вместе с ней возвращает $X$ на место. Эта группа прямо выглядит как действие: элементы куда-то передвигаются, потом применяется другое действие, а операция это композиция действий. Это аналог группы движений плоскости.

Теорема (О вложении группы в группу биекций). Всякая группа $(X, *)$ изоморфна подгруппе группы биекций $Bij (X)$ .

То есть всякую группу можно мыслить как действие на некотором множестве, в данном случае на ней самой. Как представить $(Z, +)$ в виде биекций? Каждому $a \in Z$ сопоставим сдвиг $x \mapsto x + a$ . В общем случае делается ровно так же: теорема монументальная, а доказательство очень простое.

Доказательство. Элементу $z \in X$ сопоставим отображение

f_{z} : X \to X, f_{z} (x) = z * x .

$f_{z}$ – биекция. Инъекция: если $z * x_{1} = z * x_{2}$ , то, умножив слева на $z^{- 1}$ , сократим и получим $x_{1} = x_{2}$ . Сюръекция: уравнение $z * x = y$ решается: $x = z^{- 1} * y$ ; для того группа и нужна.

Сопоставление $z \mapsto f_{z}$ инъективно. На каком $x$ разные $f_{z_{1}}$ и $f_{z_{2}}$ различаются? На единице: $f_{z} (e) = z$ , поэтому разным $z$ отвечают отображения с разными значениями в точке $e$ .

Операция сохраняется. Надо вычислить композицию:

f_{z_{1} * z_{2}} (x) = (z_{1} * z_{2}) * x = z_{1} * (z_{2} * x) = f_{z_{1}} (f_{z_{2}} (x)) = (f_{z_{1}} \circ f_{z_{2}}) (x),

и здесь на нас работает ассоциативность из определения группы. Произведение элементов перешло в композицию соответствующих отображений.

Сюръективность на все биекции проверять не нужно и нельзя: образ не обязан быть всем $Bij (X)$ . Но раз операция сохраняется, образ ${f_{z}}$ замкнут относительно композиции, содержит $f_{e} = id_{X}$ и вместе с $f_{z}$ содержит $f_{z^{- 1}} = f_{z}^{- 1}$ , то есть является подгруппой, а $z \mapsto f_{z}$ есть изоморфизм на неё.

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

Равномощность

Вернёмся с высот на землю, к сюжету сравнения множеств.

Определение (Равномощность). $A$ равномощно $B$ (пишем $A \sim B$ ), если существует биекция $f : A \to B$ .

Очевидные свойства:

$A \sim A$ : тождественная биекция.
Если $A \sim B$ , то $B \sim A$ : это снова теорема об обратной функции: обратная к биекции есть биекция. Изначальное определение несимметрично (сказано, откуда и куда), и чисто формально кажется, что равномощность несимметричное понятие; замечательным образом это не так.
Если $A \sim B$ и $B \sim C$ , то $A \sim C$ : композиция биекций является биекцией.

Упражнение. Композиция биекций есть биекция. Инъекция: первое отображение не склеило, разные $x$ перешли в разные $y$ ; второе не склеило, разные $y$ перешли в разные $z$ . Сюръекция: у каждого $z$ есть $y$ , из которого он получился, а у каждого $y$ есть $x$ ; значит, $z$ получился из этого $x$ .

Замечание. Не надо всуе поминать мощности. «Равномощны» нормально. А если вы начнёте исчислять кардиналы, вы должны уметь это делать: это снова на грани с аксиоматикой, и очень легко попасть впросак с тем, что имеется в виду под теми или иными словами. Мы так делать не будем. Мы всегда апеллируем к двум данным множествам: есть между ними биекция или нет.

Подмножества и двузначные функции

Для множества функций из $X$ в $Y$ часто используют обозначение $Y^{X}$ . Почему именно степень, и почему в основании $Y$ , а в показателе $X$ , а не наоборот, подумайте на досуге; это легко понять на конечных множествах. Множество всех подмножеств $X$ обозначают $2^{X}$ и называют булеаном. Двойка здесь усечённая запись множества ${0, 1}$ , и сейчас станет понятно, почему.

Определение (Индикатор). Индикатор подмножества $A \subset X$ – функция $1_{A} : X \to {0, 1}$ ,

1_{A} (x) = {1, 0, x \in A, x \in / A .

Теорема. Сопоставление $A \mapsto 1_{A}$ – биекция между $2^{X}$ и ${0, 1}^{X}$ .

Доказательство. Инъекция: если $A \neq = B$ , есть элемент, который лежит в одном множестве и не лежит в другом; на нём один индикатор равен $1$ , а другой $0$ . Сюръекция: любая функция $f : X \to {0, 1}$ есть индикатор, и именно множества ${x ∣ f (x) = 1}$ : там, где $f$ равна $1$ , индикатор равен $1$ , где $0$ , равен $0$ , а других значений нет.

Говорить о двузначных функциях и говорить о подмножествах одно и то же. Это способ кодирования: подмножество конечного множества ${1, \dots, n}$ или натуральных чисел естественно кодировать последовательностью нулей и единиц (единица, если элемент берём, ноль, если нет), и оказывается, так можно всегда.

Сами индикаторы полезнейшая штука. Обойдясь сложением и умножением (без максимумов и модулей):

1_{A \cap B} = 1_{A} 1_{B}, 1_{A \cup B} = 1_{A} + 1_{B} - 1_{A} 1_{B}, 1_{A ∖ B} = 1_{A} (1 - 1_{B}) .

В объединении лишнюю единицу, возникающую при попадании в оба множества, приходится вычесть.

Замечание. Все правила действий с множествами удобно проверять с помощью индикаторов: вместо логики и сравнения таблиц истинности получается обычное преобразование алгебраического выражения. Кто занимался комбинаторикой, знает: разбил всё на множества, написал индикаторы, и дальше арифметика, никакой наблюдательности проявлять не нужно.

Теорема Кантора–Бернштейна

Всё выше было сказками-присказками. Теперь два могучих утверждения про равномощные множества, которые пока не выводят ни в какой астрал, наивные теоремы.

Теорема (Кантор–Бернштейн). Если $A$ равномощно некоторому подмножеству $B$ , а $B$ равномощно некоторому подмножеству $A$ , то $A \sim B$ .

Пока мы в наивной теории и не используем теорему Цермело и лемму Цорна, это, пожалуй, самое мощное средство для доказательства равномощности множеств. Доказательств много; здесь приведено менее популярное и не самое простое, но начало у всех примерно одинаковое.

Доказательство. Сведение к трём вложенным множествам. Пусть $f : A \to B^{'}$ и $g : B \to A^{'}$ – биекции, $B^{'} \subset B$ , $A^{'} \subset A$ . Пройдём по обеим: $A$ перешло на $B^{'}$ , а затем $g$ унесло $B^{'}$ в подмножество $g (B^{'}) \subset g (B) = A^{'}$ . Обозначим

A_{0} = A, A_{1} = A^{'}, A_{2} = g (f (A)) = g (B^{'}), A_{0} \supset A_{1} \supset A_{2},

и $F = g \circ f$ есть биекция $A_{0}$ на $A_{2}$ . Условие свелось к более лаконичной картинке: множество $A_{1}$ зажато между $A_{0}$ и $A_{2}$ , а крайние равномощны. Достаточно доказать, что $A_{0} \sim A_{1}$ : тогда $A = A_{0} \sim A_{1} = A^{'} \sim B$ .

В чём проблема? В зазоре $A_{0} ∖ A_{1}$ : как упихать большее множество в меньшее, куда деть зазор? Любое доказательство, какое бы вы ни изучали, вертится вокруг того, куда спрятать это множество.

Хорошие множества. Назовём $M \subset A_{0}$ хорошим, если

M \supset (A_{0} ∖ A_{1}) \cup F (M),

то есть $M$ содержит зазор и свой образ при $F$ . Хорошие множества есть: например, всё $A_{0}$ . Положим

M = X хорошее ⋂ X .

$M$ – хорошее. Каждое хорошее $X$ содержит зазор, значит, и пересечение содержит зазор. Далее, $M \subset X$ для каждого хорошего $X$ , поэтому $F (M) \subset F (X) \subset X$ : образ $M$ лежит в каждом хорошем $X$ , а значит, $F (M) \subset M$ .

Ключевое равенство:

M = (A_{0} ∖ A_{1}) \cup F (M) .

Включение $\supset$ есть хорошесть $M$ . Предположим, оно строгое: найдётся $z \in M$ , не лежащий в $(A_{0} ∖ A_{1}) \cup F (M)$ . Тогда $M ∖ {z}$ тоже хорошее: зазор в нём остался, так как $z$ не из зазора; и $F (M ∖ {z}) \subset F (M) \subset M ∖ {z}$ , так как $z \in / F (M)$ . Получилось хорошее множество, строго меньшее $M$ , а $M$ уже самое маленькое, мы все хорошие пересекли. Противоречие.

В чём фишка $M$ : оно прячет зазор. Образ $F (M)$ лежит в $A_{2}$ и с зазором не пересекается, поэтому при применении $F$ из $M$ исчезает в точности зазор, и только он.

Биекция. Запишем

A_{0} = M ⊔ (A_{0} ∖ M), A_{1} = F (M) ⊔ (A_{1} ∖ F (M)) .

Выбросим $M$ из $A_{0}$ : уйдёт зазор и $F (M)$ , останется $A_{1} ∖ F (M)$ . То есть

A_{0} ∖ M = A_{1} ∖ F (M) .

Теперь на $M$ действуем биекцией $F$ (она переводит $M$ на $F (M)$ ), а на $A_{0} ∖ M$ действуем тождественно. Куски не пересекаются и покрывают всё, поэтому это биекция $A_{0}$ на $A_{1}$ .

Замечание. Рассуждение немного ломает мозг, но оно не использует ни натуральных чисел, ни счётной бесконечности; это чисто теоретико-множественное и относительно короткое доказательство; спасла возможность пересекать. Многие видели другое, гипнотическое доказательство, где биекция итерируется и рисуется счётный набор колечек, а ещё отдельно оговаривается сердцевина. Хорошее упражнение для тех, кто его видел: найти на той картинке множество $M$ . Оно там есть.

Теорема Кантора

Вторая важнейшая теорема, позволяющая понимать, что происходит с неравномощными множествами. Результат в некотором смысле негативный.

Теорема (Кантор). $2^{X}$ не равномощно $X$ .

Так как $2^{X} \sim {0, 1}^{X}$ , неважно, про какое из них доказывать: и ${0, 1}^{X} \neq \sim X$ . Разберём оба доказательства, оба короткие.

Доказательство. Через двузначные функции. Пусть ${0, 1}^{X} \sim X$ : каждому $z \in X$ сопоставлена функция $f_{z} : X \to {0, 1}$ , и это биекция. Сконструируем новую функцию по правилу

g (x) = 1 - f_{x} (x) .

Поскольку $f_{x} (x)$ принимает только значения $0$ и $1$ , то и $g$ двузначная функция. Раз есть биекция, $g = f_{z}$ для некоторого $z$ . Тогда $f_{z} (x) = 1 - f_{x} (x)$ при всех $x$ ; подставим $x = z$ :

f_{z} (z) = 1 - f_{z} (z), f_{z} (z) = \frac{1}{2},

а какое же это $0$ или $1$ ? Противоречие.

Три строчки, вроде бы очень просто, но с хитростью, с обманом: это сильно абстрагированная диагональная процедура Кантора, доведённое до лаконичности рассуждение о том, что последовательности из нулей и единиц несчётны.

Доказательство. На языке множеств. Пусть $F : X \to 2^{X}$ – биекция: каждому $z \in X$ отвечает подмножество $F (z) \subset X$ . Изготовим множество

Y = {x \in X ∣ x \in / F (x)}

Повеяло началом лекции. Это подмножество $X$ , может быть, пустое, может быть, всё $X$ ; неважно. Раз $F$ биекция, $Y = F (y)$ для некоторого $y \in X$ . Лежит ли $y$ в $F (y)$ ? Начинаются те же проблемы: если лежит, то не лежит; если не лежит, то лежит. Но это уже не парадокс, а противоречие: такого $y$ нет, а значит, никакой биекции не было. Ошибочно предположение, а не устройство мира.

Какое из двух доказательств интуитивно понятнее, решайте сами.

Следствия: почему парадокс Рассела не возвращается

Из теорем Кантора–Бернштейна и Кантора можно вывести, что при правильном следовании аксиомам таких проблем, как парадокс Рассела, не возникает. Отследим это.

Теорема. Множества всех множеств не существует.

Доказательство. Предположим противное: $M$ – множество всех множеств. Тогда все подмножества $M$ тоже множества, то есть $2^{M} \subset M$ . Включение всегда даёт инъекцию, тождественное отображение $2^{M} \to M$ . С другой стороны, всегда есть инъекция $M \to 2^{M}$ , $m \mapsto {m}$ . Инъекция есть биекция на своё подмножество, поэтому по теореме Кантора–Бернштейна $M \sim 2^{M}$ , а по теореме Кантора это невозможно.

Две теоремы запрещают говорить, что «всё на свете» есть множество. Хорошо, скажете вы, всё на свете брать нельзя. В теории множеств правило такое: выделять свойством можно, но только внутри множества. Была ли всеобщность единственной проблемой парадокса Рассела? Возьмём какое-нибудь множество $A$ и попробуем создать парадокс в нём:

Y = {x \in A ∣ x \in / x} .

Как строился парадокс: проверяем, лежит ли $Y$ в $Y$ .

Если $Y \in Y$ , то $Y \in A$ и $Y \in / Y$ ; запахло жареным, противоречие. Значит, $Y \in / Y$ .
$Y \in / Y$ означает, что условие « $Y \in A$ и $Y \in / Y$ » не выполнено, то есть $Y \in / A$ или $Y \in Y$ . Второе уже отвергнуто, остаётся $Y \in / A$ .

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

Замечание. Стопроцентной уверенности, что парадоксов не появится в дальнейшем, нет. Но правил мало: конечный список аксиом, а тех, что реально создают множества из ниоткуда (пара, объединение, степень, бесконечность), по пальцам одной руки, и если следовать им, то по крайней мере изначальные парадоксы и всеобъемлющие объекты не возникают.

Что дальше

Сегодня мы поговорили про множества, функции, биекции и две основные теоремы о равномощности, Кантора и Кантора–Бернштейна. В следующий раз ещё два абстрактных понятия: отношение порядка и отношение эквивалентности; подробнее о натуральных, целых и рациональных числах; а вишенкой на торте после натуральных чисел вполне упорядоченные множества и трансфинитная индукция, то есть как решаются относительно трудные задачи теории множеств.

Related works