Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
5
ся идеализированная -модель реальной математики внутри самой ;
математики. В более широком понимании речь идет даже об идеа- I
лизированной картине дедуктивного познания вообще, что опреде- 1
ляет общегуманитарную и гносеологическую ценность теорем о не- I
разрешимости. . I
Цель этой книги двоякая: описать основы математической ло- |
гики как модели математики и, пользуясь ее средствами, изло- 1
жить несколько доказательств неразрешимости, включая проблему •
континуума по Коэну, теорему Тарского о невыразимости истинно- \
сти и частично знаменитую теорему Геделя о неполноте. К сожа- 1
лению, вне рамок этой книги пришлось оставить задачи алгорит- ]
мической неразрешимости. Изложение их требует предварительно- '
го развития аппарата рекурсивных функций или одного из его |
эквивалентов (машины Тьюринга, алгоритмы Маркова). Ограниченный объем книги не позволил включить этот материал.
Книга состоит из трех глав. Две первые являются введением • в формальную логику и должны быть доступны читателю со сравнительно небольшим математическим образованием и некоторыми навыками теоретико-множественных рассуждений. Третья глава, посвященная проблеме континуума, заметно труднее технически. Однако полному изложению доказательства в ней предшествует модельный вариант на языке «случайных вещественных чисел», позволяющий при желании уяснить основные идеи конструкции, не вдаваясь в утомительные подробности.
К не вполне традиционному материалу относится параграф о квантовой логике с доказательством теоремы фон Неймана о скрытых параметрах, а также изложение теоремы Тарского методом Шмульяна. Шмульян придумал остроумный вариант фор-, мально'го языка арифметики, позволяющий легко написать на нем формулу, утверждающую свою ложность. Это снимает половину технических трудностей в доказательстве теоремы Геделя о неполноте.
Наконец, существенную часть книги составляет серия неформальных отступлений о смысле математических понятий в более широком контексте человеческой культуры. В определенном аспекте они выражают отношение автора к проблеме «обоснования» математики. Вероятно, логика способна обосновать математику не в большей мере, чем биология — обосновать жизнь.
Читатель, который пожелает расширить свои познания по обсуждаемым в этой книге вопросам и ознакомиться с другими точками зрения, может обратиться к многочисленной литературе, часть которой указана в библиографии. В частности, на русском языке имеются прекрасные курсы логики Дж. Шеяфилда [1],
Э. Мендельсона [2], С. Клини [3]. Специально проблеме континуума посвящена книга П. Дж. Коэна [7]. Теория множеств, ее формальные аспекты и философские проблемы изложены в книгах
6
Н. Бурбаки [5], А. Френкеля и И. Бар-Хиллела [17], см. также глубокий обзор К. Геделя [20] и статью П. Коэна [19]. Специально математической теории рекурсивных функций и алгоритмов посвящены книги В. А. Успенского [15], А. А. Маркова [8],
А. И. Мальцева [10], X. Роджерса [11] и статьи В. А. Успенского [15], Ю. И. Манина [13, 14], Ю. Матиясевича [12]. Различные точки зрения на философские проблемы оснований математики изложены в уже цитированных книгах С. Клини и А. Френкеля и И. Бар-Хиллела, в монографии А. Тарского [16], а также в содержательной книге В. Н. Тростникова [18] и популярной работе И. Лакатоса [21].
В заключение я хотел бы выразить свою глубокую благодарность С. Г. Гиндикину, оказавшему большую помощь автору еще в период работы над рукописью, и И. М. Яглому, чье внимательное и доброжелательное рецензирование книги помогло ее улучшению.
Глава I ВВЕДЕНИЕ В ФОРМАЛЬНЫЕ ЯЗЫКИ
Gelegentlich ergreifen wir die Feder Und schreiben Zeichen auf ein weisses Blatt, Die sagen dies und das, es kennt sie jeder. Es ist ein Spiel, das seine Regeln hat.
H. Hesse, Buchstaben
Ты пишешь на листе, и смысл, означен и закреплен блужданьями пера, для сведущего до конца прозрачен: на правилах покоится игра.
Г. Гессе. Алфавит (Пер. С. С. Аверинцева)
1. ОБЩИЕ СВЕДЕНИЯ
1.1. Пусть А — некоторое абстрактное множество — алфавит. Конечные последовательности элементов А называются выражениями в А, конечные последовательности выражений — текстами.
Мы будем говорить о языке с алфавитом А, если некоторые выражения и тексты отмечены (как «правильно составленные», «осмысленные» и т. п.). Так, в латинском алфавите А можно отметить словоформы английского языка и грамматически правильные английские фразы. Полученное множество выражений и текстов будет рабочим приближением к интуитивному представлению об «английском языке».
Язык Алгол-60 состоит из выражений и текстов, отмеченных в алфавите {латинские буквы} и {цифры} и {логические значе-ния} У {ограничители}. К числу важнейших отмеченных текстов принадлежат программы.
В естественных языках совокупность отмеченных выражений и текстов имеет обычно зыбкие границы. Чем более формализован язык, тем жестче эти границы очерчены.
8
Правила формирования отмеченных выражений и текстов со-| ставляют синтаксис языка.
I Правила их сопоставления с реальностью относятся к его семантике.
