Книги по разным темам Pages:     | 1 |   ...   | 14 | 15 | 16 | 17 | 18 |   ...   | 54 |

Остается разобрать последний вопрос: в какой мере эта аргументация проходит для любых наборов дедуктивных средств, которые могут строить все большие и большие множества D Наше рассуждение показывает, что единственно существенное свойство каждого из этих наборов Ц - возможность механического порождения всех выводов. Но здесь, разумеется, снова встает вопрос о полноте: знаем ли мы уже все принципы механического порождения или они могут пополняться Можно было бы вообразить себе существование таких процедур порождения выводов, что соответствующее им множество E уже не могло бы быть выраженным в LAr.

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

Их комбинации дают все возможные полувычислимые функции (частично рекурсивные). Арифметика и логика, заложенные в большие цифровые ЭВМ, достаточны для порождения всех выводов из любого финитного набора посылок. Любое мыслимое предписание о чисто механическом порождении выводов может быть превращено в программу для такой машины. Если принять эту точку зрения, то придется признать, что выразимость выводимости установлена в самых общих предположениях о дедуктивных средствах.

Как далеко от выводимости до истинности Уточнить этот вопрос и в какой-то степени ответить на него помогли исследования последних лет. Вот ответ в двух словах: очень далеко.

06 Ч I. М Точнее говоря, рассмотрим класс выразимых в LAr подмножеств множества целых чисел. Можно показать, что все они выражаются формулами типа:

Существуют такие x1, Е, xm, что для всех y1, Е, yn существуют такие z1, Е, zp, что для всех u1, Е, uq существуют... со свойством P(x1, Е, xm, y1, Е, uq, Е; x) = и их отрицаниями.

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

Естественно пытаться классифицировать выразимые множества по сложности формул, которые их выражают. Оказывается, что важной мерой сложности служит число перемен кванторов перед символом многочлена P. (Например, в последовательности x1x2y1 z1z2zдве перемены кванторов.) Обозначим через n класс всех множеств, выразимых формулами с не более чем n переменами кванторов.

Очевидно, 0 1 2 Е Ц - эти классы не убывают.

Около тридцати лет назад было доказано, что эти классы строго возрастают: в n+1 всегда есть множества, не лежащие в n. Их объ единение = n есть класс всех арифметически выразимых мноn=жеств. Лестница, ведущая вверх 0 < 1 < 2 < Е называется арифметической иерархией.

Пусть теперь D Ц - множество номеров выводимых формул в некотором языке математики. Из предыдущего обсуждения мы знаем, что D. На какой ступени лестницы может находиться D Совсем недавно на этот вопрос был получен поразительный ответ: серия исследований, завершенная работами молодых советских математиков Ю.В.Матиясевича и Г.В.Чудновского, показала, что обязательно D 0. Точнее говоря, любое множество D выразимо формулой вида x1Еxn (P(x1, Е, xn; x) = 0).

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

Т Г В следующем, последнем, разделе статьи мы укажем некоторые верстовые столбы на бесконечно долгом пути от D до T.

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

Фиксируем некоторый формальный язык математики L, семантику и средства дедукции в нем. Обозначим снова D множество номеров выводимых формул в некоторой фиксированной нумерации Гёделя.

Построим явно формулу P, выражающую D. Для доказательства теоремы, что истинность T не выражается формулой P, мы пользовались следующей схемой рассуждений:

а) предположим, что истинность T выразима формулой P;

б) тогда есть формула QP, говорящая ля не истинна. Не имея свободных переменных, она должна быть истинной или ложной;

в) она не может быть ложной (по своей семантике);

г) она не может быть истинной (по своей семантике);

д) следовательно, истинность не выразима формулой P.

Это рассуждение Тарского: пункты в) и г) в нем эксплуатируют в математическом контексте парадокс жеца, а пункт д) его объясняет.

Но здесь никак не использовалось специфическое свойство P выражать D; теорема Тарского применима ко всем P.

Гёдель рассуждал чуть-чуть иначе, и это маленькое отличие доставляет результат, замечательный для теории познания.

Доказательство Гёделя в параллельном изложении выглядит так:

а) выводимость D выразима формулой P;

б) есть формула QP, говорящая ля не выводима. Не имея свободных переменных, она должна быть либо истинной, либо ложной;

в) она не может быть ложной (по своей семантике: иначе она должна была быть выводимой и, следовательно, истинной);

г) значит, она истинна;

д) следовательно, она не выводима (по своей семантике).

Таким образом, Гёдель явно указывает формулу QP, которая истинна, но не выводима с помощью данных дедуктивных средств! Иными словами, его рассуждение не только демонстрирует неполноту это 08 Ч I. М го набора дедуктивных средств, но также дает эффективный способ пополнить этот набор новой аксиомой, истинность которой мы установили метаязыковыми разговорами.

Расширив так множество D, мы получим большее множество D, все еще не совпадающие с T; к нему можно снова применить конструкцию Гёделя и т. д. Таким образом, мы получаем рецепт для проведения целой серии творческих актов Ц - пополнения арифметики новыми аксиомами, истинность которых мы не доказываем, но угадываем. (Формализация этого свойства T привела к математическому понятию творческого множества, которое автор не намерен обсуждать подробнее, но вынес в заголовок раздела Ц - для рекламы.) На самом доле, разумеется, творческий акт здесь был совершен однократно Ц - самим Гёделем; и его содержание уникально.

Ясно, что как бы мы ни постарались финитно описать рецепт для бесконечного увеличения D таким способом, все T все равно окажется неисчерпанным Ц - в силу той же теоремы о неполноте.

Однако можно постараться исчерпать T формулами гёделевского типа, отказавшись от надежды описать этот набор формул финитно.

Очень красивый результат в этом направлении доказал около десяти лет назад американский математик С.Феферман. Его изложением мы и закончим статью.

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

Точнее, пусть P(x) Ц - любая формула с одной свободной переменной. С. Феферман показывает, как написать формулу AP без свободных переменных, смысл которой в метаязыке может быть выражен так:

если для всех чисел n формулы P(n) выводимы из предыдущей системы аксиом, то x P(x).

После этого оказывается, что добавление формул AP в бесконечном количестве и всех выводов из них исчерпывает T.

Иными словами, начнем с принятия элементарных арифметических тождеств и аксиом индукции.

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

Т Г Два эпилога Старательно мы наблюдаем свет, Старательно людей мы наблюдаем И чудеса постигнуть уповаем:

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

Е. Боратынский Мысль изреченная есть ложь.

Ф. Тютчев Литература. Клини С. К. Введение в метаматематику. М.: ИЛ, 957.

2. Мальцев А. И. Алгоритмы и рекурсивные функции. М.: Наука, 965.

3. Мендельсон Э. Введение в математическую логику. М.: Наука, 97.

4. Нагель Э., Хьюмен Дж. Р. Теорема Гёделя. М.: Знание, 970.

5. Успенский В. А. Теорема Гёделя о неполноте в элементарном изложении // Успехи математических наук. 974. Т. 29. Вып.. C. 347.

Георг Кантор и его наследие Бог Ц - не геометр; скорее он непредсказуемый поэт. (Геометры могут быть непредсказуемыми поэтами, так что здесь есть место для компромисса.) В. Тасич [12] о романтизме XIX века Введение Великий метанарратив Георга Кантора Ц - теория множеств, Ц - созданный им практически в одиночку примерно за пятнадцать лет, больше напоминает произведение искусства, чем научную теорию.

Пользуясь слегка модернизированным языком, основные результаты теории множеств можно резюмировать в нескольких строках.

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

Это мотивирует введение другой категории Ц - категории вполне упорядоченных множеств с монотонными отображениями в качестве морфизмов. Классы изоморфизма объектов этой категории называются ординалами; они также вполне упорядочены. Гипотеза континуума представляет собой догадку относительно порядковой структуры начального сегмента ординалов.

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

Выступление на заседании Немецкого математического общества при награждении Канторовской медалью. Впервые опубликовано в сборнике статей, посвященном памяти А. Н. Тюрина: Algebraic Geometry: Methods, Relations, and Applications. Труды МИАН им. В. А. Стеклова. 2004. Т. 246. С. 95203. Перевод с английского С. М. Львовского.

Г К Сам Кантор был бы категорически не согласен с этой точкой зрения: для него открытие иерархии бесконечностей было открытием боговдохновенной Истины.

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

Одно из главных открытий Кантора можно, несколько провокационным образом, представить в следующем виде:

2x значительно больше, чем x.

Здесь под x можно понимать целое число, произвольный ординал или же произвольное множество (в последнем случае 2x обозначает множество всех подмножеств в x). Глубокая математика начинается в тот момент, когда мы пытаемся уточнить это утверждение и выяснить, насколько 2x больше, чем x.

Если x Ц - первый бесконечный ординал, то это гипотеза континуума.

Я выскажу соображения в пользу того тезиса, что для конечных x этот вопрос при правильной постановке оказывается тесно связанным с универсальной NP-проблемой.

Затем я остановлюсь на различных вопросах, связанных с ролью теории множеств в современной математике и с рецепцией канторовских идей.

Аксиома выбора и P-NP проблема, или конечное как бесконечность для бедныхВ 900 году, в своем выступлении на Втором международном математическом конгрессе в Париже, Гильберт поставил гипотезу континуума первой в своем списке 23 основных проблем математики. Это было одно из ярких событий в научной биографии Кантора, потратившего множество усилий на консолидацию немецкого и международного математического сообществ в единый организм, способный противостоять группе влиятельных профессоров, настроенных против теории множеств.

Тем не менее противостояние его теории бесконечного продолжалось, и это Кантора сильно задевало: под вопрос ставилась ценность созданной им новой математики.

В Оперном театре Галле ноября 2006 года состоялась премьера оперы Ингомара Грюнауэра Кантор, или измерение бесконечности.

На клеевскую премию в $106 за решение P-NP проблемы я не намекаю.

2 Ч I. М В 904 году, на следующем международном конгрессе, Кёниг выступил с докладом, в котором доказывалось, что континуум нельзя вполне упорядочить; это делало гипотезу континуума бессмысленной.

Вот что по этому поводу пишет Даубен [3, c. 283]: Кантор тяжело переживал драматическую ситуацию со статьей Кёнига, доложенной на Третьем международном математическом конгрессе в Гейдельберге. Он был на конгрессе с двумя дочерьми, Эльзой и Анной-Марией, и доклад Кёнига был воспринят им как личное унижение.

Оказалось, однако, что в статье Кёнига содержится ошибка, а вскоре Цермело обнародовал доказательство того, что всякое множество можно вполне упорядочить Ц - доказательство, опирающееся на введенную им совсем новую аксиому выбора. По существу эта аксиома утверждает, что исходя из всякого множества U можно построить новое множество, состоящее из пар (V, v), где V пробегает все непустые подмножества в U, а v Ц - элемент множества V.

Век спустя математическое сообщество не представило списка проблем на новое столетие, аналогичного списку проблем Гильберта.

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

Тем не менее, по-прежнему остаются нерешенными несколько важных конкретных задач; недавно семь из них были выделены и снабжены ценниками. Я сейчас остановлюсь на одной из этих задач, а именно, на P-NP проблеме; я буду ее рассматривать как финитарную травестию цермеловской аксиомы выбора.

m Пусть через Um = 2 обозначено множество m-битовых последовательностей. Его подмножества удобно кодировать булевыми многочленами. Пользуясь стандартным (и более общим) языком коммутативной алгебры, можно отождествить всякое подмножество в Um с множеством нулей единственной функции f Bm, где Bm Ц - алгебра булевых многочленов Ц - определяется так:

2 Bm := 2[x1, Е, xm]/(x1 + x1, Е, xm + xm).

Pages:     | 1 |   ...   | 14 | 15 | 16 | 17 | 18 |   ...   | 54 |    Книги по разным темам