rt-g0_73c250c9-Kleene_VVM-russian/parts/part1-the_problems_of_foundations.tex

\part{Проблемы оснований математики}
\label{part:the_problem_of_foundations}
%% ======================= Страница 11 =======================
\chapter{Теория множеств}
\label{chap:the_theory_of_sets}

\section{Счётные множества}
\label{sec:enumerable_sets}

Прежде чем приступить к нашему основному предмету, полезно бегло рассмотреть
канторовскую теорию множеств.

Стадо из четырёх овец и роща из четырёх деревьев находятся между собой в таком
отношении, в каком ни одно из них не находится с кучей из трёх камней или с
рощей из семи деревьев. Хотя для печатного выражения этого труизма мы
использовали слова, обозначающие числа, отношение, о котором идёт речь, само
лежит в основе понятия кардинального числа. Не прибегая к пересчёту овец или
деревьев, их можно попарно сопоставить друг другу, например привязав овец к
деревьям так, что каждая овца и каждое дерево будут принадлежать в точности к
одной паре. Такое попарное соответствие между элементами двух коллекций или
,,множеств`` предметов называется взаимно однозначным или \emph{одно-однозначным
соответствием} \lbrack короче, \emph{\isom-соответствием}\rbrack.

В 1638~г. Галилей заметил, что \emph{квадраты целых положительных чисел} могут
быть поставлены в \isom-соответствие с самими \emph{целыми положительными
числами} следующим образом:
\begin{equation*}
\begin{array}{llllllll}
1,&\; 4,&\; 9,&\; 16,&\;\ldots,&\; n^{2},&\;\ldots &\\
1,&\; 2,&\; 3,&\; 4,&\;\ldots,&\; n,&\;\ldots &\text{.}
\end{array}
\end{equation*}

\noindent%
несмотря на древнюю аксиому, что целое больше любой своей части. Кантор первый
предпринял, между 1874 и 1897 гг., систематическое сравнение бесконечных
множеств в терминах возможности установления \isom-соответствия.

Два множества из <<парадокса>> Галилея и множество \emph{натуральных чисел}
\begin{equation*}
0,\; 1,\; 2,\; 3,\;\ldots,\; n-1,\;\ldots
\end{equation*}

\noindent%
служат примерами ,,счётных`` бесконечных множеств. Выбирая последнее из этих
множеств в качестве стандартного образца, мы будем называть бесконечное
множество \emph{счётным}, если можно установить \isom-соответствие между его
элементами и натуральными числами.

Чтобы установить счётность некоторого бесконечного множества, надо лишь указать,
каким образом его элементы могут быть заданы (без повторений) в виде
,,бесконечного перечня``. Тогда первый в этом перечне элемент соответствует
числу $0$, второй --- числу $1$ и т.~д. Хотя сам этот перечень и бесконечен,
каждый его элемент занимает в нём некоторое конечное положение.

Такой бесконечный (без повторений) перечень элементов множества, или
\isom-соответствие между элементами множества и натуральными числами,
называется \emph{пересчётом} множества. Число, соответствующее данному элементу,
служит \emph{индексом} этого элемента в пересчёте.

Элементы конечного множества также могут быть даны в виде списка, т.~е.
конечного перечня. Поэтому термин \emph{счётный} иногда применяется к множе%
%% ======================= Страница 12 =======================
ствам, которые или являются бесконечными и счётными, т.~е.
\emph{счётно-бесконечными}, или же конечны.

Множество \emph{целых чисел} может быть пересчитано посредством расположения
их в следующем порядке:
\begin{equation*}
0,\; 1,\; -1,\; 2,\; -2,\; 3,\; -3,\;\ldots\text{.}
\end{equation*}

Множество \emph{рациональных чисел} также является счётным, и это обстоятельство
может показаться удивительным при сравнении их с целыми числами в обычном
алгебраическом порядке. Точки с целочисленными абсциссами расположены на оси
$x$-ов изолированно, а точки с рациональными абсциссами --- ,,всюду плотно``,
т.~е. между любыми двумя сколь угодно близкими из них имеются такие же точки.
Этот пересчёт может быть выполнен при помощи следующего приёма, который мы
изложим для \emph{положительных рациональных чисел}, предоставляя случай всех
рациональных чисел читателю.

Пусть дроби с положительными числителем и знаменателем расположены в виде
следующей бесконечной матрицы:
\begin{equation*}
  \xymatrix@!@=0ex{
    \sfrac{1}{1}\ar@{->}[d]&
    \sfrac{1}{2}\ar@{->}[r]&
    \sfrac{1}{3}\ar@{->}[dl]&
    \sfrac{1}{4}\ar@{->}[r]&\ldots\\
    \sfrac{2}{1}\ar@{->}[ur]&
    \sfrac{2}{2\ar@{->}[dl]}&
    \sfrac{2}{3}\ar@{->}[ur]&
    \sfrac{2}{4}&\ldots\\
    \sfrac{3}{1}\ar@{->}[d]&
    \sfrac{3}{2}\ar@{->}[ur]&
    \sfrac{3}{3}&\sfrac{3}{4}&\ldots\\
    \sfrac{4}{1}\ar@{->}[ur]&
    \sfrac{4}{2}&\sfrac{4}{3}&\sfrac{4}{4}&\ldots\\
    &&\ldots\ldots&&
  }
\end{equation*}

Пусть теперь эти дроби пересчитаны в порядке, указанном стрелками. Положительное
рациональное число может быть представлено в виде дроби с целым положительным
числителем и знаменателем. Будем двигаться по направлению стрелок, вычёркивая
каждую дробь, которая по величине равна некоторой предыдущей дроби. Тогда
получится следующее перечисление положительных рациональных чисел:
\begin{equation*}
1,\; 2,\;\sfrac{1}{2},\;\sfrac{1}{3},\; 3,\; 4,\;\sfrac{3}{2},\;\sfrac{2}{3},\;
\sfrac{1}{4},\;\ldots\text{.}
\end{equation*}

Этот метод матрицы является общим при пересчёте \emph{упорядоченных пар
элементов счётного множества}, например упорядоченных пар натуральных чисел или
упорядоченных пар целых чисел. Каждая строка матрицы служит пересчёту пар с
фиксированным первым элементом. \emph{Упорядоченные тройки элементов счётного
множества} могут затем быть пересчитаны при помощи повторного применения метода
матрицы, при котором в качестве строк выбираются уже полученные пересчёты троек
с фиксированным первым элементом. Повторяя этот приём, можно получить пересчёт
\emph{упорядоченных $n$-ок элементов счётного множества} для каждого
фиксированного натурального $n$. Все эти пересчёты, включая пересчёт
первоначального множества, можно выбрать в качестве строк новой матрицы, чтобы
получить пересчёт упорядоченных $n$-ок для переменного $n$, т.~е. пересчёт
\emph{конечных последовательностей элементов счётного множества}.

С помощью этого результата можно получить пересчёт \emph{алгебраических
уравнений}
\begin{equation*}
a_{0}x^{n}+a_{1}x^{n-1}+\ldots +a_{n-1}x+a_{n}=0\;\;\; (a_{0}\neq 0)
\end{equation*}

\noindent%
\emph{с целыми коэффициентами}, потому что каждое уравнение можно описать
заданием последовательности
\begin{equation*}
(a_{0},\; a_{1},\;\ldots ,\ ;a_{n-1},\; a_{n})
\end{equation*}

\noindent%
его коэффициентов. ,,Действительным алгебраическим числом`` называется
действительный корень уравнения такого вида. Так как данное уравнение имеет не
более $n$ различных корней, то \emph{алгебраические числа} образуют счётное
множество.

%% ======================= Страница 13 =======================
Ещё один приём, иллюстрирующий возможности пересчёта множеств. При рассмотрении
(конечного или бесконечного) счётного множества ч\`{и}сла%
%TODO: разобраться с ударением на "и"
, соответствующие его
элементам в некотором фиксированном пересчёте, можно употреблять в качестве
индивидуальных обозначений или названий этих элементов. Но и обратно, если
название или явное выражение в некоторой заранее данной недвусмысленной системе
обозначений может быть индивидуальным образом сопоставлено каждому элементу
некоторого множества, то это множество (конечное или бесконечное) счётно при том
условии, что название или выражение должно быть конечной последовательностью
символов, выбранных из данного конечного алфавита доступных нам символов.
Например, алгебраические уравнения с целыми коэффициентами могут быть записаны с
помощью десятичных обозначений для коэффициентов и показателей. Запись
показателей вверху является несущественной особенностью наших обозначений,
которую можно устранить с помощью подходящего соглашения. Действительно, коль
скоро мы имеем дело только с этими уравнениями, мы можем писать показатели
просто в той же строке, что и $x$. Тогда требуются в точности следующие символы:
\begin{equation*}
0,\; 1,\; 2,\; 3,\; 4,\; 5,\; 6,\; 7,\; 8,\; 9,\; x,\; +,\; -,\; =\text{.}
\end{equation*}

Первый символ в уравнении отличен от $0$. Будем теперь рассматривать эти символы
как цифры(!) в четырнадцатиричной системе счисления, т.~е. в системе счисления,
основанной на числе $14$ таким же образом, каким десятичная система основана на
числе $10$. Каждое уравнение станет натуральным числом (и различные уравнения
станут различными числами). Уравнения можно пересчитать в порядке возрастания
этих чисел.

\section{Канторовский диагональный метод}
\label{sec:cantor_s_diagonal_method}

Посредством знаменитого ,,диагонального метода`` Кантора было доказано, что в
математике рассматриваются и такие бесконечные множества, которые не могут быть
пересчитаны. Множество \emph{действительных чисел} несчётно.

Рассмотрим сначала \emph{действительные числа} $x$ \emph{в полуинтервале}\
${0<x\leqslant 1}$. Каждое действительное число из этого полуинтервала
однозначно представляется посредством некоторой правильной бесконечной
десятичной дроби, т.~е. десятичной дроби, первая значащая цифра которой стоит
правее запятой и в которой имеется бесконечно много цифр, отличных от $0$. Число
может представляться в виде конечной десятичной дроби, т.~е. дроби с
повторяющимися нулями, но такую дробь можно заменить на бесконечную с
повторяющимися девятками. Например‚ ${0,483}$ или ${0,483000\ldots}$ можно
заменить на ${0,482999\ldots}$. Обратно, каждая правильная бесконечная
десятичная дробь представляет единственное число из этого полуинтервала.

Допустим теперь, что
\begin{equation*}
x_{0},\; x_{1},\; x_{2},\; x_{3},\;\ldots
\end{equation*}

\noindent%
--- бесконечный перечень или пересчёт некоторых, но не обязательно
всех, действительных чисел, принадлежащих этому полуинтервалу. Напишем теперь
одну под другой соответствующие им бесконечные десятичные дроби
% \xymatrix@C=0.125em@R=1ex{
\begin{equation*}
  \xymatrix@!@=0ex{
    0,&x_{00}\ar@{->}[dr]&x_{01}&x_{02}&x_{03}&\ldots\\
    0,&x_{10}&x_{11}\ar@{->}[dr]&x_{12}&x_{13}&\ldots\\
    0,&x_{20}&x_{21}&x_{22}\ar@{->}[dr]&x_{23}&\ldots\\
    0,&x_{30}&x_{31}&x_{32}&x_{33}\ar@{->}[dr]&\ldots\\
    &\ldots\text{.}&&&&&
  }
\end{equation*}

%% ======================= Страница 14 =======================
Образуем диагональную дробь, указанную стрелками. Заменим в ней каждую из
последовательных цифр $x_{nn}$ на отличную от неё цифру $x_{nn}'$ так, чтобы
при этом не получилась конечная дробь. Например, пусть ${x_{nn}'=5}$‚ если
${x_{nn}\neq 5}$, и ${x_{nn}'=6}$‚ если ${x_{nn}=5}$.

Полученная дробь
\begin{equation*}
0,\; x_{00}'\: x_{11}'\: x_{22}'\: x_{33}'\:\ldots
\end{equation*}


\noindent%
представляет некоторое действительное число $x$, которое принадлежит нашему
полуинтервалу, но не входит в рассматриваемый пересчёт. Действительно, эта дробь
отличается от первой из данных дробей своей первой цифрой после запятой, от
второй --- своей второй цифрой после запятой, от третьей --- третьей цифрой
после запятой и т.~д.

Поэтому данный пересчёт не является пересчётом всех действительных чисел
полуинтервала ${0<x\leqslant 1}$. Пересчёта всех действительных чисел этого
полуинтервала не существует.

Чтобы применить диагональный метод ко всем действительным числам, не
ограничиваясь полуинтервалом ${0<x\leqslant 1}$, достаточно представить
действительные числа в форме характеристика-плюс-мантисса‚ например
${37,142\ldots =37+0,142\ldots}$, ${-2,813\ldots =-3+0,186\ldots}$, и применить
этот метод к мантиссам.

Ясно, что этим обнаруживается существенное различие между множеством
рациональных чисел или множеством алгебраических чисел с одной стороны, и
множеством действительных чисел с другой.

Исторически интересно отметить, как открытия Кантора \cite{cantor1874}
(см.~библиографию) проливают свет на более раннее открытие Лиувилля в 1844~г.
Лиувилль при помощи особого метода сумел построить некоторые трансцендентные
(т.~е. неалгебраические) действительные числа. Канторовский диагональный метод
позволяет обнаружить существование трансцендентных чисел с помощью очень общих
изложенных выше соображений. В самом деле, для любого данного пересчёта
$x_0$,~$x_1$,~$x_2$,~$x_3$,~$\ldots$ алгебраических чисел при помощи
диагонального метода можно получить индивидуальные трансцендентные числа.

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

Другим примером несчётного множества служит множество (однозначных) функций, у
которых как независимая, так и зависимая переменная пробегают счётное множество.
Для определённости рассмотрим множество всех \emph{функций от натурального
числа, принимающих натуральные числа в качестве значений} (иначе говоря,
множество всех \emph{бесконечных последовательностей натуральных чисел}).
Допустим, что дан пересчёт некоторых, не обязательно всех, таких функций
\begin{equation*}
f_{0}(n),\;\;\; f_{1}(n),\;\;\; f_{2}(n),\;\;\; f_{3}(n),\;\;\;\ldots\text{.}
\end{equation*}

Напишем последовательности значений идущих друг за другом функций одну под
другой, как строки бесконечной матрицы
\begin{equation*}
  \xymatrix@!@=0ex{
    f_{0}(0)\ar@{->}[dr]&f_{0}(1)&f_{0}(2)&f_{0}(3)&\ldots\\
    f_{1}(0)&f_{1}(1)\ar@{->}[dr]&f_{1}(2)&f_{1}(3)&\ldots\\
    f_{2}(0)&f_{2}(1)&f_{2}(2)\ar@{->}[dr]&f_{2}(3)&\ldots\\
    f_{3}(0)&f_{3}(1)&f_{3}(2)&f_{3}(3)\ar@{->}[dr]&\ldots\\
    &&\ldots\text{.}&&&
  }
\end{equation*}

%% ======================= Страница 15 =======================
\noindent%
Возьмём последовательность значений, стоящих на диагонали. Изменим каждое из
этих значений, например прибавляя $1$. Функция ${f(n)}$ с полученной
последовательностью значений, которую можно записать в виде
\begin{equation*}
f(n)=f_{n}(n)+1\text{,}
\end{equation*}

\noindent%
не может принадлежать нашему пересчёту, так как она отличается от первой из
пересчитанных функций значением, которое она принимает для $0$, от второй ---
значением для $1$ и т.~д.

Чтобы иначе выразить это рассуждение, допустим, что функция ${f(n)}$ входит в
пересчёт, т.~е. допустим, что для некоторого натурального числа $q$
\begin{equation*}
f(n)=f_{q}(n)\text{,}
\end{equation*}

\noindent%
каково бы ни было натуральное число $n$. Подставляя число $q$ вместо переменного
$n$ в это и в предыдущее уравнения, получаем
\begin{equation*}
f(q)=f_{q}(q)=f_{q}(q)+1\text{.}
\end{equation*}

\noindent%
Это невозможно, потому что натуральное число ${f_{q}(q)}$ не может равняться
самому себе, увеличенному на единицу.

Дальнейшим примером несчётного множества служит множество всех \emph{множеств
натуральных чисел}. (Но множество всех конечных множеств натуральных чисел
счётно. Почему?) Мы можем выразить множество натуральных чисел посредством
\emph{представляющей функции}, которая принимает значение $0$ для натуральных
чисел, принадлежащих этому множеству, и значение $1$ для остальных натуральных
чисел. Последовательность значений представляющей функции некоторого множества
натуральных чисел --- бесконечная последовательность из $0$ и $1$. Например, эта
последовательность для множества, содержащего $0$, $2$ и $3$ и не содержащего
$1$ и $4$, начинается с ${01001\ldots}$. Эти последовательности берутся в
качестве строк бесконечной матрицы. Изменения, которые производятся на
диагонали, --- это взаимная замена $0$ и $1$.

Могут ли эти несчётные множества быть поставлены друг с другом в
\isom-соответствие и нет ли ещё и других типов бесконечных множеств?
Рекомендуем читателю попытаться самостоятельно ответить на эти вопросы
(ответы даны в \textsection~\ref{sec:higher_transfinite_cardinals}). Рассмотрим
теперь теорию Кантора в её общем виде.

\section{Кардинальное число}
\label{sec:cardinal_number}

Канторовская теория ,,абстрактных множеств`` имеет дело с множествами вообще.
(Кантор построил также теорию ,,точечных множеств``.) Введённые им термины
\emph{множество} и \emph{элемент} Кантор описывает следующим образом: <<Под
,,множеством`` мы понимаем любое объединение в одно целое $M$ определённых
вполне различаемых объектов $m$ из нашего восприятия или мысли (которые
называются ,,элементами`` $M$)>>~\cite[стр.~481]{cantor1895}.

К множествам присоединяются \emph{пустое} множество, не имеющее элементов, и
\emph{единичные} множества, каждое из которых обладает одним единственным
элементом. Пустое множество мы будем обозначать через
$\OLemptyset$~\footnote{Употребляется также
обозначение $\Lambda$. --- \textit{Прим. ред.}}, единичное множество с
единственным элементом $a$ --- через $\{a\}$, а множество с элементами
$a$,~$b$,~$c$,~$\ldots$ --- через ${\{a,b,c,\ldots\}}$.

Множество называют также \emph{совокупностью}, \emph{классом}, \emph{системой},
\emph{семейством}, \emph{комплексом}, \emph{областью}~\footnote{В подлиннике ---
\textit{aggregate, collection, class, domain, totality}. --- \textit{Прим.
ред.}}. То, что $a$ является элементом $M$, можно
%% ======================= Страница 16 =======================
выразить ещё словами: $a$ есть \emph{член} $M$, или \emph{принадлежит} $M$, или
\emph{находится} в $M$, или \emph{входит} в $M$; символически $a\in M$. Если $a$
не является элементом $M$, то в символах это записывается так:
${a\OLnotin M}$~\footnote{В зарубежной литературе (в том числе в подлиннике)
вместо ${a\in M}$ пишут также ${a\,\mathcal{E}\, M}$, а вместо ${a\OLnotin M}$
пишут ${a\,\cancel{\mathcal{E}}\, M}$. --- \textit{Прим. ред.}}.

Мы считаем, что два множества $M$ и $N$ совпадают (и пишем ${M=N}$)‚ если они
имеют одни и те же элементы, т.~е. ${a\in M}$ для любого предмета $a$ тогда и
только тогда, когда ${a\in N}$.

Два множества $M$ и $N$ мы называем \emph{эквивалентными} (и пишем ${M\sim N}$),
если существует \isom-соответствие (\textsection~\ref{sec:enumerable_sets})
между ними. (Иногда мы будем писать ,,соответствие  ${M\sim N}$`` для
обозначения некоторого индивидуального \isom-соответствия между $M$ и $N$,
которое должно существовать, если ${M\sim N}$.)

Отношение  ${M\sim N}$, очевидно, ,,рефлексивно``, ,,симметрично`` и
,,транзитивно``, т.~е. для любых множеств $M$, $N$ и $P$ справедливы
соотношения: ${M\sim M}$; если ${M\sim N}$, то ${N\sim M}$; если ${M\sim N}$ и
${N\sim P}$, то ${M\sim P}$.

\emph{Кардинальное число} множества $M$ вводится как некоторый объект
$\OLcard{M}$‚ сопоставляемый всем тем и только тем множествам, которые
эквивалентны $M$ (включая само $M$). По этому определению
${\OLcard{M}=\OLcard{N}}$ тогда и только тогда, когда ${M\sim N}$.

Что представляют собой, помимо сказанного, кардинальные числа --- это, пожалуй,
несущественно, но мы всё же отметим некоторые интерпретации. Кантор описывает
их следующим образом: <<То общее понятие, которое мы получаем с помощью нашей
интеллектуальной активности, когда, отправляясь от множества $M$‚ мы
абстрагируемся от природы его различных элементов и от порядка, в котором они
нам даны, мы называем ,,мощностью`` или ,,кардинальным числом`` множества $M$>>.
Эта двойная абстракция подсказывает канторовское обозначение
<<$\dbloverline{M}$>> для кардинального числа множества $M$.
Фрэге~\cite{frege1884} и Рассел~\cite{russel1902} отождествляют кардинальное
число $\OLcard{M}$ с множеством множеств, эквивалентных $M$, тогда как
Нейман~\cite{neumann1928}
% TODO: уточнить ibid предыдущей ссылки на билиографию
выбирает в каждом из этих множеств множеств (,,классов эквивалентности``)
некоторое индивидуальное множество, служащее кардинальным числом любого
множества этого класса.

Понятие ,,части`` множества вводится посредством следующего определения.
Множество $M_{1}$ называют \emph{подмножеством} множества $M$ и пишут
${M_{1}\subseteq M}$, если каждый элемент $M_{1}$ является элементом
$M$~\footnote{Во многих зарубежных работах (в том числе в подлиннике) часто для
обозначения того, что $M_{1}$ является подмножеством множества $M$, пишут
${M_{1}\subset M}$. В советской литературе символом ${M_{1}\subset M}$
обозначают обычно утверждение, состоящее в том, что ${M_{1}\subseteq M}$ и
${M_{1}\neq M}$‚ т.~е. что $M_{1}$ является истинным подмножеством множества $M$
(см. ниже). --- \textit{Прим. ред.}}.

\begin{SCEnvWLabel}{Пример 1.}{exmpl:p3-1}{1}
Множество ${\{ a, b, c\}}$ из трёх элементов $a$,~$b$,~$c$ имеет восемь
(${=2^{3}}$) подмножеств:
$\OLemptyset$, ${\{ a\}}$, ${\{ b\}}$, ${\{ c\}}$,
${\{ a, b\}}$, ${\{ a, c\}}$, ${\{ b, c\}}$, ${\{ a, b, c\}}$.
\end{SCEnvWLabel}

Заметим, что среди подмножеств множества $M$ имеются пустое множество
$\OLemptyset$ и само множество $M$. Последнее называется
\emph{неистинным} подмножеством, а остальные подмножества ---
\emph{истинными}~\footnote{Всякое подмножество множества $M$, отличное от
$\OLemptyset$ и $M$ (иначе говоря, всякое непустое истинное
подмножество множества $M$), называется \emph{собственным подмножеством}, или
\emph{правильной частью} множества $M$. --- \textit{Прим. ред.}}. Очевидно, что
если ${M_{2}\subseteq M_{1}}$ и ${M_{1}\subseteq M}$ (сокращённо
${M_{2}\subseteq M_{1}\subseteq M}$)‚ то ${M_{2}\subseteq M}$.

\emph{Объединением}, или \emph{суммой}
${M\OLcup N}$ двух множеств $M$ и $N$ называется множество
предметов, принадлежащих хотя бы одному из множеств $M$ и $N$ (т.~е.
принадлежащих множеству $M$ или множеству $N$), а их \emph{пересечением},
или \emph{общей частью} ${M\OLcap N}$ называется множество
предметов, принадлежащих
%% ======================= Страница 17 =======================
обоим множествам $M$ и $N$ (т.~е. принадлежащих множеству $M$ и множеству $N$).
Аналогично для более чем двух множеств. \emph{Разность}
${M\OLsetminus N}$ множеств $M$ и $N$ (при ${N\subseteq M}$,
называемая также \emph{дополнением} множества $N$ \emph{до множества} $M$ или
\emph{в множестве} $M$) определяется как множество предметов, принадлежащих $M$,
но не принадлежащих $N$\olNt{~\footnote{Часто сумма множеств $M$ и $N$
обозначается ${M\cup N}$, их пересечение ${M\cap N}$ и их разность
${M\setminus N}$. --- \textit{Прим. ред.}}}{}.
%
% исправлена ошибка. В оригинале было
% "обоим множествам M и N (т. е. принадлежащих множеству M или множеству N)."
% но очевидно, что имелось в виду
% "обоим множествам M и N (т. е. принадлежащих множеству M _и_ множеству N)."
%

\begin{SCEnvWLabel}{Пример 2.}{exmpl:p3-2}{2}
${\{ a, b, c\}\OLcup\{ b, d\}=\{ a, b, c, d\}}$,
${\{ a, b, c\}\OLcap\{ b, d\}=\{ b\}}$,
${\{ a, b, c\}\OLsetminus\{ b, d\}=
\{ a, b, c\}\OLsetminus\{ b\}=
\{ a, c\}}$.
\end{SCEnvWLabel}

Очевидно, ${M\OLsetminus M_{1}\subseteq M}$; в случае, если
${M_{1}\subseteq M}$, и только в этом случае,
${M_{1}\OLcup\left(M\OLsetminus M_{1}\right)=M}$. Два множества $M$
и $N$ \emph{не пересекаются}, если они не имеют общих элементов, т.~е. если
${M\OLcap N=\OLemptyset}$. Например, $M_{1}$ и ${M\OLsetminus M_{1}}$ не
пересекаются. Если $M$ и $N$ не пересекаются, то или ${M\neq N}$, или
${M=N=\OLemptyset}$.

Обратимся к важному вопросу сравнения кардинальных чисел. Если даны два
множества $M$ и $N$ , то может существовать \isom-соответствие между $M$ и
некоторым подмножеством $N_{1}$ множества $N$, а может такого соответствия не
существовать. С другой стороны, может существовать, а может и не существовать
подмножество $M_{1}$ множества $M$, эквивалентное $N$. Комбинируя эти две
возможности, мы получаем четыре случая, один и только один из которых должен
иметь место для любой данной пары множеств $M$ и $N$:

\begin{enumerate}
 \item[(1a)]\itemlabel{case:p3-1a}{(1a)}
 Для некоторого $N_{1}$ выполняется соотношение  ${M\sim N_{1}\subseteq N}$, но
 ни для какого $M_{1}$ не выполняется соотношение ${N\sim M_{1}\subseteq M}$.
 \item[(1b)]\itemlabel{case:p3-1b}{(1b)}
 Ни для какого $N_{1}$ не выполняется соотношение ${M\sim N_{1}\subseteq N}$‚ но
 для некоторого $M_{1}$ выполняется соотношение ${N\sim M_{1}\subseteq M}$.
 \item[(2)]\itemlabel{case:p3-2}{(2)}
 Для некоторого $N_{1}$ выполняется соотношение ${M\sim N_{1}\subseteq N}$ и
 для некоторого $M_{1}$ выполняется соотношение ${N\sim M_{1}\subseteq M}$.
 \item[(3)]\itemlabel{case:p3-3}{(3)}
 Ни для какого $N_{1}$ не выполняется соотношение ${M\sim N_{1}\subseteq N}$ и
 ни для какого $M_{1}$ не выполняется соотношение ${N\sim M_{1}\subseteq M}$.
\end{enumerate}

В случае~\ref{case:p3-1a} говорят, что кардинальное число множества $M$
\emph{меньше}, чем кардинальное число множества $N$ (обозначается
${\OLcard{M}<\OLcard{N}}$). Чтобы оправдать рассмотрение $<$ как отношения между
кардинальными числами $\OLcard{M}$ и $\OLcard{N}$, а не просто между множествами
$M$ и $N$, следует заметить, что если ${M'\sim M}$ и ${N'\sim N}$, то
случай~\ref{case:p3-1a} имеет место для пары множеств $M'$, $N'$ тогда и только
тогда, когда он имеет место для пары $M$, $N$.

Отношение порядка для кардинальных чисел транзитивно, т.~е. для любых трёх
кардинальных чисел  $\OLcard{M}$,~$\OLcard{N}$,~$\OLcard{P}$ из
${\OLcard{M}<\OLcard{N}}$ и ${\OLcard{N}<\OLcard{P}}$ следует
${\OLcard{M}<\OLcard{P}}$.

Положим по определению ${\OLcard{M}>\OLcard{N}}$‚ если
${\OLcard{N}<\OLcard{M}}$. Тогда соотношение ${\OLcard{M}>\OLcard{N}}$ имеет
место в точности в случае~\ref{case:p3-1b}.

Отношение ${\OLcard{M}=\OLcard{N}}$‚ т.~е. ${M\sim N}$, очевидно, подпадает под
случай~\ref{case:p3-2}, если выбрать в качестве $N_{1}$ и $M_{1}$ несобственные
подмножества. Следовательно, для любых двух кардинальных чисел и $\OLcard{M}$ и
$\OLcard{N}$ три отношения ${\OLcard{M}<\OLcard{N}}$, ${\OLcard{M}=\OLcard{N}}$
и ${\OLcard{M}>\OLcard{N}}$ ,,взаимно исключают друг друга``, иначе говоря, не
более чем одно из них может иметь место.

Только после значительного продвижения в рассматриваемой теории (см. ссылки в
\textsection~\ref{sec:higher_transfinite_cardinals}) можно выяснить, являются ли
эти три отношения ,,исчерпывающими``, другими словами, должно ли иметь место
хотя бы одно из них. Ситуация отчасти прояснится в результате следующей теоремы,
после которой останется только вопрос, может ли встретиться
случай~\ref{case:p3-3}.
%% ======================= Страница 18 =======================

\section{Теорема эквивалентности, конечные и бесконечные множества}
\label{sec:the_equivalence_theorem_finite_and_infinite_sets}

\begin{SCEnvWLabel}{Теорема A.}{theorem:A}{A}
\emph{Если} ${M\sim N_{1}\subseteq N}$ и ${N\sim M_{1}\subseteq M}$‚ \emph{то}
${M\sim N}$. Другими словами, \emph{в
случае}~\ref{case:p3-2}~\textsection~\ref{sec:cardinal_number}
\emph{обязательно} ${\OLcard{M}=\OLcard{N}}$. (Бернштейн~\cite{bernstein1898}.)
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:A-proof}{A-proof}
По условию, можно считать, что дано некоторое \isom-соответствие
${M\simN{1}N_{1}}$ между $M$ и подмножеством $N_{1}$ множества $N$ и аналогично
${N\simN{2}M_{1}}$. Задача состоит в том, чтобы найти третье \isom-соответствие
${M\simN{3}N}$.

Пусть ${A_{0}=M\OLsetminus M_{1}}$. В данном соответствии ${M\simN{1}N_{1}}$
элементы подмножества $A_{0}$ множества $M$ будут отвечать элементам, образующим
некоторое подмножество $B_{1}$ множества $N_{1}$ (а значит, и множества $N$),
или, в символах, ${A_{0}\simN{1}B_{1}}$. Тогда в другом данном соответствии
${N\simN{2}M_{1}}$ элементы подмножества $B_{1}$ множества $N$ будут отвечать
элементам, образующим подмножество $A_{1}$ множества $M_{1}$ (а значит, и
множества $M$), или, в символах, ${B_{1}\simN{2}A_{1}}$, и т.~д. Итак,
\begin{equation*}
A_{0}\simN{1}
B_{1}\simN{2}
A_{1}\simN{1}
B_{2}\simN{2}
A_{2}\simN{1}
B_{3}\simN{2}
A_{3}\simN{1}
\ldots\text{.}
\end{equation*}

Эту ситуацию можно описать, изображая $M$ и $N$ в виде зеркал, в которых часть
$A_{0}$ множества $M$, лежащая вне $M_{1}$, многократно отражается, порождая
бесконечную последовательность изображений $A_{1}$,~$A_{2}$,~$A_{3}$,~$\ldots$ в
$M$ и $B_{1}$,~$B_{2}$,~$B_{3}$,~$\ldots$ в $N$, как показано на чертеже
(Множества $M$, $M_{1}$ и $N$ изображены частями горизонтальных линий направо от
надписей <<$M$>>, <<$M_{1}$>> и <<$N$>>, множества
$A_{0}$,~$B_{1}$,~$A_{1}$,~$\ldots$ --- выделенными отрезками.)

\begin{center}
% original size
%\center{\includegraphics[width=0.6318957\linewidth]{p4_img0.eps}}
\includegraphics[width=0.6666667\linewidth]{p4_img0.eps}
\end{center}

Пусть ${A=A_{0}\OLcup A_{1}\OLcup A_{2}\OLcup A_{3}\OLcup\ldots}$, т.~е. $A$
есть подмножество $M$, содержащее те элементы, которые попадают в $A_{0}$ или в
любое из его изображений $A_{1}$,~$A_{2}$,~$A_{3}$,~$\ldots$ в $M$. Пусть также
${B=B_{1}\OLcup B_{2}\OLcup B_{3}\OLcup\ldots}$, т.~е. $B$ есть подмножество
$N$, содержащее те его элементы, которые попадают в одно из изображений
$B_{1}$,~$B_{2}$,~$B_{3}$,~$\ldots$ множества $A_{0}$ в $N$.

Чтобы получить \isom-соответствие ${M\simN{3}N}$, мы установим правило,
которое для каждого элемента $m$ множества $M$ определяет соответствующий
элемент $n$ множества $N$, и докажем, что полученное соответствие является
\isom-соответствием между $M$ и $N$.

\begin{SCEnvWLabel}{Правило.}{theorem:A-proof-rule}{A-proof-rule}
Рассмотрим любой элемент $m$ множества $M$. Или $m$ принадлежит подмножеству
$A$, или $m$ не принадлежит $A$, т.~е. $m$ принадлежит ${M\OLsetminus A}$. Если
$m$ принадлежит $A$, то соответствующим элементом $n$ из $N$ будет тот, который
сопоставляется с $m$ в соответствии ${M\simN{1}N_{1}}$. Если $m$
принадлежит ${M\OLsetminus A}$ (в этом случае $m$ принадлежит $M_{1}$), то
соответствующим элементом $n$ из $N$ будет тот, с которым $m$ сопоставлен в
соответствии ${N\simN{2}M_{1}}$.
\end{SCEnvWLabel}

Полученное соответствие является \isom-соответствием между $M$ и $N$, так как:

{\everypar{(a) } Различным элементам $m$ из $M$, например $m_{1}$ и $m_{2}$‚
соответствуют различные элементы $n_{1}$ и $n_{2}$ из $N$. Это ясно, когда
$m_{1}$ и $m_{2}$ оба принадлежат $A$ или оба принадлежат ${M\OLsetminus A}$. Но
это ясно и когда ${m_{1}\in A}$ и ${m_{2}\in M\OLsetminus A}$, потому что тогда
${n_{1}\in B}$ и ${n_{2}\in N\OLsetminus B}$.}
%% ======================= Страница 19 =======================

{\everypar{(b) } Каждый элемент из $N$ соответствует некоторому элементу $m$ из
$M$. Именно, все элементы $B$ соответствуют элементам $A$, а все элементы
${N\OLsetminus B}$ соответствуют элементам ${M\OLsetminus A}$.}

Этот метод приведения $M$ и $N$ в \isom-соответствие можно рассматривать как
сдвиг на предыдущем чертеже каждой из частей
$A_{0}$,~$A_{1}$,~$A_{2}$,~$A_{3}$,~$\ldots$ множества $M$ на одно положение
вправо, так что $A_{0}$ переходит на место $A_{1}$, $A_{1}$ --- на место
$A_{2}$, $A_{2}$ --- на место $A_{3}$, $\ldots$. При этом ${N\simN{2}M_{1}}$
превратится в ${N\simN{3}M}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Следствие A.}{theorem:A-corollary-A}{A}
\emph{Если} ${M\subseteq N}$, \emph{то} ${\OLcard{M}\leqslant\OLcard{N}}$.
\end{SCEnvWLabel}

(${\OLcard{M}\leqslant\OLcard{N}}$ означает, что ${\OLcard{M}<\OLcard{N}}$ или
${\OLcard{M}=\OLcard{N}}$.) Действительно, если ${M\subseteq N}$‚ то имеет место
или случай~\ref{case:p3-1a}, или случай~\ref{case:p3-2} с $M$ в качестве
$N_{1}$.

Кардинальное число пустого множества $\OLemptyset$ мы будем обозначать через
$0$. (\textsc{Замечание:}\ ${M'\sim\OLemptyset}$ только при ${M'=\OLemptyset}$.)
Кардинальное число любого множества ${N\OLcup\{ a\}}$, где ${a\OLnotin N}$‚ мы
будем обозначать через ${\OLcard{N}+1}$. (\textsc{Замечание:}\
${M'\sim N\OLcup\{ a\}}$‚ где ${a\OLnotin N}$, тогда и только тогда, когда
${M'=N'\OLcup\{ a'\}}$, где ${a'\OLnotin N'}$ и ${N'\sim N}$.)

Если рассматривать натуральные числа
$0$,~$1$,~$2$,~$\ldots$,~$n$,~${n+1}$,~$\ldots$ как последовательность уже
известных нам предметов, то два только что сформулированных определения
сопоставляют каждому натуральному числу $n$ соответствующее кардинальное число,
которое мы также будем обозначать через $n$. Эти кардинальные числа мы будем
называть \emph{конечными кардинальными числами}, а множества с этими
кардинальными числами --- \emph{конечными множествами}. Следующие два
предложения будут доказаны в примере%
~\ref{exmpl:p7-1}~\textsection~\ref{sec:mathematical_induction}

{\everypar{(1) }\itemlabel{prop:p4-1}{(1)} \emph{Для каждого натурального числа}
$n$ \emph{конечное кардинальное число} $n$ \emph{служит кардинальным числом для
множества натуральных чисел}, \emph{предшествующих натуральному числу} $n$
\emph{в их обычном порядке}; \emph{или}, \emph{в символах},
${n=\OLcard{\{0, 1, 2, \ldots, n-1\}}}$.}

{\everypar{(2) }\itemlabel{prop:p4-2}{(2)} \emph{Если} ${\OLcard{M}=n}$
(\emph{для натурального} $n$) \emph{и} ${M\sim M_{1}\subseteq M}$, \emph{то}
${M_{1}=M}$. Иначе говоря, \emph{конечное множество не эквивалентно никакому
своему истинному подмножеству}.}

Из этих двух предложений нетрудно усмотреть, что отношение равенства ${m=n}$ и
отношение порядка ${m<n}$, установленные для конечных кардинальных чисел
определениями~\textsection~\ref{sec:cardinal_number}, согласуются с обычными
отношениями равенства и порядка для натуральных чисел (в частности, ${n<n+1}$
для конечных кардинальных чисел). Итак, не возникнет никакой путаницы, если мы
отождествим натуральные числа с конечными кардинальными числами.

Множество, не являющееся конечным, мы будем называть \emph{бесконечным}, а его
кардинальное число --- \emph{бесконечным} или \emph{трансфинитным кардинальным
числом}. Кардинальное число множества всех натуральных чисел, а следовательно, и
каждого счётно-бесконечного множества~(\textsection~\ref{sec:enumerable_sets})
мы будем называть $\alephZero$ (читается <<алеф-нуль>>).

\begin{SCEnvWLabel}{Следствие B.}{theorem:A-corollary-B}{B}
\emph{Если} $n$ --- \emph{конечное кардинальное число}, \emph{то}
${n<\alephZero}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:A-corollary-B-proof}%
{A-corollary-B-proof}
Так как $n$ --- кардинальное число подмножества ${\{ 0, 1, 2, \ldots, n-1\}}$
множества всех натуральных чисел, то в силу
следствия~\ref{theorem:A-corollary-A} ${n\leqslant\alephZero}$. Допустим, что
${n=\alephZero}$. Так как ${n+1}$ также конечное
%% ======================= Страница 20 =======================
кардинальное число, то аналогично ${n+1\leqslant\alephZero}$‚ что вместе с
${n=\alephZero}$ даёт ${n+1\leqslant n}$, в противоречие с ${n<n+1}$.
Следовательно, допущение ${n=\alephZero}$ неверно и остаётся единственная
возможность: ${n<\alephZero}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Теорема B.}{theorem:B}{B}
\emph{Всякое бесконечное множество} $M$ \emph{имеет счётно-бесконечное подмножество}.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:B-proof}{B-proof}
Множество $M$ непусто, так как в противном случае оно имело бы конечное
кардинальное число $0$. Поэтому в $M$ имеется некоторый элемент $a_{0}$. Тогда
${M\OLsetminus\{ a_{0}\}}$ непусто, так как в противном случае $M$ имело бы
конечное кардинальное число $1$. Поэтому в $M$ имеется другой элемент $a_{1}$.
Продолжая таким образом, мы выберем различные элементы $a_{0}$,~$a_{1}$,~%
$a_{2}$,~$a_{3}$,~$\ldots$, соответствующие натуральным числам $0$,~$1$,~$2$,~$3$,~$\ldots$, что доказывает теорему. Если $P$ есть множество ${M\OLsetminus\{ a_{0}, a_{1}, a_{2}, a_{3}, \ldots\}}$ невыбранных элементов $M$, то
\begin{equation*}
M=P\OLcup\{ a_{0}, a_{1}, a_{2}, a_{3}, \ldots\}\text{.}
\end{equation*}
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Следствие A.}{theorem:p4-B-corollary-A}{B-corollary-A}
\emph{Если} $\OLcard{M}$ --- \emph{бесконечное кардинальное число}, \emph{то}
${\alephZero\leqslant\OLcard{M}}$.
\end{SCEnvWLabel}

Для доказательства надо воспользоваться теоремой~\ref{theorem:B} и
следствием~\ref{theorem:A-corollary-A} из теоремы~\ref{theorem:A}.

\begin{SCEnvWLabel}{Следствие B.}{theorem:B-corollary-B}{B-corollary-B}
\emph{Бесконечное множество} $M$ \emph{эквивалентно некоторому своему истинному
подмножеству}.
\end{SCEnvWLabel}

Действительно, $M$ (в тех же обозначениях, что и выше) эквивалентно своему
истинному подмножеству
\begin{equation*}
M\OLsetminus\{ a_{0}\}=P\OLcup\{ a_{1}, a_{2}, a_{3}, a_{4}, \ldots\}\text{.}
\end{equation*}

Это следствие вместе с приведённым выше предложением~\ref{prop:p4-2} было
предложено Дедекиндом~\cite{dedekind1888} в качестве другого определения
различия между конечными и бесконечными множествами. (Таким образом, свойство,
отмеченное в <<парадоксе>> Галилея, оказывается характеристическим для
бесконечных множеств.)

\begin{SCEnvWLabel}{Следствие C.}{theorem:B-corollary-C}{B-corollary-C}
\emph{Кардинальное число любого бесконечного множества} $M$ \emph{не изменяется
от присоединения к} $M$ \emph{конечного или счётно-бесконечного множества
элементов}.
\end{SCEnvWLabel}

Действительно, новые элементы $b_{0}$,~$b_{1}$,~$b_{2}$,~$b_{3}$,~$\ldots$ можно
ввести так:
\begin{equation*}
M\OLcup\{ b_{0}, b_{1}, b_{2}, b_{3}, \ldots\}=
P\OLcup\{ a_{0}, b_{0}, a_{1}, b_{1}, \ldots \}\text{.}
\end{equation*}

Обратно, это следствие утверждает, что удаление счетного множества элементов из
некоторого множества не изменяет кардинального числа при условии, что остающееся
множество $M$ бесконечно. Если первоначальное множество несчетно, то остающееся
множество должно быть бесконечным, потому что в противном случае имелся бы
очевидный пересчет первоначального множества. Итак:

\begin{SCEnvWLabel}{Следствие D.}{theorem:B-corollary-D}{D}
\emph{Кардинальное число несчётного множества не изменится от удаления конечного или счётно-бесконечного подмножества элементов}.
\end{SCEnvWLabel}
%% ======================= Страница 21 =======================

\section{Высшие трансфинитные числа}
\label{sec:higher_transfinite_cardinals}

%
% для следующах двух абзацев рассмотреть возможность добавления ссылок
% к прописным ссылкам:
% "в последнем примере"
% "эту теорему"
% "её лемму"
% "Вторая теорема"
% "теоремой эквивалентности"
% "теоремой эквивалентности" второй раз
%
Первая из теорем этого параграфа является общей формулировкой той ситуации, с
которой мы встретились в последнем
примере~\textsection~\ref{sec:cantor_s_diagonal_method}. Для читателя будет
полезно, если он попробует самостоятельно рассмотреть эту теорему или её лемму
для случая, когда $M$ --- небольшое конечное множество. Вторая теорема является
обобщением той ситуации, с которой мы столкнулись в
следствии~\ref{theorem:A-corollary-B} из теоремы~\ref{theorem:A}.

Чтобы проще изложить доказательства, мы воспользуемся теоремой эквивалентности,
а именно её следствием~\ref{theorem:A-corollary-A}. Но можно доказать эти
теоремы, только слегка изменив рассуждения, и не пользуясь теоремой
эквивалентности.

\begin{SCEnvWLabel}{Лемма A.}{lemma:A}{A}
\emph{Если} $\setOfSets{S}$ --- \emph{некоторая совокупность подмножеств
множества} $M$ \emph{и} ${M\sim\setOfSets{S}}$, \emph{то имеется подмножество}
$T$ \emph{множества} $M$‚ \emph{которое не принадлежит} $\setOfSets{S}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство}{lemma:A-proof}{A-proof}
проводится с помощью диагонального метода Кантора. Подмножество $M$ определено,
если установлено, каковы те элементы $M$, которые принадлежат этому
подмножеству. Этого можно добиться, установив общий критерий, который для любого
элемента $m$ множества $M$ определяет, принадлежит этот элемент подмножеству или
не принадлежит. Дадим теперь критерий такого рода для определения подмножества
$T$.

\begin{SCEnvWLabel}{Критерий.}{lemma:A-proof-criterion}{A-proof-criterion}
В \isom-соответствии, которое дано по условию ${M\sim\setOfSets{S}}$, любой
элемент $m$ множества $M$ отвечает некоторому элементу $S$ множества
$\setOfSets{S}$. Но $S$ является одним из подмножеств $M$. Следовательно, или
$m$ принадлежит $S$, или $m$ не принадлежит $S$. Если $m$ принадлежит $S$, то
$m$ не будет принадлежать $T$. Если $m$ не принадлежит $S$, то $m$ будет
принадлежать $T$.
\end{SCEnvWLabel}

Допустим теперь, в противоречие с утверждением леммы, что $T$ принадлежит
$\setOfSets{S}$. Выберем тот элемент $M$, скажем $m_{1}$‚ который отвечает $T$ в
\isom-соответствии ${M\sim\setOfSets{S}}$.

Принадлежит ли $m_{1}$ множеству $T$? Применяем критерий с $m_{1}$ в качестве
$m$. Так как $m_{1}$ соответствует $T$, то в качестве подмножества $S$ критерия
надо взять $T$. Критерий приводит к противоречию как в том случае, когда
$m_{1}$ принадлежит $T$‚ так и в том, когда $m_{1}$ не принадлежит $T$.

Таким образом, предположение, что $T$ принадлежит $\setOfSets{S}$, приводит к
противоречию. Поэтому методом \emph{reductio ad absurdum}~\footnote{Приведение к
нелепости (лат.). --- \textit{Прим. перев.}} (согласно которому отрицание
предложения доказывается путём вывода противоречия из этого предложения) мы
заключаем, что $T$ не принадлежит $\setOfSets{S}$.

Если $M$ --- данное множество, то множество всех подмножеств $M$‚ т.~е.
множество, элементами которого служат (все) подмножества множества $M$,
обозначается через $\OLpowerset{M}$\olNt{(<<$\mathfrak{U}$>> от немецкого
<<Untermenge>>~\footnote{<<Untermenge>> означает <<подможество>>. ---
\textit{Прим. ред.}})}{}.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Теорема C.}{theorem:C}{C}
\emph{Для любого множества} $M$ \emph{справедливо соотношение}
${\OLcard{M}<\OLcard{\OLpowerset{M}}}$ (теорема Кантора).
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:C-proof}{C-proof}
Если $N_{1}$ --- совокупность единичных подмножеств множества $M$‚ то
${M\sim N_{1}\subset\OLpowerset{M}}$. Значит, по
следствию~\ref{theorem:A-corollary-A} из теоремы~\ref{theorem:A},
${\OLcard{M}=\OLcard{N_{1}}\leqslant\OLcard{\OLpowerset{M}}}$. Допустим, в
противоречие с теоремой, что ${\OLcard{M}=\OLcard{\OLpowerset{M}}}$, т.~е.
%% ======================= Страница 22 =======================
${M\sim\OLpowerset{M}}$. Тогда $\OLpowerset{M}$ будет удовлетворять условиям для
$\setOfSets{S}$ леммы~\ref{lemma:A}. В силу леммы найдётся подмножество $T$
множества $M$, которое не принадлежит $\OLpowerset{M}$. Это невозможно, потому
что $\OLpowerset{M}$ есть множество всех подмножеств $M$. Следовательно, должно
иметь место неравенство ${\OLcard{M}<\OLcard{\OLpowerset{M}}}$.
\end{SCEnvWLabel}

Если в качестве множества $M$ этой теоремы мы возьмём множество с трансфинитным
кардинальным числом $\alephZero$, мы получим множества
$\OLpowerset{M}$,~$\OLpowerset{\OLpowerset{M}}$,~$\ldots$, которые имеют всё
б{\'o}льшие и б{\'o}льшие трансфинитные кардинальные числа. Эти новые
кардинальные числа обозначаются через
$2^{\alephZero}$,~$2^{2^{\alephZero}}$,~$\ldots$. (Вообще, для любого множества
$M$ кардинальное число множества $\OLpowerset{M}$ обозначается через
$2^{\OLcard{M}}$. Заметим, что это согласуется с обычной арифметикой, если $M$
конечно.)

\begin{SCEnvWLabel}{Лемма B.}{lemma:B}{B}
\emph{Если} $S$ --- \emph{множество}, \emph{а} $\setOfSets{M}$ ---
\emph{некоторое множество подмножеств} $S$ \emph{и для каждого элемента} $M$
\emph{из} $\setOfSets{M}$ \emph{найдётся другой элемент} $M'$ \emph{из}
$\setOfSets{M}$ \emph{такой}, \emph{что} ${\OLcard{M}<\OLcard{M'}}$, \emph{то}
${\OLcard{M}<\OLcard{S}}$ \emph{для каждого элемента} $M$ \emph{из}
$\setOfSets{M}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{lemma:B-proof}{B-proof}
Так как ${M\subseteq S}$, то, по следствию~\ref{theorem:A-corollary-A} из
теоремы~\ref{theorem:A}, ${\OLcard{M}\leqslant\OLcard{S}}$. Допустим, что, в
противоречие с леммой, ${\OLcard{M}=\OLcard{S}}$. Но аналогично
${\OLcard{M'}\leqslant\OLcard{S}}$, что вместе с ${\OLcard{M}=\OLcard{S}}$ даёт
${\OLcard{M'}\leqslant\OLcard{M}}$, в противоречие с ${\OLcard{M}<\OLcard{M'}}$.
Поэтому допущение ${\OLcard{M}=\OLcard{S}}$ ложно и имеет место случай
${\OLcard{M}<\OLcard{S}}$.
\end{SCEnvWLabel}

Если $\setOfSets{M}$ --- множество, элементами которого являются множества, то
множество (всех) предметов, каждый из которых принадлежит некоторому элементу
$M$ из $\setOfSets{M}$, называется \emph{объединением} или \emph{суммой}
множеств, принадлежащих $\setOfSets{M}$, и обозначается посредством
${\OLunion{\setOfSets{M}}}$. Множество предметов, каждый из которых принадлежит
каждому элементу $M$ из $\setOfSets{M}$, называется \emph{пересечением} или
\emph{общей частью} множеств, принадлежащих $\setOfSets{M}$, и обозначается
посредством ${\OLintersec{\setOfSets{M}}}$\olNt{ (<<$\mathfrak{D}$>> от
немецкого <<Durchschnitt>>~\footnote{Пересечение. --- \textit{Прим. ред.}})}{}.
Эти понятия совпадают с введёнными в~\textsection~\ref{sec:cardinal_number}, за
исключением того, что теперь они выражены в виде операций над множеством
$\setOfSets{M}$ множеств $M$, которые складываются или перемножаются. Например,
${M\OLcup N=\OLunion{\{ M, N\}}}$, ${M\OLcap N=\OLintersec{\{ M, N\}}}$.

\begin{SCEnvWLabel}{Теорема D.}{theorem:D}{D}
\emph{Если} $\setOfSets{M}$ --- \emph{некоторое множество множеств и если для
каждого элемента} $M$ \emph{из} $\setOfSets{M}$ \emph{найдётся другои элемент}
$M'$ \emph{из} $\setOfSets{M}$ \emph{такой}, \emph{что}
${\OLcard{M}<\OLcard{M'}}$, \emph{то}
${\OLcard{M}<\OLcard{\OLunion{\setOfSets{M}}}}$ \emph{для каждого элемента} $M$
\emph{из} $\setOfSets{M}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:D-proof}{D-proof}
В силу определения ${\OLunion{\setOfSets{M}}}$ каждый элемент $M$ из
$\setOfSets{M}$ является подмножеством множества ${\OLunion{\setOfSets{M}}}$.
Теперь теорема следует из леммы~\ref{lemma:B}, если взять в ней
${\OLunion{\setOfSets{M}}}$ в качестве $S$.
\end{SCEnvWLabel}

Согласно этой теореме, сумма множеств
$M$,~$\OLpowerset{M}$,~$\OLpowerset{\OLpowerset{M}}$,~$\ldots$, которые
имеют возрастающие трансфинитные кардинальные числа
$\alephZero$,~$2^{\alephZero}$,~$2^{2^{\alephZero}}$,~$\ldots$, является
множеством с ещё б{\'o}льшим трансфинитным кардинальным числом, чем любое из
этих кардинальных чисел. Исходя из этого множества, можно с помощью
теоремы~\ref{theorem:C} получить новую возрастающую последовательность. Эта
иерархия продолжается неограниченно.

Более глубокое изложение канторовской теории абстрактных множеств можно найти,
например, у Кантора~\cite{cantor1895},
{\renewcommand*{\multicitedelim}{\space или\space}%
Хаусдорфа~\cite{hausdorff1914,hausdorff1927}} или у
Френкеля~\cite{fraenkel1928,fraenkel1952}. Имеется родственная отрасль
этой теории, изучающая <<ординальные числа>>. <<Теорема сравнимости для
кардинальных чисел>>, которая утверждает, что возможности
${\OLcard{M}<\OLcard{N}}$, ${\OLcard{M}=\OLcard{N}}$ и
${\OLcard{M}>\OLcard{N}}$
являются исчерпывающими (конец~\textsection~\ref{sec:cardinal_number}),
оказывается следствием из
%% ======================= Страница 23 =======================
,,теоремы о полном упорядочении`` Цермело~\cite{zermelo1904} (см., например,
{\renewcommand*{\multicitedelim}{\space или\space}%
Хаусдорф~\cite[стр.~61\protect\footnotemark]{hausdorff1914,hausdorff1927}
\footnotetext{Стр.~65 русского издания книги Хаусдорфа. См. также теорему~19 на
стр.~107 книги П.~С.~Александрова~\cite{aleksandrov1948} --- \textit{Прим.
ред.}} или Френкель~\cite[стр.~205]{fraenkel1928}. Краткое рассмотрение
знаменитой <<континуум-проблемы>>, состоящей в решении вопроса, существует ли
хоть одно кардинальное число между $\alephZero$ и $2^{\alephZero}$, см. у
Гёделя~\cite{goedel1947}.


Мы начали с рассмотрения теории Кантора по двум противоположным причинам.
Во-первых, некоторые идеи и методы, которые в дальнейшем окажутся основными,
встречаются в ней в их первоначальной и простейшей форме. Во-вторых, в этой
теории, если её проследить достаточно далеко, обнаруживаются логические
трудности, которые явятся отправной точкой нашего основного исследования. Это
будет обнаружено в гл.~\ref{chap:a_critique_of_mathematical_reasons}.

\begin{SCEnvWLabel}{Примеры.}{exmpls:p5}{p5-examples}
\begin{SCEnvWLabel}{Множества с кардинальным числом $2^{\alephZero}$.}%
{exmpl:p5-1}{example-p5-1}
Это --- кардинальное число, приписанное множеству всех подмножеств множества
всех натуральных чисел, которое мы описали
в~\textsection~\ref{sec:cantor_s_diagonal_method} как множество всех
\emph{множеств натуральных чисел}. Там мы представили элементы этого множества
\emph{бесконечными последовательностями из нулей и единиц}. Эти нули и единицы
можно рассматривать как цифры в двоичной (или диадической) системе счисления,
т.~е. в системе счисления, основанной на числе $2$, так же как десятичная
система основана на числе $10$‚ --- так что мы получаем множество всех
\emph{правильных двоичных дробей}. Удаляя с помощью
следствия~\ref{theorem:B-corollary-D} теоремы~\ref{theorem:B} конечные дроби,
которые образуют счётное множество, мы получаем \emph{правильные бесконечные
двоичные дроби}. Они взаимно однозначно представляют все \emph{действительные
числа} $x$ \emph{в полуинтервале} ${0<x\leqslant 1}$. Из правильных бесконечных
двоичных дробей мы взаимно однозначно получаем \emph{бесконечные
последовательности натуральных чисел} или \emph{функции от натурального числа,
принимающие натуральные значения}, сопоставляя каждой дроби ту функцию $f(n)$,
для которой ${f(0)=}$~числу~нулей~(после~запятой) до первой единицы в дроби,
${f(1)=}$числу нулей между первой единицей и второй единицей и т.~д. (например,
функция $n^{2}$ соответствует дроби $0,101000010000000001\ldots$).

Выкинем теперь число ${x=1}$ из полуинтервала ${0<x\leqslant 1}$, после чего
останутся \emph{действительные числа} $x$ \emph{в интервале} ${0<x<1}$. Можно
найти функцию ${y=f(x)}$, которая, в то время как $x$ пробегает этот интервал,
принимает в качестве значения $y$ каждое из \emph{действительных чисел}, и
притом в точности один раз; например, функция ${y=\ctg \pi x}$. Если удалить
рациональные числа, то останутся (действительные) \emph{иррациональные числа};
или, если удалить алгебраические числа, то останутся \emph{трансцендентные
числа}. В аналитической геометрии Декарта действительные числа служат
координатами \emph{точек действительной эвклидовой прямой}. Это множество есть
,,линейный континуум``~\footnote{От латинского слова continuum --- непрерывное.
--- \textit{Прим. перев.}}, и в соответствии с этим кардинальное число
$2^{\alephZero}$ является ,,мощностью континуума``.

Теперь мы можем следующим образом получить множество \emph{упорядоченных пар
действительных чисел} или, рассматривая пару ${(x, y)}$ как декартовы координаты
на плоскости, \emph{точек действительной эвклидовой плоскости}. В силу уже
установленной эквивалентности между действительными числами и бесконечными
последовательностями нулей и единиц любые два действительных числа $x$,~$y$
соответствуют последовательностям нулей и единиц
\begin{equation*}
\begin{array}{llllllll}
x_{0}&\; x_{1}&\; x_{2}&\; x_{3}&\;\ldots\text{,}\\
y_{0}&\; y_{1}&\; y_{2}&\; y_{3}&\;\ldots\text{,}
\end{array}
\end{equation*}
%% ======================= Страница 24 =======================

\noindent%
которые можно свернуть в одну-единственную последовательность
\begin{equation*}
x_{0}\quad y_{0}\quad x_{1}\quad y_{1}\quad x_{2}\quad y_{2}\quad x_{3}\quad y_{3}\quad\ldots\text{,}
\end{equation*}

\noindent%
соответствующую некоторому единственному действительному числу. Обратно, всякая
последовательность может быть по этому методу развёрнута с получением
определённой пары последовательностей. Аналогичный процесс даёт $n$\emph{-ки
действительных чисел} или \emph{точки действительного эвклидова}
$n$\emph{-мерного пространства} для любого фиксированного натурального $n$ и
даже \emph{бесконечные последовательности действительных чисел} или \emph{точки
действительного эвклидова} $\alephZero$\emph{-мерного пространства}. Этот
последний пример можно рассмотреть с помощью
метода~\textsection~\ref{sec:enumerable_sets}, посредством которого $\alephZero$
последовательностей нулей и единиц
\begin{equation*}
  \xymatrix@!@=1.6666667ex{
    x_{00}\ar@{->}[d] &x_{01}\ar@{->}[r]&x_{02}\ar@{->}[dl]&x_{03}\ar@{->}[r]&\ldots\\
    x_{10}\ar@{->}[ur]&x_{11}\ar@{->}[dl]&x_{12}\ar@{->}[ur]&x_{13}&\ldots\\
    x_{20}\ar@{->}[d]&x_{21}\ar@{->}[ur]&x_{22}&x_{23}&\ldots\\
    x_{30}\ar@{->}[ur]&x_{31}&x_{32}&x_{33}&\ldots\\
    &&\ldots\text{.}&&&&
  }
\end{equation*}

\noindent%
свёртываются в одну-единственную последовательность
\begin{equation*}
x_{00}\quad x_{10}\quad x_{01}\quad x_{02}\quad x_{11}\quad x_{20}\quad x_{30}\quad x_{21}\quad x_{12}\quad x_{03}\quad\ldots\text{,}
\end{equation*}

\noindent%
где каждый член каждой из данных последовательностей занимает определённое
положение.

Для всякой \emph{действительной непрерывной функции от действительной
переменной} все значения функции определены по непрерывности, коль скоро заданы
значения функции для рациональных значений независимой переменной. Эти значения
можно задать в виде бесконечной последовательности действительных чисел, если
рациональные числа рассматривать в порядке некоторого их фиксированного
пересчёта. Поэтому в силу следствия~\ref{theorem:A-corollary-A} из
теоремы~\ref{theorem:A} множество этих функций имеет кардинальное число, не
б{\'o}льшее чем $2^{\alephZero}$. Но оно должно иметь по меньшей мере это
кардинальное число и, следовательно, в точности это кардинальное число, потому
что функции\nobreakdash-константы образуют подмножество с этим кардинальным
числом.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Множества с кардинальным числом $2^{2^{\alephZero}}$.}%
{exmpl:p5-2}{example-p5-2}
Это --- кардинальное число множества всех \emph{множеств множеств натуральных
чисел}. Из эквивалентности между множествами натуральных чисел и действительными
числами или точками $n$-мерного или $\alephZero$-мерного пространства следует,
что этим кардинальным числом обладают множество всех \emph{множеств
действительных чисел}, или \emph{точечных множеств действительного эвклидова}
$n$\emph{-мерного} или $\alephZero$\emph{-мерного пространства}.
\emph{Действительные функции от действительной переменной} могут быть
представлены их графиками, которые являются точечными множествами на плоскости,
а потому множество их имеет кардинальное число, не большее $2^{2^{\alephZero}}$.
Оно имеет в точности это кардинальное число, так как функции, принимающие в
качестве значений только $0$ и $1$, служат представляющими функциями для
множеств действительных чисел и тем самым составляют подмножество с этим
кардинальным числом. Распространяя на этот пример геометрическую терминологию,
можно сказать, что мы имеем дело с множеством \emph{точек действительного эвклидова} $2^{\alephZero}$\emph{-мерного пространства}.
\end{SCEnvWLabel}
\end{SCEnvWLabel}

\chapter{Некоторые основные концепции}
\label{chap:some_fundamental_concepts}

\section{Натуральные числа}
\label{sec:the_natural_numbers}

stub

\section{Математическая индукция}
\label{sec:mathematical_induction}

stub

\begin{SCEnvWLabel}{Пример 1.}{exmpl:p7-1}{1}
Докажем
предложения~\ref{prop:p4-1}~и~\ref{prop:p4-2}~%
из~\textsection~\ref{sec:the_equivalence_theorem_finite_and_infinite_sets}
при помощи индукции по $n$. Сделаем это для~\ref{prop:p4-2},
предоставляя~\ref{prop:p4-1} читателю.
\end{SCEnvWLabel}


\section{Системы объектов}
\label{sec:system_of_objects}

stub

\section{Арифметика и анализ}
\label{sec:number_theory_vs_analysis}

stub

\section{Функции}
\label{sec:functions}

stub


\chapter{Критика математических утверждений}
\label{chap:a_critique_of_mathematical_reasons}

\section{Парадоксы}
\label{sec:the_paradoxes}

stub

\section{Первые выводы из парадоксов}
\label{sec:first_inferences_from_the_paradoxes}

stub

\section{Интуиционизм}
\label{sec:intuitionism}

stub

\section{Формализм}
\label{sec:formalism}

stub

\section{Формализация теории}
\label{sec:formalization_of_a_theory}

stub