Доказуемое и недоказуемое - Манин Ю.И.
Скачать (прямая ссылка):
„ метатель огня Вьюги Ведьмы луны коня корабельных сараев"
корабль
щит копье
битва
меч
Воин, мужчина, человек
Леонид Мартынов, воспринял кеннинги как метафоры (глубокое заблуждение, хотя и простительное. Структурные роли кеннингов и метафор в разных поэтических системах совершенно различны) и написал стихотворение «Песни скальдов», которое кончается так:
... А может быть, переводчики что-то перемудрили?
Нет! Возможно и в наши живут времена
какие-то метатели огня вьюги ведьмы луны коня
корабельных сараев или
расточители янтаря холодной земли великанского кабана?
Все возможно!
И кто утверждать может твердо,
Что и ныне нет песен, которые можно назвать
Прибоем дрожжей людей костей фьорда?
Может быть, есть и нынче такие песни, как знать?
После этого профессиональное замечание М. И. Стеблнна-Ка-менского, из книги которого «Культура Исландии» [27] взяты примеры, звучит несколько расхолаживающе: «Любой кеннинг воина, или мужчины, был, как правило, не богаче содержанием, чем местоимение «он»».
Упражнения:
а) Восстановить простые кеннинги, входящие в вывод двух последних кеннингов, процитированных Мартыновым.
б) Построить кеннинги максимальной длины, выводимые из приведенных в тексте. Доказать, что более длинных кеннингов вывести нельзя.
63
6. ТЕОРЕМА ГЕДЕЛЯ О ПОЛНОТЕ
6.1. Пусть Ь— некоторый язык класса <р—его интерпретация, Т Ь— множество <р-истинных формул. В § 3 было показано, ; что множество Т Ь геделево, т. е. полно, не содержит противо-' речия, замкнуто относительно вывода и содержит все логические аксиомы АхЬ.
Основная цель этого параграфа — доказательство обратного результата (Гедель):
6.2. Теорема.
а) Любое геделево множество Т является множеством всех <р-истинных формул Т Ь для подходящей интерпретации Ь в некотором множестве М мощности г^саг<3 (алфавит (здесь и ниже имеется в виду мощность алфавита без переменных: ср. 2.12).
б) Любое непротиворечивое множество формул г, содержащее АхЬ, можно вложить в геделево множество.
Модель М, которая будет построена в доказательстве, состоит из выражений в некотором расширении алфавита Ь, т. е. носит несколько искусственный характер. В следующем параграфе будет показано, что если некоторая естественная интерпретация (М, ср) языка Ь задана, то из нее можно выбрать подмодель мощности йС1сагс1 (алфавит Ь)
6.3. Следствие .(критерий выводимости).
Пусть е^АхЬ.
а) Формула Р выводима из е в том и только в том случае, когда либо е противоречиво, либо Р ср-истинна для всех моделей <р множества е мощности ^сагс! (алфавит Ь^-Ь^,.
б) Формула Р независима от е в том и только том случае когда е у {Ру и еи{П^} непротиворечивы, или, что то же по теореме 6.2, когда е и {Р} и б и {"1 Р} имеют модели.
В дальнейшем мы будем часто опускать проверку существования разных формальных выводов. Если читатель захочет это восполнить, почти всегда проще устанавливать выводимость с помощью критерия 6.3, чем непосредственно.
Доказательство, а) Если е противоречиво, то из е выводится любая формула (предложение 4.2). Пусть б непротиворечиво и Р<р-истинна для всех моделей б. Для доказательства е |— Р рассмотрим два случая.
а1) 5 и П Р} противоречиво. Тогда е и { 1 1— откуда по
лемме о дедукции 4.5. е [— ~~]Р —*-Р. Тавтология (ДР—>-Р)— и МР дают б [— Р.
а2) е(Д{ДР} непротиворечиво. Тогда по теореме 6.2 множество б У { 1 Р} имеет модель; в ней е истинно, а Р ложна, так что этот случай невозможен.
64
б) Допустим, что Р независима от г, т. е. Р и "] Р невыводимы. Тогда по результату п. 6.3а существует модель в, в которой Р истинна, и модель е, в которой Р ложна. Обратное очевидно.
Теперь приступим к доказательству теоремы Геделя.
6.4. Определение.
Пусть г — некоторое множество формул языка Ь. Алфавит языка Ь называется достаточным для в, если для любой формулы Р(х), содержащей ровно одну свободную переменную х, существует такая константа сР (зависящая от Р), что формула
11р:-]ЧхР(х)-~\Р(Ср)
принадлежит е.
Интуитивный смысл ЯР: «если не все х обладают свойством Р, то можно указать конкретный объект сР, не обладающий этим свойством».
Терминология «достаточность алфавита» связана с тем, что в случае нехватки формул вида РР в г мы сможем просто увели-. чить е, добавив все РР, а если не хватит констант сР, нам придется добавить их к алфавиту языка.
План доказательства теоремы 6.2 состоит в следующем. Сначала мы установим, что справедлива следующая
6.5. Основная лемма.
Если множество 8 формул языка непротиворечиво, полно, со-дерокит АхЬ и алфавит Ь достаточен для е, то существует модель г мощности ^сагй (алфавит Ь)4-к§.
Следующие две леммы позволяют вложить любое непротиворечивое 8 в полное множество или в такое, для которого алфавит достаточен.
6.6. Лемма.
Если е непротиворечиво и содержит АхЬ, то существует непротиворечивое полное множество формул е'Эе.
6.7. Лемма.
Если е непротиворечиво и содержит АхЬ, то существуют:
а) язык Ь', алфавит которого получается из алфавита Ь добавлением множества новых констант мощности г^сагс! (алфавит Ь) + 1
б) множество формул е' языка Ь', непротиворечивое, содержащее е и АхЬ' и такое, что алфавит Ь' достаточен для г'.
