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

Если P вообще не содержит переменных, то вопрос сводится к проверке какого-то соотношения между конкретными целыми числами.

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

Предположим теперь, что P имеет вид для всех x (Q), где в скобках стоит высказывание Q с одной свободной переменной x. Например, для всех x (0 + 1 + 2 + Е + x = x(x + 1)/2). Как мы уже говорили, абстрактный рецепт проверки истинности P состоит в подстановке вместо x всевозможных целых чисел и проверке получившихся в бесконечном количестве числовых соотношений. Разумеется, практически так поступить нельзя.

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

лесли P(0) и если для всех x (если P(x), то P(x + 1)), то () для всех x (P(x)).

Здесь P должно пробегать всевозможные высказывания языка с одной свободной переменной x.

Все высказывания () мы считаем истинными, обосновывая их с помощью обычного рассуждения в метаязыке.

Анализируя доказательство нашей формулы 1+Е + x = x(x +1)/или теоремы Евклида о бесконечности простых чисел, мы обнаруживаем, что его можно записать в виде текста в языке LAr. Этот текст представляет собой последовательность высказываний, каждое из которых либо принадлежит к числу некоторого выбранного заранее набора аксиом, либо получается из этих аксиом и установленных ранее истинных высказываний применением одного из выбранного набора правил вывода.

Любое высказывание () доставляет пример аксиомы Ц - в данном случае аксиомы индукции применительно к утверждению P.

Примеры правил вывода, сформулированные в метаязыке:

а) если выведены высказывания лесли P, то Q и P, то можно вывести высказывание Q;

б) если выведено высказывание для всех x (P(x)), то можно вывести высказывание P(n), где n Ц - любое целое неотрицательное число.

Аксиомы и правила вывода составляют дедуктивные средства языка.

Любое высказывание, которое можно вывести из аксиом, применяя правила вывода, называется выводимым (с помощью данных дедуктивных средств).

00 Ч I. М Важнейшее требование, предъявляемое к аксиомам, состоит в том, чтобы они были истинными высказываниями. Проверку этой истинности мы вообще не проводим внутри языка. Истинность аксиом может аргументироваться в метаязыке апелляцией к наглядной очевидности или другими рассуждениями.

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

Полнота. Анализируя математические тексты, можно выделить из них набор реально используемых аксиом и правил вывода. Это Ц - нетривиальная задача; четкое описание результатов такого анализа было одним из высших достижений математической логики первой трети XX века.

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

Есть все основания верить, что этот набор не может быть расширен: все типы рассуждений, которые люди готовы считать логичными безотносительно к их содержанию, синтезируются по конечному набору правил, которые все нам уже известны. Напротив, предпринимались многочисленные попытки сузить набор правил, например, запретить использование правила исключенного третьего к бесконечным совокупностям, в частности в арифметике. Здесь не место обсуждать эти попытки.

Кроме логических аксиом и правил вывода, в набор дедуктивных средств всякого языка, ориентированного на ту или иную область математики, входят специальные аксиомы. Они выражают те сведения об объектах теории, истинность которых мы постулируем, подкрепляя ее неформальными соображениями. В LAr к ним могут относиться обычные правила действия с целыми числами, коммутативность и ассоциативность умножения и сложения, дистрибутивность сложения относительно умножения, аксиомы индукции.

Дедуктивные средства языка могут быть определены также в некотором другом языке, скажем, в расширении данного языка. Например, факты арифметики могут доказываться, исходя из аксиом теории множеств.

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

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

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

По-видимому, такого рода надежды, более или менее явно сформулированные, питали такие умы, как Декарт, Лейбниц и в нашем веке Гильберт.

Мы уже говорили во введении, что эти надежды рухнули.

Принципы неполноты Теорема Гёделя. Полного финитно описываемого набора аксиом арифметики не существует.

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

Смысл теоремы Гёделя можно выразить иначе: для порождения всех истинных высказываний о целых числах нужно бесконечно много новых идей. Творческий характер математики выявляется при таком понимании с особой силой. Ограниченность возможностей чисто дедуктивных средств составляет другую сторону медали.

02 Ч I. М Принципы доказательства. Чтобы доказать теорему Гёделя, нужно на время отказаться от рассмотрения отдельных высказываний, и обратиться к исследованию свойств истинности и выводимости в целом.

С этой целью очень удобно перенумеровать все высказывания языка L целыми числами от 0 до и говорить затем просто об их номерах. На нашем неформальном уровне представим себе, что все высказывания расположены в словарном порядке и перенумерованы подряд всеми (или некоторыми) целыми числами. Единственное существенное свойство нумерации, которым мы будем пользоваться, состоит в том, чтобы по каждому целому числу можно было чисто механически установить, является ли оно номером высказывания и если да, то какого; а по каждому высказыванию чисто механически установить его номер. Словарный порядок этому условию, очевидно, удовлетворяет, если правила образования высказываний сформулированы настолько точно, чтобы задачу их порождения и синтаксического анализа можно было поручить компьютеру. (Для LAr это не вполне так, что и будет главной причиной нестрогости последующих рассуждений.) * Вот нумерация выражений в SAr, которой удобно пользоваться для доказательства теоремы Гёделя. Перенумеруем как-нибудь все символы алфавита SAr цифрами от 1 до 9, так, чтобы 1 получил номер 9. Чтобы получить номер конечной последовательности символов в SAr, заменим все эти символы соответствующими цифрами, прочтем результат как десятичную запись и увеличим его на единицу. * Фиксируем такую нумерацию высказываний языка; ее принято называть нумерацией Гёделя.

Обозначим теперь буквой T множество номеров истинных высказываний, а D Ц - множество номеров высказываний, выводимых из какой-нибудь финитно описываемой системы аксиом арифметики, или, более общо, выводимых с помощью данных дедуктивных средств. Предполагается, что D содержится в T; мы хотим доказать, что D строго меньше, чем T. Это следует из двух фундаментальных принципов:

а) множествоT невыразимо в языке LAr, если язык L достаточно богат;

б) множество D всегда выразимо в языке LAr.

Поясним способы их доказательства.

Невыразимость истинности. Это Ц - теорема Тарского ( 936), являющаяся вариантом одного промежуточного результата в первоначальном рассуждении Гёделя.

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

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

Действительно, высказывание QP определено и потому должно быть либо истинным, либо ложным.

Если оно истинно, то истинно утверждение номер QP не обладает свойством, выраженным P, т. е. номер QP не принадлежит T, т. е.

QP не истинно Ц - противоречие.

Если же QP ложно, то ложно утверждение номер QP не обладают свойством, выраженным P, т. е. номер QP этим свойством обладает, тогда он лежит в T, и значит QP истинно Ц - снова противоречие! Значит, T не выразимо никакой из формул P и невыразимо вообще. Итак, вот содержательное разрешение старинного парадокса жеца: истинность высказываний в языке средствами этого языка невыразима. (Поэты подозревали это давно.) Читатель может заметить, что мы ведь как-то описали множество T. Верно, но мы сделали это в метаязыке, а не в языке-объекте L.

Если мы включим в язык-объект формализованный фрагмент метаязыка, необходимый для выражения T, множество высказываний в новом языке L увеличится, увеличится и множество истинных высказываний T, и хотя часть его T окажется выразимой, все T опять ускользнут от выражения.

* Опишем, как строится по P высказывание QP в языке Шмульяна SAr. Математик, знакомый с первоначальной трудной конструкцией Гёделя (или другого языка), оценит изящество и простоту идеи Шмульяна.

Пусть P(x) Ц - формула в языке SAr с одной свободной переменной x. Рассмотрим сначала формулу PE(x) : P((x) ((10) (x))), где 10 = 1Е1 ( 0 раз). Иными словами, PE(x) получается подстановкой в P(x) терма x10x вместо всех свободных вхождений x в P.

Пусть теперь Q Ц - любая конечная последовательность символов языка SAr, n(Q) Ц - ее номер, по Шмульяну (см. выше). Будем говорить, что номер Q удовлетворяет P(x), если после подстановки его вместо всех свободных вхождений x в P получится истинная формула.

Нетрудно проверить следующий факт:

04 Ч I. М Лемма. Номер Q удовлетворяет PE(x), если и только если номер Q1Е1 (1 повторена n(Q) раз) удовлетворяет P(x).

Действительно, из определения n(Q) легко следует, что n(Q1Е1) = = n(Q) 10n(Q) (здесь используется то обстоятельство, что n(1) = 9).

Рассмотрим теперь формулу S в SAr: x(PE)1Е1 (1 повторена n(x(PE)) раз). Выразим ее смысл в метаязыке, учтя, что x(PE) Ц - клас совый терм, а 1 1 Ц - имя числа n(x(PE)). Поэтому имеем:

S истинна номер x(PE) удовлетворяет PE номер x(PE)1Е(n(x(PE)) раз), т. е. S, удовлетворяет P.

Первая эквивалентность здесь следует из описания семантики SAr (см. пункт о классовых термах и формулах старших рангов), а вторая Ц - из доказанной выше леммы.

Неформально это означает, что формула S говорит: мой номер удовлетворяет P. Чтобы построить QP, остается применить аналогичную конструкцию к не P, т. е. к (P) (P) вместо P. * Выразимость выводимости. Обсудим теперь вопрос, почему множество номеров выводимых формул D выразимо в языке LAr или SAr.

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

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

Предположение о возможности написать такую программу по отношению к данному конкретному выбору дедуктивных средств может быть оправдано непосредственно. (Такие программы или их фрагменты реально были составлены для некоторых простых языков геометрии и логики.) Т Г Рассмотрим теперь множество пар целых чисел E: по определению (n, m) входит в это множество, если m есть номер высказывания, истинность которого устанавливается n-м по порядку выводом, порожденным нашей программой.

Множество пар целых чисел E выразимо в языках LAr, SAr просто потому, что машинная логика и арифметика целиком включены в дедуктивные средства этих языков. Пусть высказывание (x, y) выражает E. Тогда высказывание в LAr существует x ((x, y)) (с одной свободной переменной y) или эквивалентная ему формула SAr, выражает D. Действительно, оно истинно в точности для тех значений n переменной y, для которых можно найти значение m переменной x со свойством: n есть номер высказывания, истинность которого установлена m-м выводом. Так как программа порождает все выводы, наше утверждение оправдано.

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