rt-g0_73c250c9-Kleene_VVM-russian/parts/intros.tex

%% ======================= Страница 5 =======================
\chapter*{От переводчика}
\label{int:translator_s_preface}

Хотя математическая логика существует как наука по крайней мере с середины
прошлого столетия, круг специалистов в этой области невелик и результаты её
известны недостаточно широко. Однако за последние десятилетия~---~и в
особенности начиная с 1930~г.~---~в ней были сделаны важнейшие открытия и
развитие её приняло настолько бурный характер, что теперь трудно уже охватить
все полученные результаты одной монографией, во всяком случае, такая монография
до сих пор никем не написана. Имеются всё же две монографии, которые играют
ведущую роль в мировой литературе по математической логике,~---~это книга
Гильберта и Бернайса <<Grundlagen der Mathematik>> (т.~I~---~1934~г.,
т.~II~---~1939~г.) и предлагаемая вниманию читателя более современная книга
Клини <<Введение в метаматематику>>~(1952~г.).

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

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

Часть~\ref{part:III-recursive_functions} этой монографии может в основном
читаться независимо от остальных частей и служить руководством для изучения
теории рекурсивных функций, более сжатым и потому более трудным, чем выпущенная
недавно Издательством иностранной литературы книга Р.~Петер <<Рекурсивные
функции>>, (1951~г.; Третья часть книги Клини содержит более полное изложение
теории обще\nobreakdash-рекурсивных функций и вовсе отсутствующую у Петер теорию
частично\nobreakdash-рекурсивных функций, но зато монография Петер богаче
материалом, связанным с примитивными рекурсиями).

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

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

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

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

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

Выражаем благодарность также А.~А.~Курмитису~(Рига), указавшему на одну
неточность, допущенную автором (в замечании~\ref{remark:p27-1}%
~\textsection~\ref{sec:27-equivalences_duality}).

Ряд мелких исправлений внесён нами без специальных оговорок.

В оригинале при переносе формул последний знак, стоящий перед переносом, не
повторяется. Следуя установившейся у нас традиции, мы, как правило, повторяем
этот последний знак, если он не является знаком отрицания или запятой.

Обращаем особое внимание читателя на различие между двумя
шрифтами~---~полупрописной курсив и прямой, которое начинает появляться
в~\ref{chap:iv-a_formal_system} главе, и особенно начиная
с~\textsection~\ref{sec:40-the_further_development_of_number_theory}%
~гл.~\ref{chap:viii-formal_number_theory}.\\*
{\setlength{\tabcolsep}{0cm}
\begin{tabular}{l@{\hspace*{1.5ex}}*{21}{r@{,\hspace*{.2em}}}r}
Полупрописной курсив&%
$\frml{a}$&$\frml{b}$&$\frml{c}$&$\frml{d}$&$\frml{e}$&
$\frml{f}$&$\frml{g}$&$\frml{h}$&$\frml{i}$&\ldots&%
$\frml{l}$&$\frml{m}$&$\frml{n}$&$\frml{o}$&$\frml{p}$&
$\frml{q}$&$\frml{r}$&$\frml{s}$&\ldots&%
$\frml{x}$&$\frml{y}$&$\frml{z}$\\
Прямой&%
$\infr{a}$&$\infr{b}$&$\infr{c}$&$\infr{d}$&$\infr{e}$&%
$\infr{f}$&$\infr{g}$&$\infr{h}$&$\infr{i}$&\ldots&%
$\infr{l}$&$\infr{m}$&$\infr{n}$&$\infr{o}$&$\infr{p}$&
$\infr{q}$&$\infr{r}$&$\infr{s}$&\ldots&%
$\infr{x}$&$\infr{y}$&$\infr{z}$
\end{tabular}}

{(Полупрописной курсив употребляется для обозначения формальных переменных, а
прямой~---~для содержательных.)%
\renewcommand{\thefootnote}{\fnsymbol{footnote}}\footnote{Последние два
абзаца предисловия переводчика с описанием шрифтов и списки соответствия шрифтов
изменены при перенаборе для соответствия реальному представлению
переменных.~---~\textit{Прим.~перенаборщика.}}}
%%
%%
%% исправление
%% в оригинале вместо "Полупрописной курсив" было написано "Курсив"
%% и дан тоже курсив, но в дальнейшем формальные переменные обозначены именно
%% полупрописным курсивом
%%
%% в оригинале вместо "Прямой" было написано "Плантин" и дан полупрописной
%% курсив, но дело в том, что, во-первых, плантин -- это семейство
%% сериф-шрифтов; а, во-вторых, далее содержательные переменные обозначены
%% именно прямым обычным шрифтом
%%
%% также в оригинале было
%% "(Плантин употребляется для обозначения формальных переменных, а курсив - для
%%  содержательных.)", на самом же деле, далее в четвёртой главе, прямым обычным
%% шрифтом обозначаются содержательные переменные, а формальные обозначены
%% полупрописным курсивом.
%%
%% Вообще, в оригинале в последних абзацах явная ошибка: дело в том, что,
%% во-первых, плантин -- это семейство сериф-шрифтов; а, во-вторых, начиная с
%% четвёртой главы действительно используются два шрифта в формулах. Но в целом
%% книге (и в англоязычном оригинале тоже) использовано пять шрифтов в
%% формулах:
%%     - классический математический курсив;
%%     - прямой болд сериф для обозначения множеств вещественных чисел;
%%     - прямой болд санс сериф для обозначения множеств множеств;
%%     - неклассический полупрописной курсив, который выше назван плантином;
%%     - и прямой обычный сериф.
%% И в четвёртой главе прямым обычным серифом обозначаются содержательные
%% переменные, а формальные обозначены полупрописным курсивом.
%%
%% И ещё интересно, чем Есенину-Вольпину буквы "o" и "q" не угодили? )))
%% При перенаборе они возвращены на свои законные места.
%%

\bigskip

\hfill\textit{А. С. Есенин\nobreakdash-Вольпин.}

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

\chapter*{Предисловие}
\label{int:preface}

Две последовательные эры исследований по основаниям математики в девятнадцатом
столетии, достигшие своего наивысшего развития в теории множеств и арифметизации
анализа, сменились около 1900~г. новым кризисом и новой эрой, отмеченной
господством программ Рассела и Уайтхэда, Гильберта и Брауэра.

Появление в 1931~г. двух теорем Гёделя о неполноте, в 1933~г. работы Тарского о
понятии истины в формализованных языках, в 1934~г.
эрбран\nobreakdash-гёделевского понятия ,,обще\nobreakdash-рекурсивной функции``
и в 1936~г. связанного с ним тезиса Чёрча возвещает уже новейшую эру, в которой
математические средства применяются как для оценки прежних программ, так и в
новых, не предвиденных прежде направлениях.

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

Пришлось произвести некоторый отбор. В основном это было сделано с тем, чтобы
сосредоточиться после части~\ref{part:I-the_problem_of_foundations} на
метаматематическом исследовании элементарной арифметики с необходимым материалом
из математической логики, оставив в стороне исчисление предикатов высших
ступеней, анализ, теорию типов и теорию множеств. Этот отбор был сделан потому,
что в арифметике мы находим пример первого и простейшего применения новейших
методов и концепций, тогда как распространение их на другие отрасли математики
пока ещё находится в стадии становления (и будет приобретать, повидимому, всё
б\'{o}льшую и б\'{o}льшую важность в ближайшем будущем).

Книга написана с таким расчётом, чтобы она могла служить учебником для
аспирантов\nobreakdash-математиков первого года обучения\footnote{First year
graduate students in mathematics.~---~\textit{Прим.~перев.}} (и старше) и для
других лиц, достигших этого уровня владения математикой, независимо от их
познаний в том или ином разделе математики.

При использовании книги в качестве учебника рекомендуется быстро (в течение двух
или трёх недель при аудиторных занятиях по три раза в неделю) пройти
часть~\ref{part:I-the_problem_of_foundations}
(главы~\ref{chap:i-the_theory_of_sets}\nobreakdash--%
\ref{chap:iii-a_critique_of_mathematical_reasons}), которая содержит необходимый
подготовительный материал. Интенсивное изучение должно начаться с
части~\ref{part:II-mathematical_logic} (глава~\ref{chap:iv-a_formal_system}),
где
%% ======================= Страница 8 =======================
существенно, чтобы изучающий сосредоточился на приобретении прочного навыка в
обращении с метаматематическим методом.

Параграфы, отмеченные звёздочкой, могут быть при первом чтении опущены или
рассмотрены бегло. К изучению некоторых из них придётся в дальнейшем вернуться
(например, \textsection~\ref{sec:37-set-theoretic_predicate_logic_k_transforms}
нужно изучить перед чтением
\textsection~\ref{sec:72-goedel_s_completeness_theorem}).

Обе знаменитые теоремы Гёделя о неполноте изложены в
главе~\ref{chap:viii-formal_number_theory}, причём доказательство одной леммы
отложено до главы~\ref{chap:x-the_arithmetization_of_metamathemathics}. Автору
удавалось закончить эти десять глав (а иногда даже несколько больше) в течение
семестрового курса, который он неоднократно читал в Висконсинском университете.

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

Семестровый курс по рекурсивным функциям при наличии у студентов некоторого
предварительного знакомства с математической логикой или под руководством
осведомлённого преподавателя можно начать с
части~\ref{part:III-recursive_functions}
(глава~\ref{chap:ix-primitive_recursive_functions}). Имеются и другие
возможности выбора материала; например, тем, кто интересуется преимущественно
математической логикой, многое из
части~\ref{part:IV-mathematical_logic_additional_topics} можно
читать непосредственно за частью~\ref{part:II-mathematical_logic} или даже за
главой~\ref{chap:vii-the_predicate_calculus}.

Автор благодарен Сондерсу Маклэйну, склонившему его к написанию этой книги и
сделавшему ценные критические замечания в связи с первыми черновиками некоторых
глав. Джон Аддисон полностью прочитал гранки с большой тщательностью и
независимо от автора. Среди многих других, оказавших помощь, были Эверт Бет,
Роберт Бройш, Аренд Гейтинг, Нэнси Клини, Леонард Линский, Дэвид Нельсон, Джеймс
Ренно и Джин Роуз. Научные заимствования отмечены ссылками на библиографию;
особенно много использована книга Гильберта и Бернайса <<Grundlagen der
Mathematik>> в двух томах, 1934~и~1939~гг.
\bigskip

{\small\noindent Июль~1952~г.}\hfill\textit{С.~К.~Клини.}