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

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

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

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

Стадо из четырёх овец и роща из четырёх деревьев находятся между собой в таком
отношении, в каком ни одно из них не находится с кучей из трёх камней или с
рощей из семи деревьев. Хотя для печатного выражения этого труизма мы
использовали слова, обозначающие числа, отношение, о котором идёт речь, само
лежит в основе понятия кардинального числа. Не прибегая к пересчёту овец или
деревьев, их можно попарно сопоставить друг другу, например привязав овец к
деревьям так, что каждая овца и каждое дерево будут принадлежать в точности к
одной паре. Такое попарное соответствие между элементами двух коллекций или
,,множеств`` предметов называется взаимно однозначным или
\emph{одно\nobreakdash-однозначным соответствием} \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{счётно\nobreakdash-бесконечными}, или же конечны.

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

Множество \emph{рациональных чисел} также является счётным, и это обстоятельство
может показаться удивительным при сравнении их с целыми числами в обычном
алгебраическом порядке. Точки с целочисленными абсциссами расположены на оси
$x$\nobreakdash-ов изолированно, а точки с рациональными абсциссами --- ,,всюду
плотно``, т.~е. между любыми двумя сколь угодно близкими из них имеются такие же
точки. Этот пересчёт может быть выполнен при помощи следующего приёма, который
мы изложим для \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$\nobreakdash-ок элементов счётного множества} для каждого
фиксированного натурального $n$. Все эти пересчёты, включая пересчёт
первоначального множества, можно выбрать в качестве строк новой матрицы, чтобы
получить пересчёт упорядоченных $n$\nobreakdash-ок для переменного $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:2-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:5-higher_transfinite_cardinals}).
Рассмотрим теперь теорию Кантора в её общем виде.

\section{Кардинальное число}
\label{sec:3-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:1-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:5-higher_transfinite_cardinals}) можно выяснить, являются
ли эти три отношения ,,исчерпывающими``, другими словами, должно ли иметь место
хотя бы одно из них. Ситуация отчасти прояснится в результате следующей теоремы,
после которой останется только вопрос, может ли встретиться
случай~\ref{case:p3-3}.
%% ======================= Страница 18 =======================

\section{Теорема эквивалентности, конечные и бесконечные множества}
\label{sec:4-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:3-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:7-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:3-cardinal_number}, согласуются с обычными
отношениями равенства и порядка для натуральных чисел (в частности, ${n<n+1}$
для конечных кардинальных чисел). Итак, не возникнет никакой путаницы, если мы
отождествим натуральные числа с конечными кардинальными числами.

Множество, не являющееся конечным, мы будем называть \emph{бесконечным}, а его
кардинальное число --- \emph{бесконечным} или \emph{трансфинитным кардинальным
числом}. Кардинальное число множества всех натуральных чисел, а следовательно, и
каждого счётно\nobreakdash-бесконечного
множества~(\textsection~\ref{sec:1-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{имеет
счётно\nobreakdash-бесконечное подмножество}.
\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{конечного или счётно\nobreakdash-бесконечного
множества элементов}.
\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{Кардинальное число несчётного множества не изменится от удаления конечного
или счётно\nobreakdash-бесконечного подмножества элементов}.
\end{SCEnvWLabel}
%% ======================= Страница 21 =======================

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

%
% для следующах двух абзацев рассмотреть возможность добавления ссылок
% к прописным ссылкам:
% "в последнем примере"
% "эту теорему"
% "её лемму"
% "Вторая теорема"
% "теоремой эквивалентности"
% "теоремой эквивалентности" второй раз
%
Первая из теорем этого параграфа является общей формулировкой той ситуации, с
которой мы встретились в последнем
примере~\textsection~\ref{sec:2-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:3-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:3-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}.


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

\begin{SCEnvWLabel}{Примеры.}{exmpls:p5}{p5-examples}
\begin{SCEnvWLabel}{Множества с кардинальным числом $2^{\alephZero}$.}%
{exmpl:p5-1}{example-p5-1}
Это --- кардинальное число, приписанное множеству всех подмножеств множества
всех натуральных чисел, которое мы описали
в~\textsection~\ref{sec:2-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{\nobreakdash-ки действительных чисел} или \emph{точки действительного
эвклидова} $n$\emph{\nobreakdash-мерного пространства} для любого фиксированного
натурального $n$ и даже \emph{бесконечные последовательности действительных
чисел} или \emph{точки действительного эвклидова}
$\alephZero$\emph{\nobreakdash-мерного пространства}. Этот последний пример
можно рассмотреть с помощью метода~\textsection~\ref{sec:1-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$\nobreakdash-мерного или $\alephZero$\nobreakdash-мерного
пространства следует, что этим кардинальным числом обладают множество всех
\emph{множеств действительных чисел}, или \emph{точечных множеств
действительного эвклидова} $n$\emph{\nobreakdash-мерного} или
$\alephZero$\emph{\nobreakdash-мерного пространства}. \emph{Действительные
функции от действительной переменной} могут быть представлены их графиками,
которые являются точечными множествами на плоскости, а потому множество их имеет
кардинальное число, не большее $2^{2^{\alephZero}}$. Оно имеет в точности это
кардинальное число, так как функции, принимающие в качестве значений только $0$
и $1$, служат представляющими функциями для множеств действительных чисел и тем
самым составляют подмножество с этим кардинальным числом. Распространяя на этот
пример геометрическую терминологию, можно сказать, что мы имеем дело с
множеством \emph{точек действительного эвклидова} 
$2^{\alephZero}$\emph{\nobreakdash-мерного пространства}.
\end{SCEnvWLabel}
\end{SCEnvWLabel}

%% ======================= Страница 25 =======================

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

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

Цель этой главы --- сопоставить (отчасти для ссылок, отчасти для более
внимательного рассмотрения) некоторые идеи и методы математики.

Когда мы выписываем натуральный ряд чисел
\begin{equation*}
0,\; 1,\; 2,\; 3,\;\ldots\text{,}
\end{equation*}

\noindent%
мы предполагаем, что точки <<$\ldots$>> указывают на продолжение
последовательности за указанные несколько её членов.

Кронекер заметил в 1886 г.: <<Бог создал целые числа, все остальное --- творение
человека>>. Мы не можем надеяться, что наше познание натурального ряда сведётся
к познанию чего\nobreakdash-либо существенно более простого.

Но исследуя, что содержится в нашем понимании натурального ряда, мы можем
преуспеть в выяснении основ наших рассуждений о натуральных числах.

Мы начнём с описания натуральных чисел как объектов, которые могут быть
порождены, если отправляться от начального объекта $0$ (\emph{нуль}) и
последовательно переходить от уже порождённого объекта $n$ к другому объекту
${n+1}$ или $n'$ (\emph{следующему за} $n$).

При этом мы считаем возможным, как бы далеко мы уже ни зашли при получении $n$,
сделать ещё один шаг и получить $n'$. Употребление обозначения со штрихом
<<$n'$>> вместо более обычного <<${n+1}$>> подчёркивает, что~$'$~есть первичная
унарная\footnote{Т. е. с одним аргументом.~---~\textit{Прим.~перев.}} операция
или функция, употребляемая при порождении натуральных чисел, тогда как~$+$~может
быть определён на дальнейшей стадии как бинарная операция или функция от двух
натуральных чисел.

Чтобы получить натуральные числа с их обычными обозначениями, остаётся лишь
разъяснить, что ${0, 1, 2, 3, \ldots}$ заменяют соответственно
\begin{equation*}
0,\; 0',\; 0'',\; 0''',\;\ldots\text{.}
\end{equation*}

\noindent%
Это относится уже к специфике десятичных обозначений.

В этом описании мы апеллировали к нашему пониманию последовательности дискретных
шагов. Последние состояли в отправлении от $0$ и повторном переходе от $n$ к
следующему натуральному числу $n'$. Это описание можно следующим образом разбить
на несколько пунктов:

1.\itemlabel{list:p6-l1-i1}{1}~$0$ является \emph{натуральным числом}.
2.\itemlabel{list:p6-l1-i2}{2}~Если $n$ --- \emph{натуральное
число}, то и $n'$ --- \emph{натуральное число}.
3.\itemlabel{list:p6-l1-i3}{3}~Никаких \emph{натуральных чисел}, кроме тех,
которые получаются согласно \ref{list:p6-l1-i1} и \ref{list:p6-l1-i2}, нет.

В этой форме наша последовательность дискретных шагов становится применением
пункта~\ref{list:p6-l1-i1} и последовательностью применений
пункта~\ref{list:p6-l1-i2}. Все три пункта вместе образуют пример того, что мы
будем называть \emph{индуктивным определением}. Определяемый термин
(,,натуральное число``) выделен курсивом. Эти пункты,
%% ======================= Страница 26 =======================
за исключением последнего, предусматривают случаи, в которых определён этот
термин; они называются \emph{прямыми пунктами}; последний пункт называется
\emph{косвенным пунктом}; в нём утверждается, что случаи, когда этот термин
определён, исчерпывающим образом рассмотрены в предыдущих пунктах.

В этом индуктивном определении не выражено условие различия, а именно, что
числа, различным образом порождённые применениями пунктов \ref{list:p6-l1-i1} и
\ref{list:p6-l1-i2}, должны быть различными объектами. Это условие можно разбить
на два следующих предложения.

4.\itemlabel{list:p6-l1-i4}{4} Для любых натуральных чисел $m$ и $n$ из
${m'=n'}$ следует ${m=n}$. 5.\itemlabel{list:p6-l1-i5}{5} Для любого
натурального числа $n$, ${n'\neq 0}$.

При этом подразумевается, что $'$ есть унивалентный оператор, или однозначная
функция, так что, обратно к~\ref{list:p6-l1-i4}: для любых натуральных чисел $m$
и $n$ из ${m=n}$ следует ${m'=n'}$.

Чтобы убедиться в том, что предложения \ref{list:p6-l1-i4} и \ref{list:p6-l1-i5}
требуют различия любых двух различно порождённых чисел, мы можем рассуждать
следующим образом. Допустим, что на некоторой данной стадии порождения чисел все
до сих пор порождённые числа ${0, 1,\ldots, n}$ различны. Тогда ближайшее из
далее порождаемых чисел --- число $n'$ должно отличаться от тех чисел
${1, \ldots, n}$, которые среди ранее порождённых следуют за какими-то числами
(в силу~\ref{list:p6-l1-i4}), и от $0$ (в силу~\ref{list:p6-l1-i5}). Таким
образом, каждый следующий шаг в этом порождении производит некоторое новое
число.

Например, ${0''''\neq 0''}$, в чем можно убедиться следующим образом. В
силу~\ref{list:p6-l1-i4}, применённого с $0'''$ в качестве $m$ и $0'$ в качестве
$n$, ${0''''=0''}$ возможно только при ${0'''=0'}$. Опять в
силу~\ref{list:p6-l1-i4}, ${0'''=0'}$ влечёт ${0''=0}$. Но в
силу~\ref{list:p6-l1-i5} с $0'$ в качестве $n$ ${0''\neq 0}$.

Эти пять предложений~\ref{list:p6-l1-i1}--\ref{list:p6-l1-i5} с одним отличием
были выбраны Пеано~\cite{peano1889,peano1891} в качестве аксиом, характеризующих
натуральный ряд чисел. Пеано вместо предложения~\ref{list:p6-l1-i3}
сформулировал принцип математической индукции
(\textsection~\ref{sec:7-mathematical_induction}) и поместил его в списке на пятом
месте, сдвинув предложения \ref{list:p6-l1-i4} и \ref{list:p6-l1-i5}
соответственно на третье и четвёртое места.

Здесь мы не рассматриваем внутреннюю природу натуральных чисел; нас интересует
только, как они образуют натуральный ряд. Каждое индивидуальное натуральное
число рассматривается только как объект, занимающий некоторое конкретное место в
натуральном ряду. Другими словами, индивидуальное натуральное число задано, если
задано его порождение согласно индуктивному определению. Например, натуральное
число $4$ задаётся как объект, который мы получаем, отправляясь от начального
объекта $0$, путём применения операции <<следующий за>> однажды, затем опять,
опять и опять; или, короче, $4$ задаётся как $0''''$. Число вроде $872656$ (в
десятичном обозначении) также в принципе может быть выписано при помощи
применения $'$ к $0$, хотя на практике мы так не поступаем.

Разумеется, имея дело с предложениями типа <<некоторое уравнение имеет два
корня>>, мы продолжаем пользоваться тем, что натуральные числа суть кардинальные
числа конечных множеств
(\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}).

\begin{SCEnvWLabel}{Порядок}{order:p6}{order:p6}
Согласно индуктивному определению натуральных чисел, они порождаются в некотором
(обычном) порядке. Таким образом, мы определяем, что ${m<n}$, если $m$
порождается раньше $n$ по ходу порождения $n$. Расчленяя это, мы получаем
следующее индуктивное определение отношения ${m<n}$ (где $m$, $n$ пробегают
натуральный ряд).

O1.\itemlabel{list:p6-l2-i1}{O1}~${m<m'}$.
O2.\itemlabel{list:p6-l2-i2}{O2}~Если ${m<n}$, то ${m<n'}$.
O3.\itemlabel{list:p6-l2-i3}{O3}~${m<n}$ в том и только в том случае, если это
вытекает из \ref{list:p6-l2-i1} и \ref{list:p6-l2-i2}.

Если взять это определение для некоторого фиксированного $m$ в качестве
индуктивного определения класса чисел $n$, больших $m$, то оно имеет вид
первоначального индуктивного определения натуральных чисел с заменой $0$ на
$m'$.
\end{SCEnvWLabel}

%% ======================= Страница 27 =======================

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

Пусть $P$ --- некоторое свойство натуральных чисел. Допустим, что:

(1)\itemlabel{list:p7-l1-i1}{(1)} $0$ обладает свойством $P$.

(2)\itemlabel{list:p7-l1-i2}{(2)} Если какое-нибудь натуральное число $n$
обладает свойством $P$, то и следующее за ним число $n'$ обладает свойством $P$.

Тогда каждое натуральное число обладает свойством $P$.

Это --- принцип \emph{математической индукции}. Мы можем высказать его немного
короче, пользуясь <<$n$>> в качестве переменной для натурального числа и
<<$P(n)$>> как обозначением для предложения, состоящего в том, что $n$ обладает
свойством $P$: если~\ref{list:p7-l1-i1}\itemlabel{list:p7-l1-i1-1}{(1)}~$P(0)$
и~\ref{list:p7-l1-i2}\itemlabel{list:p7-l1-i2-2}{(2)}~для любого $n$ из $P(n)$
следует $P(n')$, то $P(n)$ для всех $n$.

Обоснование этого принципа индукции является почти непосредственным, если
натуральные числа рассматриваются как объекты, порождённые согласно индуктивному
определению~\ref{list:p6-l1-i1}--\ref{list:p6-l1-i3}~%
\textsection~\ref{sec:6-the_natural_numbers}. Предположим, что имеется свойство
$P$, для которого справедливы
свойства~\ref{list:p7-l1-i1-1}~и~\ref{list:p7-l1-i2-2}. Должно ли тогда каждое
натуральное число $n$ обладать свойством $P$? Мы рассматриваем положительный
ответ просто как утверждение, что, если нам дано произвольное натуральное число
$n$, мы можем быть уверены в том, что $n$ обладает свойством $P$. Но любое
натуральное число $n$ дано в точности тогда, когда (фактически или в принципе)
мы имеем его порождение согласно индуктивному определению, отправляясь от $0$ и
применяя некоторое указанное число раз операцию <<следующий за>>. При этих
обстоятельствах, чтобы заключить, что $n$ обладает свойством $P$, мы можем
воспользоваться~\ref{list:p7-l1-i1-1}~и~\ref{list:p7-l1-i2-2}. Например, $P(4)$
потому, что $4$ задается как $0''''$; в силу~\ref{list:p7-l1-i1-1}~$P(0)$;
отсюда в силу~\ref{list:p7-l1-i2-2}~$P(0')$; опять в
силу~\ref{list:p7-l1-i2-2}~$P(0'')$; опять в
силу~\ref{list:p7-l1-i2-2}~$P(0''')$ и опять в
силу~\ref{list:p7-l1-i2-2}~$P(0'''')$.

Иначе говоря,~\ref{list:p7-l1-i1-1}~и~\ref{list:p7-l1-i2-2} служат орудиями,
которые позволяют нам, параллельно с порождением натуральных чисел согласно
пунктам~\ref{list:p6-l1-i1} и~\ref{list:p6-l1-i2} индуктивного определения,
проверять для каждого порождаемого числа, что оно обладает свойством $P$.

Это рассуждение зависит, конечно, от косвенного пункта~\ref{list:p6-l1-i3}
индуктивного определения. Обратно, наш принцип индукции можно применить для
доказательства пункта~\ref{list:p6-l1-i3}, применяя его со следующим
предложением в качестве $P(n)$: $n$ дано как натуральное число посредством
пунктов~\ref{list:p6-l1-i1} и~\ref{list:p6-l1-i2}, т.~е. может быть порождено
путём применений операции <<следующий за>> отправляясь от $0$.

В связи с доказательством посредством математической индукции мы будем
пользоваться следующей терминологией. Предложение $P(n)$, зависящее от
переменного натурального числа $n$, мы будем называть \emph{индукционным
предложением}, или \emph{предложением индукции}, а переменную $n$ ---
\emph{индукционной переменной}, или \emph{индукционным числом}, или
\emph{переменной индукции}, или переменной, \emph{по} которой производится
индукция. Часть доказательства, состоящую в установлении~\ref{list:p7-l1-i1-1},
т.~е. доказательство предложения $P(0)$, мы будем называть \emph{базисом}
индукции. Часть доказательства, состоящую в установлении~\ref{list:p7-l1-i2-2},
т.~е. доказательство того, что если $P(n)$, то $P(n')$, мы будем называть
\emph{индукционным шагом}, или \emph{шагом индукции}. Внутри индукционного шага
допущение $P(n)$, из которого мы выводим $P(n')$, будем называть
\emph{индуктивным предположением}, или \emph{предположением индукции}.

Иногда для проведения индукционного шага необходимо допустить в качестве
индуктивного предположения не просто $P(n)$, а то, что $P(m)$ для всех
${m\leqslant n}$. Читателю предоставляется самостоятельно убедиться в том, что
принцип индукции сохраняет силу и в этой изменённой форме, которая называется
\emph{возвратной индукцией}, или \emph{индукцией пробега}. Индукцией можно
пользоваться при доказательстве предложения, зависящего не от натурального,
а от целого положительного числа; в этом случае базис состоит из доказательства
$P(1)$.
%% ======================= Страница 28 =======================

Изучающий встречался с математической индукцией в курсах элементарной алгебры. В
качестве примеров предложений, требующих доказательства по индукции и не
очевидных, пока эти доказательства не проведены, часто приводят формулы для
суммирования прогрессий. Многие предложения, которые обычно принимаются на веру,
при строгом доказательстве зависят от индукции, а в других случаях индукционный
шаг настолько прост, что от него отделываются словами <<и так далее>> или
чем-нибудь в этом роде (например, теоремы~\ref{theorem:A}~и~\ref{theorem:B}
из~\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}).

\begin{SCEnvWLabel}{Пример 1.}{exmpl:p7-1}{1}
Докажем предложения~\ref{prop:p4-1}~и~\ref{prop:p4-2}~%
из~\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}
при помощи индукции по $n$. Сделаем это для~\ref{prop:p4-2},
предоставляя~\ref{prop:p4-1} читателю. Индукционное предложение таково:
\emph{Для любых множеств} $M$ \emph{и} $M_{1}$ \emph{из} ${\OLcard{M}=n}$
\emph{и} ${M\sim M_{1}\subseteq M}$ \emph{следует} ${M_{1}=M}$.
\textsc{Базис:}~${n=0}$. Пусть $M$ и $M_{1}$ --- такие множества, что
${\OLcard{M}=0}$, т.~е. ${M=\OLemptyset}$ и
${\OLemptyset\sim M_{1}\subseteq\OLemptyset}$. Тогда ${M_{1}=\OLemptyset}$.
\textsc{Индукционный~шаг}.~Допустим (в качестве индуктивного предположения), что
индукционное предложение установлено. Пусть теперь $M$ и $M_{1}$ --- такие
множества, что ${\OLcard{M}=n+1}$, т.~е. ${M=N\OLcup\left\{ a\right\}}$, где
${\OLcard{N}=n}$ и ${a\OLnotin N}$ и
${N\OLcup\left\{ a\right\}\sim M_{1}\subseteq N\OLcup\left\{ a\right\}}$. Нам
надо доказать, что при этом ${M_{1}=N\OLcup\left\{ a\right\}}$. В данном
\isom-соответствии ${N\OLcup\left\{ a\right\}\sim M_{1}}$ элемент $a$ множества
${N\OLcup\left\{ a\right\}}$ соответствует некоторому элементу $b$ из $M_{1}$.
Поэтому
${N\sim M_{1}\OLsetminus\left\{ b\right\}\subset
 \left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}}$.
Кроме того,
${\left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}\sim N}$.
Поэтому
${\OLcard{\left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}}=n}$
и
${\left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}\sim
 M_{1}\OLsetminus\left\{ b\right\}\subseteq
 \left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}}$.
По индуктивному предположению, применённому с
${\left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}}$ в качестве
$M$ и ${M_{1}\OLsetminus\left\{ b\right\}}$ в качестве $M_{1}$,
${M_{1}\OLsetminus\left\{ b\right\}=
 \left(N\OLcup\left\{ a\right\}\right)\OLsetminus\left\{ b\right\}}$.
Следовательно (ввиду того, что ${b\in M_{1}}$ и
${b\in N\OLcup\left\{ a\right\}}$)‚ ${M_{1}=N\OLcup\left\{ a\right\}}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Пример 2.}{exmpl:p7-2}{2}
В математических формулах скобки вводятся попарно, чтобы показать, каким образом
формула составляется из связанных между собой частей. В более сложных случаях
употребляют скобки разных родов, например, $(\quad)$, $\{\quad\}$, $[\quad]$, а
очень сложных случаев удаётся избежать при помощи различных сокращений. Однако
принципиально остаётся вопрос, можно ли, пользуясь только одним родом скобок,
однозначно установить распадение формулы на части. (Этот вопрос допускает
эквивалентную геометрическую формулировку, связанную с погружением интервалов.)

Чтобы уточнить этот вопрос, допустим, что у нас имеется $2n$ скобок, из них $n$
левых скобок <<$($>> и $n$ правых скобок <<$)$>> и что они расположены в
линейном порядке слева направо. Именно таким образом они могут встретиться в
математической формуле, причём между ними будут как-то расположены другие
символы этой формулы, которыми мы сейчас не интересуемся.

Мы будем говорить, что две пары скобок \emph{разделяют друг друга}, если они
встречаются в порядке ${(_{i}\;(_{j}\,)_{i}\;)_{j}}$, где индексы $i$ служат для
указания одной пары, а индексы $j$ --- для указания другой, и другие скобки
также могут встретиться в каком-нибудь расположении относительно этих четырёх
указанных.

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

Почти очевидно, что если $2n$ скобок спарены собственным образом, то после
удаления любой из этих пар остающиеся скобки спарены собственным образом. Кроме
того, скобки, заключённые между обеими скобками некоторой пары спаренных скобок
из собственного спаривания $2n$ скобок, спарены собственным образом.
\end{SCEnvWLabel}
%% ======================= Страница 29 =======================

Следующие три леммы содержат ответ на поставленный вопрос и некоторые
относящиеся к нему сведения.

\begin{SCEnvWLabel}{Лемма 1.}{lemma:1}{1}
\emph{При всяком собственном спаривании} $2n$ \emph{скобок} (${n>0}$) 
\emph{имеется по крайней мере одна самая внутренняя пара}, \emph{т}. \emph{е}.
\emph{пара скобок}, \emph{между которыми нет никаких других скобок}.
\end{SCEnvWLabel}

Это доказывается возвратной индукцией по $n$. Можно по желанию рассматривать $n$
как целое положительное или как натуральное число. В последнем случае базис
\emph{выполняется тривиально}, т.~е. является истинным предложением в силу того,
что условие не выполнено. (\textsc{Указание.} При индукционном шаге самая левая
скобка будет некоторой левой скобкой $(_{i}$, которая вместе со второй скобкой
своей пары $)_{i}$ или образует самую внутреннюю пару, или окружает некоторое
множество скобок, к которым можно применить индуктивное предположение.)

\begin{SCEnvWLabel}{Лемма 2.}{lemma:2}{2}
\emph{Всякое множество из} $2n$ \emph{скобок допускает не более одного
собственного спаривания}.
\end{SCEnvWLabel}

Это доказывается (простой) индукцией по $n$. (\textsc{Указание.} В индукционном
шаге в силу леммы~\ref{lemma:1} среди данных скобок имеется самая внутренняя
пара. Если её удалить‚ то к множеству оставшихся скобок будет применимо
индуктивное предположение.)

\begin{SCEnvWLabel}{Лемма 3.}{lemma:3}{3}
\emph{Если множество из} $2n$ \emph{скобок и подмножество последовательных} $2m$
\emph{скобок из их числа оба допускают собственные спаривания}, \emph{то
собственное спаривание этого подмножества образует часть собственного спаривания
всего множества}, \emph{т}. \emph{е}. \emph{каждая скобка подмножества спарена с
одной и той же скобкой в обоих спариваниях}.
\end{SCEnvWLabel}

Это доказывается индукцией по $m$.

Например, рассмотрим 22 скобки:
\begin{equation*}
\big(\vphantom{a}^{1}_{7}\;\:
 \big(\vphantom{a}^{2}_{6}\;\:
  \big(\vphantom{a}^{3}_{4}\;\:
   \big(\vphantom{a}^{4}_{2}\;\:
    \big(\vphantom{a}^{5}_{1}\;\:
    \big)\vphantom{a}^{6}_{1}\;\:
   \big)\vphantom{a}^{7}_{2}\;\:
   \big(\vphantom{a}^{8}_{3}\;\:
   \big)\vphantom{a}^{9}_{3}\;\:
  \big)\vphantom{a}^{10}_{4}\;\:
  \big(\vphantom{a}^{11}_{5}\;\:
  \big)\vphantom{a}^{12}_{5}\;\:
 \big)\vphantom{a}^{13}_{6}\;\:
\big)\vphantom{a}^{14}_{7}\;\:
\big(\vphantom{a}^{15}_{11}\;\:
 \big(\vphantom{a}^{16}_{10}\;\:
  \big(\vphantom{a}^{17}_{8}\;\:
  \big)\vphantom{a}^{18}_{8}\;\:
  \big(\vphantom{a}^{19}_{9}\;\:
  \big)\vphantom{a}^{20}_{9}\;\:
 \big)\vphantom{a}^{21}_{10}\;\:
\big)\vphantom{a}^{22}_{11}\;\:
\end{equation*}

Собственное спаривание, указанное нижними индексами, обнаруживается посредством
следующего ,,алгоритма`` (подсказанного доказательством леммы~\ref{lemma:2}) на
каждой стадии, двигаясь слева, находим первую самую внутреннюю пару среди ещё не
использованных и присоединяем эту пару к спариванию. По лемме~\ref{lemma:2}
никакого другого собственного спаривания найти невозможно. Скобки с третьей по
двенадцатую образуют подмножество последовательных скобок, собственное
спаривание которых уже получено в процессе спаривания всего множества. По
лемме~\ref{lemma:3}, не существует никакого подмножества последовательных
скобок, допускающего собственное спаривание, отличное от каждого из тех, которые
уже введены при собственном спаривании всего множества.

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

Под системой $S$ объектов мы будем иметь в виду (непустое) множество класс, или
область $D$ (или, может быть‚ несколько таких множеств) объектов‚ между которыми
установлены некоторые соотношения.

Например, натуральный ряд (\textsection~\ref{sec:6-the_natural_numbers})
образует систему типа ${(D, 0, \vphantom{s}')}$‚ где $D$~---~множество,
$0$~---~элемент множества $D$, а $'$~---~унарная операция над элементами
множества $D$. Другой простой тип системы --- это ${(D, \OLprec)}$‚ где
$D$~---~множество,  а $\OLprec$~---~бинарное отношение между элементами этого
множества.
%% ======================= Страница 30 =======================

Если об объектах системы мы ничего не знаем, кроме соотношений, имеющихся между
ними в системе, то такая система называется \emph{абстрактной}. В этом случае
устанавливается только структура системы, а природа её объектов остаётся
неопределённой во всех отношениях, кроме одного, --- что они согласуются с этой
структурой.

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

Вот несколько представлений абстрактного натурального ряда: (a)~натуральные
числа как мощности конечных множеств; (b)~целые положительные числа ($1$
представляет абстрактный объект $0$); (c)~чётные натуральные числа ($+2$
представляет абстрактную операцию $'$). (d)~Иногда товары упаковывают в ящики,
снабжённые этикеткой, на которой изображён рисунок самого этого ящика. Физически
точность такого рисунка должна быть ограниченной. Но если мы вообразим идеальную
точность рисунка, то можно представить $0$ посредством самого ящика, $1$ ---
посредством рисунка ящика, помещённого на ящике, $2$ --- посредством рисунка
ящика в рисунке ящика, помещённом на ящике, и т.~д.

Два представления одной и той же абстрактной системы (\emph{просто})
\emph{изоморфны}, т.~е. могут быть поставлены в \isom-соответствие, сохраняющее
отношения. Точнее, две системы ${(D_{1}, 0_{1}, \vphantom{s}'\vphantom{s}_{1})}$
и ${(D_{2}, 0_{2}, \vphantom{s}'\vphantom{s}_{2})}$ типа
${(D, 0, \vphantom{s}')}$ просто изоморфны, если существует
\isom-соответствие между $D_{1}$ и $D_{2}$, при котором $0_{1}$
соответствует $0_{2}$ (что обозначается через ${0_{1}\leftrightarrow 0_{2}}$), и
если ${m_{1}\leftrightarrow m_{2}}$‚ то
${m_{1}\vphantom{s}'\vphantom{s}_{1}\leftrightarrow
 m_{2}\vphantom{s}'\vphantom{s}_{2}}$. Две системы ${(D_{1}, \OLprec_{1})}$ и
${(D_{2}, \OLprec_{2})}$ типа ${(D, \OLprec)}$ изоморфны, если существует
\isom-соответствие между $D_{1}$ и $D_{2}$, при котором, если
${m_{1}\leftrightarrow m_{2}}$ и ${n_{1}\leftrightarrow n_{2}}$, то
${m_{1}\OLprec_{1}n_{1}}$ тогда и только тогда, когда ${m_{2}\OLprec_{2}n_{2}}$.

Обратно, любые две изоморфные системы служат представлениями одной и той же
абстрактной системы, которая получается путём абстрагирования от любой из них,
т.~е. путём игнорирования всех отношений и свойств, за исключением тех, которые
рассматриваются в этой абстрактной системе.

Второй пример абстрактной системы типа ${(D, 0, \vphantom{s}')}$. Пусть $D$
содержит ровно два (различных) объекта $0$ и $1$ и пусть ${0'=1}$ и ${1'=0}$.
Это будет так называемая система \emph{вычетов по модулю} $2$. Натуральный ряд
превращается в эту систему, если каждое число заменять его остатком от деления
на $2$ (т.~е. его \emph{вычетом} по модулю $2$), так что получается
\begin{equation*}
0,\; 1,\; 0,\; 1,\; 0,\; 1,\;\ldots\;\text{.}
\end{equation*}

\noindent%
(Системы вычетов впервые были рассмотрены Гауссом в 1801 г.)

Третий пример. Пусть $S$ состоит из двух последовательностей
{\renewcommand{\theequation}{\arabic{equation}}%
\begin{equation}\label{eq:p8-1}
0,\; 1,\; 2,\; 3,\;\ldots\text{;}\quad\quad
\omega,\; \omega+1,\; \omega+2,\; \omega+3,\;\ldots\text{,}
\end{equation}

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

Каждый из этих трёх примеров можно очевидным образом изменить так, что получится
система типа ${(D, \OLprec)}$. В третьем примере мы при этом будем рассматривать
элементы в порядке, показанном в строке~\eqref{eq:p8-1}, и называть их
\emph{ординальными числами}, \emph{м{\'e}ньшими чем} $2\omega$ (из канторовской
теории ординальных чисел).}

Система вычетов по модулю $2$ (или её представление) не изоморфна натуральному
ряду (или его представлению), так как между обеими этими
%% ======================= Страница 31 =======================
системами невозможно установить \isom-соответствия. Система ординальных чисел,
меньших $2\omega$, не изоморфна натуральному ряду, потому что при установлении
\isom-соответствия невозможно сохранить операцию ,,следующий за`` $'$ (или
отношение порядка $\OLprec$).

В этом параграфе мы будем употреблять <<$S$>> для обозначения системы и <<$D$>>
для обозначения её множества объектов, в случае когда система имеет одно такое
множество. Часто можно, не боясь путаницы, упростить обозначения, пользуясь
одной буквой в обеих целях. Например, это можно сделать, если понимать
натуральный ряд $\OLNaturalNumSet$ как выше. Этого нельзя сделать, если речь
идёт о системе ${(\OLNaturalNumSet, \OLprec)}$, состоящей из натурального ряда
чисел, причём чётные (нечётные) числа упорядочены, как обычно, и все чётные
числа предшествуют всем нечётным. (Эта система служит представлением для
ординальных чисел, меньших $2\omega$.)

При введении в математику систем объектов можно исходить из двух противоположных
методов, или точек зрения (см. Гильберт~\cite{hilbert1900}).

\emph{Генетический}, или \emph{конструктивный}, метод иллюстрируется
индуктивным определением натуральных
чисел~(\textsection~\ref{sec:6-the_natural_numbers}). В этой связи натуральные
числа рассматриваются как порождаемые (generated), или конструируемые в
некотором определённом порядке. (Этим не исключается их абстрактное
рассмотрение.)

При \emph{аксиоматическом} методе, или методе \emph{постулатов}, с другой
стороны некоторые предложения, именуемые \emph{аксиомами} или
\emph{постулатами}, с самого начала кладутся в основу в качестве допущении или
условий относительно системы $S$ объектов. Затем получаются следствия из этих
аксиом, которые и образуют теорию относительно любой существующей системы
объектов $S$, удовлетворяющей этим аксиомам.

Например, рассмотрим пять аксиом Пеано. Чтобы пояснить нашу точку зрения,
перепишем эти аксиомы, подставляя понятие <<элемент $D$>> вместо <<натуральное
число>>:

P1.\itemlabel{axiom:p8-p1}{P1}~${0\in D}$.
P2.\itemlabel{axiom:p8-p2}{P2}~Если ${n\in D}$, то ${n'\in D}$.
P3.\itemlabel{axiom:p8-p3}{P3}~Если ${m\in D}$ и ${n\in D}$, то ${m'=n'}$ только
в том случае, если ${m=n}$.
P4.\itemlabel{axiom:p8-p4}{P4}~Если ${n\in D}$, то ${n'\neq 0}$.
P5.\itemlabel{axiom:p8-p5}{P5}~Пусть ${P\subseteq D}$‚ причём $P$ обладает
следующими свойствами: (1) ${0\in P}$ и (2), если ${n\in P}$, то ${n'\in P}$;
тогда ${P=D}$.

Мы уже знаем, что только одна абстрактная система $S$ удовлетворяет этим пяти
аксиомам, а именно, натуральный ряд чисел, который мы прежде ввели с
генетической точки зрения.

Но с аксиоматической точки зрения мы можем с равным успехом рассматривать и
другие списки аксиом, например~\ref{axiom:p8-p1}--\ref{axiom:p8-p4}. Тогда $S$
может быть системой натуральных чисел, или ординальных чисел, меньших $2\omega$,
или любой из многих других абстрактно различных, т.~е. неизоморфных систем.

Если вместо этого рассматривать
аксиомы~\ref{axiom:p8-p1}--\ref{axiom:p8-p3},~\ref{axiom:p8-p5}, то различными
абстрактными системами, удовлетворяющими этим аксиомам, будут следующие и только
следующие системы: натуральный ряд чисел и системы вычетов по модулю $m$ для
каждого целого положительного числа $m$.

Допустим теперь, что мы не просто откинули~\ref{axiom:p8-p4}, но заменили её
аксиомой

P6.\itemlabel{axiom:p8-p6}{P6}~Если ${n\in D}$, то ${n'\neq n}$, но ${n''=n}$.

Тогда спять только одна система удовлетворяет аксиомам --- система вычетов по
модулю $2$.

Для шести аксиом~\ref{axiom:p8-p1}--\ref{axiom:p8-p6} не существует никакой
системы $S$‚ которая удовлетворяла бы всем этим аксиомам, потому что только
натуральный ряд удовлетворяет~\ref{axiom:p8-p1}--\ref{axiom:p8-p5} и только
система вычетов по модулю $2$ удовлетворяет~%
\ref{axiom:p8-p1}--\ref{axiom:p8-p3},~\ref{axiom:p8-p5},~\ref{axiom:p8-p6}.

Иногда говорят, что аксиомы аксиоматической теории служат неявным определением
системы объектов этой теории, но это может означать только, что аксиомы
определяют то, к каким системам, определённым вне теории, эта теория
%% ======================= Страница 32 =======================
применима. При этом возможны три случая. Или аксиомам не удовлетворяет никакая
система объектов (например,~\ref{axiom:p8-p1}--\ref{axiom:p8-p6}), или
удовлетворяет в точности одна абстрактная система, так что любые две системы,
удовлетворяющие аксиомам, изоморфны
(например,~\ref{axiom:p8-p1}--\ref{axiom:p8-p5}
или~\ref{axiom:p8-p1}--\ref{axiom:p8-p3},~\ref{axiom:p8-p5},~\ref{axiom:p8-p6}),
или удовлетворяет более чем одна абстрактная система, т.~е. существуют
неизоморфные системы, удовлетворяющие аксиомам
(например,~\ref{axiom:p8-p1}--\ref{axiom:p8-p4}‚
или~\ref{axiom:p8-p1}--\ref{axiom:p8-p3},~\ref{axiom:p8-p5}). В первом случае мы
будем называть множество аксиом \emph{невыполнимым}, в последних двух --- 
\emph{выполнимым}, и притом во втором случае --- \emph{категорическим}
(Веблен~\cite{veblen1904}), а в третьем --- \emph{неполным} (ambiguous). (С
другой стороны, при генетическом методе процесс порождения обычно претендует на
полное определение абстрактной структуры системы, т.~е. служит категорическим
определением системы.)

По данной аксиоматике, вообще говоря, совершенно не видно, какой из этих трёх
случаев имеет место. Исторически это иллюстрируется примером эвклидовой
геометрии без постулата Эвклида о параллельных, от которого зависит теорема, что
через данную точку, не лежащую на данной прямой, проходит ровно одна прямая,
параллельная данной. От <<Начал>> Эвклида (около 330--320~гг.~до~н.~э.) до
открытия неэвклидовой геометрии Лобачевским (1829) и Больаи (1833) обычно
предполагалось, что эти аксиомы являются категорическими; или по крайней мере,
что если бы вопрос был задан в этих терминах, то на него, вероятно, был бы
получен такой ответ.

Вера греков в то, что они имели дело с однозначно определённой структурой
пространства, не была выражена посредством современной терминологии. Эвклид
полагал, что его аксиомы выражают известные основные свойства реального
пространства. Аксиоматический метод в этом старинном понимании, согласно
которому объекты системы $S$ предполагаются известными прежде аксиом, можно
охарактеризовать как метод \emph{содержательной} (неформальной), или
\emph{материальной аксиоматики}. При этом аксиомы только выражают те свойства
объектов, которые с самого начала были приняты как очевидные в силу их
построения или, в случае теорий, которые применяются к эмпирическому миру,
непосредственно абстрагируются из опыта или постулируются.

Аксиоматический метод в новом, описанном выше понимании, при котором аксиомы
предшествуют всякому описанию системы $S$ объектов, о которых идёт речь в
аксиомах (и служат для введения или <<неявного определения>> системы $S$),был
впервые систематически рассмотрен в книге Гильберта
<<Основания геометрии>>~\cite{hilbert1899} и может быть охарактеризован как
\emph{формальная} или \emph{экзистенциальная} аксиоматика. Заметим, что вопрос о
том, существует ли --- и если да, то единственна ли --- абстрактная система $S$,
удовлетворяющая аксиомам некоторой аксиоматической теории, можно исследовать
только средствами, внешними по отношению к этой аксиоматической теории (т.~е. в
некоторой другой теории). В самой же формальной аксиоматической теории область
$D$ из $S$ играет роль фиксированного и полного множества объектов, причём
существование всех этих объектов предполагается сразу, независимо от
какого\nobreakdash-либо порядка порождения, и к этим объектам применяются
операции, отношения и т.~д. из системы $S$.

В системе $S$ типа ${(D, 0, \vphantom{s}')}$ понятия $0$ и $'$ или $D$, $0$ и
$'$ называются \emph{первоначальными}, или \emph{техническими}, или
\emph{неопределяемыми}, т.~е. эти понятия не определены, пока не введены
аксиомы. Остальные термины в аксиомах являются \emph{обычными}, или
\emph{логическими}, или \emph{определяемыми}, т.~е. их значения должны быть
предварительно объяснены. Относительно $D$, $0$ и $'$ заранее должно быть
указано только, что $D$~---~множество, $0$~---~предмет, принадлежащий $D$,
$'$~--- операция над элементом $D$; иначе говоря, заранее должны быть определены
только грамматические категории, к которым принадлежат <<$D$>>, <<$0$>> и
<<$'$>>. Аналогично для системы вида ${(D, \OLprec)}$ неопределяемыми понятиями
являются или $\OLprec$, или $D$ и $\OLprec$.
%%
%% исправлен типографский брак:
%% в оригинале последний символ "<" в предыдущем абзаце не пропечатан
%%

В математической практике генетический и аксиоматический методы введения систем
объектов часто оказываются связанными, когда генетически строится пример системы
объектов, удовлетворяющей аксиомам. В других случаях
%% ======================= Страница 33 =======================
пример заимствуется из другой формальной аксиоматической теории. (Во всех
случаях, когда $S$ для данной формальной аксиоматической теории отождествляется
с некоторой системой объектов, заимствованной извне, налицо \emph{применение}
рассматриваемой формальной аксиоматической теории, при котором она становится
материальной аксиоматической теорией.)

Формальный аксиоматический метод часто с успехом применяется в связи с неполными
системами аксиом в целях одновременного построения общей части теории для многих
различных систем. Знаменитым примером является ,,теория групп`` из алгебры.

В качестве другого примера рассмотрим следующие аксиомы
\emph{линейного порядка}, которые применяются к системам типа ${(D, \OLprec)}$:

L1.\itemlabel{axiom:p8-l1}{L1}~Если ${m\OLprec n}$ и ${n\OLprec p}$‚ то
${m\OLprec p}$.
L2.\itemlabel{axiom:p8-l2}{L2}~Имеет место не более чем одно из соотношений
${m\OLprec n}$, ${m=n}$‚ ${m\OLsucc n}$.
L3.\itemlabel{axiom:p8-l3}{L3}~Имеет место по крайней мере одно из соотношений
${m\OLprec n}$, ${m=n}$‚ ${m\OLsucc n}$.

Здесь ${m\OLsucc n}$ означает ${n\OLprec m}$. Переменные $m$, $n$, $p$ относятся
к произвольным элементам области $D$. Эти аксиомы выполняются, если в качестве
$D$ взять натуральный ряд, или множество ординальных чисел, меньших $2\omega$,
или множество целых, или рациональных, или действительных чисел, а в качестве
$\OLprec$~---~обычное отношение порядка для каждой из этих областей, а также для
многих других систем. Опуская~\ref{axiom:p8-l3}, получаем множество аксиом
\emph{частичного порядка}.

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

\emph{Арифметику}, или \emph{теорию чисел}, можно рассматривать как отрасль
математики, в которой изучаются натуральные числа и другие (категорически
определённые) счётные системы объектов, например целые или рациональные числа.
Всякую конкретную систему такого рода (или соответствующую этой системе теорию)
можно называть \emph{арифметикой} (an arithmetic). Рассмотрение обычно
происходит абстрактно (\textsection~\ref{sec:8-system_of_objects}). Объекты
обычно рассматриваются как \emph{индивидуумы} (т.~е. без анализа их построения
из других объектов), исключая некоторые случаи (например, основные свойства
неотрицательных рациональных чисел изучаются при помощи представления их в виде
упорядоченных пар натуральных чисел).

В \emph{арифметике в узком смысле} рассматриваются главным образом конкретные
операции, именуемые $+$ (сложение) и $\cdot$ (умножение), а иногда также
некоторые другие связанные с ними операции. В \emph{арифметике в широком
смысле}, или \emph{теории чисел}, используется более широкий класс понятий.

Эти определения мы привели для разъяснения нашей терминологии. Иногда термин
<<арифметика>> употребляется и по отношению к теории операций $+$ и $\cdot$ для
несчётных систем чисел (например, ,,арифметика трансфинитных кардинальных
чисел``).

В то время как арифметика, или теория чисел, изучает системы мощности
$\alephZero$ (а иногда конечные), \emph{анализ} имеет дело с действительными
числами и другими системами объектов мощности $2^{\alephZero}$ (а иногда и
б{\'o}льшей мощности). Как и в теории чисел, в анализе подлежащие рассмотрению
системы объектов считаются обычно категорически определёнными.

Результаты анализа иногда применяются в теоретико\nobreakdash-числовых
исследованиях --- такие исследования составляют \emph{аналитическую теорию
чисел}. Теория чисел, не использующая анализа, называется \emph{чистой}, или
\emph{элементарной}, теорией чисел\footnote{Согласно сказанному, термины
<<теория чисел>> и <<арифметика>> являются синонимами (поэтому английский термин
<<number theory>> переводится обычно в дальнейшем словом <<арифметика>>).
Повидимому, синонимами следует считать также термины <<арифметика в узком
смысле>> и <<элементарная теория чисел>>. При этом в дальнейшем (как в
английском тексте, так и в переводе) эпитеты <<в узком смысле>> и
<<элементарная>> обычно опускаются.~---~\textit{Прим.~ред.}}.
%% ======================= Страница 34 =======================

Рассмотрим теперь бегло основную систему объектов анализа --- континуум
действительных чисел.

Та теория действительных чисел, которая обычно кладётся в основу анализа (за
исключением исследований по критике оснований анализа), является продуктом
раннего критического движения, начатого Гауссом (1777--1855), Коши (1789--1857)
и Абелем (1802--1829)

Это направление привело в конце девятнадцатого столетия к так называемой
\emph{арифметизации анализа}, произведённой Вейерштрассом (1815--1897),
Дедекиндом (1831--1916), Мерэ (1835--1911) и Кантором (1845--1918). Доверие к
несколько туманной геометрической интуиции было заменено определением
действительных чисел как некоторых объектов, построенных из натуральных, целых
или рациональных чисел. При этом свойства действительных чисел сводились в
конечном счёте к свойствам натуральных чисел. Как сказал
Пуанкаре~\cite{poincare1900}, <<сегодня в анализе остаются только целые числа, а
также конечные и бесконечные системы целых чисел, связанных между собой сетью
отношений равенства и неравенства>>.

Определение действительных чисел через натуральные, целые или рациональные может
быть дано несколькими способами. Все они приводят к одной и той же абстрактной
структуре континуума действительных чисел. Другими словами, то, что даёт каждое
из этих определений, является
представлением~(\textsection~\ref{sec:8-system_of_objects}) действительных чисел
посредством объектов, построенных (прямо или косвенно) из натуральных чисел.

Мы уже пользовались представлениями действительных чисел посредством бесконечных
десятичных или двоичных
дробей~(\textsection~\ref{sec:2-cantor_s_diagonal_method},~%
\ref{sec:5-higher_transfinite_cardinals}). В принципе можно пользоваться любым
множеством, эквивалентность которого множеству таких дробей
доказана~(см.~\textsection~\ref{sec:5-higher_transfinite_cardinals}), например
множеством всех множеств натуральных чисел. Но на практике выбирают такие
представления, которые упрощают определения свойств действительных чисел.

Упорядочение действительных чисел оказывается особенно прозрачным в случае
представления посредством дедекиндовых сечений (Дедекинд~\cite{dedekind1872}).
Допустим, что множество $\OLRealNumSet$ всех рациональных чисел разбито на два
непустых класса $X_{1}$, $X_{2}$‚ таких, что каждое рациональное число из
$X_{1}$ меньше каждого рационального числа из $X_{2}$. Такое разбиение
называется \emph{дедекиндовым сечением} $\OLRealNumSet$. В случае, если не
существует ни наибольшего рационального числа в нижнем классе $X_{1}$‚ ни
наименьшего в верхнем классе $X_{2}$, сечение называется \emph{открытым}.
Согласно идее Дедекинда, иррациональные числа должны быть именно там, где
встречаются открытые сечения. Рациональное число появляется в связи с любым из
двух \emph{замкнутых} сечений: одним --- для которого оно оказывается наибольшим
числом в $X_{1}$, и другим --- для которого оно наименьшее число в $X_{2}$.
Чтобы представление каждого действительного числа (рационального или
иррационального) было однозначным, можно пользоваться только нижними множествами
$X_{1}$ сечений, у которых $X_{1}$ не имеет наибольшего числа. Это приводит к
следующему определению (в котором мы пишем $\mathbf{x}$ вместо $X_{1}$ и
${\OLRealNumSet\OLsetminus\mathbf{x}}$ вместо $X_{2}$.

\emph{Действительное число} --- это такое множество $\mathbf{x}$ рациональных
чисел, что
(a)\itemlabel{property:p9-a}{(a)}~ни $\mathbf{x}$, ни
${\OLRealNumSet\OLsetminus\mathbf{x}}$ не пусто;
(b)\itemlabel{property:p9-b}{(b)}~$\mathbf{x}$ не содержит наибольшего
рационального числа; 
(c)\itemlabel{property:p9-c}{(c)}~каждое рациональное число из $\mathbf{x}$
меньше каждого рационального числа из ${\OLRealNumSet\OLsetminus\mathbf{x}}$.

Множество $\setOfSets{C}$ всех действительных чисел --- это множество всех таких
множеств $\mathbf{x}$ рациональных чисел.

В этом определении предполагается, что уже имеется система $\OLRealNumSet$ всех
рациональных чисел и эта система используется для построения представителей
действительных чисел таким образом, что $\OLRealNumSet$ не оказывается
подсистемой полученной системы $\setOfSets{C}$. (Если элементы
$\OLRealNumSet$~---~индивидуумы, то элементами $\setOfSets{C}$ будут множества
этих индивидуумов.)
%% ======================= Страница 35 =======================

Назовём теперь действительное число $\mathbf{x}$ \emph{рациональным}, если
${\OLRealNumSet\OLsetminus\mathbf{x}}$ имеет наименьший элемент $x$, и в этом
случае будем говорить, что $\mathbf{x}$ \emph{соответствует} этому рациональному
числу $x$ (системы $\OLRealNumSet$). В противном случае $\mathbf{x}$ называется
\emph{иррациональным} числом.

Рациональные числа среди действительных образуют подсистему
$\setOfSets{C}_{\OLRealNumSet}$ системы $\setOfSets{C}$,
изоморфную~(\textsection~\ref{sec:8-system_of_objects}) первоначальной системе
$\OLRealNumSet$ рациональных чисел; это подтверждается каждый раз, когда с
помощью описанного представления для действительных чисел определяется некоторое
понятие, которое первоначально было определено для чисел рациональных.

\begin{SCEnvWLabel}{Примеры.}{exmpls:p9}{exmpls:p9}
Действительное число $\boldsymbol{2}$ --- это множество рациональных чисел,
меньших рационального числа $2$, которому оно соответствует. Действительное
число $\boldsymbol{\sqrt{2}}$ --- это множество рациональных чисел, которые или
отрицательны, или имеют квадраты, меньшие рационального числа $2$ (среди этих
рациональных чисел нет наибольшего). Ввиду того, что не существует рационального
числа, квадрат которого ${=2}$ (как открыл Пифагор в шестом веке до~н.~э.),
${\OLRealNumSet\OLsetminus\boldsymbol{\sqrt{2}}}$ состоит из положительных
рациональных чисел, квадраты которых больше $2$ (среди этих рациональных чисел
нет наименьшего), так что число $\boldsymbol{\sqrt{2}}$ иррационально.
\end{SCEnvWLabel}

Отношение порядка для действительных чисел определяется таким образом:
${\mathbf{x}\OLprecB\mathbf{y}}$, если существует рациональное число $r$,
которое входит в $\mathbf{y}$, но не в $\mathbf{x}$. (Теперь докажите, что
$\setOfSets{C}$ линейно упорядочено посредством отношения $\OLprecB$ и что
система ${(\setOfSets{C}_{\OLRealNumSet}, \OLprecB)}$ изоморфна системе
${(\OLRealNumSet, <)}$.)

Действительное число $\mathbf{v}$ называется \emph{верхней гранью} множества
$\setOfSets{M}$ действительных чисел, если
${\mathbf{v}\OLsucceqB\mathbf{x}}$ для каждого действительного числа
$\mathbf{x}$, принадлежащего $\setOfSets{M}$.

\begin{SCEnvWLabel}{(A)}{theorem:p9-A}{(A)}
\emph{Если непустое множество} $\setOfSets{M}$ \emph{действительных чисел имеет
верхнюю грань}, \emph{то оно имеет и наименьшую верхнюю грань} $\mathbf{u}$
(${=\OLsup\setOfSets{M}}$).
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:p9-A-proof}{theorem:p9-A-proof}
Нам надо построить $\mathbf{u}$ как множество рациональных чисел, обладающее
свойствами~\ref{property:p9-a}--\ref{property:p9-c}. $\setOfSets{M}$ дано нам
как множество таких множеств рациональных чисел. Множество $\mathbf{u}$ мы
определяем так: рациональное число ${r\in\mathbf{u}}$ тогда и только тогда,
когда ${r\in\mathbf{x}}$ для некоторого действительного числа
${\mathbf{x}\in\setOfSets{M}}$. В
обозначениях~\textsection~\ref{sec:5-higher_transfinite_cardinals}
${\mathbf{u}=\OLunion{\setOfSets{M}}}$. Читателю предоставляется доказать, что
${\mathbf{u}=\OLsup\setOfSets{M}}$. (Доказать, что
$\mathbf{u}$~---~действительное число, $\mathbf{u}$ является верхней гранью
множества $\setOfSets{M}$ и $\setOfSets{M}$ не имеет верхней грани
${\mathbf{v}\OLprecB\mathbf{u}}$.)
%%
%% исправлена опечатка:
%% в оригинале последний в абзаце символ "<" выполнен нормальным шрифтом
%% вместо жирного
%%
\end{SCEnvWLabel}

Аналогично определяются нижние грани. Если действительное число $\mathbf{x}$
рационально, положим 
${\overline{\mathbf{x}}=\mathbf{x}\OLcup\left\{ x\right\}}$; в противном случае
пусть ${\overline{\mathbf{x}}=\mathbf{x}}$. Пусть
${\boldsymbol{-}\mathbf{x}}$~---~множество рациональных чисел ${-r}$ для
${r\in\OLRealNumSet\OLsetminus\overline{\mathbf{x}}}$. (Если $\mathbf{x}$
рационально, то ${\boldsymbol{-}\mathbf{x}}$ соответствует ${-x}$.) Пусть
${\boldsymbol{\setOfSets{M}}}$~---~множество действительных чисел
${\boldsymbol{-}\mathbf{x}}$ для ${\mathbf{x}\in\setOfSets{M}}$. Если
$\mathbf{w}$~---~нижняя грань для $\setOfSets{M}$, то
${\boldsymbol{-}\mathbf{w}}$~---~верхняя грань для
${\boldsymbol{-}\setOfSets{M}}$, так что ${\boldsymbol{-}\setOfSets{M}}$ имеет
$\OLsup$ и
${\boldsymbol{-}\left(\OLsup\boldsymbol{-}\setOfSets{M}\right)=%
 \OLinf\setOfSets{M}}$~%
\footnote{$\OLinf$~---~наибольшая нижняя грань.~---~\textit{Прим.~перев.}}.
%%
%% исправлен брак оригинала:
%% во второй строке предыдущего абзаца в оригинале непропечатано надчёркивание
%% над переменной x
%%

Если $\mathbf{x}$ и $\mathbf{y}$~---~действительные числа, то пусть
${\mathbf{x}\boldsymbol{+}\mathbf{y}}$ будет множеством рациональных чисел
${r+s}$ для ${r\in\mathbf{x}}$ и ${s\in\mathbf{y}}$; пусть
${\mathbf{x}\boldsymbol{-}\mathbf{y}=%
 \mathbf{x}\boldsymbol{+}\left(\boldsymbol{-}\mathbf{y}\right)}$; наконец, пусть
${\boldsymbol{|}\mathbf{x}\boldsymbol{|}=\mathbf{x}}$, если
${\mathbf{x}\OLsucceqB\boldsymbol{0}}$, и
${\boldsymbol{|}\mathbf{x}\boldsymbol{|}=\boldsymbol{-}\mathbf{x}}$, если
${\mathbf{x}\OLprecB\boldsymbol{0}}$. (Не следует путать $\boldsymbol{+}$
и $\boldsymbol{-}$ со сложением и вычитанием множеств, которые обозначаются
через $\OLcup$ и $\OLsetminus$.)

Пусть дана бесконечная последовательность $\mathbf{a}_{0}$,~$\mathbf{a}_{1}$,~%
$\ldots$,~$\mathbf{a}_{n}$,~$\ldots$ действительных чисел и действительное число
$\mathbf{a}$; мы говорим, что ${\lim\mathbf{a}_{n}=\mathbf{a}}$‚
%% ======================= Страница 36 =======================
если для каждого действительного числа
${\OLepsilon\OLsuccB\boldsymbol{0}}$ найдётся натуральное число
$n_{\OLepsilon}$, такое, что для каждого ${n>n_{\OLepsilon}}$ имеет место
${\boldsymbol{|}%
    \mathbf{a}_{n}\boldsymbol{-}\mathbf{a}%
 \boldsymbol{|}\OLprecB\OLepsilon}$. Например,
${\lim\frac{\boldsymbol{1}}{\boldsymbol{2}^{n}}=\boldsymbol{0}}$
(где ${\frac{\boldsymbol{1}}{\boldsymbol{2}^{n}}}$~---~действительное число,
соответствующее рациональному числу ${\frac{1}{2^{n}}}$).

\begin{SCEnvWLabel}{(B)}{theorem:p9-B}{(B)}
\emph{Если} ${\mathbf{u}=\OLsup\setOfSets{M}}$
(\emph{как в}~\ref{theorem:p9-A}), \emph{то существует такая
последовательность} $\mathbf{a}_{0}$,~$\mathbf{a}_{1}$,~$\ldots$,~%
$\mathbf{a}_{n}$,~$\ldots$ \emph{элементов} $\setOfSets{M}$, \emph{что}
${\lim\mathbf{a}_{n}=\mathbf{u}}$.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:p9-B-proof}{theorem:p9-B-proof}
Пусть $\setOfSets{M}_{n}$ есть множество действительных чисел, принадлежащих
$\setOfSets{M}$ и ${\OLsuccB%
 \mathbf{u}\boldsymbol{-}\frac{\boldsymbol{1}}{\boldsymbol{2}^{n}}}$. (Доказать,
что $\setOfSets{M}_{n}$ непусто.) Пусть $\mathbf{a}_{n}$~---~любое
действительное число, выбранное из $\setOfSets{M}_{n}$. (Доказать, что
${\lim\mathbf{a}_{n}=\mathbf{u}}$.)
\end{SCEnvWLabel}

Несмотря на то, что в этой теории анализ оказывается <<арифметизованным>>,
сохраняется глубокое различие между арифметикой и анализом, потому что в
качестве объектов анализа приходится пользоваться бесконечными множествами
объектов арифметики.

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

В самом общем смысле (однозначная) \emph{функция} $f$, или ${f(x)}$, или
${y=f(x)}$ \emph{от одной переменной} $x$~---~это соответствие, в силу которого
каждому элементу $x$ некоторого множества $X$ отвечает единственный элемент $y$
некоторого множества $Y$.

Множество $X$ называется при этом \emph{областью изменения независимой
переменной}, или \emph{областью определения функции}. Функцию называют также
\emph{отображением} $X$ \emph{в} $Y$ (или \emph{функцией от} элемента множества
$X$, \emph{принимающей в качестве значения} элемент множества $Y$, или
\emph{операцией над} элементом множества $X$, \emph{дающей} элемент множества
$Y$, и т.~д.).

\emph{Область изменения зависимой переменной} $y$, или ${f(x)}$‚~---~это
подмножество $Y_{1}$ множества $Y$, состоящее из тех элементов $Y$, которые
используются при этом соответствии, т.~е. из тех, которые посредством функции
$f$ поставлены в соответствие каким-нибудь элементам множества $X$. При этом $X$
и $Y_{1}$ находятся в \emph{много\nobreakdash-однозначном соответствии}, потому
что каждому элементу из $X$ соответствует ровно один элемент из $Y_{1}$, но
элемент из $Y_{1}$ может (вообще говоря) соответствовать многим элементам из
$X$. Элемент $x$ из $X$ является \emph{аргументом функции}, или \emph{значением
независимой переменной}. Соответствующий элемент $y$ из $Y$ является
\emph{соответствующим значением функции}, или \emph{зависимой переменной}, или
\emph{значением функции для этого аргумента}. (Иногда <<аргумент>> употребляется
в смысле <<независимой переменной>>.)

(Однозначная) \emph{функция} $f$, или ${f(x_{1}, \ldots, x_{n})}$‚ или
${y=f(x_{1}, \ldots, x_{n})}$, \emph{от} $n$ \emph{переменных}
${x_{1}, \ldots, x_{n}}$~---~это соответствие, в силу которого каждой
упорядоченной $n$\nobreakdash-ке ${(x_{1}, \ldots, x_{n})}$ объектов, где
${x_{1}\in X_{1}}$, ${x_{2}\in X_{2}}$, $\ldots$, ${x_{n}\in X_{n}}$, отвечает
единственный объект $y$, где ${y\in Y}$. Функцию от $n$ переменных можно
рассматривать как функцию от одной переменной, множеством $X$ для которой служит
класс всех упорядоченных $n$\nobreakdash-ок ${(x_{1}, \ldots, x_{n})}$
указанного вида. Терминология, введённая для функций от одной переменной,
распространяется на случай $n$ переменных. Так, $X_{1}$ есть \emph{область
изменения} переменной $x_{1}$, $X_{2}$~---~\emph{область изменения} $x_{2}$,
$\ldots$, $X_{n}$~---~\emph{область изменения} $x_{n}$. При этом множества
$X_{1}$, $X_{2}$, $\ldots$‚ $X_{n}$ могут все совпадать, или же может иметься и
несколько (вплоть до $n$) различных областей изменения. Всякая отдельная
последовательность ${x_{1}, \ldots, x_{n}}$ элементов соответственно из
${X_{1}, \ldots, X_{n}}$ является \emph{cистемой}, или \emph{набором} (или
$n$\nobreakdash-кой) \emph{аргументов}.
%%
%% исправлена опечатка
%% в оригинале было "истемой" вместо "системой"
%%
%% ======================= Страница 37 =======================

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

Первая идея является более объемлющей, и изучающий должен иметь в виду прежде
всего её. Но вторая идея естественным путём приводит к полезным соглашениям,
касающимся обозначений, в силу которых, например, если <<$f(x)$>> обозначает
некоторую функцию от независимой переменной $x$, а $a$, $b$ и т.~д. являются
значениями этой независимой переменной (т.~е. аргументами), то <<$f(a)$>>
обозначает значение функции для этого аргумента $a$, <<$f(b)$>>~---~значение
функции для ${x=b}$ и т. д.

Нужно иметь в виду, что <<$f(x)$>> можно понимать в каждом из следующих двух
значений:
1.\itemlabel{list:p10-l1-1}{1}~Как саму функцию (т.~е. как
много\nobreakdash-однозначное соответствие между $X$ и $Y_{1}$).
2.\itemlabel{list:p10-l1-2}{2}~Если $x$ означает некоторый объект из области, то
как соответствующее этому объекту значение функции (т.~е. как некоторый элемент
$y$ из $Y_{1}$). Если $x$ никак не зафиксирован, то $f(x)$ в последнем смысле
называется \emph{общим значением} рассматриваемой функции.

\begin{SCEnvWLabel}{Пример 1.}{exmpl:p10-1}{exmpl:p10-1}
Когда мы говорим <<${x+y}$ симметрична>>, мы подразумеваем под <<${x+y}$>> саму
функцию. Когда мы говорим <<сумма ${x+y}$ любых двух натуральных чисел $x$ и $y$
должна быть ${\geqslant x}$>>‚ мы подразумеваем под <<${x+y}$>> не функцию, а
число (общее значение функции).
\end{SCEnvWLabel}

Этой неопределённости можно избежать, если для обозначения функции употреблять
<<$f$>> вместо <<$f(x)$>>‚ коль скоро речь идёт о функциях, для каждой из
которых был введён символ, например <<$f$>>, <<$g$>>, <<$+$>> или <<$\phi$>>. Но
обозначения, в которых указываются независимые переменные, очень удобны для
получения обозначений других функций, составленных из данных функций (и
констант), например <<${f(g(x))}$>>‚ <<${x^{2}+3x}$>> или <<${\phi(2, x)}$>>.

\begin{SCEnvWLabel}{Пример 2.}{exmpl:p10-2}{exmpl:p10-2}
Чтобы рассмотреть это подробнее, допустим, что $f$ и $g$~---~данные
\emph{арифметические функции} от одной переменной, т.~е. отображения множества
натуральных чисел на это же множество. Пусть $x$~---~произвольное натуральное
число. Тогда $g(x)$ будет натуральным числом, т.~е. значением функции $g$ для
$x$ как аргумента, и ${f(g(x))}$ будет натуральным числом, т.~е. значением
функции $f$ для натурального числа $g(x)$ как аргумента. Таким образом, для
любого натурального числа $x$ определено другое число ${f(g(x))}$. Итак,
<<${f(g(x))}$>> обозначает общее значение новой функции
(смысл~\ref{list:p10-l1-2}); удобно также пользоваться этим обозначением в
качестве названия для самой новой функции (смысл~\ref{list:p10-l1-1}).
\end{SCEnvWLabel}

Имеется и другой способ обозначения (введённый Чёрчем~\cite{church1932})‚ в
котором участвуют независимые переменные, но функция $f$ обозначается иначе, чем
её общее значение, а именно <<${\OLlambda{x}{f(x)}}$>> или, для функции
от $n$ переменных,
<<${\OLlambda{x_{1}\ldots x_{n}}{f(x_{1}, \ldots, x_{n})}}$>>, например
<<${\OLlambda{x}{f(g(x))}}$>>‚ <<${\OLlambda{x}{x^{2}+3x}}$>>‚
<<${\OLlambda{x}{\phi(2, x)}}$>>. Мы будем для ясности пользоваться этими
\lamcalc-обозначениями в тех случаях, когда нужна будет особенная
осторожность.

\begin{SCEnvWLabel}{Пример 3.}{exmpl:p10-3}{exmpl:p10-3}
Пусть $\phi$~---~функция от двух натуральных чисел. Используя
\lamcalc-обозначения надлежащим образом, т.~е. как раз всюду там, где имеется
в виду функция, а не её общее значение, мы можем различать между собой:
(a)\itemlabel{list:p10-l2-a}{(a)}~число ${\phi(x, y)}$,
(b)\itemlabel{list:p10-l2-b}{(b)}~функцию ${\OLlambda{x}{\phi(x, y)}}$ от одной
переменной $x$ с параметром $y$,
(c)\itemlabel{list:p10-l2-c}{(c)}~функцию ${\OLlambda{xy}{\phi(x, y)}}$ от
двух переменных, для которой $x$~---~первая, а $y$~---~вторая переменная,
(d)\itemlabel{list:p10-l2-d}{(d)}~функцию ${\OLlambda{yx}{\phi(x, y)}}$, для
которой
%% ======================= Страница 38 =======================
$y$~---~первая, а $x$~---~вторая переменная,
(e)\itemlabel{list:p10-l2-e}{(e)}~функцию
${\OLlambda{x}{\OLlambda{y}{\phi(x, y)}}}$ от одной переменной $x$, значениями
которой служат функции от другой переменной $y$, и т.~д.
(Шейнфинкель~\cite{schoenfinkel1924} и Чёрч
отождествляют~\ref{list:p10-l2-c}~и~\ref{list:p10-l2-e}, но в этом нет для нас
необходимости.)
\end{SCEnvWLabel}

Для любой $n$\nobreakdash-ки ${t_{1}, \ldots, t_{n}}$ аргументов функции $f$
\begin{equation*}
\left\{\OLlambda{x_{1}\ldots x_{n}}%
 {f(x_{1}, \ldots, x_{n})}\right\}(t_{1}, \ldots, t_{n})=%
 f(t_{1}, \ldots, t_{n})\text{.}
\end{equation*}

\noindent%
Например,
\begin{gather*}
\left\{\OLlambda{x}{x^{2}+3x}\right\}(2)=10\text{,}\quad
\left\{\OLlambda{x}{\phi(x, y)}\right\}(0)=\phi(0, y)\text{,}\\
\left\{\OLlambda{yx}{\phi(x, y)}\right\}(0, 3)=\phi(3, 0)\text{,}\quad
\left\{\OLlambda{xy}{\phi(x, y)}\right\}(z, x)=\phi(z, x)\text{.}
\end{gather*}

Мы рассматриваем функцию как много\nobreakdash-однозначное соответствие. Можно
пойти дальше и определить, что такое много\nobreakdash-однозначное соответствие,
в зависимости от того, в какой теории производится всё рассмотрение. В
теоретико\nobreakdash-множественных терминах это соответствие можно отождествить
с множеством всех упорядоченных пар ${(x, y)}$ соответствующих элементов
множеств $X$ и $Y_{1}$. Вместо этого можно говорить и о законе или правиле
установления соответствия, по крайней мере если рассматриваются такие функции,
что для каждой из них может быть задан такой закон или правило в некотором
принятом смысле. В случае, когда $X$~---~конечное множество, функцию можно
задать в виде таблицы.

\begin{SCEnvWLabel}{Пример 4.}{exmpl:p10-4}{exmpl:p10-4}
Пусть $X$ и $Y$ оба являются системой вычетов по модулю $2$, т.~е.
${X=Y=\{0, 1\}}$. Функции ${x'}$ и ${x\cdot y}$ можно определить посредством
следующих таблиц:

\begin{center}\noindent
\begin{tabular}{lcccccccc}
&&$x'$&&&&&\multicolumn{2}{c}{$x\cdot y$}\\
&&&&&&$y$&$0$&$1$\\\cline{3-3}\cline{6-9}
$x$&$0$&\multicolumn{1}{|c|}{$1$}&&&$x$&$0$&%
    \multicolumn{1}{|c|}{$0$}&%
    \multicolumn{1}{c|}{$0$}\\\cline{3-3}\cline{8-9}
&$1$&\multicolumn{1}{|c|}{$0$}&&&&$1$&%
    \multicolumn{1}{|c|}{$0$}&%
    \multicolumn{1}{c|}{$1$}\\\cline{3-3}\cline{8-9}
\end{tabular}
\end{center}

\noindent%
Тогда по второй таблице ${0\cdot 0=0\cdot 1=1\cdot 0=0}$ и ${1\cdot 1=1}$.
\end{SCEnvWLabel}

%% ======================= Страница 39 =======================

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

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

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

При арифметизации анализа~(\textsection~\ref{sec:9-number_theory_vs_analysis})
бесконечная совокупность (например, рациональных чисел, образующих нижнюю
половину дедекиндова сечения, или цифр последовательности, образующих
бесконечную десятичную дробь,~и~т.~п.) составляла один объект, и множество всех
таких объектов рассматривалось как новая совокупность. Отсюда напрашивался
переход к канторовской общей теории множеств.

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

\begin{SCEnvWLabel}{(A)}{paradox:p11-A}{(A)}
\emph{Парадокс Бурали-Форти}~\cite{buraliforti1897}‚ известный также Кантору
ещё в 1895~г., возник в канторовской теории трансфинитных ординальных
чисел~\footnote{Речь идёт о парадоксе, к которому приводит рассмотрение
порядкового типа множества всех порядковых чисел. Ср. Хаусдорф, Теория
множеств~\cite[стр. 65 перевода на русский язык]{hausdorff1927}~---~%
\emph{Прим. перев.}}.
%%
%% исправлена опечатка
%% в оригинале "трасфинитных"
%%
%% в примечании добавлено "перевода на русский язык"
%% TODO: подумать об исправлении. Возможно стоит выделить перевод
%% в отдельную запись библиографии
%%
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{(B)}{paradox:p11-B}{(B)}
Несколько аналогичных антиномий встречается в теории трансфинитных
кардинальных чисел, в частности \emph{парадокс Кантора} (найденный им
в~1899~г.). Рассмотрим множество всех множеств; обозначим его
через~$\setOfSets{M}$. По теореме Кантора~(теорема~\ref{theorem:C}~%
\textsection~\ref{sec:5-higher_transfinite_cardinals})
${\OLcard{\OLpowerset{\setOfSets{M}}}>\OLcard{\setOfSets{M}}}$. Кроме того, так
как $\setOfSets{M}$ есть множество всех множеств, а
${\OLpowerset{\setOfSets{M}}}$~---~некоторое множество множеств (именно,
множество всех подмножеств $\setOfSets{M}$), то
${\OLpowerset{\setOfSets{M}}\subseteq \setOfSets{M}}$. Поэтому, в силу
следствия~\ref{theorem:A-corollary-A} из теоремы~\ref{theorem:A},
${\OLcard{\OLpowerset{\setOfSets{M}}}\leqslant\OLcard{\setOfSets{M}}}$‚ а
значит, в силу~\textsection~\ref{sec:3-cardinal_number}, неверно, что
${\OLcard{\OLpowerset{\setOfSets{M}}}>\OLcard{\setOfSets{M}}}$. Итак, мы
доказали как то, что
${\OLcard{\OLpowerset{\setOfSets{M}}}>\OLcard{\setOfSets{M}}}$, так и то, что
это неверно.

Отправляясь от того же самого $\setOfSets{M}$, мы можем получить парадокс также
следующим образом. Для каждого элемента $M$ из $\setOfSets{M}$, т.~е. для
произвольного множества $M$ по теореме~\ref{theorem:C} найдётся другой элемент
$M'$ из $\setOfSets{M}$, а именно ${\OLpowerset{\setOfSets{M}}}$, такой, что
${\OLcard{M}<\OLcard{M'}}$. Отсюда, по теореме~\ref{theorem:D},
${\OLcard{M}<\OLcard{\OLunion{\setOfSets{M}}}}$ для любого элемента $M$ из
$\setOfSets{M}$. Но $\setOfSets{M}$~---~множество всех множеств, так что
${\OLunion{\setOfSets{M}}}$ является одним из его элементов. Выбирая этот
элемент в качестве $M$ для только что доказанного неравенства, получаем
${\OLcard{\OLunion{\setOfSets{M}}}<\OLcard{\OLunion{\setOfSets{M}}}}$. Но в
силу~\textsection~\ref{sec:3-cardinal_number}, для любого множества $M$ неверно,
что ${\OLcard{M}<\OLcard{M}}$; поэтому, в частности, неверно, что
${\OLcard{\OLunion{\setOfSets{M}}}<\OLcard{\OLunion{\setOfSets{M}}}}$.
%% ======================= Страница 40 =======================

Парадокс с ${\OLunion{\setOfSets{M}}}$ получится таким же образом, если,
отправляясь от множества всех мощностей, мы выберем в качестве $\setOfSets{M}$
множество, содержащее для каждой мощности некоторое множество $M$ этой мощности.

Если использованное здесь понятие множеств произвольных элементов кажется
слишком расплывчатым и потому нематематическим, можно условиться, что
допустимыми элементами множеств являются:
(a\textsubscript{1})\itemlabel{list:p11-l1-a1}{(a\textsubscript{1})}~натуральные
числа ${0,\; 1,\; 2,\;\ldots}$ (или
(a\textsubscript{2})\itemlabel{list:p11-l1-a2}{(a\textsubscript{2})}~пустое
множество $\OLemptyset$) и 
(b)\itemlabel{list:p11-l1-b}{(b)}~всякое множество, элементы которого являются
допустимыми. При этом условии предыдущие парадоксы и следующий получаются, как
прежде (с~\ref{list:p11-l1-a1}, см. Генцен~\cite{gentzen1936}).
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{(C)}{paradox:p11-C}{(C)}
\emph{Парадокс Рассела}~\cite{russel1902-1903}‚ независимо от него открытый также
Цермело, связан с множеством всех множеств, которые не являются элементами самих
себя. Обозначим это множество через $T$. Является ли $T$ элементом самого себя?

Допустим, что $T$ является элементом самого себя, т.~е.~${T\in T}$. Согласно
этому допущению, $T$ является элементом~$T$, т.~е.~$T$~---~элемент множества
всех множеств, не являющихся элементами самих себя, т.~е.~$T$~---~это множество,
которое не является элементом самого себя, т.~е.~${T\OLnotin T}$. Это
противоречит допущению~${T\in T}$. Пока что ещё нет парадокса, потому что
противоречие между ${T\in T}$ и ${T\OLnotin T}$ возникло только в результате
допущения ${T\in T}$. Посредством reductio ad absurdum мы заключаем, что это
допущение ложно. Итак, полностью, без каких-либо допущений, доказано,
что~${T\OLnotin T}$.

Продолжим рассуждения, отправляясь теперь от полученного
результата~${T\OLnotin T}$. Этот результат состоит в том, что $T$~---~не элемент
множества всех множеств, которые не являются элементами самих себя,
т.~е.~$T$~---~это не множество, которое не является элементом самого
себя~\footnote{Без этого снятия двойного отрицания можно
обойтись.~---~\emph{Прим. перев.}}, т.~е.~$T$~---~это множество, которое
является элементом самого себя, т.~е.~${T\in T}$. Теперь установлено как то,
что~${T\OLnotin T}$, так и то, что~${T\in T}$, и мы получили парадокс.

Этот парадокс можно следующим образом извлечь из парадокса Кантора. Если мы
условимся, что допустимыми элементами являются
только~\ref{list:p11-l1-a2}~и~\ref{list:p11-l1-b}, так что элементами множеств
могут служить только множества, то, коль скоро $\setOfSets{M}$ является
множеством всех множеств,~${\OLpowerset{\setOfSets{M}}=\setOfSets{M}}$ и
множество $T$ парадокса Рассела получается, если доказательство
леммы~\ref{lemma:A}~\textsection~\ref{sec:5-higher_transfinite_cardinals}
применить к тождественному \isom-соответствию
${\setOfSets{M}\sim\OLpowerset{\setOfSets{M}}}$, при котором каждый элемент
множества $\setOfSets{M}$ соответствует в ${\OLpowerset{\setOfSets{M}}}$ самому
себе. Популяризируя этот парадокс, Рассел~\cite{russel1919} рассматривает
деревенского парикмахера, который бреет всех тех и только тех жителей своей
деревни, которые не бреются сами. Бреет ли он самого себя? (Конечно, здесь мы не
можем избежать парадокса просто путём заключения, что никогда не было такого
парикмахера~\footnote{Но зато удаётся избежать парадокса путём заключения, что
такого парикмахера вообще не может существовать, и это заключение как раз
доказывается этим парадоксом, --- только и всего.~---~\emph{Прим. перев.}}.)

Каждый муниципалитет в Голландии должен иметь мэра, и два разных муниципалитета
не могут иметь одного и того же мэра. Иногда оказывается, что мэр не проживает в
своём муниципалитете. Допустим, что издан закон, по которому некоторая
территория $S$ выделяется исключительно для таких мэров, которые не живут в
своих муниципалитетах, и предписывающий всем этим мэрам поселиться на этой
территории. Допустим, далее, что этих мэров оказалось столько, что $S$ образует
муниципалитет. Где должен проживать мэр $S$?
(Маннури,~ср.~ван~Данциг~\cite{dantzig1948}.)

Можно говорить также о библиотекаре конгресса, составляющем для библиотеки
конгресса библиографию всех тех библиографий, имеющихся в библиотеке конгресса,
которые не перечисляют самих себя (Гонсет~\cite{gonseth1933}).
%% ======================= Страница 41 =======================

Рассел указал также, как можно изложить его парадокс посредством логической
терминологии вместо теоретико-множественной. Свойство называется
,,предикабельным``, если оно имеет место по отношению к самому себе, и
,,импредикабельным``, если оно не имеет места по отношению к самому себе.
Например, свойство ,,абстрактно`` является абстрактным, а потому предикабельным;
но свойство ,,конкретно`` также является абстрактным, а не конкретным и потому
импредикабельно. Каково свойство ,,импредикабельно``?
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{(D)}{paradox:p11-D}{(D)}
\emph{Парадокс Ришара}~\cite{richard1905}, полученный по существу также
Диксоном~\cite{dixon1906}, связан с понятием конечной определимости. Для
конкретности мы будем иметь в виду конечную определимость в некотором
языке~---~например русском\footnote{В подлиннике речь идёт об английском
языке.~---~\emph{Прим. перев.}} --- с заранее данными алфавитом, запасом слов и
грамматикой. Алфавит мы будем считать состоящим из пробела (для разделения
слов), 33 русских букв и запятой. Под ,,выражением`` этого языка мы будем
понимать просто произвольную последовательность из этих 35 символов, не
начинающуюся с пробела. Все такие выражения можно пересчитать при помощи того
метода, которым мы воспользовались в
конце~\textsection~\ref{sec:1-enumerable_sets} для пересчёта всех алгебраических
уравнений.

Выражение может служить определением арифметической функции от одной переменной
(т.~е. функции от натурального числа, принимающей в качестве значений только
натуральные числа). Опуская в упомянутом выше пересчёте всех выражений русского
языка те выражения, которые не являются определениями арифметических функций, мы
получаем некоторый пересчёт ${E_{0}, E_{1}, E_{2}, \ldots}$ тех выражений,
которые служат такого рода определениями (а сами определяемые функции пусть
будут соответственно ${f_{0}(n), f_{1}(n), f_{2}(n), \ldots}$).

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

В этом заключённом в кавычки выражении упоминается вышеописанный пересчёт всех
выражений русского языка, служащих определением арифметической функции, но не
даётся определения этого пересчёта. Однако нетрудно в качестве части взятого в
кавычки выражения полностью выписать определение этого пересчёта. Тогда мы
получим определение некоторой функции (короче говоря, функции ${f_{n}(n)+1}$)
посредством некоторого выражения русского языка. Эта функция, в силу её
определения, должна отличаться от каждой функции, определимой посредством
какого-либо выражения русского языка.

Этот парадокс представляет особый интерес ввиду его применимости к таким языкам,
как русский, и в связи с тем, что он так сходен с канторовским доказательством
неперечислимости всех арифметических
функций~(\textsection~\ref{sec:2-cantor_s_diagonal_method}). Ришар дал этот
парадокс в форме, связанной с определением действительного числа, параллельно
канторовскому доказательству неперечислимости всех действительных чисел.

Рассмотрим выражение <<наименьшее натуральное число, которое нельзя назвать
посредством меньше чем тридцати трёх слогов>>. Это выражение при помощи тридцати
двух слогов называет некоторое число, которое по определению нельзя назвать
посредством меньше чем тридцати трёх слогов! (Берри~\cite{berry1906})
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{(E)}{paradox:p11-E}{(E)}
Эти современные парадоксы, более или менее связанные с теорией множеств,
родственны одному очень древнему.

Высказывание <<все критяне~---~лжецы\ldots>> приписывается критскому философу
Эпимениду (шестой век до~н.~э.). (Это высказывание приводится апостолом
%% ======================= Страница 42 =======================
Павлом в <<Послании к Титу>> I, 12, как принадлежащее одному критскому
<<пророку>>, которого раннее христианство, согласно позднейшим исследованиям,
отождествляло с Эпименидом. См. Вейль~\cite[стр.228]{weyl1949}.)

Будем различать два рода лжецов: лжецы первого рода, которые иногда говорят
правду, и лжецы второго рода, которые говорят только ложь. Будем понимать
высказывание Эпименида в том смысле, что все критяне являются лжецами второго
рода. Допустим, что это высказывание истинно. В силу его смысла и того факта,
что Эпименид~---~критянин, оно должно быть тогда ложным. Получилось
противоречие; отсюда путём reductio ad absurdum заключаем, что это высказывание
ложно. Из ложности этого высказывания вытекает, что существовал или будет
существовать некоторый критянин, который иногда говорит правду. Если бы это
высказывание было единственным, которое когда-либо произносил хоть один
критянин, мы получили бы парадокс. Логически неудовлетворительно то, что
парадокса можно избежать только с помощью исторического предположения, что
существовал критянин, который иногда говорил правду.

\emph{Парадокс Эпименида}, известный также как \emph{парадокс лжеца},
встречается также в сильной форме, когда некоторое лицо говорит просто
<<высказывание, которое я сейчас произношу, ложно>>. Стоящее в кавычках
высказывание не может быть без противоречия ни истинным, ни ложным. Этот вариант
парадокса приписывается Эвбулиду (четвёртый век до~н.~э.) и был хорошо известен
в древности. (См. Рюстов\cite{rustow1910}.) Если высказывание <<все
критяне~---~лжецы\ldots>> не принадлежит Эпимениду или первоначально не
воспринималось как парадокс, то эвбулидовский вариант лжеца может быть древнее,
чем вариант <<лгущего критянина>>.

В древней <<дилемме крокодила>> крокодил украл ребёнка. Крокодил обещал отцу
вернуть ребёнка, если отец угадает, вернёт ему крокодил ребёнка или нет. Что
должен сделать крокодил, если отец скажет, что крокодил не вернёт ему ребёнка?
(См.~Прандтль~\cite[стр.493]{prandtl1855}.)

С этим парадоксом связана следующая загадка. Путешественник попал к людоедам.
Они разрешают ему произнести какое-нибудь высказывание и ставят условие, что
если его высказывание будет истинным, то его сварят, а если ложным~---~то его
зажарят. Какое высказывание следует произнести путешественнику? (В другой форме
эта загадка встречается в <<Дон Кихоте>> Сервантеса‚ 1605, II, 51.)
\end{SCEnvWLabel}

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

Читатель может испробовать свои силы, пытаясь разрешить эти парадоксы. За
половину столетия с тех пор, как возникла эта проблема, не было найдено ни
одного решения, с которым бы все согласились.

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

Мысль, что парадоксы следует решать в этом направлении, приходит на ум при
первом знакомстве с ними. Можно предположить, что в
парадоксах~\ref{paradox:p11-A}--\ref{paradox:p11-C} ошибка состоит в
употреблении слишком обширных множеств, таких, как множество всех множеств или
множество всех кардинальных чисел, или в разрешении рассматривать множества как
элементы самих себя, что опять-таки служит возражением против множества всех
множеств. Отвергать эти предположения не обязательно, но только их нельзя
считать простыми. Они ставят нас перед проблемой перестройки теории множеств на
совершенно изменённой основе, детали которой содержатся в них разве что в виде
намёка. Например, если мы запретим множество всех кардинальных чисел, мы не
сможем рассматривать множество всех натуральных чисел, пока нам не станет
известно, что этими числами не исчерпываются все кардинальные числа, и та же
самая

stub

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

stub

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

stub

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

stub