Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
Внимательный читатель отметит следующее. В L,Set можно написать формулу, в которую входил бы квантор у по всем подмножествам целых чисел (конечных ординалов). Но в L'iSet нельзя написать формулы, которые бы явно описывали многие конкретные подмножества, потому что их имеется континуум, а формул всего счетное количество. В гл. II мы коснемся этих проблем ближе, обсуждая парадокс Сколема.
Итак, в языки первого порядка (и в особенности в язык Li Set) заложены почти все фундаментальные логико-множественные принципы, используемые в повседневной работе математика. Поэтому они будут основным объектом изучения в этой книге. Конкретные ориентированные языки могут, однако, быть оформлены иначе, с большими или меньшими отступлениями от правил 3?i. Кроме L'2Real мы рассмотрим в качестве примеров таких языков а гл. II SELF (язык Шмульяна для самоописания) и SAr — язык арифметики, для которого удобно доказывать теорему Тарского о невыразимости истинности.
Отступление о синтаксисе
1. Важнейшая общая черта большинства искусственных языков— возможность задать богатый спектр средств выражения конечным и небольшим числом порождающих принципов.
20
21
В каждом конкретном случае выбор этих принципов (включая алфавит и синтаксис) есть результат компромисса между двумя крайностями.
Экономия выразительных средств ведет к унификации записи и упрощению механического анализа текста. Однако она удаляет тексты от текстов на естественных языках и очень удлиняет их.
Обогащение выразительных средств приближает искусственные тексты к естественным, но усложняет синтаксис и формальный анализ. (Ср. машинные языки с языками программирования типа Алгола, Фортрана, Кобола и т. п.)
Приведем несколько примеров на нашем материале.
2. Диалекты 3?\. а) Не меняя логики, заложенной в З’и мы могли бы обойтись в алфавите без скобок и любого из двух кванторов, а все связки заменить одной \ (конъюкция отрицаний) (кроме того, константы можно было бы объявить функциями ранга О, а функции свести к отношениям).
Это достигается следующим изменением определений. Если .. ..., 1Г—термы, /—операция ранга г,р— отношение ранга г, то II;..Лг— терм, рЬх... А — атомарная формула. Если Р, С? — формулы, то \ Р<2, ухР — формулы. Содержательно \ РО, означает “не Р и не С“, так что на этом диалекте имеем следующие выражения:
1 (Р): 1 РР, (Р)ЛЮ): I I Рр 1 0.& т«) №1 Р&
Видно, как экономия на скобках и связках ведет к многократному! повторению одной и той же формулы. Тем не менее доказательства! теорем о таком языке ,могут упроститься за счет сокращения спи-| ска его синтаксических норм. |
б) Язык теории множеств по Н. Бурбаки [5] содержит в алфа-1 вите знак О], 1, \/, ””1» ==> ^ и буквы. Выражения в этом языке,|
однако, суть не просто последовательности знаков алфавита, но! последовательности, в которых некоторые элементы объединены! в пары (надстрочными соединителями). Пример:
Главное отличие языка Бурбаки от L, Set состоит в наличии “символа выбора Гильберта“. Если, скажем, €?ху есть формула “х I 1
элемент г/“, то у есть терм, который означает “некоторый
элемент множества уа.
Язык Бурбаки не слишком удобен и не получил распространения. Он стал известен в популярной литературе благодаря при-
меру сокращенной записи терма «единица», неосторожно приведенной авторами:
*Л(а“)(Е^(и=(?/. {0}. 2) С {0}Х^ Л (ух) ((X е {0})
=> (ЗУ) ((*» У) ? Щ/\ (V-«) (чу) (уу')
(((х, у)е г/Д(.к,у') 0(?/) (у=у')) Л (уу) ((у е^)^> (нх ((х,у) е Ц)))).
Полная запись этого терма содержала бы несколько десятков тысяч знаков; для «единицы» этого, пожалуй, многовато.
в) Очень значительным расширением выразительных возможностей почти любого языка класса 2>1 было бы разрешение формировать «классовые термы» типа {х\ Р(х)}, которые обозначали бы «класс всех объектов х, обладающих свойством Р». Эта идея была использована Морзом в языке теории множеств и Шмулья-ном в языке арифметики (см. § 10 гл. II).
3. Общие замечания. Для большинства естественных и искусственных языков характерны дискретность и линейность (одномерность).
Восприятие внешнего мира человеком не ощущается нами ни как дискретное, ни как линейное, хотя эти характеристики прослеживаются на уровне физиологических механизмов (кодирование импульсами-спайками в нейронных сетях). Однако языки общения тяготеют к последовательному разворачиванию информации в серию различимых элементарных знаков. Вероятно, главной причиной этого является значительно большая (теоретически неограниченная) степень однозначности и воспроизводимости информации, чем эго достижимо при других способах ее передачи (ср. часто обсуждавшиеся преимущества цифровых ЭВМ перед аналоговыми.)
Но человеческий мозг явно пользуется обоими принципами. Целостное восприятие образов, а также эмоции связаны, скорее, с нелинейными и недискретными процессами, возможно, волновой природы. Интересно с этой точки зрения проанализировать нелинейные фрагменты различных языков.
В математике к ним относится, в первую очередь, употребление чертежей. Оно, однако, почти не поддается формальному описанию, за исключением отщепившейся и формализовавшейся теории графов. Граф — исключительно популярный объект, минимально удаленный как от своего целостного пространственного образа, так и от описания по всем правилам теории множеств. Всякий раз, когда с задачей удается связать граф, обсуждение резко упрощается и большие фрагменты словесного описания заменяются манипуляцией с картинками. Менее известный класс примеров — коммутативные диаграммы и спектральные последовательности гомологической алгебры. Типичный образец — «лемма о змее». Вот ее точная формулировка.
