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-\emph{ок элементов счётного множества} для
каждого фиксированного натурального~$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}$, достаточно представить
действительные числа в форме
характеристика\nobreakdash-плюс\nobreakdash-мантисса‚ например
${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-1897}.

К множествам присоединяются \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{russell1902} отождествляют кардинальное
число~$\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}{Пример\kern1ex1.}{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}{Пример\kern1ex2.}{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}{Теорема\kern1exA.}{theorem:p4-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:p4-A-proof}{theorem:p4-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:p4-A-proof-rule}{theorem:p4-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}{Следствие\kern1exA.}{theorem:p4-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}$.)

\itemlabel{def:p4-m_plus_one}{def:p4-m_plus_one}Если рассматривать натуральные
числа~${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$ (читается <<алеф\nobreakdash-нуль>>).

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

\begin{SCEnvWLabel}{Доказательство.}{theorem:p4-A-corollary-B-proof}%
{A-corollary-B-proof}
Так как $n$~---~кардинальное число подмножества~${\{0,1,2,\ldots,n-1\}}$
множества всех натуральных чисел, то в силу
следствия~\ref{theorem:p4-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}{Теорема\kern1exB.}{theorem:p4-B}{B}
\emph{Всякое бесконечное множество}~$M$ \emph{имеет
счётно\nobreakdash-бесконечное подмножество}.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:p4-B-proof}{theorem:p4-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}{Следствие\kern1exA.}{theorem:p4-B-corollary-A}{B-corollary-A}
\emph{Если} $\OLcard{M}$~---~\emph{бесконечное кардинальное число},
\emph{то}~${\alephZero\leqslant\OLcard{M}}$.
\end{SCEnvWLabel}

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

\begin{SCEnvWLabel}{Следствие\kern1exB.}%
{theorem:p4-B-corollary-B}{theorem:p4-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}{Следствие\kern1exC.}%
{theorem:p4-B-corollary-C}{theorem:p4-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}{Следствие\kern1exD.}{theorem:p4-B-corollary-D}{D}
\emph{Кардинальное число несчётного множества не изменится от удаления конечного
или счётно\nobreakdash-бесконечного подмножества элементов}.
\end{SCEnvWLabel}
%% ======================= Страница 21 =======================

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

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

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

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

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

\begin{SCEnvWLabel}{Критерий.}%
                   {lemma:p5-A-proof-criterion}{lemma:p5-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}{Теорема\kern1exC.}{theorem:p5-C}{C}
\emph{Для любого множества}~$M$ \emph{справедливо
соотношение}~${\OLcard{M}<\OLcard{\OLpowerset{M}}}$ (теорема Кантора).
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Доказательство.}{theorem:p5-C-proof}{p5-C-proof}
Если $N_{1}$~---~совокупность единичных подмножеств множества~$M$‚
то~${M\sim N_{1}\subset\OLpowerset{M}}$. Значит, по
следствию~\ref{theorem:p4-A-corollary-A} из теоремы~\ref{theorem:p4-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:p5-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}{Лемма\kern1exB.}{lemma:p5-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:p5-B-proof}{lemma:p5-B-proof}
Так как~${M\subseteq S}$, то, по следствию~\ref{theorem:p4-A-corollary-A} из
теоремы~\ref{theorem:p4-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}{Теорема\kern1exD.}{theorem:p5-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:p5-D-proof}{theorem:p5-D-proof}
В силу определения~${\OLunion{\setOfSets{M}}}$ каждый элемент~$M$
из~$\setOfSets{M}$ является подмножеством множества~${\OLunion{\setOfSets{M}}}$.
Теперь теорема следует из леммы~\ref{lemma:p5-B}, если взять в
ней~${\OLunion{\setOfSets{M}}}$ в качестве~$S$.
\end{SCEnvWLabel}

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

Более глубокое изложение канторовской теории абстрактных множеств можно найти,
например, у Кантора~\cite{cantor1895-1897},
{\renewcommand*{\multicitedelim}{~или~}%
Хаусдорфа~\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}{~или~}%
Хаусдорф~\cite[стр.~61\protect\footnotemark]{hausdorff1914,hausdorff1927}}
\footnotetext{Стр.~65 русского издания книги Хаусдорфа. См.~также теорему~19 на
стр.~107 книги П.~С.~Александрова~\cite{aleksandrov1948}~---~\textit{Прим.~%
ред.}} или Френкель~\cite[стр.~205]{fraenkel1928}). Краткое рассмотрение
знаменитой <<континуум\nobreakdash-проблемы>>, состоящей в решении вопроса,
существует ли хоть одно кардинальное число между
$\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:p4-B-corollary-D} теоремы~\ref{theorem:p4-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%
которые можно свернуть в одну\nobreakdash-единственную последовательность
\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%
свёртываются в одну\nobreakdash-единственную последовательность
\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:p4-A-corollary-A} из
теоремы~\ref{theorem:p4-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}$,
которые среди ранее порождённых следуют за какими\nobreakdash-то числами~(в
силу~\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)}~Если какое\nobreakdash-нибудь натуральное
число~$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 =======================

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

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

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

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

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

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

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

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

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

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

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

\begin{SCEnvWLabel}{Лемма\kern1ex3.}{lemma:p7-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:p7-2})
на каждой стадии, двигаясь слева, находим первую самую внутреннюю пару среди ещё
не использованных и присоединяем эту пару к спариванию. По
лемме~\ref{lemma:p7-2} никакого другого собственного спаривания найти
невозможно. Скобки с третьей по двенадцатую образуют подмножество
последовательных скобок, собственное спаривание которых уже получено в процессе
спаривания всего множества. По лемме~\ref{lemma:p7-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$ состоит из двух последовательностей
\begin{equation}\label{eq:p8-1}\tag{1}
0,\;1,\;2,\;3,\;\ldots\text{;}\quad\quad
\omega,\;\omega+1,\;\omega+2,\;\omega+3,\;\ldots\text{,}
\end{equation}

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

Каждый из этих трёх примеров можно очевидным образом изменить так, что получится
система типа~${(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{арифметике в узком смысле} рассматриваются главным образом конкретные
операции, именуемые $+$~(сложение)~и~$\OLmult$~(умножение), а иногда также
некоторые другие связанные с ними операции. В \emph{арифметике в широком
смысле}, или \emph{теории чисел}, используется более широкий класс понятий.

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

В то время как арифметика, или теория чисел, изучает системы
мощности~$\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\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
%%
%% затем замечание на эту опечатку замечено в списке опечаток в конце оригинала
%% для страницы 35 строка 13 снизу
%%

Если $\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}{(B)}
Пусть $\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$ поставлены в соответствие каким\nobreakdash-нибудь элементам
множества~$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{системой}, или \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}{Пример\kern1ex1.}{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}{Пример\kern1ex2.}{exmpl:p10-2}{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\nobreakdash-обозначениями в тех случаях, когда нужна будет особенная
осторожность.

\begin{SCEnvWLabel}{Пример\kern1ex3.}{exmpl:p10-3}{exmpl:p10-3}
Пусть $\phi$~---~функция от двух натуральных чисел. Используя
\lamcalc\nobreakdash-обозначения надлежащим образом, т.~е. как раз всюду там,
где имеется в виду функция, а не её общее значение, мы можем различать между
собой:
(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}{Пример\kern1ex4.}{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{Парадокс Бурали\nobreakdash-Форти}~\cite{buraliforti1897}‚ известный также
Кантору ещё в 1895~г., возник в канторовской теории трансфинитных ординальных
чисел~\footnote{Речь идёт о парадоксе, к которому приводит рассмотрение
порядкового типа множества всех порядковых чисел. Ср. Хаусдорф, Теория
множеств~\cite[стр.~65 перевода на русский язык]{hausdorff1927}~---~%
\emph{Прим.~перев.}}.
%%
%% исправлена опечатка
%% в оригинале "трасфинитных"
%%
%% в примечании добавлено "перевода на русский язык"
%% TODO: подумать об исправлении. Возможно стоит выделить перевод
%% в отдельную запись библиографии
%%
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{(B)}{paradox:p11-B}{(B)}
Несколько аналогичных антиномий встречается в теории трансфинитных
кардинальных чисел, в частности \emph{парадокс Кантора} (найденный им
в~1899~г.). Рассмотрим множество всех множеств; обозначим его
через~$\setOfSets{M}$. По теореме Кантора~(теорема~\ref{theorem:p5-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:p4-A-corollary-A} из теоремы~\ref{theorem:p4-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:p5-C} найдётся другой
элемент~$M'$ из~$\setOfSets{M}$, а именно~${\OLpowerset{\setOfSets{M}}}$, такой,
что~${\OLcard{M}<\OLcard{M'}}$. Отсюда, по теореме~\ref{theorem:p5-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{russell1902-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 мы заключаем, что это
допущение ложно. Итак, полностью, без каких\nobreakdash-либо допущений,
доказано, что~${T\OLnotin T}$.

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

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

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

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

Рассел указал также, как можно изложить его парадокс посредством логической
терминологии вместо теоретико\nobreakdash-множественной. Свойство называется
,,предикабельным``, если оно имеет место по отношению к самому себе, и
,,импредикабельным``, если оно не имеет места по отношению к самому себе.
Например, свойство ,,абстрактно`` является абстрактным, а потому предикабельным;
но свойство ,,конкретно`` также является абстрактным, а не конкретным и потому
импредикабельно. Каково свойство ,,импредикабельно``?
\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}$)
посредством некоторого выражения русского языка. Эта функция, в силу её
определения, должна отличаться от каждой функции, определимой посредством
какого\nobreakdash-либо выражения русского языка.

Этот парадокс представляет особый интерес ввиду его применимости к таким языкам,
как русский, и в связи с тем, что он так сходен с канторовским доказательством
неперечислимости всех арифметических
функций~(\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 заключаем, что это высказывание
ложно. Из ложности этого высказывания вытекает, что существовал или будет
существовать некоторый критянин, который иногда говорит правду. Если бы это
высказывание было единственным, которое когда\nobreakdash-либо произносил хоть
один критянин, мы получили бы парадокс. Логически неудовлетворительно то, что
парадокса можно избежать только с помощью исторического предположения, что
существовал критянин, который иногда говорил правду.

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

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

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

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

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

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

Мысль, что парадоксы следует решать в этом направлении, приходит на ум при
первом знакомстве с ними. Можно предположить, что в
парадоксах~\ref{paradox:p11-A}--\ref{paradox:p11-C} ошибка состоит в
употреблении слишком обширных множеств, таких, как множество всех множеств или
множество всех кардинальных чисел, или в разрешении рассматривать множества как
элементы самих себя, что опять\nobreakdash-таки служит возражением против
множества всех множеств. Отвергать эти предположения не обязательно, но только
их нельзя считать простыми. Они ставят нас перед проблемой перестройки теории
множеств на совершенно изменённой основе, детали которой содержатся в них разве
что в виде намёка. Например, если мы запретим множество всех кардинальных чисел,
мы не сможем рассматривать множество всех натуральных чисел, пока нам не станет
известно, что этими числами не исчерпываются все кардинальные числа, и та же
самая
%% ======================= Страница 43 =======================
трудность возникает на более высоких ступенях. Если мы запретим множество всех
множеств, то получим конфликт с канторовским определением множества. Чтобы
вообще имелась теория множеств, надо иметь теоремы, справедливые для всех
множеств, а все множества, по канторовскому определению, образуют множество.
Если это не так, то мы должны указать, каким определением множества мы будем
пользоваться взамен, или же дополнить канторовское определение некоторым
дальнейшим критерием, устанавливающим, когда описанная в его определении
совокупность объектов образует множество~(Сколем~\cite{skolem1929-1930}).

\begin{SCEnvWLabel}{Аксиоматическая теория множеств.}%
{spar:p12-axiomatic_set_theory}{spar:p12-axiomatic_set_theory}
Были предложены построения теории множеств, в которых понятие множества связано
лишь такими ограничениями, исключающими образование слишком обширных множеств,
какие необходимы для предупреждения известных антиномий. Ввиду того, что
свободное пользование нашими понятиями при построении множеств согласно
канторовскому определению приводит к крушению, употребление
теоретико\nobreakdash-множественных понятий регулируется аксиомами вроде тех,
которым подчиняются ,,точка`` и ,,прямая`` в эвклидовой планиметрии. Первая
система \emph{аксиоматической теории множеств} принадлежит
Цермело~\cite{zermelo1908}. Френкель~\cite{fraenkel1922, fraenkel1925},
Сколем~\cite{skolem1922-1923,skolem1929}, Нейман~\cite{neumann1925,neumann1928},
Бернайс~\cite{bernays1937-1954} и другие улучшили аксиоматическое рассмотрение
множеств. На базе аксиоматической теории множеств можно обосновать анализ, и эта
база является, пожалуй, простейшей базой, предложенной для построения
существующей математики с тех пор, как были обнаружены парадоксы. В связи с
аксиоматической теорией множеств были сделаны некоторые очень интересные
открытия, особенно Сколемом~\cite{skolem1922-1923}~(см.~ниже~\textsection~%
\ref{sec:75-axiom_systems_skolem_s_paradox_the_natural_number_sequence}) и
Гёделем~\cite{goedel1938,goedel1939,goedel1940}\footnote{А также
П.~С.~Новиковым~\cite{novikov1951}.~---~\textit{Прим.~ред.}}.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Широкая постановка проблемы оснований математики.}%
{spar:p12-the_broader_problem_of_foundations}%
{spar:p12-the_broader_problem_of_foundations}
Допустим, что при аксиоматизации теории множеств парадоксы устраняются~---~а у
нас имеется лишь единственный довод в пользу этого допущения, состоящий в том,
что до сих пор при упомянутых выше аксиоматизациях не было обнаружено ни одного
парадокса,~---~означает ли это, что мы получили полное решение той проблемы,
которая была поставлена в связи с парадоксами?

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

Но что касается кульминирующих в теории множеств арифметики и анализа, то до
современной эпохи критицизма математики обычно считали, что они имеют дело с
системами объектов, порождаемыми генетически теми определениями, которые
предназначены для полного описания их структуры. Считали, что теоремы выражают
истины, относящиеся к этим системам, а не предложения, гипотетически приложимые
ко всяким системам объектов, удовлетворяющих аксиомам (если такие системы
объектов существуют). А тогда, как могут в этих областях появляться
противоречия, если только нет какого\nobreakdash-нибудь дефекта в логике или
ошибки в тех методах построения и рассуждений о математических объектах, которым
мы до сих пор доверяли?
%%
%% исправлена опечатка
%% в оригинале "системам объектов, удовлетворяющим аксиомам"
%%

Сказать, что теперь эти области надо строить на аксиоматической основе,~---~это
ещё не значит избавиться от проблемы. И после аксиоматизации на некотором уровне
остаются ещё истина и ложь. Если аксиоматика содержательна
%% ======================= Страница 44 =======================
(т.~е. не формальна), то аксиомы должны быть истинными. Если же аксиоматика
формальна, то по крайней мере нам нужна уверенность, что теоремы следуют из
аксиом; и, кроме того, чтобы математическое творчество не сводилось к
бессмыслице, должно иметься какое\nobreakdash-то соответствие между этими
результатами и некоторой действительностью, лежащей вне аксиоматической теории.
Формально аксиоматизированные математические предложения не могут составить всей
математики; должна иметься также интуитивно понимаемая математика. Если мы
вынуждены отказаться от нашей прежней веры, что она содержит всю арифметику,
анализ и теорию множеств, то мы не можем испытать полного удовлетворения, пока
не узнаем, в чем была ошибочность этой веры и где теперь должна проходить
разделительная черта.

Таким образом, непосредственная проблема устранения парадоксов поглощается более
широкой проблемой обоснования математики и логики. Какова природа математической
истины? Какой смысл имеют математические предложения и на какого рода
доказательствах они основаны? С этой широкой проблемой или комплексом проблем
философия имеет дело независимо от того, что в окраинных областях математики
появились парадоксы. Исторически последнее обстоятельство привело к более
интенсивному изучению этого вопроса математиками, чем это, вероятно, было бы при
других обстоятельствах; очевидно, что эти парадоксы накладывают условия на
решение задачи\footnote{Интересные результаты, проливающие свет на проблему
парадоксов, принадлежат Д.~А.~Бочвару~\cite{bochvar1938,bochvar1944} и
П.~С.~Новикову~\cite{novikov1947}.~---~\textit{Прим.~ред.}}.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Непредикативные определения.}%
{spar:p12-impredicative_definition}%
{spar:p12-impredicative_definition}
Пусть множество~$M$ и объект~$m$ определены таким образом, что, с одной стороны,
$m$~является элементом~$M$‚ а с другой стороны, определение~$m$ зависит от~$M$;
тогда мы будем говорить, что процесс (или определение~$m$, или определение~$M$)
является \emph{непредикативным}. Аналогично, когда свойством~$P$ обладает
некоторый объект~$m$, определение которого зависит от~$P$ (при этом
множеством~$M$ служит множество объектов, обладающих свойством~$P$).
Непредикативное определение является порочным\footnote{В подлиннике
circular.~---~\textit{Прим.~перев.}}, по крайней мере по виду, так как то, что в
нём определяется, принимает участие в своём собственном определении.

Каждая из антиномий~\textsection~\ref{sec:11-the_paradoxes} использует
непредикативное определение. В~\ref{paradox:p11-B} множество~$\setOfSets{M}$
всех множеств содержит в качестве элементов
множества $\OLpowerset{\setOfSets{M}}$~и~$\OLunion{\setOfSets{M}}$, определяемые
через~$\setOfSets{M}$. В парадоксе Рассела~\ref{paradox:p11-C} непредикативный
процесс бросается в глаза после следующей переработки определения~$T$. Мы
разделим множество~$\setOfSets{M}$ всех множеств на две части, из которых первая
содержит те элементы, которые содержат самих себя, а вторая (которая и
есть~$T$)~---~те‚ которые не содержат самих себя. Затем мы
помещаем~$T$ (определённое этим разделением~$\setOfSets{M}$ на две части)
обратно в~$\setOfSets{M}$ и спрашиваем, в какую часть~$\setOfSets{M}$ оно при
этом попадает. В парадоксе Ришара~\ref{paradox:p11-D} совокупность всех
выражений русского языка, которые образуют определение функции (действительного
числа или натурального числа), рассматривается как содержащая выражение, стоящее
в кавычках и определяемое через эту совокупность. В парадоксе
Эпименида~\ref{paradox:p11-E} совокупность всех высказываний разделяется на две
части~---~совокупность всех истинных и совокупность всех ложных высказываний.
Высказывание, зависящее от этого разделения, считается затем принадлежащим
первоначальной совокупности, когда мы спрашиваем, истинно оно или ложно.

Пуанкаре~\cite{poincare1905-1906,poincare1908} считал, что причина парадоксов
лежит в этих непредикативных определениях, а
Рассел~\cite{russell1906,russell1910} провозгласил это же объяснение в своём
принципе порочного круга: никакая совокупность не может содержать элементов,
определимых только в терминах этой совокупности, а также элементов, включающих в
себя или предполагающих эту совокупность. Возможно, что в этом состоит
достаточное разрешение и точное проникновение
%% ======================= Страница 45 =======================
в сущность парадоксов, но возникает следующее затруднение: части математики,
которые мы желаем сохранить, и в том числе анализ, также содержат
непредикативные определения.

Примером служит определение~${\mathbf{u}=\OLsup\setOfSets{M}}$%
~(\textsection~\ref{sec:9-number_theory_vs_analysis}~\ref{theorem:p9-A}).
Согласно дедекиндовскому определению действительных чисел,
множество~$\setOfSets{C}$ всех действительных чисел~---~это множество всех тех
множеств $\mathbf{x}$~рациональных чисел, которые обладают тремя
свойствами~\ref{property:p9-a},~\ref{property:p9-b},~\ref{property:p9-c}. Эта
совокупность разбивается затем на две части
$\setOfSets{M}$~и~${\setOfSets{C}\OLsetminus\setOfSets{M}}$. Мы
определяем~$\mathbf{u}$ как~${\OLunion{\setOfSets{M}}}$ и затем рассматриваем
это множество~${\OLunion{\setOfSets{M}}}$ как элемент~$\setOfSets{C}$. Это
определение~${\mathbf{u}=\OLunion{\setOfSets{M}}}$ в общем случае зависит
от~$\setOfSets{C}$, так как~$\setOfSets{M}$ в общем случае определяется как
множество тех элементов~$\setOfSets{C}$, которые обладают некоторым
свойством~$P$.

Можно пытаться защищать это непредикативное определение, истолковывая его не как
определение или создание в первый раз действительного числа~$\mathbf{u}$ (при
таком истолковании определение совокупности~$\setOfSets{C}$ всех действительных
чисел было бы порочным\footnote{В подлиннике
circular.~---~\textit{Прим.~перев.}}), а только как описание, которое выделяет
это индивидуальное число~$\mathbf{u}$ из уже существующей
совокупности~$\setOfSets{C}$ всех действительных чисел. Но этот же довод можно
применить для защиты непредикативных определений в парадоксах.
\end{SCEnvWLabel}

\begin{SCEnvWLabel}{Конструктивный континуум Вейля.}%
{spar:p12-weil_s_constructive_continuum}%
{spar:p12-weil_s_constructive_continuum}
Непредикативный характер некоторых определений анализа особенно подчёркивался
Вейлем, который в своей книге <<Das Kontinuum>>~(Континуум)~\cite{weyl1918}
предпринял исследование того, какая часть анализа может быть построена без
непредикативных определений. Можно указать ряд операций, достаточных для
построения многих частных категорий иррациональных чисел. Вейлю удалось на этом
пути получить значительную часть анализа~---~но не теорему о том, что
произвольное непустое множество~$\setOfSets{M}$ действительных чисел, имеющее
верхнюю границу‚ имеет наименьшую верхнюю
границу~(см.~также~Вейль~\cite{weyl1919}).
\end{SCEnvWLabel}

Имеются три основных направления в основаниях математики: (i)~логицистическая
школа~(Рассел и Уайтхед, Англия), (ii)~интуиционистская школа~(Брауэр,
Голландия) и (iii)~формалистическая, или аксиоматическая, школа~(Гильберт,
Германия). (Иногда вместо <<логицистическая>> говорят <<логистическая>>; но
термин <<логистика>> имеет также другой смысл,
см.~\textsection~\ref{sec:15-formalization_of_a_theory}.) Эта широкая
классификация не включает различных других точек зрения, которые не столь широко
культивировались или не совмещают в такой же степени реконструкцию математики и
философию, лежащую в её основе.

\begin{SCEnvWLabel}{Логицизм.}{spar:p12-logicism}{spar:p12-logicism}
Логицистический тезис состоит в том, что математика является отраслью логики.
Математические понятия следует определять в терминах логических понятий. Теоремы
математики следует доказывать как теоремы логики.

Лейбниц~\cite{leibniz1666} первый рассматривал логику как науку, идеи и принципы
которой лежат в основе всех других наук. Дедекинд~\cite{dedekind1888} и
Фреге~\cite{frege1884,frege1893,frege1903} занимались определением
математических понятий в терминах логических, а
Пеано~\cite{peano1889,peano1894-1908}~---~выражением математических теорем в
логическом символизме.

Для иллюстрации того, каким образом математические понятия определяются через
логические, примем сначала определение кардинального числа по
Фреге\nobreakdash-Расселу~(\textsection~\ref{sec:3-cardinal_number}) и
определения кардинального числа~$0$ и кардинального числа~${n+1}$ для каждого
кардинального числа~$n$\footnote{Имеется в виду определение~${n+1}$ на
стр.~\pageref{def:p4-m_plus_one}.~---~\textit{Прим.~перев.}}~%
(\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}).
Тогда \emph{конечное кардинальное} (или \emph{натуральное}) \emph{число} можно
определить как кардинальное число, обладающее каждым свойством~$P$, таким, что
(1)\itemlabel{prop:p12-1}{(1)}~$0$~обладает свойством~$P$ и
(2)%
%% ======================= Страница 46 =======================
\itemlabel{prop:p12-2}{(2)}~${n+1}$~обладает свойством~$P$, коль скоро 
$n$~обладает свойством~$P$. Короче говоря, натуральное число определяется как
кардинальное число, для которого имеет место математическая индукция. Эта точка
зрения резко отличается от той, которая была принята
в~\textsection\textsection~\ref{sec:6-the_natural_numbers}%
~и~\ref{sec:7-mathematical_induction}, где мы, исходя из интуитивного понимания
натурального ряда, извлекли принцип, что если дано некоторое частное
свойство~$P$ натуральных чисел, такое, что~\ref{prop:p12-1}~и~\ref{prop:p12-2},
то любое натуральное число должно обладать свойством~$P$. Здесь же мы исходим из
совокупности всех свойств кардинальных чисел, предполагая тем самым её
существование в логике, и затем уже определяем натуральный ряд чисел. Заметим,
что это определение непредикативно, потому что определяемое свойство~---~быть
натуральным числом~---~принадлежит совокупности свойств кардинальных чисел,
которая предполагается в определении.

Чтобы приспособить логицистическое построение математики к той ситуации, которая
возникла в связи с открытием парадоксов, Рассел посредством своей
\emph{разветвлённой теории типов}~\cite{russell1908,russell1910}%
\footnote{См.~также
Гильберт~и~Аккерман~\cite{hilbert_and_ackerman1928}.~---~\textit{Прим.~ред.}}
исключил непредикативные определения. Грубо говоря, эта теория состоит в
следующем. Первичные объекты или индивидуумы (т.~е. данные вещи, которые не
подвергаются логическому анализу) приписываются одному типу (скажем,
\emph{типу}~$0$), свойства индивидуумов~---~\emph{типу}~$1$, свойства свойств
индивидуумов~---~\emph{типу}~$2$ и~т.~д.; не допускается никаких свойств,
которые не попадали бы в один из этих логических типов (например, свойства
,,предикабельно`` и ,,импредикабельно``
из~\textsection~\ref{sec:11-the_paradoxes} при этом исключаются из логики). При
более подробном изложении описываются также допустимые типы для других объектов,
таких, как отношения и классы\footnote{Каждый класс приписывается тому же типу,
что и соответствующее свойство, т.~е. свойство, присущее всем элементам данного
класса и только им, а каждое $n$\nobreakdash-аргументное~(${n>1}$)
отношение~---~типу~(${i_{1},\ldots,i_{n}}$),
где ${i_{p}}$~(${1\leqslant p\leqslant n}$)~---~тип
$p$\nobreakdash-го аргумента отношения. Таким образом, типы отношений~---~это
уже не числа. Но можно и не вводить этих типов, определяя вместо этого отношения
через классы упорядоченных $n$\nobreakdash-ок; при этом
$n$\nobreakdash-ка~${\langle x_{1},\ldots,x_{n}\rangle}$ определяется
при~${n>2}$
как~${\left\langle x_{1},\langle x_{2},\ldots,x_{n}\rangle\right\rangle}$, а
${\langle x,y\rangle}$~определяется как~${\left((x)(x, y)\right)}$, так что в
конечном счёте теория отношений сводится к теории классов и можно обойтись
натуральными типами.
См.~\textit{Гильберт и Аккерман},~Основы теоретической логики,
М.---Л.,~1947,~стр.~192~и~199, Гёдель~\cite{goedel1940}. Такое описание
разветвлённой теории типов в деталях отличается от ступенчатого исчисления
Гильберта и Аккермана.~---~\textit{Прим.~перев.}}. Затем, чтобы исключить
непредикативные определения внутри каждого типа, типы, отличные от типа~$0$,
разделяются далее на порядки. Так, для типа~$1$ свойства, определяемые без
упоминания о какой\nobreakdash-либо совокупности, принадлежат
\emph{порядку}~$0$, а свойства, определяемые при помощи совокупности свойств
данного порядка, принадлежат следующему за ним порядку. (Логицистическое
определение натурального числа становится теперь предикативным, если в нём
$P$~рассматривать как пробегающее только по свойствам данного порядка, а
свойство быть натуральным числом относится при этом к следующему порядку.) Но
это разделение на порядки делает невозможным построение обычного анализа,
который, как мы видели выше, содержит непредикативные определения. Чтобы
избежать этого затруднения, Рассел постулировал свою \emph{аксиому сводимости},
которая утверждает, что для каждого свойства, принадлежащего ненулевому порядку,
имеется равнообъёмное (т.~е. имеющее место в точности для тех же объектов)
свойство порядка~$0$. Если только определимые свойства рассматриваются как
существующие, то эта аксиома означает, что для каждого непредикативного
определения внутри данного типа имеется эквивалентное ему предикативное.

Дедукция математики как области логики была выполнена на этой основе с помощью
некоторого логического символизма в фундаментальном труде
Уайтхеда~и~Рассела~<<Principia mathematica>> (в трёх
томах~\cite{whitehead_and_russell1910-1913}). Эта книга имела огромное влияние
на последующее развитие символической логики.

%% ======================= Страница 47 =======================
Эта дедукция математики из логики была предложена в качестве интуитивной
аксиоматики. В аксиомы предлагается поверить или, по крайней мере, предлагается
принять их как вероятные гипотезы о мире.

Теперь возникает трудность: на каком основании будем мы верить в аксиому
сводимости? Если свойство надлежит строить, то этот вопрос должен быть решён на
основе построения, а не посредством аксиомы. Как допускают авторы во введении ко
второму изданию их книги~(1925), <<эта аксиома имеет чисто прагматическое
оправдание: она приводит к желаемым результатам и, насколько известно, ни к
каким другим. Но, конечно, эта аксиома не такого рода, чтобы мы могли остаться
ею довольны>>.

Рамсей~\cite{ramsey1926} обнаружил, что желаемые результаты, и только они, могут
быть, повидимому, получены без иерархии порядков (т.~е. при помощи \emph{простой
теории типов}). Он классифицирует известные антиномии, разделяя их на два рода,
именуемые теперь ,,логическими`` (например, антиномии Бурали\nobreakdash-Форти,
Кантора и Рассела) и ,,эпистемологическими`` или ,,семантическими`` (например,
антиномии Ришара и Эпименида), и он заметил, что логические антиномии
(повидимому) исключаются простой иерархией типов, а семантические (повидимому)
не могут появиться внутри символического языка простой теории типов
из\nobreakdash-за отсутствия в ней тех средств, которые требуются для описания
выражений того же языка. Но доводы Рамсея для обоснования непредикативных
определений внутри данного типа предполагают понятие совокупности всех
предикатов этого типа как существующей независимо от их
конструируемости\footnote{Т.~е. возможности построить их намеченным выше
способом.~---~\textit{Прим.~перев.}} или определяемости. Эти доводы были названы
<<теологическими>>. Таким образом, ни Уайтхеду и Расселу, ни Рамсею не удалось
конструктивным путём достичь логицистической цели. (Интересный план обоснования
непредикативных определений внутри данного типа, предложенный
Лангфордом~\cite{langford1927} и Карнапом~\cite{carnap1931-1932}, также не
свободен от трудностей.)

Вейль~\cite{weyl1946} утверждает, что в системе <<Principia mathematica>>
<<математика основывается уже не на логике, а на своего рода логическом
рае\ldots>>, и он замечает, что тот, кто готов поверить в этот <<трансцендентный
мир>>, может также принять систему аксиоматической теории множеств~(Цермело,
Френкеля~и~т.~д.), которая для дедукции математики имеет то преимущество, что
устроена проще.

Логицизм рассматривает существование натурального ряда как гипотезу о
действительном мире (,,аксиому бесконечности``). Совершенно отличный подход к
проблеме бесконечности предлагается
интуиционистами~(\textsection~\ref{sec:13-intuitionism}) и
формалистами~(\textsection~\ref{sec:14-formalism}).

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

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

К числу более новых работ логицистической школы относится работа
Куайна~\cite{quine1940}. Критическое, но сочувственное обсуждение
логицистического хода мысли дано Гёделем~\cite{goedel1944}. Вводное изложение
имеется у Рассела~\cite{russell1919} и Блэка~\cite{black1933}.
\end{SCEnvWLabel}

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

В 1880\nobreakdash-х годах, когда процветали методы Вейерштрасса, Дедекинда и
Кантора, Кронекер настойчиво утверждал, что их фундаментальные понятия~---~%
%% ======================= Страница 48 =======================
это только слова, потому что они, вообще говоря, не дают нам возможности решить,
удовлетворяет ли данный объект определению.

Пуанкаре, защищавший математическую индукцию как ни к чему не сводимое орудие
интуитивных математических
рассуждений~(Пуанкаре~\cite{poincare1902,poincare1905-1906}), также был
предшественником современной интуиционистской школы.

Брауэр~\cite{brouwer1908} в статье, озаглавленной ,,Недостоверность логических
принципов``‚ бросил вызов вере в то, что правила классической логики, дошедшие
до нас по традиции в основном от Аристотеля~(384--322 до~н.~э.), являются
абсолютно законными, независимо от содержания того, к чему они прилагаются.
Цитируем по Вейлю~\cite{weyl1946}: ,,Согласно его взглядам и пониманию истории,
классическая логика была абстрагирована от математики конечных множеств
и их подмножеств\ldots\ Забывая об этом ограниченном происхождении, впоследствии
эту логику приняли ошибочно за нечто высшее и первичное по отношению ко всей
математике и в конце концов стали применять её без какого\nobreakdash-либо
оправдания к математике бесконечных множеств``.

Два очевидных примера показывают, что принципы, истинные при рассмотрении
конечных множеств, не обязательно переносятся на бесконечные множества. Один из
них~---~принцип, заключающийся в том, что целое больше любой собственной части,
в применении к \isom-соответствиям между
множествами~(\textsection\textsection~\ref{sec:1-enumerable_sets},%
~\ref{sec:3-cardinal_number},%
~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}). Другой принцип
состоит в том, что во всяком множестве натуральных чисел имеется наибольшее
число.

Принципом классической логики, который является истинным при рассуждениях о
конечных множествах, но который Брауэр не принимает для бесконечных множеств,
является закон исключённого третьего. Этот закон, в его общем виде, утверждает,
что \emph{для каждого предложения}~$A$ \emph{либо}~$A$,
\emph{либо}~\emph{не\nobreakdash-}$A$. Пусть теперь $A$~будет предложением
\emph{существует элемент множества}~(\emph{или области})~$D$,
\emph{обладающий свойством}~$P$. Тогда~\emph{не\nobreakdash-}$A$ эквивалентно
предложению \emph{каждый элемент}~$D$ \emph{не обладает свойством}~$P$ или,
другими словами, \emph{каждый элемент}~$D$ \emph{обладает
свойством}~\emph{не\nobreakdash-}$P$. Значит, в применении к этому~$A$ закон
исключённого третьего даёт: \emph{или существует элемент}~$D$, \emph{обладающий
свойством}~$P$, \emph{или каждый элемент}~$D$
\emph{обладает свойством}~\emph{не\nobreakdash-}$P$.

Для ясности пусть свойство~$P$ выбрано так, что для любого данного элемента~$D$
мы можем определить, обладает этот элемент свойством~$P$ или нет.

Допустим теперь, что $D$~---~конечное множество. Тогда мы можем исследовать все
элементы~$D$ по очереди и таким образом либо найти элемент, обладающий
свойством~$P$, либо убедиться в том, что все элементы обладают
свойством~\emph{не\nobreakdash-}$P$. Возможны практические трудности, например,
для очень большого множества, имеющего, например, миллион элементов, или даже
для малого~$D$, если решение вопроса, обладает ли данный элемент свойством~$P$,
оказывается слишком громоздким. Но в принципе имеется возможность закончить
исследование. С точки зрения Брауэра, именно эта возможность делает закон
исключённого третьего справедливым принципом при рассуждениях о конечных
множествах~$D$ и свойствах~$P$ указанного рода.

Для бесконечного множества~$D$ ситуация в корне другая, так как принципиально
невозможно закончить исследование всего множества~$D$.

Более того, в этой ситуации, с точки зрения Брауэра, закон исключённого третьего
нельзя спасти, заменяя невозможное исследование всех элементов бесконечного
множества~$D$ каким\nobreakdash-либо математическим решением поставленной
проблемы. Мы можем в некоторых случаях, т.~е. для некоторых множеств~$D$ и
свойств~$P$, преуспеть в нахождении элемента~$D$, обладающего свойством~$P$, а в
других случаях мы можем преуспеть в доказательстве посредством математического
рассуждения, что каждый элемент~$D$ обладает
свойством~\emph{не\nobreakdash-}$P$, например путём вывода противоречия из
допущения, что какой\nobreakdash-то произвольный (т.~е. никак не определённый)
элемент~$D$ обладает свойством~$P$. (Пример второго рода решения получаем, когда
$D$~---~множество всех упорядоченных
%% ======================= Страница 49 =======================
пар~${(m,n)}$ целых положительных чисел, а $P$~---~свойство пары~${(m,n)}$,
заключающееся в том, что~${m^{2}=2n^{2}}$. Результатом служит тогда пифагорово
открытие иррациональности~${\sqrt{2}}$.) Но у нас нет оснований утверждать
возможность получения в общем случае одного из этих двух родов решения.

Примером из истории современной математики может служить <<великая теорема>>
Ферма, которая утверждает, что уравнение~${x^{n}+y^{n}=z^{n}}$ не имеет решения
в целых положительных числах~$x$,~$y$,~$z$,~$n$ при~${n>2}$. (Для~${n=2}$
имеются тройки целых положительных чисел, называемые пифагоровыми числами,
которые удовлетворяют этому уравнению, например, ${x=3}$‚~${y=4}$‚~${z=5}$ или
${x=5}$‚~${y=12}$‚~${z=13}$.) Здесь $D$~является множеством всех упорядоченных
четвёрок~${(x,y,z,n)}$ целых положительных чисел с~${n>2}$, а $P$~---~свойством
четвёрки~${(x,y,z,n)}$, состоящим в том, что~${x^{n}+y^{n}=z^{n}}$. Около
1637~г. Ферма написал на полях своего экземпляра Диофанта в издании Баше, что он
открыл поистине изумительное доказательство этой <<теоремы>>, но поля слишком
узки, чтобы уместить его. Несмотря на огромную затрату усилий, никому с тех пор
не удалось доказать или опровергнуть эту <<теорему>>; более того, нам неизвестно
никакого систематического метода, следуя которому, мы принципиально должны были
бы в конце концов установить её истинность или ложность.~(Подробности
см.~у~Вандивера~\cite{vandiver1946}.)\footnote{Теорема Ферма была доказана
Уайлсом~\cite{wiles1995} в 1995 году.~---~\textit{Прим.~перенаборщика.}}

Непринятие Брауэром закона исключённого третьего для бесконечных множеств~$D$ не
основано на том, что математикам до сих пор не удалось решить ту или иную
конкретную проблему. Чтобы предупредить брауэровскую критику, пришлось бы
изобрести метод, принципиально годящийся для решения не только всех
замечательных нерешённых математических проблем, но и любых других, которые
могут быть когда\nobreakdash-либо предложены в будущем. О том, насколько
правдоподобно, что такой метод будет найден, мы пока предоставляем размышлять
читателю. Позже мы вернёмся к этому вопросу~(%
\textsection~\ref{sec:60-church_s_theorem_the_generalized_goedel_s_theorem}).

Обычную математику с её методами и логикой в том виде, в каком она развивалась
до критики Брауэра или не принимая её во внимание, мы будем называть
\emph{классической}, а математику, с методами и логикой которой согласны Брауэр
и его школа, мы будем называть \emph{интуиционистской}\footnote{Хотя основы этой
математики действительно были заложены возглавляемой Брауэром школой
интуиционистов, употребление многими авторами (в том числе и автором
настоящей книги) терминов <<интуиционистская математика>>, <<интуиционистская
логика>> и~т.~п. следует признать не совсем удачным, поскольку охватываемое
этими терминами положительное содержание не имеет обычно (как, например, и в
этой книге) никакого отношения к философии интуиционизма. Лучше было бы говорить
<<конструктивная математика>>, <<конструктивная логика>>
и~т.~п.~---~\textit{Прим.~ред.}}. Классическая математика содержит как
интуиционистскую, так и неинтуиционистскую часть.

Неинтуиционистская математика, которая кульминировала в теориях Вейерштрасса,
Дедекинда и Кантора, и интуиционистская математика Брауэра существенно
различаются в их точке зрения на бесконечность. В классической математике
бесконечность рассматривается как \emph{актуальная}, или \emph{завершённая}, или
\emph{протяжённая}, или \emph{экзистенциальная}. Бесконечное множество
рассматривается как существующее в виде завершённой совокупности, до и
независимо от всякого процесса порождения или построения его человеком, как если
бы оно полностью лежало перед нами для нашего обозрения. В интуиционистской
математике бесконечность рассматривается только как \emph{потенциальная}, или
\emph{становящаяся}, или \emph{конструктивная}. Осознание этого различия в
понимании бесконечных величин восходит к Гауссу, который в 1831~г. писал: <<Я
возражаю\ldots\ против употребления бесконечной величины, как
чего\nobreakdash-либо завершённого, что никогда не позволительно в
математике>>.~(Werke,~VIII,~стр.~216.)
% TODO: решить, а не стоит ли работы Гаусса добавить в библиографию?

Согласно Вейлю~\cite{weyl1946}, <<Брауэр выяснил и, как мне кажется, не оставил
никакого сомнения в том, что не существует доводов, защищающих веру в экзи%
%% ======================= Страница 50 =======================
стенциальный характер совокупности всех натуральных чисел\ldots\ Этот ряд чисел,
который растёт, не останавливаясь ни на какой стадии, за счёт перехода к
следующему числу, представляет собой многообразие возможностей, открытых для
бесконечности; он вечно остаётся в состоянии становления, а не является
замкнутым царством вещей, существующих в себе. То, что мы слепо превращаем одно
в другое, является истинным источником наших трудностей, в том числе
антиномий,~---~источником более глубокой природы, чем указанный Расселом принцип
порочного круга. Брауэр открыл нам глаза и показал, как далеко классическая
математика, вскормленная превосходящей всякую человеческую способность
реализации верой в ,,абсолютное``, идёт дальше таких утверждений, которые могут
претендовать на реальный смысл и истинность, основанную на доказательствах>>.

Брауэровская критика классической логики в применении к бесконечному
множеству~$D$ (например, натуральному ряду чисел) возникает вследствие этой
точки зрения на бесконечность. Это ясно видно из рассмотрения значений, которые
интуиционисты связывают с различными видами высказываний.

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

Математическая индукция служит примером интуиционистского метода доказательства
универсальных предложений о натуральных числах. Доказательство по индукции
предложения ${P(n)}$~\emph{для всех}~${n}$ показывает, что любое данное~$n$
должно обладать свойством~$P$, посредством рассуждения, в котором используются
только числа от~$0$~до~$n$~(\textsection~\ref{sec:7-mathematical_induction}).
Конечно, для того чтобы некоторое доказательство по индукции было
интуиционистским, рассуждения, использованные в его базисе и индукционном шаге,
также должны быть интуиционистскими.

Экзистенциальное высказывание \emph{существует натуральное число}~$n$,
\emph{обладающее свойством}~$P$, или, короче, \emph{существует}~$n$,
\emph{такое}, \emph{что}~${P(n)}$, интуиционистами рассматривается как частичное
сообщение о высказывании (или абстракция от такого высказывания), которое даёт
конкретный пример натурального числа~$n$ со свойством~$P$ или хотя бы метод,
позволяющий в принципе найти такой
пример\footnote{\label{footnote:page50-1}%
П.~С.~Новиков~\cite{novikov1939,novikov1943}
(см.~добавление~\ref{apx:vii-proof_of_consistency_of_classic_arithmetic})
показал, что при некоторых условиях из неконструктивного доказательства
существования можно извлечь конструктивное
доказательство.~---~\textit{Прим.~ред.}}.

Поэтому интуиционистское доказательство предложения \emph{существует такое}~$n$,
\emph{что}~${P(n)}$, должно быть \emph{конструктивным} в следующем (узком)
смысле: это доказательство действительно представляет пример такого~$n$,
что~${P(n)}$‚ или, по крайней мере, указывает метод, позволяющий в принципе
найти такой пример.

В классической математике встречаются \emph{неконструктивные} или
\emph{косвенные} доказательства существования, которых не принимают
интуиционисты. Например, чтобы доказать предложение \emph{существует}~$n$
\emph{такое}, \emph{что}~${P(n)}$‚ классически настроенный математик может
вывести противоречие из допущения, что \emph{для
всех}~$n$~\emph{не\nobreakdash-}${P(n)}$. Согласно обеим
логикам~---~классической и интуиционистской~---~это в силу reductio ad absurdum
даёт предложение \emph{не для всех}~$n$~\emph{не\nobreakdash-}${P(n)}$%
\footnote{А.~Н.~Колмогоров~\cite{kolmogorov1932} высказал мысль, что при
последовательном проведении конструктивной (интуиционистской) точки зрения
\emph{для высказывания о всеобщности} (т.~е. имеющего форму <<для всех~$n$ имеет
место~${P(n)}$>>), \emph{вообще говоря}, \emph{является бессмысленным
рассматривать его отрицание как определённое
высказывание}.~---~\textit{Прим.~ред.}}. Классическая логика позволяет
преобразовать этот результат в утверждение
%% ======================= Страница 51 =======================
\emph{существует}~$n$, \emph{такое}, \emph{что}~${P(n)}$, но (вообще говоря)
этого не позволяет сделать логика интуиционистская. Такое классическое
доказательство существования не приближает нас к обладанию примером числа~$n$,
такого, что~${P(n)}$ (хотя иногда мы всё же можем получить такой пример другим
% TODO: разобраться со ссылкой на примечание
способом)\footnote{См.~примечание~\ref{footnote:page50-1} к
стр.~\pageref{footnote:page50-1}.~---~\textit{Прим.~ред.}}. Интуиционисты
отказываются принять такое доказательство существования, потому что его
заключение \emph{существует}~$n$, \emph{такое}, \emph{что}~${P(n)}$‚ они могут
воспринимать только как ссылку на пример числа~$n$, такого, что~${P(n)}$‚ а
такого примера получено не было. Классическое понимание, обозначающее что
где\nobreakdash-то в завершённой бесконечной совокупности всех натуральных чисел
встречается такое~$n$, что~${P(n)}$‚ для них не годится, поскольку они не
рассматривают натуральные числа как образующие завершённую совокупность.

В качестве другого примера неконструктивного доказательства существования
предположим, что для некоторого свойства~$P$ интуиционистскими методами
показано, что если <<великая теорема>> Ферма верна, то число~$5013$ обладает
свойством~$P$, а также, что если <<великая теорема>> Ферма ложна, то
$10$~обладает свойством~$P$. Классически этого достаточно, чтобы доказать
существование числа~$n$ такого, что~${P(n)}$. Но пока проблема
<<великой теоремы>> не решена, Брауэр не согласился бы с таким доказательством
существования, потому что оно не даёт никакого примера. Нам неизвестно ни то,
что $5013$~служит нужным примером, ни то, что $10$~служит таким примером. Нам
также не известен никакой процесс, который в принципе (т.~е. отвлекаясь от
практических ограничений, относящихся к длине выполнимого процесса) дал бы нам
некоторое конкретное число, относительно которого мы могли бы быть уверены, что
оно служит примером. То, что нам дано, Брауэр принял бы только в качестве
доказательства импликации (или условного высказывания) \emph{если}
$F$~\emph{или}~\emph{не\nobreakdash-}$F$, \emph{то существует}~$n$ \emph{такое},
\emph{что}~${P(n)}$‚ где $F$~---~это высказывание \emph{для всех}~${x,y,z,n}$,
\emph{таких}, \emph{что} ${x,y,z>0}$~\emph{и}~${n>2}$‚
\emph{имеет место}~${x^{n}+y^{n}\neq z^{n}}$. Классически настроенный математик,
в силу его закона исключённого третьего, имеет посылку
$F$~\emph{или}~\emph{не\nobreakdash-}$F$ этой импликации, поэтому он может
вывести её заключение \emph{существует}~$n$, \emph{такое}, \emph{что}~${P(n)}$.
Но при настоящем состоянии науки Брауэр не воспринимает как известную посылку
$F$~\emph{или}~\emph{не\nobreakdash-}$F$.

Как видно из этого примера, интуиционистские методы следует отличать от
классических не только в случае доказательств, но и в случае определений. При
существующем состоянии науки Брауэр не воспринимает слова \emph{число}~$n$,
\emph{которое равно}~$5013$, \emph{если}~$F$, \emph{и равно}~$10$,
\emph{если}~\emph{не\nobreakdash-}$F$, как законное определение некоторого
натурального числа~$n$.

Дизъюнкция $A$~\emph{или}~$B$ является для интуициониста неполным сообщением о
высказывании, которое утверждает, что $A$~имеет место или что $B$~имеет место,
или по крайней мере даёт метод, посредством которого из $A$~и~$B$ можно выбрать
одно, которое имеет место. Конъюнкция $A$~\emph{и}~$B$ означает, что оба
высказывания, $A$~и~$B$, имеют место. Импликация $A$~\emph{влечёт}~$B$ (или
\emph{если}~$A$, \emph{то}~$B$) выражает, что $B$~следует из~$A$ в силу
интуиционистского рассуждения, или, более явно, что имеется метод, который по
каждому доказательству~$A$ позволяет получить некоторое доказательство~$B$.
Отрицание \emph{не\nobreakdash-}$A$ (или $A$~\emph{абсурдно}) означает, что
противоречие $B$~\emph{и}~\emph{не\nobreakdash-}$B$ следует из~$A$ в силу
интуиционистского рассуждения, или, более явно, что имеется метод, который по
любому доказательству~$A$ позволяет получить доказательство противоречия
$B$~\emph{и}~\emph{не\nobreakdash-}$B$ (или утверждения, абсурдность которого
уже известна, например,~${1=0}$). Дополнительные замечания о таком
интуиционистском понимании будут приведены
в~\textsection~\ref{sec:82-recursive_realizability}%
\footnote{А.~Н.~Колмогоров~\cite{kolmogorov1932} открыл интерпретацию
конструктивной (интуиционистской) логики в виде логики решения \emph{задач}, или
\emph{проблем}. Возможны различные способы уточнения используемого в этой
интерпретации интуитивного понятия <<проблема>>. Один из таких способов
предложил Клини~(см.~ниже~\textsection~\ref{sec:82-recursive_realizability});
рассматриваемые им проблемы суть проблемы построения реализаций. Другой способ
предложен в последнее время Ю.~Т.~Медведевым~\cite{medvedev1955}. Каждая из
рассматриваемых им проблем есть проблема построения
арифметической~(см.~\textsection~\ref{sec:10-functions},
пример~\ref{exmpl:p10-2}) функции, принадлежащей заданному классу функций. К
кругу вопросов, связанных с истолкованием конструктивной логики, примыкают также
исследования Н.~А.~Шанина~\cite{shanin1953,shanin1955} о \emph{частных типах
понятий конструктивной истинности и конструктивной
ложности}.~---~\textit{Прим.~ред.}}.
%%
%% исправление в соответсвие со списком опечаток в конце оригинала
%% для страницы 51 строка 18 снизу (включая примечание)
%% добавлена запятая в конце
%% "высказывании, которое утверждает, что A имеет место или что B имеет место,"
%%

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

Цитируем Гейтинга~\cite{heyting1934}: <<Согласно Брауэру, математика
тождественна с точной частью нашего мышления\ldots\ Никакая наука~---~в
частности, ни философия, ни логика~---~не может служить предпосылкой для
математики. Было бы порочным кругом применять в качестве средств для
доказательств какие\nobreakdash-либо философские или логические принципы, потому
что в формулировке таких принципов уже предполагаются математические понятия>>.
Для математики не остается <<никакого другого источника, кроме интуиции, которая
с непосредственной ясностью помещает перед нашими глазами математические понятия
и выводы>>. Эта интуиция <<является не чем иным, как способностью рассматривать
в отдельности различные понятия и выводы, регулярно встречающиеся в обычном
мышлении>>. Анализируя идею натурального ряда чисел, мы видим, что она может
быть основана на возможности, во\nobreakdash-первых, рассматривать
какой\nobreakdash-либо предмет или опыт как данный нам независимо от всего
остального мира, во\nobreakdash-вторых, отличать одно такое рассмотрение от
другого и, в\nobreakdash-третьих, представлять себе неограниченное повторение
второго процесса. <<В интуиционистской математике выводы не извлекаются по
фиксированным правилам, которые можно объединить в логику, а каждый вывод в
отдельности непосредственно подтверждается своей очевидностью>>. Но, кроме того,
<<имеются общие правила, посредством которых из данных математических теорем
можно интуитивно ясным образом получать другие; теорию этих соотношений можно
рассматривать в некоторой ,,математической логике``, которая при этом является
отраслью математики и не имеет ощутимых применений вне математики>>.

Обратимся теперь к вопросу, как велика та роль, которую в классической
математике играют неинтуиционистские методы.

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

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

С другой стороны, в анализе (и в ещё более абстрактных областях математики)
неинтуиционистские способы определения и доказательства проходят через всю
методологию. Действительные числа в дедекиндовом представлении являются
бесконечными множествами рациональных
чисел~(\textsection~\ref{sec:9-number_theory_vs_analysis}). Таким образом, уже
для того, чтобы рассматривать их как объекты в обычном смысле, мы пользуемся
завершённой бесконечностью. И даже в связи с простейшими определениями теории мы
применяем закон исключённого третьего к этим множествам. Например, чтобы
показать, что для любых двух действительных чисел $\mathbf{x}$~и~$\mathbf{y}$
либо~${\mathbf{x}\OLprecB\mathbf{y}}$‚
либо~${\mathbf{x}\boldsymbol{=}\mathbf{y}}$‚
либо~${\mathbf{x}\OLsuccB\mathbf{y}}$‚ мы применяем его дважды в следующей
форме: или существует рациональное число~$r$ в~$\mathbf{y}$, не
принадлежащее~$\mathbf{x}$, или все рациональные числа из~$\mathbf{y}$
принадлежат~$\mathbf{x}$; аналогично с переменой ролей
$\mathbf{x}$~и~$\mathbf{y}$. В непредикативном определении~$\OLsup$
множества~$\setOfSets{M}$~(%
\textsection~\ref{sec:9-number_theory_vs_analysis}~\ref{theorem:p9-A}‚~%
\textsection~\ref{sec:12-first_inferences_from_the_paradoxes}) мы таким же
образом пользуемся совокупностью всех действительных чисел. Неконструктивное
рассуждение другого рода встречается в
доказательстве~\ref{theorem:p9-B-proof}~%
\textsection~\ref{sec:9-number_theory_vs_analysis}, где мы допускаем законность
выбора элемента~${\mathbf{a}_{n}}$ из множества~${\setOfSets{M}_{n}}$
одновременно для бесконечно многих значений~$n$, когда не дано никакого свой%
%% ======================= Страница 53 =======================
ства, определяющего то, какой элемент выбирается. (Это~---~частный случай
<<аксиомы выбора>>, на которую как на допущение впервые обратил внимание
Цермело~\cite{zermelo1904}\footnote{Согласно Серпинскому~\cite{sierpinski1928},
на необходимость аксиомы выбора для многих теоретико\nobreakdash-множественных
доказательств, в частности для доказательства
теоремы~\ref{theorem:p4-B}~%
\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets},
ещё в 1902~г. указал Беппо Леви.~---~\textit{Прим.~перев.}}. Этим
допущением мы пользовались также при доказательстве теоремы~\ref{theorem:p4-B}~%
\textsection~\ref{sec:4-the_equivalence_theorem_finite_and_infinite_sets}.)
%%
%% исправлена опечатка в примечании
%% в оригинале было "Беппо-Леви"
%%

Хотя в качестве величины завершённая бесконечность была уничтожена (к чему
призывал нас Гаусс), она вновь появляется в полной мере при рассмотрении
совокупностей. Гильберт и Бернайс в их <<Grundlagen der Mathematik>>
(<<Основания математики>>, т.~I,~1934,~стр.~41) следующим образом описывают
эту ситуацию: <<\ldots\ Арифметизация анализа оказалась неполной, так как с нею
были введены некоторые систематические основные идеи, не принадлежащие области
интуитивного арифметического мышления. Строгое обоснование анализа убедило нас
только в том, что эти немногие основные допущения достаточны для построения
теории величин как теории множеств целых чисел>>.
%%
%% исправлена опечатка
%% в оригинале было "Crundlagen der Mathematik"
%%

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

% TODO: подумать над символом "прямая решетка" в следующем абзаце
% текущее решение полагаю временным
Интуиционисты построили целую новую математику, включая теорию континуума и
теорию множеств~(см.~Гейтинг~\cite{heyting1934}). В этой математике,
по\nobreakdash-своему очень заманчивой, встречаются понятия и различия, которых
нет в классической математике. В качестве замены для классической математики
интуиционистская математика оказалась менее мощной и во многих случаях более
сложной. Например, в брауэровской теории континуума мы не может утверждать, что
любые два действительных числа $a$~и~$b$ либо равны, либо неравны. Наши знания о
равенстве или неравенстве $a$~и~$b$ могут иметь более или менее точный характер.
Под~${a\neq b}$ понимается, что ${a=b}$~приводит к противоречию, тогда как
${a\text{\textsf{\#}}b}$~является неравенством более строгого вида и означает,
что можно указать пример рационального числа, разделяющего $a$~и~$b$. Конечно,
${a\text{\textsf{\#}}b}$~влечёт~${a\neq b}$. Но имеются пары действительных
чисел $a$~и~$b$, для которых неизвестно, что либо~${a=b}$, либо~${a\neq b}$
(или~${a\text{\textsf{\#}}b}$). Ясно, что при таких усложнениях классическая
теория континуума заменяется чем\nobreakdash-то менее прозрачным по форме.

Однако не следует исключать другую (недавно обнаруженную) возможность
интуиционистского построения классической математики, основанного на
интерпретации~(см.~%
\textsection~\ref{sec:81-reduction_of_classical_to_intuitionistic_systems}).
%%
%% исправлена опечатка
%% в оригинале
%% "не следует исключать другую (недавно обнаруженную возможность)
%%  интуиционистского построения"
%%

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

Брауэр показал, что происходит при последовательном проведении генетической, или
конструктивной, точки зрения; Гильберт проделал то же самое для аксиоматической,
или экзистенциальной, точки зрения~(\textsection~\ref{sec:8-system_of_objects}).
Аксиоматический метод был уточнён уже при переходе от материальной аксиоматики
Эвклида к формальной аксиоматике гильбертовских
<<Оснований геометрии>>~\cite{hilbert1899}. Формализм возникает в результате
дальнейшего шага, направленного на преодоление кризиса, причинённого парадоксами
и тем вызовом классической математике, который был брошен Брауэром и Вейлем.
Этот шаг был намечен Гильбертом~\cite{hilbert1904}; серьёзное продвижение было
осуществлено его сотрудниками Бернайсом, Аккерманом, Нейманом и другими после
1920~года~(см.~Бернайс~\cite{bernays1935a}, Вейль~\cite{weyl1944}).

Гильберт признавал, что предложения классической математики, содержащие
завершённую бесконечность, выходят за пределы интуитивной очевид%
%% ======================= Страница 54 =======================
ности. Но он не соглашался, следуя Брауэру, отказаться от классической
математики.

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

Метод, которым пользовались при доказательствах непротиворечивости
аксиоматических теорий до этого предложения Гильберта, особенно в круге его
ранних аксиоматических идей, состоял в задании ,,модели``. \emph{Модель} для
некоторой аксиоматической теории~---~это просто система объектов, взятая из
некоторой другой теории и удовлетворяющая аксиомам данной
теории~(\textsection~\ref{sec:8-system_of_objects}). Иными словами, каждому
объекту или первоначальному понятию данной аксиоматической теории сопоставляется
объект или понятие другой теории таким образом, что аксиомы оказываются
теоремами этой другой теории (или соответствуют им). Если эта вторая теория
непротиворечива, то должна быть непротиворечивой и данная аксиоматическая
теория. Действительно, допустим, что в данной аксиоматической теории из аксиом
можно вывести противоречие. Тогда и в другой теории из соответствующих теорем
можно было бы вывести противоречие, пользуясь соответствующими выводами по
отношению к объектам, образующим модель.

Бельтрами~(1868) в знаменитом старом примере показал, что прямые плоской
неэвклидовой геометрии Лобачевского\nobreakdash-Больаи (плоской гиперболической
геометрии) могут быть представлены геодезическими некоторой поверхности
постоянной отрицательной кривизны в эвклидовом пространстве\footnote{Здесь и в
следующей фразе автор допускает неточность.\par
Представление, о котором идёт речь, осуществимо только локально, именно оно
даёт возможность наложить на поверхность постоянной отрицательной кривизны в
эвклидовом пространстве некоторый круг плоскости Лобачевского, но не всю эту
плоскость. Поэтому результата Бельтрами недостаточно для высказанного автором
утверждения о непротиворечивости. Однако модель Клейна может служить этой цели.
См.~{\sparseFnt Ефимов~Н.~В.}, Высшая геометрия, М.\nobreakdash---Л.‚~1945,
гл.~V,~\textsection\textsection~6~и~8; гл.~VII,
\textsection~3.~---~\textit{Прим.~перев.}}. Таким образом, плоская
гиперболическая геометрия непротиворечива, если непротиворечива эвклидова
геометрия. (Клейн~(1871) достиг той же цели другим методом, пользуясь плоской
проективной геометрией с метрикой Кэли~(1859), а для этой последней можно
построить модель в эвклидовой плоскости.~(См.~Юнг~\cite{young1911},
лекции~II~и~III).)
%%
%% исправлена опечатка в примечании
%% удалена лишняя запятая в обороте "именно, оно даёт возможность наложить"
%%

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

Доказательства непротиворечивости методом модели являются относительными.
Теория, для которой строится модель, непротиворечива, если непротиворечива та
теория, из которой модель берётся.

Только если эта последняя теория безупречна, модель даёт нам абсолютное
доказательство непротиворечивости. Веблен и Басси~\cite{veblen_and_bussey1906}
получили абсолютные доказательства непротиворечивости для некоторых
рудиментарных проективных геометрии при помощи моделей, в которых точки
представляются элементами некоторого конечного (sic!) класса
объектов~(см.~Юнг~\cite{young1911}, лекции~IV~и~V).

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

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

Гильберт и Бернайс~\cite[стр.~15--17]{hilbert_and_bernays1934} показали, что для
построения модели невозможно воспользоваться воспринимаемым, или физическим
миром. Они иллюстрируют это, рассматривая первый парадокс Зенона~(пятое столетие
до~н.~э.), согласно которому бегун не может пробежать дистанцию за конечное
время, так как для этого он должен был бы пробежать сначала первую половину
дистанции, затем следующую четверть, затем следующую восьмую часть и~т.~д., и
таким образом ему пришлось бы совершить бесконечное число действий. Обычное
решение этого парадокса состоит в замечании, что ряд интервалов времени, нужный
для пробега последовательных отрезков пути, сходится. <<В действительности
имеется гораздо более радикальное решение этого парадокса. Оно состоит в
указании на то обстоятельство, что мы вовсе не обязательно должны верить в то,
что математическое пространственно\nobreakdash-временн{\'o}е представление
движения имеет физическое значение для произвольно малых интервалов пространства
и времени; скорее мы имеем все основания предполагать, что эта математическая
модель экстраполирует факты из некоторой области опыта, а именно, из области
движений в пределах того порядка величин, который пока что доступен нашему
наблюдению, экстраполирует просто в смысле образования идей, подобно тому, как
механика сплошной среды совершает экстраполяцию, предполагающую непрерывное
заполнение пространства материей\ldots\ Ситуация оказывается сходной во всех
случаях, когда имеется вера в возможность непосредственного узрения (актуальной)
бесконечности как данной посредством опыта или восприятия\ldots\ Более подробное
исследование показывает затем, что бесконечность на самом деле вовсе не была нам
дана, а была только интерполирована или экстраполирована посредством некоторого
интеллектуального процесса>>.

Следовательно, если мы хотим доказать непротиворечивость арифметики (включая её
неинтуиционистскую часть), анализа и~т.~д., то это надо делать другим методом.
Заслуга Гильберта состоит в нахождении нового прямого подхода и в распознании
того, чт{\'o} при этом требуется от аксиоматизации. Этот прямой метод содержится
неявно в самом понятии непротиворечивости (по крайней мере в современном
понимании этого слова\footnote{В подлиннике непротиворечивость называется
consistency (согласованность, совместность).~---~\textit{Прим.~перев.}})‚
означающем, что никакое противоречие (т.~е. ситуация, при которой некоторое
предложение~$A$ и его отрицание~\emph{не\nobreakdash-}$A$ оба являются
теоремами) не может возникнуть в рассматриваемой теории в процессе вывода из
аксиом. Итак, чтобы непосредственно доказать непротиворечивость
какой\nobreakdash-либо теории, нужно доказать некоторое предложение о самой этой
теории, а также о всех возможных в этой теории доказательствах теорем.
Математическая теория, непротиворечивость которой пытаются доказать, становится,
в свою очередь, предметом изучения некоторой математической науки, названной
Гильбертом <<метаматематикой>> или <<теорией доказательств>>. Каким образом это
возможно и каковы должны быть методы этой науки, это мы рассмотрим в следующем
параграфе.

А пока мы рассмотрим дальнейшие выводы из гильбертовой концепции.
Гильберт~\cite{hilbert1926,hilbert1928} устанавливает различие между
,,действительными`` и ,,идеальными`` предложениями классической математики,
сущность которого состоит в следующем. \emph{Действительные предложения}~---~это
те, которые рассматриваются как имеющие содержательный смысл, а \emph{идеальные
предложения}~---~это те, которые так не рассматриваются. Предложения,
соответствующие употреблению актуальной бесконечности, идеальны. Классическая
математика присоединяет идеальные предложения к действительным, чтобы простые
правила аристотелевской логики были по-прежнему применимы к рассуждениям о
бесконечных множествах.
%%
%% исправлена опечатка
%% в оригинале "попрежнему"
%%

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

Присоединение ,,идеальных элементов`` к системе с целью пополнить её структуру и
упростить теорию этой системы является обычным и плодотворным методом в
современной математике. Например, в плоской геометрии Эвклида две различные
прямые пересекаются в единственной точке, за исключением случая, когда эти
прямые параллельны. Чтобы избавиться от этого исключения, Понселе в своей
проективной геометрии~(1822) ввёл \emph{бесконечно удалённую точку} на каждой из
первоначальных прямых таким образом, что параллельные прямые имеют одну и ту же
бесконечно удалённую точку, а непараллельные прямые имеют различные бесконечно
удалённые точки. Совокупность этих бесконечно удалённых точек образует
\emph{бесконечно удалённую прямую}. Если вокруг конечной точки проективной
плоскости вращать прямую, то бесконечно удалённая точка этой прямой опишет
бесконечно удалённую прямую. В результате этого приёма соотношения инцидентности
между точками и прямыми упрощаются. Две различные точки определяют единственную
прямую (которая находится ,,на`` обеих этих точках, т.~е. проходит через обе эти
точки), и две различные прямые определяют единственную точку (которая находится
на обеих прямых). Эти два предложения \emph{двойственны} друг другу. Имеется
общий принцип, называемый \emph{принципом двойственности} для плоской
проективной геометрии, который утверждает, что для каждой теоремы этой области
предложение, получающееся из неё взаимной заменой слов <<точка>> и <<прямая>>,
также является теоремой\footnote{При этом к числу теорем относятся также и
аксиомы.~---~\textit{Прим.~перев.}}.
%%
%% исправлена опечатка
%% ссылки на работу Понселе нет ни в библиографии оригинала, ни в библиографии
%% перевода. В оригинале ссылка на Понселе дана в круглых скобках как
%% внебиблиографический источник.
%%

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

Грубо говоря, задача Гильберта аналогична той, которая существовала, когда
впервые начали употреблять мнимые числа. Так как ясного понимания этих чисел
тогда не было, то кто\nobreakdash-нибудь мог предложить скептикам в качестве
обоснования употребления мнимых чисел доказательство того, что если мнимые числа
используются согласно предписанным правилам для получения результата,
выраженного в терминах одних только действительных чисел, то этот результат
должен быть верным. Конечно, в наше время нет надобности в такого рода
относительном обосновании мнимых чисел, потому что имеется известная
интерпретация этих чисел точками плоскости~(Вессель,~1799~г.) и парами
действительных чисел (Гаусс,~1831~г.).

Ввиду этой аналогии напрашивается следующий вопрос: если бы удалось найти
доказательство непротиворечивости в гильбертовском смысле для части классической
математики, содержащей как действительные, так и идеальные
предложения,~---~могли бы мы тогда заключить, что действительные предложения,
доказанные при помощи идеальных, истинны интуиционистски? Вопрос о том, в какой
мере можно было бы прийти к такому заключению, мы рассмотрим
впоследствии~(конец~\textsection~\ref{sec:42-goedel_s_theorem},
конец~\textsection~\ref{sec:82-recursive_realizability}); это будет зависеть от
того, какие рассуждения охватываются доказательством непротиворечивости и какие
предложения берутся в качестве действительных. В той мере, в какой это
заключение было бы возможно, успешное выполнение гильбертовской программы
позволило бы применять классическую математику в интуиционистских
доказательствах.

В первые годы после того, как оформилась гильбертовская программа, возник острый
спор между Брауэром и Гильбертом. Брауэр~\cite{brouwer1923} говорил:
<<Неправильная теория, не натолкнувшаяся на противоречие, не становится
%% ======================= Страница 57 =======================
от этого менее неправильной, подобно тому как преступное поведение, не
остановленное правосудием, не становится от этого менее преступным>>.
Гильберт~\cite{hilbert1928} возразил: <<Отнять у математиков закон исключённого
третьего~---~это то же, что забрать у астрономов телескоп или запретить боксёрам
пользоваться кулаками>>\footnote{Приведенная фраза едва ли является серьёзным
возражением ввиду принципиальной беспощадности критики Брауэра. Такое возражение
могло оказаться убедительным для самого Гильберта, но не для Брауэра. Но в той
же статье Гильберт приводит и другие серьёзные соображения, например то, что не
закон исключённого третьего, а недопустимые и бессмысленные образования понятий
повинны в парадоксах теории множеств, а также то, что его <<игра формулами>>
содействует изучению <<техники нашего мышления>>.~См.~{\sparseFnt Гильберт},
Основания геометрии, М.,~1948, стр.~382--383.~---~\textit{Прим.~перев.}}.

Согласно Брауэру~\cite{brouwer1928} и
Гейтингу~\cite{heyting1931-1932,heyting1934}, возможно соглашение между
интуиционизмом и формализмом при условии (по Нейману~\cite{neumann1931-1932})‚
что формалисты не станут приписывать неинтуиционистской классической математике
содержательного значения, благодаря которому доказательство непротиворечивости
служило бы её обоснованием. Такое
обоснование‚~---~говорит Брауэр‚~---~<<содержит порочный круг потому, что оно
зависит от (содержательной~(inhaltlichen)) истинности предложения, что из
непротиворечивости некоторого высказывания следует его истинность, т.~е. от
(содержательной) истинности закона исключённого третьего>>, который является
подлежащей обоснованию частью формалистской математики.

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

Классическая математика строит теории совершенно не в том смысле, как
интуиционистская. Гильберт~\cite{hilbert1928} говорит: <<Выставить общее
требование, согласно которому каждая отдельная формула сама по себе допускала бы
истолкование‚~---~отнюдь не разумно\ldots>>. В теоретической физике <<только
известная часть комбинаций и следствий из физических законов может быть
проверена опытом~---~подобно тому как в моей теории доказательств только
действительные предложения могут быть непосредственно проверяемы>>.

Классическую математическую теорию можно рассматривать как простую и изящную
систематизирующую схему, благодаря которой совокупность (вероятно) истинных
высказываний, сначала казавшихся разнородными и не связанными друг с другом и
зачастую сначала неизвестных, объединяется в виде следствий из идеальных теорем
этой теории~(ср.~Нейман~\cite{neumann1947},
Эйнштейн~\cite[стр.~288]{einstein1944}).

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

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

Теория посредством лёгких переходов может подниматься на более высокие уровни,
на которых она только очень косвенно связана с систематизацией действительных
предложений; теснее она связана с систематизацией идеальных предложений на
промежуточных уровнях. В этой связи интересно, увеличивают ли последовательно
все более высокие теоретические построения область охваченных ими действительных
предложений первоначального рода, а также
%% ======================= Страница 58 =======================
вызывают ли они существенные упрощения ранее имевшихся
доказательств~(см.~конец~\textsection~\ref{sec:42-goedel_s_theorem}).

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

Гильберт и Бернайс~\cite{hilbert_and_bernays1934} подчёркивают, что в науках
<<мы преимущественно имеем дело с теориями, которые не воспроизводят полностью
действительного положения вещей, а являются \emph{упрощающей идеализацией} этого
положения вещей, в чем и состоит их значение>>~(стр.~2\nobreakdash--3). Анализ
служит <<образованием идей~(Ideenbildung)>>‚ в терминах которых могут быть
выражены эти теории или к которым они могут быть сведены посредством метода
моделей. Доказательство непротиворечивости анализа убедило бы нас в
непротиворечивости идеализаций, которые осуществляются в этих теориях~(стр.~19).

Вейль~\cite{weyl1926,weyl1928,weyl1931} замечает, что в теоретической физике с
опытом согласуются не отдельные утверждения, а вся теоретическая система в
целом. В результате получается не истинное описание того, что дано, а
теоретическое, чисто символическое построение мира. (Он также утверждает, что
наш теоретический интерес не заключается исключительно и даже преимущественно в
,,действительных предложениях``, например в том, что данная стрелка находится
возле такого\nobreakdash-то деления на шкале, а скорее в идеальных
предположениях, например в предположении, что электрон является универсальным
электрическим квантом). Глубокий философский вопрос состоит в том, какая
,,истина`` или объективность соответствует этому теоретическому построению мира,
далеко выходящему за пределы непосредственного опыта. Этот вопрос тесно связан
с другим: что побуждает нас принять за основу определённую избранную нами
систему аксиом? Непротиворечивость для этого необходима, но не достаточна. Если
предоставить математика самому себе, он вместе с Брауэром ограничится
интуитивными истинами; у него не найдётся достаточного мотива, чтобы идти
дальше. Если же заставить математика заняться вместе с физиком процессом
теоретического построения мира, он будет на стороне Гильберта.

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

Заметим заранее, что метаматематика потребует строгой математической техники для
исследования большого многообразия проблем обоснования математики и логики, и
проблема непротиворечивости будет только одной из этих проблем. Например,
метаматематические методы применяются теперь при изучении систематизаций
математики, возникающих из логицистической и интуиционистской школ, так же как и
для возникающих из школы Гильберта. (Обратно, своим возникновением
метаматематика многим обязана логицистическим и интуиционистским исследованиям.)
В дальнейших частях этой книги наша цель будет состоять не в вынесении
окончательного решения, утверждающего или отвергающего формалистскую точку
зрения в какой\nobreakdash-либо принятой версии, а в рассмотрении существа
метаматематического метода и в изучении некоторых результатов, которые были
открыты на пути следования этому методу.

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

Мы собираемся теперь заняться программой, которая превращает саму математическую
теорию в объект точного математического изучения. В математической теории мы
изучаем систему математических объектов. Как
%% ======================= Страница 59 =======================
может математическая теория сама служить объектом математического изучения?

Результат творчества математиков воплощается в предложениях~---~доказанных
предложениях или теоремах данной математической теории. Невозможно в точных
терминах изучить, что происходит в уме математика, но можно рассматривать
систему этих предложений.

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

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

Этот первый шаг будет выполнен только после того, как посредством аксиом будут
выражены все свойства неопределяемых или технических терминов, существенные для
вывода теорем. Тогда можно будет, производя выводы, рассматривать технические
термины как слова, сами по себе не имеющие смысла. Ибо утверждение, что они
имеют значения, необходимые для вывода теорем и отличные от тех, которые можно
вывести из аксиом, регулирующих употребление этих терминов, сводится к
утверждению, что не все их свойства, существенные для выводов, выражены
посредством аксиом. После того как таким образом исключены из рассмотрения
значения технических терминов, мы пришли к точке зрения формальной
аксиоматики~(\textsection~\ref{sec:8-system_of_objects}).

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

Во всяком случае, мы ещё не достигли нашей цели~---~высказать явно все условия,
определяющие, какие предложения имеют место в теории. В самом деле, мы не
установили, какими логическими принципами надлежит пользоваться при выводах. Как
нам теперь хорошо известно, эти принципы различны для различных
теорий~(\textsection~\ref{sec:13-intuitionism}).

Чтобы выразить их явно, необходим второй шаг, который дополняет предыдущий для
так называемых технических терминов по отношению к неграмматической стороне их
значений. Все значения всех слов исключены из рассмотрения, и все условия,
регулирующие употребление этих слов в теории, явно высказаны. Логические
принципы, прежде входившие неявно через значение обычных терминов, теперь будут
введены в действие~---~отчасти, может быть, при помощи новых аксиом, но во
всяком случае, хотя бы частично, посредством правил, позволяющих вывести одну
фразу из другой или других. Так как мы полностью абстрагировались от содержания
или сущности, сохранив только форму, то мы будем говорить, что данная теория
\emph{формализована}. Будучи формализованной, теория по своей структуре является
уже не системой осмысленных предложений, а системой фраз, рассматриваемых как
последовательность слов, которые, в свою очередь, являются последовательностями
букв. Только по форме будем мы судить о том, какие сочетания слов являются
фразами, какие фразы~---~аксиомами и когда фразы вытекают в качестве
непосредственных следствий из других.

Возможна ли такая формализация? В какой мере может быть формализована данная
теория, это мы узнаем только после попытки формализации и изучения
результатов~(например,~\textsection\textsection~%
\ref{sec:29-completness_normal_form},~\ref{sec:42-goedel_s_theorem},~%
\ref{sec:60-church_s_theorem_the_generalized_goedel_s_theorem},~%
\ref{sec:72-goedel_s_completeness_theorem}).

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

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

Открытие аксиоматико\nobreakdash-дедуктивного метода в математике, по
древнегреческой традиции, приписывается Пифагору~(шестое столетие до~н.~э.); оно
дошло до нас благодаря Эвклиду~(365?--275?~гг. до~н.~э.), <<Начала>> которого,
говорят, были некогда самой распространённой книгой после Библии. Эвклид не
сумел явно выразить все постулаты, которые требуются для вывода теорем. В новое
время были обнаружены другие постулаты, например те, которые регулируют порядок
точек на прямой~(Паш~\cite{pasch1882}).

Открытие формального рассмотрения логики, т.~е. открытие того, что дедуктивные
рассуждения можно описывать через форму их фраз, принадлежит, повидимому,
Аристотелю~(384--322~гг. до~н.~э.). И здесь новое время внесло
усовершенствования.

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

Этот новый язык будет носить тот общий характер символизма, с которым мы
встречаемся в математике. В алгебре мы производим выводы как формальные
манипуляции с уравнениями, которые чрезвычайно утомительно было бы производить в
обычном языке, как это делалось до того, как Виет~(1591) и другие изобрели
современные алгебраические обозначения. Открытие простых символических
обозначений, которые сами приводят к манипуляциям по формальным правилам,
явилось одним из путей, на которых развивалась мощь современной математики.
Однако в обычной математической практике мы имеем дело только с частичной
символизацией и формализацией, так как часть предложений остаётся выраженной
словами и часть выводов производится в терминах значений слов, а не по
формальным правилам.
%%
%% исправлена опечатка
%% в оригинале "Виета"
%%

После того как Лейбниц~\cite{leibniz1666} пришёл к мысли об ,,универсальной
характеристике``, в трудах де~Моргана~\cite{morgan1847,morgan1864},
Буля~\cite{boole1847,boole1854}, Пирса~\cite{peirce1867,peirce1880},
Шрёдера~\cite{schroeder1877,schroeder1890-1905} и других для формальной логики
также был получен символический способ обращения с помощью математической
техники.

Эти совпадающие по духу исследования в конечном счёте привели к строгим
формализациям различных разделов математики~---~Фреге\cite{frege1893,frege1903},
Пеано~\cite{peano1894-1908} и
Уайтхед и Рассел~\cite{whitehead_and_russell1910-1913}. (Описанный метод явного
изложения теории часто называется \emph{логистическим} методом.)

Гильберту принадлежит, во\nobreakdash-первых, подчёркивание того, что строгая
формализация теории предполагает полную абстракцию от смысла~---~результат такой
формализации называется \emph{формальной системой}, или
\emph{формализмом}\footnote{Не путать с формализмом как направлением в философии
математики.~---~\textit{Прим.~ред.}} (или иногда \emph{формальной теорией}, или
\emph{формальной математикой}); во\nobreakdash-вторых, ему принадлежит метод,
делающий формальную систему в целом предметом изучения математической
дисциплины, называемой \emph{метаматематикой} или \emph{теорией доказательств}.

Метаматематика содержит в себе описание или определение формальных систем, а
также исследование свойств формальных систем. При рассмотрении конкретной
формальной системы мы будем называть эту систему \emph{предметной теорией}, а
относящуюся к ней метаматематику~---~её \emph{метатеорией}.

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

С точки зрения метатеории, предметная теория является вовсе не теорией в прежнем
смысле этого слова, а системой бессодержательных предметов, аналогичных позициям
в шахматной игре, над которыми проделываются механические манипуляции,
аналогичные шахматным ходам. Предметная теория описывается и изучается как
система символов и предметов, построенных из символов. Символы рассматриваются
просто как типы распознаваемых объектов\footnote{Т.~е. таких объектов, любые два
из которых могут быть распознаны либо как одинаковые, либо как
различные.~---~\textit{Прим.~ред.}}. Для определённости мы можем представлять
себе их конкретно как знаки на бумаге, или, точнее, как абстракции от нашего
обращения со знаками на бумаге. (Теория доказательств должна быть в известной
мере абстрактна, потому что она предполагает выполнимыми построения произвольно
длинных последовательностей символов, хотя количество бумаги и чернил во всем
мире ограничено.) Остальные предметы системы рассматриваются только в связи со
способом их построения из символов\footnote{См.~об этом у
{\renewcommand*{\multicitedelim}{~или~}%
А.~А.~Маркова~%
\brackettext{\cites*[с~(пп.~5--15)]{markov1951}[(гл.~I)]{markov1954}}}.%
~---~\textit{Прим.~ред.}}. По определению, этим
исчерпывается роль формальной системы как предмета изучения метаматематики.

Метатеория принадлежит интуитивной, неформальной математике (если только
метатеория не формализуется, в свою очередь, в некоторой метаметатеории, чего мы
здесь рассматривать не будем). Метатеория будет выражаться на обычном языке с
математическими символами, например метаматематическими переменными, вводимыми
по мере надобности. Утверждения метатеории должны быть понимаемы. Её выводы
должны убеждать. Они должны состоять в интуитивных умозаключениях‚ а не в
применении установленных правил, как выводы в формальной теории. Чтобы
формализовать предметную теорию, были установлены правила, но теперь без всяких
правил мы должны понимать, как эти правила действуют. Интуитивная математика
необходима даже для определения формальной.

(Мы будем понимать это в том смысле, что для обоснования метаматематического
умозаключения приходится обращаться в конечном счёте к смыслу и очевидности, а
не к какому\nobreakdash-либо множеству условно принятых правил. На практике это
не помешает нам систематизировать наши метаматематические результаты как теоремы
или правила, которые можно будет затем применять квазиформально для сокращения
содержательных рассуждений. Это~---~обычный процесс в содержательной математике.
Иногда мы будем ссылаться даже на формально установленные принципы
(интуиционистской) логики, причём формальные выводы этих принципов будут
указывать метод, посредством которого рассуждение может быть проведено
содержательно.)

В метатеории мы будем применять только те методы, которые формалисты
называют \emph{финитными}~(finitary) и которые используют только интуитивно
представляемые предметы и осуществимые процессы. (Мы переводим немецкое
<<finit>> словом <<финитный>>\footnote{В
подлиннике~---~<<finitary>>.~---~\textit{Прим.~ред.}}; русское
<<конечный>>\footnote{В
подлиннике~---~английское <<finite>>.~---~\textit{Прим.~ред.}} соответствует
немецкому <<endlich>>.) Мы никогда не будем рассматривать бесконечный класс как
завершённое целое. Каждое доказательство существования будет давать, хотя бы
неявно, метод для построения предмета, существование которого
доказывается~(ср.~\textsection~\ref{sec:13-intuitionism})\footnote{%
\itemlabel{footnote:p15-1}{предыдущее подстрочное примечание}Такая точка
зрения не является единственно возможной. Метаматематику (теорию доказательств)
можно рассматривать и как содержательную математическую дисциплину (подобную,
например, алгебре или топологии), на методы которой не налагается никаких
специфических ограничений (см.~по этому поводу~\ref{par:p15-starred}).~%
---~\textit{Прим.~ред.}}.
%%
%% в сноске исправлена некорректная ссылка (зависящая от представления)
%% в оригинале вместо
%% "см.~по этому поводу~\ref{par:p15-starred}"
%% было
%% "см. по этому поводу четвёртый абзац следующей страницы"
%%

Это ограничение требуется для той цели, с которой Гильберт ввёл метаматематику.
Предложения данной математической теории могут не иметь ясного смысла, а её
умозаключения могут не иметь в себе несомненной очевидности.
%% ======================= Страница 62 =======================
Формализация сводит развитие теории к форме и правилу. Она устраняет всякую
неопределённость в отношении того, чт{\'o} такое предложение теории или чт{\'o}
такое доказательство в ней. И вопрос о том, не приводят ли к противоречию те
методы, которые были формализованы, а также другие вопросы о действии этих
методов должны изучаться в метатеории посредством методов, не подверженных тем
же сомнениям, что и методы первоначальной теории.

Финитные методы имеют ту же природу, что и методы интуиционистской элементарной
арифметики. Некоторые формалисты пытаются ограничить их ещё
{\'y}же~(Гильберт и Бернайс~\cite[стр.~43]{hilbert_and_bernays1934} и
Бернайс~\cite{bernays1935,bernays1938}).

Рассмотрение последнего обстоятельства мы отложим
до~\textsection~\ref{sec:81-reduction_of_classical_to_intuitionistic_systems}.
Чтобы защитить классическую математику от интуиционистов‚ нет надобности
стремиться пользоваться меньшим, чем они разрешают. Но естественно
придерживаться строго элементарных методов до тех пор, пока они достаточны. Все
приведённые в~\textsection~\ref{sec:13-intuitionism} примеры интуиционистских
арифметических рассуждений мы будем считать финитными. Мы увидим, что вплоть до
одной отдалённой стадии наших метаматематических исследований будет достаточно
интуиционистских методов совсем элементарного рода. Окончательным критерием
допустимости некоторого метода в метаматематике должна быть, конечно, его
интуитивная убедительность.

(*)\itemlabel{par:p15-starred}{абзац, помеченный звездочкой~(*)} (Некоторые
авторы пользуются приставкой <<мета>> для обозначения языка или теории‚ в
которой другой язык или теория делаются предметом изучения, не ограниченного
финитными методами. В этой связи в противовес
<<предметному языку>>~(<<object language>>) употребляется также
термин <<синтаксис>>~(<<syntax language>>).~Ср.~Карнап~\cite{carnap1934};
ср.~также~\textsection~\ref{sec:37-set-theoretic_predicate_logic_k_transforms}.
В этой книге мы пользуемся приставкой <<мета>> только тогда, когда методы
финитны.)
%%
%% исправлена опечатка
%% в оригинале было
%% "употребляется также термин <<синтаксис <<syntax language>>)."
%%

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

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

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

Насколько стеснительно это ограничение? Метаматематика должна изучать формальную
систему как систему символов и~т.~п., которые рассматриваются совершенно
объективно. Это означает попросту, что символы и~т.~п. сами по себе являются
окончательными предметами и не должны использоваться для обозначения
чего\nobreakdash-либо отличного от них самих. Метаматематик смотрит на них, а не
через них и не на то, что за ними; таким образом, они являются предметами без
интерпретации или значения.

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

Изучая эти предметы, метаматематика должна пользоваться своими собственными
методами и орудиями. Последние можно выбирать как угодно, лишь бы они были
финитны. Например, метаматематика может финитным способом употреблять
натуральные числа. Если речь идёт о формулах, допускающих (за пределами
метаматематики) финитную интерпретацию, то можно внутри метаматематики
определить свойства таких формальных объектов, которые (с точки зрения, внешней
по отношению к метаматематике) эквивалентны интерпретациям этих формул. Таким
образом, финитные интерпретации можно протащить через чёрный ход. Но
метаматематика никоим образом не может иметь дело с нефинитными интерпретациями
идеальных предложений классической математики.%
\footnote{См.~\ref{footnote:p15-1}.~---~\textit{Прим.~ред.}}

Чтобы в дальнейшем всюду было ясно, почему мы интересуемся формальными
системами, которые мы рассматриваем, и каким образом они представляют собой
формализации тех разделов логики и математики, с которыми содержательно мы уже
знакомы, мы в этой книге будем указывать возможные интерпретации и пользоваться
естественной терминологией, например, выражением <<доказательство>> для
формальных выводов и <<и>> как названием символа~$\OLand$. Это необходимо для
полного достижения нашей цели, хотя интерпретация сама по себе чужда
метаматематике.

Подведём итоги. Если рассматривать картину полностью, то имеются три отдельные и
отличные друг от друга <<теории>>:
(a)\itemlabel{listItem:p4-a}{(a)}~содержательная~(informal) теория,
формализацией которой служит формальная система,
(b)\itemlabel{listItem:p4-b}{(b)}~формальная система или предметная теория и
(c)\itemlabel{listItem:p4-c}{(c)}~метатеория, в которой описывается и изучается
эта формальная система.

Здесь~\ref{listItem:p4-b}, являющаяся формальной, служит не теорией в обычном
смысле, а системой символов и предметов, построенных из символов (описанных
в~\ref{listItem:p4-c}), причём эта система является своего рода условным
образом, или моделью, для~\ref{listItem:p4-a}. С другой стороны,
\ref{listItem:p4-a}~и~\ref{listItem:p4-c}, являющиеся содержательными, не имеют
точно определённой структуры, какую имеет~\ref{listItem:p4-b}.

Далее, \ref{listItem:p4-c}~---~это теория, изучающая~\ref{listItem:p4-b}, и она
должна применяться к~\ref{listItem:p4-b}, не взирая на~\ref{listItem:p4-a}, или,
точнее, не взирая на интерпретацию~\ref{listItem:p4-b} в
терминах~\ref{listItem:p4-a}.

Кроме того, \ref{listItem:p4-c}~ограничена употреблением только финитных
методов, тогда как для~\ref{listItem:p4-a}, вообще говоря, не имеется такого
ограничения.