% ---------------------------- страница 6 ----------------------------------
\chapter{Множества и мощности\index{Мощности}\index{Множества!мощность}}
        \label{sets-cardinalities}

\section{Множества}
        \label{sets}

Основные понятия и обозначения, связанные с множествами
и операциями над ними:

\begin{itemize}

\item
\emph{Множества}\index{Множества} состоят из
\emph{элементов}\index{Элемент множества}.
Запись $x\hm\in M$ означает, что $x$~является элементом множества~$M$.

\item
Говорят, что множество~$A$ является \emph{подмножеством}\index{Подмножество}
множества~$B$ (запись: $A\hm\subset B$\index{$\subset$}),
если все элементы~$A$ являются элементами~$B$.

\item
Множества~$A$ и~$B$
\emph{равны}\index{Равенство множеств}\index{Множества!равенство}
(запись: $A\hm=B$\index{$=$ (равенство)}), если они
содержат одни и те же элементы (другими словами, если
$A\hm\subset B$ и~$B\hm\subset A$).

\item
Если $A$\т подмножество~$B$, не равное всему~$B$, то~$A$~называют
\emph{собственным} подмножеством~$B$
(запись: $A\hm\subsetneq B$\index{$\subsetneq$}).

\item
\emph{Пустое}\index{Множества!пустые}\index{Пустое множество}
множество~$\varnothing$ не содержит ни одного
элемента и является подмножеством любого множества.

\item
\emph{Пересечение}\index{Пересечение множеств}\index{Множества!пересечение}
$A\hm\cap B$\index{$\cap$} двух множеств~$A$ и~$B$
состоит из элементов, которые принадлежат обоим множествам~$A$
и~$B$. Это записывают так:
        $$
A \cap B = \{ x\mid x\in A \text{ и } x\in B\}
        $$
(читается: множество таких~$x$, что\,$\dots$).

\item
\emph{Объединение}\index{Объединение множеств}\index{Множества!объединение}
$A\cup B$\index{$\cup$} состоит из элементов, которые принадлежат хотя
бы одному из множеств~$A$ и~$B$:
        $$
A \cup B = \{ x\mid x\in A \text{ или } x\in B\}.
        $$

% ---------------------------- страница 7 ----------------------------------
\item
\emph{Разность}\index{Разность множеств}\index{Множества!разность}
$A\setminus B$ состоит из элементов, которые принадлежат~$A$, но
не принадлежат~$B$:
        $$
A \setminus B = \{ x\mid x\in A \text{ и } x\notin B\}.
        $$
Если множество
$B$~является подмножеством
множества~$A$, разность $A\setminus B$
называют также \emph{дополнением~$B$ до~$A$}\index{Дополнение множества}.

\item
\emph{Симметрическая разность}\index{Множества!симметрическая разность}%
\index{Симметрическая разность множеств} $A\bigtriangleup B$%
\index{$\bigtriangleup$} состоит из
элементов, которые принадлежат ровно одному из множеств $A$
и~$B$:
        $$
A \bigtriangleup B =
 (A\setminus B)\cup (B\setminus A)=(A\cup B)\setminus (A\cap B).
        $$

\item
Через~$\{a,b,c\}$\index{$\{a,b,c\}$} обозначается множество, которое содержит
% ??????????     ~~~~~~~~~~~~~~~~~~~
элементы $a$, $b$, $c$ и не содержит других. Если среди~$a$, $b$, $c$
есть равные,
оно может содержать один
или два элемента. Подобное
обозначение используется и в менее формальных ситуациях:
множество членов последовательности $a_0, a_1, \dots$ обозначается
$\{a_0,a_1,\ldots\}$ или даже~$\{a_i\}$. Более аккуратная запись для
того же множества такова: $\{a_i\mid i\in\mathbb{N}\}$, где
$\mathbb{N}$\т множество натуральных чисел $\{0,1,2,\dots\}$.

\end{itemize}

Понятие множества появилось в математике сравнительно недавно, в
конце 19\д го века, в связи с работами Кантора\glossary{Кантор@\Кантор} (сравнение
мощностей множеств), о которых пойдёт речь дальше
(раздел~\ref{same-cardinality} и следующие).
Некоторое время назад этот язык пытались внедрить в школьное преподавание,
объясняя ученикам, что у уравнения $x^2\hm+1\hm=0$ есть множество
решений (впрочем, пустое), что множество решений системы
уравнений есть пересечение множеств решений каждого из них (а
для \лк совокупности\пк\ уравнений\т объединение), что в
множестве $\{2,2,3\}$ не три элемента, а два, и оно равно
множеству~$\{2,3\}$, что $\varnothing$, $\{\varnothing\}$ и
$\{\varnothing,\{\varnothing\}\}$\т это три совершенно разных
множества \итд Но всё равно большинство школьников так и не
поняло, почему множество решений уравнения $x^2\hm=4$ можно
записывать как $\{-2,2\}$, а множество решений уравнения
$x^2\hm=-4$ нельзя записывать как $\{\varnothing\}$ (а надо писать
$\varnothing$). Отметим кстати ещё два расхождения: в школе
натуральные числа начинаются с единицы, а в некоторых
книжках\т с нуля (мы тоже будем называть нуль натуральным
числом). Кроме того, иногда вместо~$\subset$
пишут~$\subseteq$\index{$\subseteq$},
% ---------------------------- страница 8 ----------------------------------
используя~$\subset$ для собственных подмножеств (вместо
нашего~$\subsetneq$).

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

\problskip
\begin{problem}
        %
Старейший математик среди шахматистов и старейший шахматист
среди математиков\т это один или тот же человек или (возможно) разные?
        %
\end{problem}

\begin{problem}
        %
Лучший математик среди шахматистов и лучший шахматист среди
математиков\т это один или тот же человек или (возможно)
разные?
        %
\end{problem}

\begin{problem}
        %
Каждый десятый математик\т шахматист, а каждый шестой
шахматист\т математик. Кого больше\т математиков или
шахматистов\т и во сколько раз?
        %
\end{problem}

\begin{problem}
        %
Существуют ли такие множества~$A$,~$B$~и~$C$, что ${A\cap
B}\hm\ne \varnothing$, $A\cap C\hm=\varnothing$ и $(A\cap
B)\setminus C\hm=\varnothing$?
        %
\end{problem}


\begin{problem}
        %
Какие из равенств
        (\textbf{а})~%
$(A\hm\cap B)\hm\cup C \hm= (A\hm\cup C)\hm\cap (B\hm\cup C)$;
        (\textbf{б})~%
$(A\hm\cup B)\hm\cap C \hm= (A\hm\cap C)\hm\cup (B\hm\cap C)$;
        (\textbf{в})~%
$(A\hm\cup B)\setminus C \hm= (A\setminus C)\hm\cup B$;
        (\textbf{г})~%
$(A\hm\cap B)\setminus C \hm= (A\setminus C)\hm\cap B$;
        (\textbf{д})~%
$A\setminus (B\hm\cup C) = (A\setminus B)\hm\cap (A\setminus C)$;
        (\textbf{е})~%
$A\setminus (B\hm\cap C) = (A\setminus B)\hm\cup (A\setminus C)$
верны для любых множеств~$A,B,C$?
        %
\end{problem}

\begin{problem}
        %
Проведите подробное доказательство верных равенств предыдущей
задачи, исходя из определений. (Докажем, что множества в левой и
правой частях равны. Пусть~$x$\т любой элемент левой части
равенства. Тогда\dots\ Поэтому $x$~входит в правую часть.
Обратно, пусть\,$\dots\,$) Приведите контрпримеры к неверным
равенствам.
        %
\end{problem}

\begin{problem}
        %
Докажите, что симметрическая разность ассоциативна:
${A\bigtriangleup(B\bigtriangleup C)}\hm=
{(A\bigtriangleup B)\bigtriangleup C}$
для любых $A$,~$B$ и~$C$. (Указание: сложение по модулю~$2$
ассоциативно.)
        %
\end{problem}

\begin{problem}
        %
Докажите, что $(A_1\hm\cap\ldots\hm\cap A_n)\hm\bigtriangleup
(B_1\hm\cap\ldots\hm\cap B_n)\hm\subset (A_1\hm\bigtriangleup
B_1)\hm\cup\ldots\hm\cup(A_n\hm\bigtriangleup B_n)$ для любых
множеств $A_1,\dots,A_n$ и $B_1,\dots,B_n$.
        %
\end{problem}

\begin{problem}
        %
Докажите, что если какое\д то равенство (содержащее переменные для
множеств и операции $\cap$, $\cup$, $\setminus$) неверно, то можно
найти контрпример к нему, в котором множества пусты или состоят
из одного элемента.
        %
\end{problem}

\begin{problem}
        %
Сколько различных выражений для множеств можно составить из
переменных~$A$ и~$B$ с помощью (многократно используемых)
операций пересечения, объединения и разности? (Два выражения
считаются одинаковыми, если они равны при любых значениях
переменных.) Тот же вопрос для трёх множеств и для $n$~множеств.
(Ответ в общем случае: $2^{2^n-1}$.)
        %
\end{problem}

\begin{problem}
        %
Тот же вопрос, если используются только операции~$\cup$ и~$\cap$.
(Для двух и трёх переменных это число несложно подсчитать,
% ---------------------------- страница 9 ----------------------------------
но общей формулы для $n$~переменных не известно.  Эту
задачу называют также задачей о
числе монотонных булевых функций\index{Монотонные булевы функции}
от $n$~аргументов.)
        %
\end{problem}

\begin{problem}
        %
Сколько существует подмножеств у $n$\д элементного множества?
        %
\end{problem}

\begin{problem}
        %
Пусть множество $A$ содержит~$n$ элементов, а его
подмножество~$B$ содержит~$k$ элементов. Сколько существует
множеств~$C$, для которых $B\hm\subset C\hm\subset A$?
        %
\end{problem}

\begin{problem}
        \label{noncomparable-subsets}%
Множество~$U$ содержит $2n$~элементов. В нём выделено $k$~подмножеств,
причём ни одно из них не является подмножеством
другого. Каково может быть максимальное значение числа~$k$?
(Указание. Максимум достигается, когда все подмножества имеют
по~$n$ элементов. В самом деле, представим себе, что мы начинаем
с пустого множества и добавляем по одному элементу, пока не получится
множество~$U$. В ходе такого процесса может появиться не
более одного выделенного множества; с другой стороны, можно
подсчитать математическое ожидание числа выделенных множеств по
линейности; вероятность пройти через данное множество
$Z\hm\subset U$ минимальна, когда $Z$~содержит $n$~элементов,
поскольку все множества данного размера равновероятны.)
        %
\end{problem}

\section{Число элементов}
        \label{number-of-elements}

Число элементов в конечном
множестве~$A$ называют также его
\emph{мощностью}\index{Мощности}\index{Множества!мощность}
и обозначают~$|A|$ (а также~$\#A$). (Вскоре мы
будем говорить о мощностях и для бесконечных множеств.)
Следующая формула позволяет найти мощность объединения
нескольких множеств, если известны мощности каждого из них, а
также мощности всех пересечений.
        %
\begin{theorem}[Формула включений и исключений]%
\index{Формула включений и исключений}
        %
\begin{align*}
    |A\cup B|        & =|A|+|B|-|A\cap B|;\\
    |A\cup B \cup C| & =|A|+|B|+|C|-\\
                     &{}-|A\cap B|-|A\cap C|-|B\cap C|+\\
                     &{}+|A\cap B\cap C|;
\end{align*}
% ---------------------------- страница 10 ----------------------------------
вообще $|A_1\cup\ldots\cup A_n|$ равно
        $$
      \sum_{i}|A_i| - \sum_{i<j}|A_i \cap A_j| +
      \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \ldots
        $$
\end{theorem}

\begin{proof}
        %
Это утверждение несложно доказать индукцией по~$n$, но мы
приведём другое доказательство. Фиксируем произвольное
множество~$U$, подмножествами которого являются множества
$A_1, \dots, A_n$.
        %

\emph{Характеристической функцией}\index{Характеристическая функ\-ция множества}
множества $X\hm\subset U$
называют функцию~$\highchi_X$, которая равна~$1$ на элементах~$X$
и~$0$ на остальных элементах~$U$. Операции над подмножествами
множества~$U$ соответствуют операциям с их характеристическими
функциями. В частности, пересечению множеств соответствует
произведение характеристических функций:
$\highchi_{A\cap B}(u)\hm=\highchi_{A}(u)\highchi_{B}(u)$. Дополнению (до~$U$)
соответствует функция $1-\highchi$, если $\highchi$\т
характеристическая функция исходного множества.

Число элементов множества можно записать как сумму значений его
характеристической функции:
        $$
|X|=\sum_{u} \highchi_{X}(u).
        $$
Объединение $A_1\cup\ldots\cup A_N$ можно записать как
дополнение к пересечению дополнений множеств $A_i$;
в терминах характеристических функций имеем
        $$
\highchi_{A_1\cup\ldots\cup A_n}=
1 - (1-\highchi_{A_1})\ldots (1-\highchi_{A_n}).
        $$
Раскрыв скобки в правой части, мы получим
        $$
\sum_{i}\highchi_{A_i}-\sum_{i<j}\highchi_{A_i}\highchi_{A_j}+
\sum_{i<j<k}\highchi_{A_i}\highchi_{A_j}\highchi_{A_k}-\ldots
        $$
и просуммировав левую и правую часть
по всем элементам $U$ (обе они есть функции на~$U$),
получим формулу включений и исключений.
        %
\end{proof}

\begin{problem}
        %
Докажите, что
   $|A_1\bigtriangleup\ldots\bigtriangleup A_n|$ равно
        $$
      \sum_{i}|A_i| - 2\sum_{i<j}|A_i \cap A_j| +
      4\sum_{i<j<k} |A_i \cap A_j \cap A_k| - \ldots
        $$
% ---------------------------- страница 11 ----------------------------------
(коэффициенты\т последовательные степени двойки).
        %
\end{problem}

Подсчёт количеств элементов в конечных множествах относят
к \emph{комбинаторике}\index{Комбинаторика}. Некоторые начальные сведения из
комбинаторики приведены дальше в качестве задач. Сейчас
нас в первую очередь интересует следующий принцип:

\quot{%
        %
если между двумя множествами можно установить взаимно
однозначное соответствие, то в них одинаковое число элементов.
        }

\noindent
(Взаимная однозначность требует, чтобы каждому элементу
первого множества соответствовал ровно один элемент второго
и наоборот.)

Вот несколько примеров использования этого принципа.

\begin{problem}
        %
На окружности выбраны 1000 белых точек и одна чёрная.
Чего больше\т треугольников с вершинами в белых точках
или четырёхугольников, у которых одна вершина чёрная,
а остальные три белые? (Решение: их поровну, поскольку
каждому четырёхугольнику соответствует треугольник,
образованный тремя его белыми вершинами.)
        %
\end{problem}

\begin{problem}
        %
Каких подмножеств больше у $100$\д элементного множества:
мощности~$57$ или мощности~$43$? (Указание: $57\hm+43\hm=100$.)
        %
\end{problem}

\begin{problem}
        %
Докажите, что последовательностей длины~$n$, составленных из
нулей и единиц, столько же, сколько подмножеств у множества
$\{1,2,\dots,n\}$. (Указание: каждому подмножеству
$X\hm\subset\{1,2,\dots,n\}$ соответствует \лк характеристическая
последовательность\пк, на $i$\д м месте которой стоит единица,
если и только если
$i\hm\in X$.)
        %
\end{problem}

\begin{problem}
        %
Докажите, что последовательностей нулей и единиц длины $n$,
в которых число единиц равно~$k$, равно числу $k$\д элементных
подмножеств $n$\д элементного множества.
        %
\end{problem}

\problskip

Это число называется \emph{числом сочетаний из $n$ по $k$}%
\index{Число сочетаний} и
обозначается~$C_n^k$\index{$C_n^k$} в русских книжках; в иностранных обычно
используется обозначение $\binom{n}{k}$\index{$\binom{n}{k}$}.

\problskip

\begin{problem}
        %
Докажите, что $C_n^k\hm=C_n^{n-k}$.
        %
\end{problem}

\begin{problem}
        %
Докажите, что $C_n^0\hm+C_n^1\hm+\ldots\hm+C_n^n\hm=2^n$.
        %
\end{problem}

% ---------------------------- страница 12 ----------------------------------
\begin{problem}
        %
Пусть $U$\т непустое конечное множество. Докажите, что
подмножеств множества~$U$, имеющих чётную мощность, столько же,
сколько имеющих нечётную мощность. (Указание: фиксируем
элемент~$u\hm\in U$ и объединим в пары подмножества, отличающиеся только
в точке~$u$.)
        %
\end{problem}

\begin{problem}
        %
Докажите, что $C_n^0\hm-C_n^1\hm+C_n^2\hm-\ldots\hm+(-1)^nC_n^n\hm=0$.
(Указание: как это связано с предыдущей задачей?)
        %
\end{problem}

\begin{problem}
        %
        \glossary{Ньютон@\Ньютон}%
Докажите формулу \emph{бинома Ньютона}\index{Бином Ньютона}:
        $$
(a+b)^n= C_n^0 a^n + C_n^1 a^{n-1}b +
    \ldots+C_n^k a^{n-k}b^{k}+\ldots+C_n^n b^n.
        $$
\end{problem}

\begin{problem}
        %
Докажите, что способов расстановки скобок (указывающих порядок
действий) в неассоциативном произведении из~$n$ элементов
столько же, сколько способов разбить выпуклый
$(n+1)$\д угольник на треугольники непересекающимися диагоналями.
(Для произведения трёх множителей есть два варианта $(ab)c$ и
$a(bc)$; с другой стороны, есть два способа разрезать
четырёхугольник на два треугольника, проведя диагональ. Для
произведения четырёх сомножителей и для пятиугольника имеется по
$5$~вариантов.)
        %
\end{problem}

\section{Равномощные множества}
        \label{same-cardinality}

Два множества называют \emph{равномощными}\index{Множества!равномощные}%
\index{Равномощность множеств}, если между ними
можно установить взаимно однозначное соответствие, при котором
каждому элементу одного множества соответствует ровно один элемент
другого.

Для конечных множеств это означает, что в них одинаковое число
элементов, но определение имеет смысл и для бесконечных
множеств. Например, отрезки~$[0,1]$ и~$[0,2]$ равномощны,
поскольку отображение~$x\hm\mapsto 2x$ осуществляет искомое соответствие.

\begin{problem}
        %
Докажите, что любые два интервала~$(a,b)$ и~$(c,d)$
на прямой равномощны.
        %
\end{problem}

\begin{problem}
        %
Докажите, что любые две окружности на плоскости равномощны.
Докажите, что любые два круга на плоскости равномощны.
        %
\end{problem}

\begin{problem}
        %
Докажите, что полуинтервал~$[0,1)$ равномощен полуинтервалу~$(0,1]$.
        %
\end{problem}

Несколько более сложна такая задача: доказать, что интервал
$(0,1)$ и луч $(0,+\infty)$ равномощны. Это делается
% ---------------------------- страница 13 ----------------------------------
так. Заметим,
что отображение $x\hm\mapsto 1/x$ является взаимно однозначным соответствием
между $(0,1)$ и $(1,+\infty)$, а $x\hm\mapsto (x-1)$\т
взаимно однозначным соответствием между $(1,+\infty)$ и
$(0,+\infty)$, поэтому их композиция $x\hm\mapsto (1/x)-1$
является искомым взаимно однозначным соответствием между~$(0,1)$
и~$(0,+\infty)$.

Вообще, как говорят, отношение равномощности есть
\emph{отношение эквивалентности}\index{Отношение!эквивалентности}. Это
означает, что оно \emph{рефлексивно}\index{Рефлексивность}
(каждое множество равномощно самому себе),
\emph{симметрично}\index{Симметричность}
(если $A$~равномощно~$B$, то и $B$ равномощно~$A$)
и \emph{транзитивно}\index{Транзитивность} (если $A$~равномощно~$B$ и
$B$~равномощно~$C$, то $A$~равномощно~$C$). Свойством
транзитивности мы только что воспользовались, взяв луч~$(1,+\infty)$
в качестве промежуточного множества.

\medskip
Ещё несколько примеров:
\begin{itemize}
        %
\item
Множество бесконечных последовательностей нулей и единиц
равномощно множеству всех подмножеств натурального
ряда. (В самом деле, сопоставим с каждой последовательностью
множество номеров мест, на которых стоят единицы: например,
последовательность из одних нулей соответствует пустому
множеству, из одних единиц\т натуральному ряду, а
последовательность $10101010\dots$\т множеству чётных чисел.)
        %
\item
Множество бесконечных последовательностей цифр $0$, $1$, $2$, $3$
равномощно множеству бесконечных последовательностей цифр
$0$ и~$1$. (В самом деле, можно закодировать цифры $0$, $1$, $2$, $3$
группами $00$, $01$, $10$, $11$. Обратное преобразование
разбивает последовательность нулей и единиц на пары,
после чего каждая пара заменяется на цифру от~$0$ до~$3$.)
        %
\item
      \label{01-012}%
Множество бесконечных последовательностей цифр $0$, $1$, $2$
равномощно множеству бесконечных последовательностей цифр $0$ и~$1$.
(Можно было бы пытаться рассуждать так: это множество заключено
между двумя множествами одной и той же мощности, и потому
равномощно каждому из них. Этот ход мыслей
% ---------------------------- страница 14 ----------------------------------
правилен, как показывает теорема Кантора\ч Бернштейна из
раздела~\ref{cantor-bernstein}.
Но здесь можно обойтись и без этой теоремы, если
закодировать цифры $0$, $1$ и $2$ последовательностями $0$, $10$
и $11$: легко сообразить, что всякая последовательность нулей и
единиц однозначно разбивается на такие блоки слева направо.
Такой способ кодирования называют \лк префиксным кодом\пк%
\index{Префиксный код}.)

\item
Пример с последовательностями нулей и единиц можно обобщить:
множество подмножеств любого множества~$U$ (оно обычно
обозначается~$P(U)$\index{$P(U)$} и по\д
английски называется power set) равномощно
множеству всех функций, которые ставят в соответствие каждому
элементу ${x\in U}$ одно из чисел $0$ и~$1$ (множество таких
функций обычно обозначают~$2^X$\index{$2^X$}). (В самом деле, каждому
множеству $X\hm\subset U$ соответствует его характеристическая
функция.)

\end{itemize}

Мы продолжим этот список, но сначала полезно доказать несколько
простых фактов о счётных множествах (равномощных множеству
натуральных чисел).

\section{Счётные множества}
        \label{countable-sets}

Множество называется \emph{счётным}\index{Множества!счётные}%
\index{Счётное множество}, если оно равномощно
множеству~$\bbN$\index{$\bbN$} натуральных чисел\index{Числа!натуральные},
то есть если его можно
представить в виде $\{x_0,x_1,x_2,\dots\}$ (здесь~$x_i$\т
элемент, соответствующий числу~$i$; соответствие взаимно
однозначно, так что все~$x_i$ различны).

Например, множество целых чисел~$\mathbb{Z}$ счётно, так как
целые числа можно расположить в последовательность
$0,1,-1,2,-2, 3, -3, \dots$

\begin{theorem}
        \label{countable-sets-properties}
(\textsf{а})~Подмножество счётного множества конечно или счётно.

(\textsf{б})~Всякое бесконечное множество содержит счётное
        подмножество.

(\textsf{в})~Объединение конечного или счётного числа конечных
        или счётных множеств конечно или счётно.
        %
\end{theorem}

% ---------------------------- страница 15 ----------------------------------
\begin{proof}
        %
(а)~Пусть $B$\т подмножество счётного множества
$A\hm=\{a_0,a_1,a_2,\dots\}$. Выбросим из последовательности
$a_0, a_1, \dots$ те члены, которые не принадлежат~$B$ (сохраняя
порядок оставшихся). Тогда оставшиеся члены образуют либо
конечную последовательность (и тогда $B$~конечно), либо
бесконечную (и тогда $B$~счётно).

(б)~Пусть~$A$ бесконечно. Тогда оно непусто и
содержит некоторый
элемент~$b_0$. Будучи бесконечным, множество~$A$ не исчерпывается
элементом~$b_0$\т возьмём какой\д нибудь другой элемент~$b_1$, \итд
Получится последовательность $b_0, b_1, \dots$;
построение не прервётся ни на каком шаге, поскольку $A$~бесконечно.
Теперь множество
$B\hm=\{b_0,b_1,\dots\}$ и будет искомым счётным
подмножеством. (Заметим, что~$B$ вовсе не обязано совпадать
с~$A$, даже если $A$~счётно.)

(в)~Пусть имеется счётное число счётных множеств
$A_1, A_2, \dots$ Расположив элементы каждого из них слева направо в
последовательность ($A_i\hm=\{a_{i0},a_{i1},\dots\}$) и
поместив эти последовательности друг под другом, получим
таблицу
        $$
        \begin{array}{ccccc}
   a_{00} & a_{01} & a_{02} & a_{03} & \ldots \\
   a_{10} & a_{11} & a_{12} & a_{13} & \ldots \\
   a_{20} & a_{21} & a_{22} & a_{23} & \ldots \\
   a_{30} & a_{31} & a_{32} & a_{33} & \ldots \\
   \ldots & \ldots & \ldots & \ldots & \ldots
        \end{array}
        $$
Теперь эту таблицу можно развернуть в последовательность,
например, проходя по очереди диагонали:
    $$
        a_{00},\ a_{01}, a_{10}, \
        a_{02}, a_{11}, a_{20}, \
        a_{03}, a_{12}, a_{21}, a_{30}, \ldots
    $$
Если множества~$A_i$ не пересекались, то мы получили искомое
представление для их объединения. Если пересекались, то из
построенной последовательности надо выбросить повторения.

Если множеств конечное число или какие\д то из множеств конечны,
то в этой конструкции части членов не будет\т и
останется либо конечное, либо счётное множество.
        %
\end{proof}

% ---------------------------- страница 16 ----------------------------------
\begin{problem}
        %
Описанный
проход по диагоналям задаёт взаимно
однозначное соответствие между множеством всех пар натуральных
чисел (которое обозначается $\bbN\times\bbN$) и $\bbN$.
Любопытно, что это соответствие
задаётся простой формулой
(многочленом второй степени с рациональными коэффициентами).
Укажите этот многочлен.
        %
\end{problem}

\label{axiom-of-choice}%
\textsf{Замечание.}~В доказательстве утверждения~(б)
теоремы~\ref{countable-sets-properties}
есть тонкий момент: на
каждом шаге мы должны выбрать один из оставшихся элементов
множества~$A$; такие элементы есть, но у нас нет никакого
правила, позволяющего такой выбор описать. При более формальном
построении теории множеств тут нужно сослаться на специальную
аксиому, называемую \emph{аксиомой выбора}\index{Аксиома!выбора}.
Законность этой
аксиомы вызывала большие споры в начале 20\д го века, но
постепенно к ней привыкли, и эти споры сейчас почти не
воспринимаются. В середине века великий логик Курт
Гёдель\glossary{Гёдель@\Гёдель} доказал, что аксиому выбора
нельзя опровергнуть, пользуясь остальными аксиомами теории
множеств, а в 1960\д е годы американский математик
Пол~Дж.\,Коэн\glossary{Коэн@\Коэн} доказал, что её нельзя и вывести
из остальных аксиом. (Конечно, понимание этих утверждений
требует подробного изложения теории множеств как аксиоматической
теории.)

\begin{problem}
        %
Такой же тонкий момент (хотя и менее очевидный) есть и в
доказательстве утверждения~(в). Можете ли вы догадаться,
где он? (Ответ: мы знаем, что множества~$A_i$ счётны,
то есть что \textsl{существует} взаимно однозначное
соответствие между~$\bbN$ и~$A_i$. Но нужно
выбрать и фиксировать эти соответствия, прежде чем
удастся построить соответствие между объединением всех~$A_i$
и~$\bbN$.)
        %
\end{problem}

\medskip
Ещё несколько примеров счётных множеств:
        %
\begin{itemize}
        %
\item
Множество~$\bbQ$\index{$\bbQ$} рациональных чисел\index{Числа!рациональные}
счётно. В самом деле,
рациональные числа представляются несократимыми дробями с целым
числителем и знаменателем. Множество дробей с данным знаменателем
счётно, поэтому $\bbQ$~представимо в виде
объединения счётного числа счётных множеств. Забегая вперёд
(см.~раздел~\ref{cantor}), отметим, что множество $\bbR$\index{$\bbR$} всех
действительных чисел\index{Числа!действительные} несчётно.
        %
% ---------------------------- страница 17 ----------------------------------
\item
Множество~$\bbN^k$\index{$\bbN^k$}, элементами которого являются наборы
из~$k$ натуральных чисел, счётно. Это легко доказать индукцией
по $k$. При $k\hm=2$ множество
$\bbN^2\hm=\bbN\hm\times\bbN$ пар натуральных
чисел разбивается на счётное число счётных множеств
$\{0\}\hm\times\bbN, \{1\}\hm\times\bbN, \dots$
(элементами $i$\д го множества будут пары, первый член которых равен~$i$).
Поэтому $\bbN^2$~счётно. Аналогичным образом множество~$\bbN^3$
троек натуральных чисел разбивается на счётное
число множеств~$\{i\}\hm\times\bbN\hm\times\bbN$.
Каждое из них состоит из троек, первый член которых фиксирован и
потому равномощно множеству~$\bbN^2$, которое счётно.
Точно так же можно перейти от счётности множества~$\bbN^k$
к счётности множества~$\bbN^{k+1}$.
        %
\item
Множество всех конечных последовательностей натуральных чисел
счётно. В самом деле, множество всех последовательностей
данной длины счётно (как мы только что видели), так что
интересующее нас множество разбивается на счётное число
счётных множеств.
        %
\item
В предыдущем примере не обязательно говорить о натуральных числах\т можно
взять любое счётное (или конечное) множество. Например, множество
всех текстов, использующих русский алфавит (такой текст можно считать
конечной последовательностью букв, пробелов, знаков препинания \итп),
счётно; то же самое можно сказать о множестве (всех мыслимых)
компьютерных программ \итд
        %
\item
Число называют \emph{алгебраическим}\index{Числа!алгебраические}, если оно является корнем
ненулевого многочлена с целыми коэффициентами. Множество
алгебраических чисел счётно, так как многочленов счётное число
(многочлен задаётся конечной последовательностью целых чисел\т
его коэффициентов), а каждый многочлен имеет конечное число
корней (не более~$n$ для многочленов степени~$n$).
        %
% ---------------------------- страница 18 ----------------------------------
\item
Множество периодических дробей\index{Периодическая дробь} счётно.
В самом деле, такая дробь
может быть записана как конечная последовательность символов из
конечного множества (запятая, цифры, скобки); например,
дробь $0{,}16666{\dots}$ можно записать как
$0{,}1(6)$. А таких последовательностей счётное множество.
        %
\end{itemize}

\begin{problem}
        %
Докажите, что любое семейство непересекающихся интервалов
на прямой конечно или счётно. (Указание: в каждом интервале
найдётся рациональная точка.)
        %
\end{problem}

\begin{problem}
        %
(\textbf{а})~%
        %
Докажите, что любое множество непересекающихся восьмёрок на
плоскости конечно или счётно. (Восьмёрка\т объединение двух
касающихся окружностей любых размеров.)
         %
(\textbf{б})~%
         %
Сформулируйте и докажите аналогичное утверждение для букв
\лк\textsf{Т}\пк.
        %
\end{problem}

\begin{problem}
        %
Докажите, что множество точек строгого локального максимума любой
функции действительного аргумента конечно или счётно.
        %
\end{problem}

\begin{problem}
        %
Докажите, что множество точек разрыва неубывающей функции
действительного аргумента конечно или счётно.
        %
\end{problem}

\problskip
\begin{theorem}\label{countable-add}
        %
Если множество~$A$ бесконечно, а множество~$B$ конечно или счётно,
то объединение~$A\hm\cup B$ равномощно~$A$.
        %
\end{theorem}

\begin{proof}
        %
Можно считать, что $B$~не пересекается с~$A$ (пересечение можно
выбросить из~$B$, останется по\д прежнему конечное или счётное
множество).

Выделим в~$A$ счётное подмножество~$P$; остаток обозначим через~$Q$.
Тогда нам надо доказать, что $B\hm+P\hm+Q$~равномощно~$P\hm+Q$
(знак $+$ символизирует объединение непересекающихся множеств).
Поскольку~$B\hm+P$ и~$P$ оба счётны, между ними существует
взаимно однозначное соответствие. Его легко продолжить до
соответствия между~$B\hm+P\hm+Q$ и~$P\hm+Q$ (каждый элемент
множества~$Q$ соответствует сам себе).
        %
\end{proof}

\begin{problem}
        %
Примените эту конструкцию и явно укажите соответствие между
отрезком~$[0,1]$ и полуинтервалом~$[0,1)$.
        %
\end{problem}

\begin{problem}
        %
Теорема~\ref{countable-add} показывает, что добавление
счётного множества\index{Добавление счётного множества}
к бесконечному не меняет его
мощности. Можно ли сказать то же самое про удаление?
Докажите, что если $A$~бесконечно и не является счётным,
а $B$~конечно или счётно, то
% ---------------------------- страница 19 ----------------------------------
$A\setminus B$~равномощно~$B$.
        %
\end{problem}

\begin{problem}
        %
Немецкий математик Р.\,Дедекинд\glossary{Дедекинд@\Дедекинд} предложил такое
определение бесконечного множества: множество бесконечно, если
оно равномощно некоторому своему подмножеству, не совпадающему
со всем множеством. Покажите, что указанное Дедекиндом свойство
действительно определяет бесконечные множества.
        %
\end{problem}

Добавляя конечные или счётные множества, легко понять, что
прямая, все промежутки на прямой (отрезки, интервалы,
полуинтервалы), лучи, их конечные или счётные объединения \итп
равномощны друг другу.

\smallskip

\begin{problem}
        %
Укажите взаимно однозначное соответствие между
множеством $[0,1]\hm\cup[2,3]\hm\cup[4,5]\cup\ldots$ и
отрезком~$[0,1]$.
        %
\end{problem}

\begin{problem}
        %
Докажите, что множество всех прямых на плоскости
равномощно множеству всех точек на плоскости. (Указание:
и точки, и прямые задаются парами чисел\т за небольшими
исключениями.)
        %
\end{problem}

\begin{problem}
        %
Докажите, что полуплоскость (точки плоскости, лежащие по
одну сторону от некоторой прямой) равномощна плоскости.
(Это верно независимо от того, включаем мы граничную
прямую в полуплоскость или нет.)
        %
\end{problem}

\begin{theorem}
        \label{continuum-sequences}
        %
Отрезок~$[0,1]$ равномощен множеству всех
бесконечных последовательностей нулей и единиц.
        %
\end{theorem}

\begin{proof}
        %
В самом деле, каждое число~$x\hm\in[0,1]$ записывается
в виде бесконечной двоичной дроби. Первый знак этой дроби
равен~$0$ или~$1$ в зависимости от того, попадает ли
число~$x$ в левую или правую половину отрезка. Чтобы
определить следующий знак, надо выбранную половину
поделить снова пополам и посмотреть, куда попадёт~$x$,~\итд

Это же соответствие можно описать в другую сторону:
последовательности $x_0x_1x_2\dots$ соответствует число,
являющееся суммой ряда
        $$
\frac{x_0}{2} + \frac{x_1}{4} + \frac{x_2}{8} + \ldots
        $$
(В этом построении мы используем некоторые факты
из математического анализа, что не удивительно\т
нас интересуют свойства действительных чисел.)

% ---------------------------- страница 20 ----------------------------------
Описанное соответствие пока что не совсем взаимно однозначно:
двоично\д рациональные числа (дроби вида~$m/2^n$) имеют два
представления. Например, число $3/8$ можно записать как в виде
$0{,}011000{\dots}$, так и в виде $0{,}010111{\dots}$
Соответствие станет
взаимно однозначным, если отбросить дроби с единицей в периоде. Но
таких дробей счётное число, поэтому на мощность это не повлияет.
        %
\end{proof}

\begin{problem}
        %
Какая двоичная дробь соответствует числу~$1/3$?
        %
\end{problem}

В этом доказательстве можно было бы использовать более привычные
десятичные дроби вместо двоичных. Получилось бы, что отрезок~$[0,1]$
равномощен множеству всех бесконечных
последовательностей цифр $0,1,\dots,9$. Чтобы перейти отсюда к
последовательностям нулей и единиц, можно воспользоваться приёмом,
описанным на~с.~\pageref{01-012}.

Теперь всё готово для доказательства такого удивительного факта:

\begin{theorem}
        \label{square-and-segment}
        %
    Квадрат (со внутренностью) равномощен отрезку.
        %
\end{theorem}

\begin{proof}
        %
Квадрат равномощен множеству $[0,1]\hm\times [0,1]$ пар
действительных чисел, каждое из которых лежит на отрезке $[0,1]$
(метод координат). Мы уже знаем, что вместо чисел на отрезке
можно говорить о последовательностях нулей и единиц. Осталось
заметить, что паре последовательностей нулей и единиц
$\langle x_0x_1x_2\ldots, y_0y_1y_2\ldots\rangle$
можно поставить в соответствие последовательность\д смесь
$x_0y_0x_1y_1x_2y_2\ldots$ и что это соответствие будет
взаимно однозначным.
        %
\end{proof}

\begin{historyremark}
        %
Этот результат был получен в 1877 году немецким математиком
Георгом К\'антором\glossary{Кантор@\Кантор} и удивил его самого, поскольку
противоречил интуитивному ощущению \лк размерности\пк\ (квадрат
двумерен, поэтому вроде бы должен содержать больше точек, чем
одномерный отрезок). Вот что Кантор писал
Дедекинду\glossary{Дедекинд@\Дедекинд} (20 июня
1877 года), обсуждая вопрос о равномощности пространств разного
числа измерений: \лк Как мне кажется, на этот вопрос следует
ответить утвердительно, хотя на протяжении ряда лет я
придерживался противоположного мнения\пк.

В одном из ответных писем Дедекинд отмечает, что результат
% ---------------------------- страница 21 ----------------------------------
Кантора не лишает смысла понятие размерности, поскольку можно
рассматривать лишь непрерывные в обе стороны соответствия, и
тогда пространства разной размерности можно будет различить. Эта
гипотеза оказалось верной, хотя не такой простой; первые попытки
её доказать, в том числе одна из статей Кантора, содержали
ошибки, и только спустя тридцать лет голландский математик
Л.\,Брауэр\glossary{Брауэр@\Брауэр} дал правильное доказательство. Впрочем,
отсутствие непрерывного в обе стороны соответствия между
отрезком и квадратом доказать несложно; трудности начинаются в
б\'ольших размерностях. (Заметим также, что существует непрерывное
отображение отрезка в квадрат, которое проходит через любую
точку квадрата. Оно называется \лк кривой
Пеано\пк\glossary{Пеано@\Пеано}\index{Кривая Пеано}.)
        %
\end{historyremark}

Из теоремы~\ref{square-and-segment}
легко получить много других утверждений
про равномощность геометрических объектов: круг равномощен
окружности, прямая равномощна плоскости \итп

Можно также заметить, что пространство (точки которого задаются
тремя координатами $\langle x,y,z\rangle$) равномощно плоскости (надо
закодировать пару $\langle x,y\rangle$ одним числом), и, следовательно,
прямой. То же самое можно проделать и для
пространств большей размерности.

\begin{problem}
        %
Докажите, что множество всех конечных последовательностей
действительных чисел равномощно $\bbR$\index{$\bbR$} (множеству всех
действительных чисел\index{Числа!действительные}).
        %
\end{problem}

\begin{problem}
        %
Докажите, что множество всех бесконечных последовательностей
действительных чисел равномощно~$\bbR$.
        %
\end{problem}

Отметим, что мы пока не умеем доказывать, что множество
действительных чисел (или множество бесконечных последовательностей
нулей и единиц) несчётно. Это будет сделано в
разделе~\ref{cantor}.

Мощность множества действительных чисел называют \emph{мощностью
континуума}\index{Континуум}
(от латинского слова, означающего \лк непрерывный\пк;
имеется в виду, что точка на отрезке может непрерывно
двигаться от одного конца к другому).

% ---------------------------- страница 22 ----------------------------------
\section{Теорема Кантора\ч Бернштейна}
        \label{cantor-bernstein}
        \glossary{Кантор@\Кантор}%
        \glossary{Бернштейн@\Бернштейн}%
        \index{Теорема!Кантора\Ч Шрёдера\Ч Бернштейна}%

Определение равномощности уточняет интуитивную идею о множествах
\лк одинакового размера\пк. А как формально определить, когда
одно множество \лк больше\пк\ другого?

\label{card-inequality-def}%
Говорят, что множество~$A$ \emph{по мощности не больше}%
\index{Мощности!сравнение}
множества~$B$, если оно равномощно некоторому подмножеству
множества~$B$ (возможно, самому~$B$).

\begin{problem}
        %
Некто предложил такое определение: множество~$A$ имеет строго
меньшую мощность, чем множество~$B$, если оно равномощно
некоторой части множества~$B$, не совпадающей со всем~$B$.
Почему это определение неудачно?
(Указание. Популярные рассказы о теории множеств часто начинаются с такого
парадокса, восходящего к Галилею\glossary{Галилей@\Галилей}.
Каких чисел больше\т всех натуральных чисел или точных квадратов? С~одной
стороны, точные квадраты составляют лишь небольшую часть
натуральных чисел; с другой стороны их можно поставить во
взаимно однозначное соответствие со всеми натуральными числами.)
        %
\end{problem}

Отношение \лк иметь не большую мощность\пк\ обладает многими
естественными свойствами:
        %
\begin{itemize}
        %
\item
Если $A$ и~$B$ равномощны, то $A$~имеет не большую мощность,
чем~$B$. (Очевидно.)
        %
\item
Если $A$~имеет не большую мощность, чем~$B$, а $B$~имеет не большую
мощность, чем~$C$, то $A$~имеет не большую мощность, чем~$C$.
(Тоже несложно. Пусть $A$~находится во взаимно однозначном
соответствии с $B'\hm\subset B$, а $B$~находится во взаимно однозначном
соответствии с $C'\hm\subset C$. Тогда при втором соответствии
$B'$~соответствует некоторому множеству $C''\hm\subset C'\hm\subset C$,
как показано на рис.~\ref{cb-0}, и потому $A$~равномощно~$C''$.)
        %
\begin{figure}[ht]
        $$
\epsffile{cb0.1}
        $$
\caption{Транзитивность сравнения мощностей}
\label{cb-0}
        %
\end{figure}
        %
\item
Если $A$~имеет не большую мощность, чем~$B$, а $B$~имеет не большую
мощность, чем~$A$, то они равномощны. (Это вовсе не очевидное
утверждение составляет содержание теоремы Кантора\ч Бернштейна,
которую мы сейчас докажем.)
        %
% ---------------------------- страница 23 ----------------------------------
\item
Для любых двух множеств~$A$ и~$B$ верно (хотя бы) одно из двух:
либо $A$~имеет не большую мощность, чем~$B$, либо $B$~имеет не
большую мощность, чем~$A$. (Доказательство этого факта требует
так называемой \лк трансфинитной индукции\пк; см.~раздел~\ref{zermelo},
теорема~\ref{zermelo-cardinals-comparing}.)
        %
\end{itemize}

\begin{theorem}[Кантора\ч Бернштейна]
        %
Если множество~$A$ равномощно некоторому подмножеству
множества~$B$, а $B$~равномощно некоторому подмножеству
мно\-жест\-ва~$A$, то множества~$A$ и~$B$ равномощны.
        %
\end{theorem}

\begin{proof}
        %
Пусть $A$~равномощно подмножеству~$B_1$ множества~$B$, а
$B$~равномощно подмножеству~$A_1$ множества~$A$ (см.~рис.~\ref{cb-1}).
        %
\begin{figure}[ht]
        $$
\epsffile{cb1.1}
        $$
\caption{}
\label{cb-1}
\end{figure}
        %
При
взаимно однозначном соответствии между~$B$ и~$A_1$
подмножество $B_1\hm\subset B$ переходит в некоторое
подмножество $A_2\hm\subset A_1$. При этом все три множества
$A$, $B_1$ и~$A_2$ равномощны,\т и нужно доказать, что они
равномощны множеству~$B$, или, что то же самое,~$A_1$.

Теперь мы можем забыть про множество~$B$ и его подмножества
и доказывать такой факт:
        \quot{
            %
если $A_2 \hm\subset A_1\hm\subset A_0$ и $A_2$~равномощно~$A_0$,
то все три множества равномощны.
           }
        %
% ---------------------------- страница 24 ----------------------------------
\noindent
(Для единообразия мы говорим~$A_0$ вместо~$A$.)

\begin{figure}[ht]
        $$
\epsffile{cb2.1}
        $$
\caption{}
\label{cb-2}
\end{figure}

Пусть~$f$\т функция, осуществляющая взаимно однозначное
соответствие $A_0\hm\to A_2$ (элемент~$x\hm\in A_0$
соответствует элементу~$f(x)\hm\in A_2$). Когда $A_0$~переходит
в~$A_2$, меньшее множество~$A_1$ переходит в какое\д то
множество $A_3\hm\subset A_2$ (см.~рис.~\ref{cb-2}). Аналогичным
образом само~$A_2$ переходит в некоторое
множество~$A_4\hm\subset A_2$. При этом $A_4\hm\subset A_3$, так
как $A_1\hm\subset A_2$.

Продолжая эту конструкцию, мы получаем убывающую
последовательность множеств
        $$
A_0 \supset A_1 \supset A_2 \supset A_3 \supset A_4 \supset\ldots
        $$
и взаимно однозначное соответствие $f\colon A_0\hm\to A_2$, при
котором $A_i$ соответствует~$A_{i+2}$ (иногда это записывают так:
$f(A_i)\hm=A_{i+2}$). Формально можно описать~$A_{2n}$ как
множество тех элементов, которые получаются из какого\д то
элемента множества~$A_0$ после $n$\д кратного применения
функции~$f$. Аналогичным образом $A_{2n+1}$~состоит из тех и
только тех элементов, которые получаются из какого\д то элемента
множества~$A_1$ после $n$\д кратного применения функции~$f$.

Заметим, что пересечение всех множеств~$A_i$ вполне может быть
непусто: оно состоит из тех элементов, у которых
% ---------------------------- страница 25 ----------------------------------
можно сколько угодно раз брать $f$\д прообраз. Теперь можно сказать так:
множество $A_0$ мы разбили на непересекающиеся слои
$C_i\hm=A_i\setminus A_{i+1}$ и на сердцевину $C\hm=\bigcap_{i}
A_i$.

Слои $C_0$, $C_2$, $C_4$, $\dots$ равномощны (функция $f$ осуществляет
взаимно однозначное соответствие между $C_0$ и~$C_2$, между
$C_2$ и~$C_4$ \итд):
        $$
  C_0 \stackrel{f}\longrightarrow C_2 \stackrel{f}\longrightarrow
  C_4 \stackrel{f}\longrightarrow \ldots
        $$
То же самое можно сказать про слои с нечётными номерами:
        $$
  C_1 \stackrel{f}\longrightarrow C_3 \stackrel{f}\longrightarrow
  C_5 \stackrel{f}\longrightarrow \ldots
        $$
% ---------------------------- страница 26 ----------------------------------
Можно ещё отметить (что, впрочем, не понадобится), что функция~$f$
на множестве~$C$ осуществляет его перестановку (взаимно однозначное
соответствие с самим собой\-).

Теперь легко понять, как построить взаимно однозначное
соответствие $g$ между $A_0$ и~$A_1$. Пусть $x\hm\in A_0$. Тогда
соответствующий ему элемент~$g(x)$ строится так: $g(x)\hm=f(x)$
при $x\hm\in C_{2k}$ и $g(x)\hm=x$ при $x\hm\in C_{2k+1}$ или
$x\hm\in C$ (см.~рис.~\ref{cb-3}).
        %
\end{proof}
\begin{figure}[ht]
        $$
\hspace*{4mm}\epsffile{cb3.1}
        $$
\vspace*{-5mm}
\caption{}
\label{cb-3}
\end{figure}

\begin{historyremark}
        %
История этой теоремы (называемой также теоремой Шрё\-де\-ра\ч
Бернштейна) такова.
Кантор формулирует её без доказательства в
        \glossary{Кантор@\Кантор}%
1883 году, обещая: \лк К этому я ещё вернусь в одной более
поздней работе и тогда выявлю своеобразный интерес этой общей
теоремы\пк. Однако этого обещания он не выполнил, и первые
доказательства были даны Шрёдером\glossary{Шрёдер@\Шрёдер} (1896) и
Бернштейном\glossary{Бернштейн@\Бернштейн} (1897).
Как видно из работ и писем Кантора, он предполагал доказывать
эту теорему одновременно с возможностью сравнить любые два
множества (см.~раздел~\ref{zermelo},
теорема~\ref{zermelo-cardinals-comparing}), но как именно\т
остаётся непонятным. (Работы Кантора по теории множеств и его
письма переведены на русский язык~\cite{cantor}; все цитаты
даются по этому изданию.)
        %
\end{historyremark}

Теорема Кантора\ч
Бернштейна значительно упрощает доказательства равномощности:
например, если мы хотим доказать, что бублик и шар в
пространстве равномощны, то достаточно заметить, что из бублика
можно вырезать маленький шар (гомотетичный большому), а из
шара\т маленький бублик.

% ---------------------------- страница 27 ----------------------------------
\begin{problem}
        %
Посмотрите на приведённые выше задачи, где требовалось
доказать равномощность, и убедитесь, что во многих из
них применение теоремы Кантора\ч Бернштейна сильно
упрощает дело.
        %
\end{problem}

\begin{problem}
        %
Докажите, что все геометрические фигуры, содержащие хотя бы
кусочек прямой или кривой, равномощны.
        %
\end{problem}

\begin{problem}\label{split-continuum-1}
        %
Докажите, что если квадрат разбит на два множества, то
хотя бы одно из них равномощно квадрату. (Указание.
Если одна из частей содержит отрезок, то можно воспользоваться
теоремой Кантора\ч Бернштейна. Если же, скажем, первая часть
не содержит отрезков, то в каждом горизонтальном сечении
квадрата есть точка второй части, и снова можно сослаться
на теорему Кантора\ч Бернштейна.)
        %
\end{problem}

\begin{problem}\label{split-continuum-2}
        %
Докажите, что если отрезок разбит на две части, то
хотя бы одна из них равномощна отрезку.
        %
\end{problem}

То же самое доказательство можно изложить более
абстрактно (и избавиться от упоминания натуральных
чисел). Напомним, что $f\colon A\hm\to A_2$ есть взаимно однозначное
соответствие между множеством~$A$ и его подмножеством~$A_2$,
а $A_1$\т некоторое промежуточное множество. Назовём
множество $X\hm\subset A$ \лк хорошим\пк, если оно содержит
$A\setminus A_1$ и замкнуто относительно~$f$, \те
        $$
X \supset (A\setminus A_1) + f(X)
        $$
(мы используем знак $+$ для объединения, поскольку объединяемые
множества заведомо не пересекаются). Легко проверить, что
пересечение любого семейства хороших множеств хорошее, поэтому
если мы пересечём все хорошие множества, то получим минимальное
по включению хорошее множество. Назовём его~$M$. Легко
проверить, что множество $(A\setminus A_1)+f(M)$ будет хорошим,
поэтому в силу минимальности $M$ включение в определении
хорошего множества превращается в равенство:
        $$
M = (A\setminus A_1) + f(M).
        $$
Теперь всё готово для построения биекции $g\colon A\hm\to A_1$.
Эта биекция совпадает с~$f$ внутри~$M$ и тождественна вне~$M$.

\begin{problem}
        %
Проведите это рассуждение подробно.
        %
\end{problem}

% ---------------------------- страница 28 ----------------------------------
Это рассуждение удобно при построении аксиоматической теории
множеств, так как в нём не нужны натуральные числа (которые
строятся далеко не сразу). Но по существу это то же самое
рассуждение, поскольку~$M$ есть $C_0\cup C_2\cup\dots$

Теперь, имея в виду теорему Кантора\ч Бернштейна, вернёмся к
вопросу о сравнении мощностей. Для данных множеств $A$ и~$B$
теоретически имеются четыре возможности:

\label{comparing-cardinalities}
\begin{itemize}
        %
\item
$A$~равномощно некоторой части~$B$, а $B$~равномощно некоторой
части~$A$. (В этом случае, как мы знаем, множества равномощны.)
        %
\item
$A$~равномощно некоторой части~$B$, но $B$~не равномощно никакой
части~$A$. В этом случае говорят, что $A$~\emph{имеет меньшую
мощность, чем}~$B$\index{Мощности!сравнение}.
        %
\item
$B$~равномощно некоторой части~$A$, но $A$~не равномощно никакой
части~$B$. В этом случае говорят, что $A$~\emph{имеет большую
мощность, чем}~$B$\index{Мощности!сравнение}.
        %
\item
Ни~$A$ не равномощно никакой части~$B$, ни~$B$ не равномощно
никакой части~$A$. Этот случай на самом деле невозможен, но мы
этого пока не знаем (см.~раздел~\ref{zermelo}).
        %
\end{itemize}

\begin{problem}
        %
Докажите, что счётное множество имеет меньшую мощность,
чем любое несчётное.
        %
\end{problem}

\begin{problem}
        %
Проверьте аккуратно, что если $A$~имеет меньшую мощность, чем~$B$,
а $B$~имеет меньшую мощность, чем~$C$, то $A$~имеет меньшую
мощность, чем~$C$ (транзитивность сравнения мощностей).
        %
\end{problem}

Заметим, что мы уже долго говорим о сравнении мощностей, но
воздерживаемся от упоминания \лк мощности множества\index{Мощности}%
\index{Множества!мощность}\пк\ как
самостоятельного объекта, а только сравниваем мощности разных
множеств. В принципе можно было бы определить мощность
множества~$A$ как класс всех множеств, равномощных~$A$. Такие
классы для множеств $A$ и~$B$ совпадают в том и только том случае,
% ---------------------------- страница 29 ----------------------------------
когда $A$ и~$B$ равномощны, так что слова \лк имеют
равную мощность\пк\ приобрели бы буквальный смысл. Проблема тут
в том, что таких множеств (равномощных множеству~$A$) слишком
много, поскольку всё на свете может быть их элементами. Их
насколько много, что образовать из них множество затруднительно,
это может привести к парадоксам (см.~раздел~\ref{cantor},
с.~\pageref{russell-paradox}).

Из этой ситуации есть несколько выходов. Самый простой\т по\д
прежнему говорить только о сравнении мощностей, но не о самих
мощностях. Можно также ввести понятие \лк класса\index{Класс}\пк\т такой
большой совокупности объектов, что её уже нельзя считать
элементом других совокупностей (\лк если вы понимаете, о чём я
тут толкую\пк\т добавила бы Сова из книжки о Винни\д Пухе), и считать
мощностью множества~$A$ класс всех множеств, равномощных~$A$.
Ещё один выход\т для каждого~$A$ выбрать некоторое \лк
стандартное\пк\ множество, равномощное~$A$, и назвать его
мощностью множества~$A$. Обычно в качестве стандартного
множества берут минимальный ординал, равномощный~$A$,\т но это
построение уже требует более формального (аксиоматического)
построения теории множеств.

\begin{historyremark}
        %
Кантор\glossary{Кантор@\Кантор} говорил о мощностях так (1895): \лк
\emph{Мощностью}\index{Мощности}\index{Множества!мощность}
или \emph{кардинальным числом}\index{Кардинальное число множества}
множества~$M$ мы называем то
общее понятие, которое получается при помощи нашей активной
мыслительной способности из~$M$, когда мы абстрагируемся от
качества его различных элементов~$m$ и от порядка их задания.
$\langle\,\dots\rangle$ Так как из каждого отдельного элемента
% ??????????
$m$, когда мы отвлекаемся от качества, получается некая
\glqq единица\grqq, то само кардинальное число оказывается
множеством, образованным исключительно из единиц, которое
существует как интеллектуальный образ или как проекция заданного
множества~$M$ в наш разум\пк.
        %
\end{historyremark}

Так или иначе, мы будем употреблять обозначение $|A|$\index{$|A|$} для
мощности множества~$A$ хотя бы как вольность речи: $|A|\hm=|B|$
означает, что множества $A$ и $B$ равномощны; $|A|\hm\le |B|$
означает, что $A$ равномощно некоторому подмножеству
множества~$B$, а $|A|\hm<|B|$ означает, что $A$~имеет
% ---------------------------- страница 30 ----------------------------------
меньшую мощность, чем~$B$ (см.~с.~\pageref{comparing-cardinalities}).

\section{Теорема Кантора}\index{Теорема!Кантора}
         \label{cantor}

Классический пример неравномощных бесконечных множеств (до сих
пор такого примера у нас не было!) даёт \лк диагональная
конструкция\index{Диагональная конструкция} Кантора\пк.

\begin{theorem}[Кантора]
        \label{continuum-diagonal}
Множество бесконечных последовательностей нулей и единиц
несчётно.
        %
\end{theorem}

\begin{proof}
        %
Предположим, что оно счётно. Тогда все последовательности нулей
и единиц можно перенумеровать: $\alpha_0,\alpha_1,\dots$
Составим бесконечную вниз таблицу, строками которой будут наши
последовательности:
        $$
\begin{array}{c}
\begin{array}{cccccc}
\alpha_0 & = & \underline{\alpha_{00}}&
            \alpha_{01} & \alpha_{02} & \ldots\\
\alpha_1 & = & \alpha_{10} & \underline{\alpha_{11}}& \alpha_{12} & \ldots\\
\alpha_2 & = & \alpha_{20} & \alpha_{21} & \underline{\alpha_{22}}& \ldots
\end{array}\\
\hbox to 4.5cm{\dotfill}
\end{array}
        $$
% ????????????
(через $\alpha_{ij}$ мы обозначаем $j$\д й член $i$\д й
последовательности). Теперь рассмотрим последовательность,
образованную стоящими на диагонали членами $\alpha_{00}$,
$\alpha_{11}$, $\alpha_{22}$, $\dots$; её $i$\д й член есть~$\alpha_{ii}$ и
совпадает с $i$\д м членом $i$\д й последовательности.
Заменив все члены на противоположные, мы получим
последовательность~$\beta$, у которой
        $$
\beta_{i}= 1 - \alpha_{ii},
        $$
так что последовательность~$\beta$ отличается от любой из
последовательностей~$\alpha_i$ (в позиции~$i$) и потому отсутствует в
таблице. А мы предположили, что таблица включает в себя все
последовательности \т противоречие.
        %
\end{proof}

Из этой теоремы следует, что множество~$\bbR$\index{$\bbR$} действительных
чисел\index{Числа!действительные} (которое, как мы видели, равномощно множеству
последовательностей нулей и единиц) не\-счёт\-но. В частности, оно
не может совпадать со счётным множеством алгебраических чисел и
потому существует действительное число, не являющееся
алгебраическим (не являющееся корнем никакого ненулевого многочлена
% ---------------------------- страница 31 ----------------------------------
с целочисленными коэффициентами). Такие числа называют
\emph{трансцендентными}\index{Числа!трансцендентные}.

\begin{historyremark}
        %
К моменту создания Кантором\glossary{Кантор@\Кантор} теории множеств уже было известно,
что такие числа существуют. Первый пример такого числа построил
в 1844 году французский математик Ж.\,Лиувилль\glossary{Лиувилль@\Лиувилль}. Он
показал, что число, хорошо приближаемое рациональными, не может
быть алгебраическим (таково, например, число $\sum(1/10^{n!})$).
Доказательство теоремы Лиувилля не очень сложно, но всё\д таки
требует некоторых оценок погрешности приближения; на его фоне
доказательство Кантора, опубликованное им в~1874 году, выглядит
чистой воды фокусом. Эта публикация была первой работой
по теории множеств; в её первом параграфе доказывается
счётность множества алгебраических чисел, а во втором\т несчётность
множества действительных чисел. (Общее определение равномощности
было дано Кантором лишь через три года, одновременно с доказательством
равномощности пространств разного числа измерений, о котором мы
уже говорили.)

Отметим кстати, что в том же~1874 году
французский математик Ш.\,Эрмит\glossary{Эрмит@\Эрмит} доказал, что основание натуральных
логарифмов~$e$ трансцендентно, а через восемь лет немецкий
математик Ф.\,Линдеман\glossary{Линдеман@\Линдеман} доказал
трансцендентность числа $\pi$ и тем самым невозможности квадратуры круга.)
        %
\end{historyremark}

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

\begin{problem}
        %
Покажите, что для всякого несчётного множества $A\hm\subset\bbR$
можно указать точку $a$, любая окрестность которой пересекается
с $A$ по несчётному множеству. (Утверждение остаётся верным,
если слова \лк несчётное множество\пк\ заменить на \лк множество
мощности континуума\пк.)
        %
\end{problem}

\begin{problem}
        %
Покажите, что любое непустое замкнутое множество $A\subset\bbR$ без
изолированных точек имеет мощность континуума.
        %
\end{problem}

\begin{problem}
        %
Покажите, что любое замкнутое множество $A\subset\bbR$ либо
конечно, либо счётно, либо имеет мощность континуума. (Указание.
Рассмотрим множество $B\hm\subset A$, состоящее из тех
точек множества~$A$, в любой окрестности которых несчётно много
других точек из~$A$. Если $B$ пусто, то $A$ конечно или счётно.
Если $B$ непусто, то оно замкнуто и не имеет изолированных
точек.)
        %
\end{problem}

% ---------------------------- страница 32 ----------------------------------
Эта задача показывает, что для замкнутых подмножество прямой
верна гипотеза континуума\index{Гипотеза континуума}, утверждающая,
что любое подмножество
прямой либо конечно, либо счётно, либо равномощно~$\bbR$.
(Кантор\glossary{Кантор@\Кантор}, доказавший этот факт,
рассматривал его как первый шаг к доказательству гипотезы
континуума для общего случая, но из этого ничего не вышло.)

\begin{problem}
        %
Из плоскости выбросили произвольное счётное множество точек.
Докажите, что оставшаяся часть плоскости линейно связна и, более
того, любые две невыброшенные точки можно соединить двухзвенной
ломаной, не задевающей выброшенных точек.
        %
\end{problem}

Вернёмся к диагональной конструкции.
Мы знаем, что множество последовательностей нулей и единиц
равномощно множеству подмножеств натурального ряда (каждому
подмножеству соответствует его \лк характеристическая
последовательность\пк, у которой единицы стоят на местах из
этого подмножества). Поэтому можно переформулировать эту
теорему так:

\quot{
        %
Множество~$\bbN$ не равномощно множеству своих
подмножеств.
        }

\noindent
Доказательство также можно шаг за шагом перевести на такой язык:
пусть они равномощны; тогда есть взаимно однозначное
соответствие~$i\hm\mapsto A_i$ между натуральными числами и
подмножествами натурального ряда. Диагональная
последовательность в этих терминах представляет собой множество
тех~$i$, для которых $i\hm\in A_i$, а
последовательность~$\beta$, отсутствовавшая в перечислении,
теперь будет его дополнением ($B=\{i \mid i \notin A_i\}$).

При этом оказывается несущественным, что мы имеем дело с
натуральным рядом, и мы приходим к такому утверждению:

\begin{theorem}[общая формулировка теоремы Кантора]\index{Теорема!Кантора}
        \label{theorem-cantor}%
Никакое множество~$X$ не равномощно множеству всех своих
подмножеств.
        %
\end{theorem}

\begin{proof}
        %
Пусть $\varphi$\т взаимно однозначное соответствие между~$X$ и
множеством $P(X)$ всех подмножеств множества~$X$. Рассмотрим те
элементы~$x\in X$, которые не принадлежат соответствующему им подмножеству.
% ---------------------------- страница 33 ----------------------------------
Пусть $Z$\т образованное ими множество:
        $$
Z = \{ x\in X \mid x \notin \varphi(x) \}.
        $$
Докажем, что подмножество~$Z$ не соответствует никакому
элементу множества~$X$. Пусть это не так и $Z\hm=\varphi(z)$ для некоторого
элемента~$z\hm\in X$. Тогда
        $$
z \in Z \Leftrightarrow z \notin \varphi(z) \Leftrightarrow z \notin Z
        $$
(первое\т по построению множества~$Z$, второе\т по предположению
$\varphi(z)\hm=Z$). Полученное противоречие показывает, что
$Z$ действительно ничему не соответствует, так что $\varphi$
не взаимно однозначно.
        %
\end{proof}

С другой, стороны, любое множество~$X$ равномощно некоторой
части множества~$P(X)$. В самом деле, каждому элементу~$x\hm\in X$ можно
поставить в соответствие одноэлементное подмножество $\{x\}$.
Поэтому, вспоминая определение сравнения множеств по мощности
(с.~\pageref{comparing-cardinalities}), можно сказать, что мощность
множества $X$ всегда меньше мощности множества~$P(X)$

\begin{problem}
        %
Докажите, что $n\hm<2^n$ для всех натуральных $n\hm=0,1,2,\dots$
        %
\end{problem}

\begin{historyremark}
        %
В общей формулировке теорема~\ref{theorem-cantor} появляется в работе Кантора
1890/91 года. Вместо подмножеств Кантор говорит о функциях,
принимающих значения $0$~и~$1$.
        %
\end{historyremark}

На самом деле мы уже приблизились к опасной границе, когда
наглядные представления о множествах приводят к противоречию. В
самом деле, рассмотрим множество всех множеств~$U$, элементами
которого являются все множества. Тогда, в частности, все
подмножества множества~$U$ будут его элементами,
и~$P(U)\hm\subset U$, что невозможно по теореме Кантора.

Это рассуждение можно развернуть, вспомнив доказательство
теоремы Кантора\т получится так называемый парадокс Рассела\glossary{Рассел@\Рассел}%
\index{Парадокс!Рассела}. Вот
как его обычно излагают.

        \label{russell-paradox}
Типичные множества не являются своими
элементами. Скажем, множество натуральных чисел~$\bbN$
само не является натуральным числом и потому не будет своим
% ---------------------------- страница 34 ----------------------------------
элементом. Однако в принципе можно себе представить и
множество, которое является своим элементом (например, множество
всех множеств). Назовём такие множества \лк необычными\пк.
Рассмотрим теперь множество всех обычных множеств. Будет
ли оно обычным? Если оно обычное, то оно является своим
элементом и потому необычное, и наоборот. Как же так?

Модифицированная версия этого парадокса такова: будем называть
прилагательное самоприменимым, если оно об\-ла\-да\-ет описываемым
свойством. Например, при\-ла\-га\-тель\-ное \лк русский\пк\
самоприменимо, а прилагательное \лк глиняный\пк\ нет. Другой
пример: прилагательное \лк трёх\-слож\-ный\пк\ самоприменимо, а \лк
двусложный\пк\ нет. Теперь вопрос: будет ли прилагательное \лк
несамоприменимый\пк\ самоприменимым? (Любой ответ очевидно
приводит к противоречию.)

Отсюда недалеко до широко известного \лк парадокса
лжеца\index{Парадокс!лжеца}\пк,
говорящего \лк я лгу\пк, или до истории о солдате, который
должен был брить всех солдат одной с ним части, кто не бреется
сам \итп

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

\begin{itemize}
        %
\item
Понятие множества не является непосредственно очевидным;
разные люди (и научные традиции) могут понимать его по\д разному.
        %
\item
Множества\т слишком абстрактные объекты для того, чтобы
вопрос \лк а что на самом деле?\пк\ имел смысл. Например,
        \label{continuum-hypothesis}%
в работе Кантора\glossary{Кантор@\Кантор} 1878~года была сформулирована \emph{континуум\д
гипотеза}\index{Гипотеза континуума}: всякое подмножество отрезка либо конечно, либо
счётно, либо равномощно всему отрезку. (Другими словами,
между счётными множествами и множествами
% ---------------------------- страница 35 ----------------------------------
мощности континуум нет промежуточных мощностей). Кантор написал, что это
может быть доказано \лк с помощью некоторого метода индукции, в
изложение которого мы не будем входить здесь подробнее\пк, но на
самом деле доказать это ему не удалось. Более того, постепенно
стало ясно, что утверждение континуум\д гипотезы можно считать
истинным или ложным,\т при этом получаются разные теории
множеств, но в общем\д то ни одна из этих теорий не лучше
другой.

Тут есть некоторая аналогия с неевклидовой геометрией. Мы можем
считать \лк пятый постулат Евклида\index{Пятый постулат}\glossary{Евклид@\Евклид}%
\пк\ (через данную точку
проходит не более одной прямой, параллельной данной) истинным.
Тогда получится геометрия, называемая евклидовой. А можно
принять в качестве аксиомы противоположное утверждение: через
некоторую точку можно провести две различные прямые,
параллельные некоторой прямой. Тогда получится неевклидова
геометрия. [Отметим, кстати, распространённое заблуждение:
почему\д то широкие массы писателей о науке и даже отдельные
математики в минуты затмений (см.~статью в Вестнике Академии Наук,
посвящённую юбилею Лобачевского\glossary{Лобачевский@\Лобачевский}) считают, что в
неевклидовой геометрии параллельные
прямые пересекаются. Это не так\т
параллельные прямые и в евклидовой, и в неевклидовой геометрии
определяются как прямые, которые не пересекаются.]

Вопрос о том, евклидова или неевклидова геометрия правильна \лк
на самом деле\пк, если вообще имеет смысл, не является
математическим\т скорее об этом следует спрашивать физиков.
К теории множеств это относится в ещё
большей степени, и разве что теология (Кантор\glossary{Кантор@\Кантор}
неоднократно обсуждал вопросы теории множеств с
профессионалами\д теологами) могла бы в принципе претендовать на
окончательный ответ.

% ---------------------------- страница 36 ----------------------------------
\item
Если мы хотим рассуждать о множествах, не впадая в противоречия,
нужно проявлять осторожность и избегать определённых видов
рассуждений. Безопасные (по крайней мере пока не приведшие к
противоречию) правила обращения со множествами сформулированы в
аксиоматической теории множеств (формальная теория ZF\index{ZF, ZFC, теории},
названная
в честь Цермело\glossary{Цермело@\Цермело} и
Френкеля\glossary{Френкель@\Френкель}).
Добавив к этой теории аксиому
выбора\index{Аксиома!выбора}, получаем теорию, называемую ZFC
(сhoice по\д английски\т выбор). Есть и другие, менее популярные теории.
        %
\end{itemize}

Однако формальное построение теории множеств выходит за рамки
нашего обсуждения. Поэтому мы ограничимся неформальным описанием
ограничений, накладываемых во избежание противоречий: нельзя
просто так рассмотреть множество всех множеств или множество
всех множеств, не являющихся своими элементами, поскольку класс
потенциальных претендентов слишком \лк необозрим\пк. Множества
можно строить лишь постепенно. Например, можно образовать
множество всех подмножеств данного множества (\emph{аксиома
степени}\index{Аксиома!степени}). Можно рассмотреть подмножество
данного множества, образованное элементами с каким\д то свойством (\emph{аксиома
выделения}\index{Аксиома!выделения}).
Можно рассмотреть множество всех элементов,
входящих хотя бы в один из элементов данного множества
(\emph{аксиома суммы}\index{Аксиома!суммы}). Есть и другие аксиомы.

Излагая сведения из теории множеств, мы будем стараться
держаться подальше от опасной черты, и указывать на опасность в
тех местах, когда возникнет искушение к этой черте приблизиться. Пока
что такое место было одно: попытка определить мощность%
\index{Мощности}\index{Множества!мощность} множества
как класс (множество) всех равномощных ему множеств.

\section{Функции}\index{Функция}
        \label{functions}

До сих пор мы старались ограничиваться минимумом формальностей и
говорили о функциях, их аргументах,
% ---------------------------- страница 37 ----------------------------------
значениях, композиции \итп
без попыток дать определения этих понятий. Сейчас мы дадим
формальные определения.

Пусть $A$ и~$B$\т два множества. Рассмотрим множество всех
упорядоченных пар\index{Упорядоченная пара}
$\langle a,b\rangle$\index{$\langle a,b\rangle$}, где $a\hm\in A$
и~$b\hm\in B$. Это множество называется \emph{декартовым
произведением}\index{Декартово произведение множеств}%
\index{Множества!декартово произведение} множеств $A$ и~$B$ и
обозначается~$A\hm\times B$\index{$A\times B$}.
(К вопросу о том, что такое упорядоченная пара, мы ещё вернёмся
на с.~\pageref{kuratowski-pair}.)

Любое подмножество~$R$ множества~$A\hm\times B$ называется
\emph{отношением}\index{Отношение} между множествами $A$ и~$B$. Если~$A\hm=B$,
говорят о \emph{бинарном отношении}\index{Отношение!бинарное} на множестве~$A$.
Например, на множестве натуральных чисел можно рассмотреть
бинарное отношение \лк быть делителем\пк, обычно обозначаемое
символом~$|$. Тогда можно в принципе было бы написать $\langle
2, 6\rangle\hm\in |$ и $\langle 2, 7\rangle\hm\notin |$. Обычно,
однако, знак отношения пишут между объектами (например, $2|6$).

\begin{problem}
        %
Вопрос для самоконтроля: отношения \лк быть делителем\пк\
и \лк делиться на\пк\т это одно и то же отношение или разные?
(Ответ: конечно, разные\т в упорядоченной паре порядок существен.)
        %
\end{problem}

Если аргументами функции являются элементы множества~$A$, а
значениями\т элементы множества~$B$, то можно рассмотреть
отношение между~$A$ и~$B$, состоящее из пар вида~$\langle
x,f(x)\rangle$. По аналогии с графиками функций на плоскости
такое множество можно назвать графиком функции~$f$\index{График функции}%
\index{Функция!график}. С формальной
точки зрения, однако,
удобнее не вводить отдельного неопределяемого
понятия функции, а вместо этого отождествить функцию с её
графиком.

        \label{function}%
Отношение $F\hm\subset A\hm\times B$ называется \emph{функцией
из~$A$ в~$B$}\index{Функция!из \dots в \dots}, если оно не содержит
пар с одинаковым первым
членом и разными вторыми. Другими словами, это означает,
что для каждого~$a\in A$ существует не более одного~$b\in B$,
при котором~$\langle a,b\rangle\hm\in F$.

        \label{domain}%
Те элементы~$a\in A$, для которых такое~$b$ существует, образуют
\emph{область определения}\index{Область определения функции}%
\index{Функция!область определения} функции~$F$.
Она обозначается~$\Dom F$\index{$\Dom F$}
(от английского слова domain). Для любого элемента $a\hm\in
\Dom F$ можно определить \emph{значение}\index{Значение функции}%
\index{Функция!значение}
% ---------------------------- страница 38 ----------------------------------
функции~$F$ на аргументе\index{Аргумент функции}\index{Функция!аргумент}~$a$
(\лк в точке~$a$\пк, как иногда говорят) как тот
единственный элемент~$b\hm\in B$, для которого $\langle a,b\rangle\hm\in F$.
Этот элемент записывают как~$F(a)$. Все такие элементы~$b$ образуют
        \label{range}%
\emph{множество значений}\index{Функция!множество значений}
функции~$F$, которое обозначается
$\Val F$\index{$\Val F$}.

Если $a\notin\Dom F$, то говорят, что функция \emph{не определена}
на~$a$. Заметим, что по нашему определению функция из $A$ в $B$
не обязана быть определена на всех элементах множества $A$\т её
область определения может быть любым подмножеством
множества~$A$. Симметричным образом множество её значений может
не совпадать с множеством~$B$.

Если область определения функции~$f$ из~$A$ в~$B$ совпадает с~$A$, то
пишут $f\colon A\hm\to B$\index{$f\colon A\to B$}.

        \label{identity-function}%
Пример: \emph{тождественная}\index{Тождественная функция}%
\index{Функция!тождественная} функция~$\id_A\colon A\hm\to A$\index{$\id_A$}
переводит множество~$A$ в себя, причём $\id(a)\hm=a$ для любого $a\hm\in
A$. Она представляет собой множество пар вида~$\langle a,a\rangle$
для всех~$a\in A$. (Индекс~$A$ в~$\id_A$ иногда опускают,
если ясно, о каком множестве идёт речь.)

        \label{composition}%
\emph{Композицией}\index{Композиция функций}
двух функций $f\colon A \hm\to B$ и $g\colon B\hm\to C$
называют функцию $h\colon A\hm\to C$, определённую
соотношением~$h(x)\hm=g(f(x))$. Другими словами, $h$~представляет собой
множество пар
        $$
\{\langle a,c\rangle \mid \langle a,b\rangle \in f \text{ и }
   \langle b,c\rangle \in g \text{ для некоторого $b\in B$}\}.
        $$
Композиция функций обозначается $g\hm\circ f$\index{$g\circ f$} (мы, как и в
большинстве книг, пишем справа функцию, которая применяется
первой).

Очевидно, композиция (как операция над функциями)
ассоциативна, то есть $h\circ (f\circ g) \hm=
(h\circ f)\circ g$, поэтому в композиции нескольких подряд
идущих функций можно опускать скобки.

        \label{preimage}%
Пусть $f\colon A\hm\to B$. \emph{Прообразом}\index{Прообраз}
подмножества $B'\hm\subset B$
называется множество всех элементов~$x\hm\in A$, для которых~$f(x)\hm\in B'$.
Оно обозначается~$f^{-1}(B')$\index{$f^{-1}(B)$}:
        $$
f^{-1}(B')=\{ x \in A \mid f(x)\in B'\}.
        $$
        \label{image}%
% ---------------------------- страница 39 ----------------------------------
\emph{Образом}\index{Образ} множества~$A'\hm\subset A$ называется множество всех
значений функции~$f$ на всех элементах множества~$A'$. Оно
обозначается~$f(A')$:
        \begin{align*}
f(A')& =\{f(a)\mid a\in A'\}=\\ &= \{ b\in B\mid\langle a,b\rangle \in f
                        \text{ для некоторого $a\in A'$}\}.
        \end{align*}
Строго говоря, обозначение~$f(A')$ может привести к путанице (одни и
те же круглые скобки употребляются и для значения функции, и для
образа множества), но
обычно ясно, что имеется в виду.

\begin{problem}
        %
Какие из следующих равенств верны?
        \begin{align*}
f(A' \cap A'') &= f(A') \cap f(A'');\\
f(A' \cup A'') &= f(A') \cup f(A'');\\
f(A' \setminus A'') &= f(A') \setminus f(A'');\\
f^{-1}(B' \cap B'') &= f^{-1}(B') \cap f^{-1}(B'');\\
f^{-1}(B' \cup B'') &= f^{-1}(B') \cup f^{-1}(B'');\\
f^{-1}(B' \setminus B'') &= f^{-1}(B') \setminus f^{-1}(B'');\\
f^{-1}(f(A'))&\subset A';\\
f^{-1}(f(A'))&\supset A';\\
f(f^{-1}(B') )&\subset B';\\
f(f^{-1}(B') )&\supset B';\\
(g\circ  f)(A)&=g(f(A));\\
(g\circ f)^{-1}(C')&= f^{-1}(g^{-1}(C'));
%(g\circ f)^{-1}(C')&= g^{-1}(f^{-1}(C')).
        \end{align*}
(Здесь $f\colon A\hm\to B$, $g\colon B\hm\to C$, $A',A''\hm\subset A$,
$B',B''\hm\subset B$, $C'\hm\subset C$.)
        %
\end{problem}
\problskip

Иногда вместо функций говорят об отображениях\index{Отображение}
(резервируя термин
\лк функция\пк\ для отображений с числовыми аргументами и
значениями). Мы не будем строго придерживаться таких различий,
употребляя слова \лк отображение\пк\ и \лк функция\пк\ как
синонимы.

% ---------------------------- страница 40 ----------------------------------
        \label{injection}%
Функция $f\colon A\hm\to B$ называется \emph{инъективной}%
\index{Функция!инъективная}, или
\emph{инъекцией}\index{Инъекция}, или \emph{вложением}\index{Вложение},
если она переводит
разные элементы в разные, то есть если $f(a_1)\hm\neq f(a_2)$
при различных $a_1$ и~$a_2$.

        \label{surjection}%
Функция $f\colon A\hm\to B$ называется \emph{сюръективной}%
\index{Функция!сюръективная}, или
\emph{сюръекцией}\index{Сюръекция}, или \emph{наложением}\index{Наложение},
если множество её значений есть
всё~$B$. (Иногда такие функции называют \emph{отображениями
на}~$B$.)

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

\begin{problem}
        %
Докажите, что функция~$f\colon A\hm\to B$ является вложением
тогда и только тогда, когда она имеет \emph{левую обратную}
     \index{Функция!обратная}%
функцию~$g\colon B\hm\to A$, то есть функцию~$g$,
для которой~$g\hm\circ f \hm= \id_A$.
        %
Докажите, что функция $f\colon A\hm\to B$ является наложением
     \index{Функция!обратная}%
тогда и только тогда, когда она имеет \emph{правую обратную}
функцию~$g\colon B\hm\to A$, для которой~$f\hm\circ g \hm= \id_B$.
        %
\end{problem}

\begin{problem}
        %
Докажите, что функция $f\colon A\hm\to B$ является вложением тогда и
только тогда, когда на неё можно сокращать слева: из равенства
$f\hm\circ g_1 \hm= f\hm\circ g_2$ следует равенство $g_1 \hm= g_2$ (для
любых функций $g_1$, $g_2$, области значений которых содержатся в~$A$).
        %
Докажите, что функция $f\colon A\hm\to B$ является наложением тогда и
только тогда, когда на неё можно сокращать справа: из равенства
$g_1 \hm\circ f \hm= g_2 \hm\circ f$ следует равенство $g_1 \hm= g_2$ (для
любых функций $g_1$, $g_2$, область определения которых есть $B$).
        %
\end{problem}

\problskip
        \label{bijection}%
Отображение (функция) $f\colon A\hm\to B$, которое одновременно
является инъекцией и сюръекцией (вложением и наложением),
называется \emph{биекцией}\index{Биекция}, или взаимно однозначным
соответствием\index{Соответствие взаимно однозначное}\index{Взаимно
однозначное соответствие}.

Если $f$\т биекция, то существует \emph{обратная}\index{Обратная функция}%
\index{Функция!обратная} функция
$f^{-1}$, для которой ${f^{-1}(y)=x}\hm\Leftrightarrow{f(x)=y}$.

\begin{problem}
        %
Могут ли для некоторой функции левая и правая обратные
существовать, но быть различны?
        %
\end{problem}

Напомним, что множества $A$~и~$B$ равномощны\index{Множества!равномощные}%
\index{Равномощность множеств}, если существует
биекция $f\colon A\hm\to B$. В каком случае существует инъекция
(вложение) $f\colon A\hm\to B$? Легко понять, что вложение является
взаимно однозначным соответствием между~$A$ и некоторым
подмножеством множества~$B$, поэтому такое
% ---------------------------- страница 41 ----------------------------------
вложение существует тогда и
только тогда, когда в~$B$ есть подмножество,
равномощное~$A$, \те когда мощность~$A$ не превосходит
мощности~$B$ (в смысле определения, данного в
разделе~\ref{cantor-bernstein}).

Чуть менее очевиден другой результат: наложение $A$~на~$B$
существует тогда и только тогда, когда мощность~$B$ не
превосходит мощности~$A$.

В самом деле, пусть наложение $f\colon A\hm\to B$ существует. Для
каждого элемента~$b\hm\in B$ найдётся хотя бы один элемент~$a\hm\in A$,
для которого~$f(a)\hm=b$. Выбрав по одному такому элементу, мы
получим подмножество~$A'\hm\subset A$, которое находится во
взаимно однозначном соответствии с множеством~$B$. (Здесь
снова используется аксиома выбора\index{Аксиома!выбора},
о которой мы говорили на
с.~\pageref{axiom-of-choice}.)

В обратную сторону: если какое\д то подмножество~$A'$ множества~$A$
равномощно множеству~$B$ и имеется биекция $g\colon A'\hm\to B$,
то наложение~$A$ на~$B$ можно получить, доопределив эту биекцию на
элементах вне~$A'$ каким угодно образом.

\begin{problem}
        %
Найдите ошибку в этом рассуждении, не читая дальше.
        %
\end{problem}

На самом деле такое продолжение возможно, только если $B$~непусто,
так что правильное утверждение звучит так:
наложение~$A$ на~$B$ существует только и только тогда, когда $B$~непусто и
равномощно некоторому подмножеству~$A$, или когда
оба множества пусты.

В нашем изложении остаётся ещё один не вполне понятный момент:
что такое \лк упорядоченная пара\index{Упорядоченная пара}\пк?
Неформально говоря, это
способ из двух объектов $x$ и~$y$ образовать один
объект~$\langle x,y\rangle$, причём этот способ обладает таким
свойством:
        $$
\langle x_1,y_1\rangle = \langle x_2,y_2\rangle
        \
\Leftrightarrow
        \
\text{$x_1=x_2$ и $y_1=y_2$}.
        $$
В принципе, можно так и считать понятие упорядоченной пары
неопределяемым, а это свойство\т аксиомой. Однако при формальном
построении теории множеств удобно использовать трюк, придуманный
польским математиком
Куратовским\glossary{Куратовский@\Куратовский}, и избежать появления отдельного
понятия упорядоченной пары.
(Напомним, что
% ---------------------------- страница 42 ----------------------------------
$\{x\}$\index{$\{a,b,c\}$}~обозначает множество,
единственным элементом которого является~$x$, а $\{x,y\}$\index{$\{a,b,c\}$}~обозначает
множество, которое содержит $x$ и~$y$ и не содержит других элементов.
Тем самым ${\{x,y\}} \hm= {\{x\}} \hm= {\{y\}}$, если $x\hm=y$.)

\begin{theorem}[Упорядоченная пара по Куратовскому]\index{Упорядоченная
пара!по Куратовскому}
        \label{kuratowski-pair}%
Оп\-ре\-де\-лим $\langle x,y\rangle$\index{$\langle a,b\rangle$} как ${\{\{x\},\{x,y\}\}}$.
Тогда выполнено указанное выше свойство:
        $$
\langle x_1,y_1\rangle = \langle x_2,y_2\rangle
        \
\Leftrightarrow
        \
\text{$x_1=x_2$ и $y_1=y_2$}.
        $$
\end{theorem}

\begin{proof}
        %
Пусть
        $
\langle x_1,y_1\rangle = \langle x_2,y_2\rangle
        $.
По определению это означает, что
        $$
{\{\{x_1\},\{x_1,y_1\}\}}=
{\{\{x_2\},\{x_2,y_2\}\}}.
        $$
Теперь нужно аккуратно разобрать случаи (не путая при этом $x$ с
$\{x\}$). Это удобно делать в следующем порядке. Пусть сначала
$x_1\hm\neq y_1$. Тогда множество ${\{x_1,y_1\}}$ состоит из
двух элементов. Раз оно принадлежит левой части равенства, то
принадлежит и правой. Значит, оно равно либо $\{x_2\}$, либо
${\{x_2,y_2\}}$. Первое невозможно, так как двухэлементное
множество не может быть равно одноэлементному. Значит,
${\{x_1,y_1\}}\hm= {\{x_2,y_2\}}$. С другой стороны,
одноэлементное множество $\{x_1\}$ принадлежит левой части
равенства, поэтому оно принадлежит и правой, и потому равно
$\{x_2\}$ (поскольку не может быть равно двухэлементному).
Отсюда $x_1\hm=x_2$ и $y_1\hm=y_2$, что и требовалось.

Аналогично можно разобрать симметричный случай, когда
$x_2\hm\neq y_2$.

Осталось рассмотреть ситуацию, когда $x_1\hm=y_1$ и
$x_2\hm=y_2$. В этом случае ${\{x_1,y_1\}}\hm=\{x_1\}$ и потому
левая часть данного нам равенства есть $\{\{x_1\}\}$.
Аналогичным образом, правая его часть есть $\{\{x_2\}\}$, и
потому $x_1=x_2$, так что все четыре элемента $x_1$, $x_2$, $y_1$, $y_2$
совпадают.
        %
\end{proof}

Заметим, что возможны и другие определения упорядоченной пары,
для которых аналогичное утверждение верно, так что никакого \лк
философского смысла\пк\ в этом
% ---------------------------- страница 43 ----------------------------------
определении нет\т это просто
удобный технический приём\-.

\begin{problem}
        %
Докажите утверждение теоремы~\ref{kuratowski-pair} для
\emph{упорядоченной пары по Винеру}\index{Упорядоченная пара!по Винеру}%
\glossary{Винер@\Винер}:
$\langle x,y\rangle\hm=
\{\{\varnothing,\{x\}\},\{\{y\}\}\}$.
        %
\end{problem}

\section{Операции над мощностями}\index{Мощности!операции}%
\index{Операции над мощностями}
        \label{cardinal-operations}%

Мощности конечных множеств\т натуральные числа, и их можно
складывать, умножать, возводить в степень. Эти операции можно
обобщить и на мощности бесконечных множеств, и делается это так.

        \label{cardinal-sum}
Пусть $A$ и~$B$\т два множества. Чтобы сложить их мощности, надо
взять мощность
множества~$A\hm\cup B$, если $A$ и~$B$ не пересекаются. Если они
пересекаются, то их надо заменить на непересекающиеся
равномощные им множества $A'$ и~$B'$. Мощность объединения и
будет \emph{суммой}\index{Мощности!сумма}\index{Сумма мощностей}
мощностей множеств $A$ и~$B$.

\textsf{Замечания.} \textsf{1.} Чтобы избежать упоминания мощностей как
самостоятельных объектов, следует считать выражение \лк мощность
множества~$C$ есть сумма мощностей множеств $A$~и~$B$\пк\
идиоматическим выражением (а сказанное выше\т его определением).
Но мы для удобства будем часто пренебрегать такими
предосторожностями.

\textsf{2.} В принципе следовало бы проверить корректность этого
определения и доказать, что мощность множества $A'\hm\cup B'$ не
зависит от того, какие именно не\-пе\-ре\-се\-ка\-ю\-щие\-ся
множества~$A'$ и~$B'$
(равномощные~$A$ и~$B$) мы выберем. (Что, впрочем, очевидно.)

\textsf{3.} Для конечных множеств получается
обычное сложение натуральных чисел.

\textsf{4.} Наконец, формально следовало бы ещё доказать, что такие $A'$
и~$B'$ можно выбрать. Это можно сделать, например, так: положим
$A'\hm=A\times\{0\}$ и~$B'\hm=B\times\{1\}$.

        \label{cardinal-product}%
Последней проблемы не будет при определении \emph{произведения}%
\index{Мощности!произведение}\index{Произведение мощностей}
мощностей как мощности декартова произведения~$A\hm\times B$%
\index{$A\times B$}. (Но остальные замечания остаются в силе.)

        \label{cardinal-exponent}%
Теперь определим \emph{возведение в степень}%
\index{Мощности!возведение в степень}\index{Возведение в степень мощностей}.
Для этого рассмотрим (для данных $A$ и~$B$) множество всех функций
% ---------------------------- страница 44 ----------------------------------
вида $f\colon B\hm\to A$
(напомним: это означает, что их область определения есть~$B$, а
область значений содержится в~$A$). Это множество обозначается~$A^B$%
\index{$A^B$},
и его мощность и будет результатом операции возведения в степень.

Если множества $A$ и~$B$ конечны и содержат $a$ и~$b$ элементов
соответственно, то $A^B$~содержит как раз $a^b$~элементов. В
самом деле, определяя функцию $f\colon B\hm\to A$, мы должны определить
её значение на каждом из $b$~элементов. Это можно сделать $a$~способами,
так что получаем всего $a^b$~вариантов.

\begin{problem}
        %
Чему равно~$0^0$ согласно нашему определению?
(Ответ: единице.)
%заметим, что $0^b$ и~$a^0$ при положительных $a$ и~$b$
%5определены правильно.)
        %
\end{problem}

%\problskip
\textsf{Пример.} Обозначим через~$2$ какое\д нибудь множество из двух
элементов, например,~$\{0,1\}$. Что такое~$2^\mathbb{N}$\index{$2^X$}? По
определению это множество функций $f\colon\mathbb{N}\hm\to\{0,1\}$.
Такие функции\т это по существу последовательности нулей и
единиц, только вместо
$f_0f_1f_2\dots$
мы пишем
$f(0), f(1), f(2), \dots$
(Формально последовательность элементов
некоторого множества~$X$ так и определяется\т как функция
типа~$\bbN\hm\to X$.)

Заметим, что $2^X$~равномощно~$P(X)$\index{$P(U)$} (в частном случае~$X\hm=\bbN$
мы это доказывали; для общего случая доказательство такое же).

Обычные свойства сложения и умножения (коммутативность, ассоциативность и
дистрибутивность)
сохраняют силу
и для арифметики мощностей:
       %
\begin{align*}
        %
 a+b&= b+a;\\
        %
a+(b+c)&=(a+b)+c;\\
        %
a\times b&= b\times a;\\
%\end{align*}
%\begin{align*}
        %
a\times (b \times c)&= (a\times b)\times c;\\
        %
(a+b)\times c&= (a\times c)+(b \times c).
        %
\end{align*}

Формально их следует читать, избегая слова \лк мощность\пк\
как самостоятельного объекта: например, $a\hm\times b\hm=b\hm\times a$
означает, что $A\hm\times B$ и $B\hm\times A$ равномощны (и это легко
проверить: $\langle x,y\rangle \hm\mapsto \langle y,x\rangle$ будет
взаимно однозначным соответствием между ними). Остальные свойства
% ---------------------------- страница 45 ----------------------------------
доказываются столь же просто. Чуть сложнее свойства,
включающие возведение в степень:
        %
\begin{align*}
        %
a^{b+c}&=a^b\times a^c;\\
        %
(ab)^c&=a^c\times b^c;\\
        %
(a^b)^c&=a^{b\times c}.
        %
\end{align*}

Проверим первое из них. Из чего состоит~$A^{B+C}$? (Будем
считать, что $B$ и~$C$ не пересекаются.) Его элементами являются
функции со значениями в~$A$, определённые на~$B\hm+C$.
Такая функция состоит из двух частей: своего сужения на~$B$
(значения на аргументах из~$B$ остаются теми же, остальные
отбрасываются) и своего сужения на~$C$. Тем самым для каждого
элемента множества~$A^{B+C}$ мы получаем пару элементов из~$A^B$
и~$A^C$. Это и будет искомое взаимно однозначное
соответствие.

С соответствием между множествами~$(A\times B)^C$ и~$A^C\hm\times B^C$ мы тоже
часто сталкиваемся. Например, элемент
множества~$(\bbR\hm\times\bbR)^{\bbR}$ есть отображение типа
$\bbR\hm\to\bbR\hm\times\bbR$, то есть кривая
$t\hm\mapsto z(t)\hm= \langle x(t),y(t)\rangle$ на плоскости. Такая
кривая задаётся парой функций $x,y\colon \bbR\hm\to\bbR$.

Соответствие между $(A^B)^C$ и~$A^{(B\times C)}$ встречается
несколько реже. Элемент $f\hm\in A^{(B\times C)}$ является
отображением $B\hm\times C\hm\to A$, то есть, в обычной терминологии,
функцией двух аргументов (первый из~$B$, второй из~$C$). Если
зафиксировать в ней второй аргумент, то получится
функция~$f_c\colon B\hm\to A$, определённая
соотношением~$f_c(b)\hm=f(b,c)$ (точнее,
$f(\langle b,c\rangle)$). Отображение $с\hm\mapsto f_c$,
принадлежащее $(A^B)^C$, и соответствует
элементу $f\hm\in A^{(B\times C)}$.
(Отчасти сходная конструкция встречается в
алгебре, когда многочлен от двух переменных рассматривают как
многочлен от одной переменной с коэффициентами в кольце многочленов
от второй переменной.)

Мощность счётного множества символически обозначается~$\aleph_0$%
\index{$\aleph_0$},
мощность континуума (отрезка или множества бесконечных последовательностей
нулей и единиц) обозначается~$\mathfrak{c}$\index{$\mathfrak{c}$}.
По определению,~$\mathfrak{c}=2^{\aleph_0}$.

(Естественный вопрос: каков смысл индекса~$0$ в~$\aleph_0$?
% ---------------------------- страница 46 ----------------------------------
что такое, скажем,~$\aleph_1$? Обычно $\aleph_1$~обозначает
наименьшую несчётную мощность (как мы увидим, такая существует).
Гипотеза континуума\index{Гипотеза континуума}, о которой мы упоминали на
с.~\pageref{continuum-hypothesis}, утверждает,
что~$\mathfrak{c}=\aleph_1$.)

Известные нам свойства счётных множеств можно записать так:
   \begin{itemize}
        %
\item
$\aleph_0 \hm+ n \hm= \aleph_0$ для конечного~$n$ (объединение счётного
             и конечного множеств счётно);
        %
\item
$\aleph_0 \hm+ \aleph_0 \hm= \aleph_0$ (объединение двух счётных множеств
                                 счётно);
        %
\item
$\aleph_0 \hm\times \aleph_0 \hm= \aleph_0$ (объединение счётного числа
                счётных множеств счётно).
   \end{itemize}

Отсюда можно формально получить многие факты манипуляциями
с мощностями. Например, цепочка равенств
        $$
\mathfrak{c}\times \mathfrak{c} = 2^{\aleph_0}\times 2^{\aleph_0} =
                                  2^{\aleph_0+\aleph_0} =
                                  2^{\aleph_0} = \mathfrak{c}
        $$
показывает, что прямая и плоскость равномощны.

Аналогичным образом,
        $$
\mathfrak{c}^{\aleph_0}= (2^{\aleph_0})^{\aleph_0}=
2^{\aleph_0 \times \aleph_0}= 2^{\aleph_0} = \mathfrak{c}.
        $$

\begin{problem}
        %
Объясните подробно выкладку:
        $$
\mathfrak{c}+\mathfrak{c} = 1\times\mathfrak{c}+1\times\mathfrak{c}=
        2\times\mathfrak{c}=2^1\times 2^{\aleph_0} = 2^{1+\aleph_0} =
                              2^{\aleph_0} = \mathfrak{c}.
        $$
\end{problem}

\begin{problem}
        %
Проверьте, что $\aleph_0 \times \mathfrak{c} = \mathfrak{c}$.
        %
\end{problem}

\problskip
Приведённые нами свойства мощностей полезно сочетать с теоремой
Кантора\ч Бернштейна.
        \index{Теорема!Кантора\Ч Шрёдера\Ч Бернштейна}%
Например, заметим, что
        $$
\mathfrak{c} =
    2^{\aleph_0}
     \le {\aleph_0}^{\aleph_0}
        \le \mathfrak{c}^{\aleph_0}
           = \mathfrak{c},
        $$
поэтому ${\aleph_0}^{\aleph_0}= \mathfrak{c}$
(словами: множество всех бесконечных последовательностей
натуральных чисел имеет мощность континуума).

\begin{problem}
        %
Последнее рассуждение неявно использует монотонность операции
возведения в степень для мощностей (если~$a_1\hm\le a_2$,
% ---------------------------- страница 47 ----------------------------------
то~$a_1^b
\hm\le a_2^b$). Проверьте это и аналогичные свойства для других
операций (впрочем, почти очевидные).
        %
\end{problem}

\begin{problem}
        %
Установите явное соответствие между последовательностями
натуральных чисел и иррациональными числами на отрезке~$(0,1)$,
используя цепные дроби\index{Цепные дроби}, то есть дроби вида
$1/(n_0\hm+1/(n_1\hm+1/(n_2+\ldots)))$.
        %
\end{problem}

\begin{problem}
        %
Проверьте, что $\aleph_0 ^\mathfrak{c} \hm= 2^\mathfrak{c}$.
(Напомним, что по теореме Кантора эта мощность больше
мощности континуума.)
        %
\end{problem}

\begin{problem}
        %
Какова мощность множества всех непрерывных функций с действительными
аргументами и значениями? Существенна ли здесь непрерывность?
        %
\end{problem}

\begin{problem}
        %
Какова мощность множества всех монотонных функций с
действительными аргументами и значениями?
        %
\end{problem}

\begin{problem}
        %
Может ли семейство подмножеств натурального ряда быть
несчётным, если любые два его элемента имеют конечное
пересечение? конечную симметрическую разность?
        %
\end{problem}

\problskip
Впоследствии мы увидим, что для бесконечных мощностей $a\hm\times b
\hm= a\hm+b \hm= \max(a,b)$, но пока этого мы доказать не можем. Поэтому
в задачах~\ref{split-continuum-1},~\ref{split-continuum-2} нам
пришлось воспользоваться обходным манёвром, чтобы доказать, что
из $a\hm+b\hm=\mathfrak{c}$ следует $a\hm=\mathfrak{c}$ или
$b\hm=\mathfrak{c}$. Следующее утверждение обобщает этот приём:

\begin{theorem}\label{koenig-theorem}
        %
Если множество
$A_1\hm\times A_2\hm\times\dots\times A_n$ разбито на непересекающиеся
части $B_1, \dots, B_n$, то найдётся такое~$i$, при котором
мощность~$B_i$ не меньше мощности~$A_i$.
        %
\end{theorem}

\begin{proof}
        %
В самом деле, рассмотрим проекцию множества $B_i\hm\subset
A_1\hm\times\ldots\hm\times A_n$ на~$A_i$. Если хотя бы при одном~$i$
она покрывает~$A_i$ полностью, то всё доказано. Если нет,
выберем для каждого~$i$ непокрытую точку~$x_i$. Набор $\langle
x_1,\dots,x_n\rangle$ не входит ни в одно из множеств~$B_i$, что
противоречит предположению.
        %
\end{proof}

Заметим, что в формулировке этого утверждения (которое иногда
называют теоремой~Кёнига\index{Теорема!Кёнига}\glossary{Кёниг@\Кёниг})
говорится о декартовом
произведении конечного числа множеств, которое можно определить
индуктивно (скажем, $A\hm\times B\hm\times C$ будет состоять из
троек $\langle a,b,c\rangle$, которые суть пары $\langle \langle
a,b\rangle,c\rangle$). Декартово произведение счётного числа
множеств уже так не определишь. Выход такой:
$A_0\hm\times A_1\hm\times A_2 \hm\times\ldots$ (счётное число
сомножителей) можно определить
% ---------------------------- страница 48 ----------------------------------
как множество всех
последовательностей $a_0, a_1, a_2, \dots$, у которых $a_i\hm\in
A_i$, то есть как множество всех функций~$a$, определённых на~$\bbN$
со значениями в объединении всех~$A_i$, причём
$a(i)\in A_i$ при всех~$i$. После такого определения
теорема~\ref{koenig-theorem} легко переносится и на счётные
(а также и на любые) произведения.

Переходя к отрицаниям, теорему~Кёнига можно сформулировать так:
если при всех~$i=0,1,2\dots$ для мощностей $a_i$ и $b_i$
выполнено неравенство~$b_i \hm< a_i$, то
        $$
b_0 + b_1 + b_2 + \ldots < a_0 \times a_1 \times a_2\times\ldots
        $$

Учитывая, что $\mathfrak{c}\hm\times\mathfrak{c}\hm\times\ldots$
(счётное произведение) равно~$\mathfrak{c}^{\aleph_0}$,
то есть~$\mathfrak{c}$, можно сформулировать такое следствие
теоремы~Кёнига: если континуум разбит на счётное число
подмножеств, то одно из них имеет мощность континуума.

\begin{problem}
        %
Докажите подробно это утверждение.
        %
\end{problem}

\begin{problem}
        %
Пусть $a_0,a_1,a_2,\ldots$\т мощности, причём $a_i\ge 2$ для всех $i$.
Покажите, что
        $$
a_0 + a_1 + a_2 + \ldots \le a_0 \times a_1 \times a_2\times\ldots
        $$
\end{problem}

\begin{problem}
        %
Пусть $m_0 < m_1 < m_2 <\dots$\т возрастающая последовательность
мощностей. Докажите, что сумма $m_0\hm+m_1\hm+m_2\hm+\ldots$ не представима
в виде $a^{\aleph_0}$ ни для какой мощности~$a$.
        %
\end{problem}
