23.162. Логика и теорема Гёделя

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

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

Самой тщательной попыткой реализовать эту возможность был грандиозный труд Principia Mathematica Уайтхеда и Рассела (1910). В Principia использовались аксиомы теории множеств, наряду с небольшой совокупностью правил умозаключений, чтобы вывести существенную часть обычной математики на полностью формальном языке. Цель формального языка — избежать неопределенности и двусмысленности естественного языка, с тем чтобы доказательства можно было проверить механически. Механическая проверка доказательства тогда считалась не целью в себе, а скорее гарантией строгости. Когда Уайтсхед и Рассел начали писать свои Principia в 1900 г., они считали, что уже почти достигли цели девятнадцатого века, полной и абсолютно строгой математической системы. Они не осознавали, что строгость их системы, возможность проверки доказательств механически, фактически, была несовместима с полнотой. Гёдель (1931) показал, что есть истинные предложения, которые можно выразить на языке Principia Mathematica, но они не следуют из их аксиом. (Если Principia не противоречивы, в этом случае все предложения следуют из их аксиом. Допущение о противоречивости действительное веское, как мы увидим к концу этого раздела.)

Теорема Гёделя, когда она впервые появилась, произвела сенсацию. Она не только разрушила предшествующие концепции математики и логики, но ее доказательство было нового и смущающего рода. Гёдель использовал механическую природу доказательства в Principia, чтобы определить зависимость предложение Principia доказуемо» на языке самих Principia. Используя это, он смог придумать предложение, которое, в сущности, говорит «Это предложение не доказуемо». Предложение Гёделя, если оно истинно, поэтому не доказуемо. И если оно ложно, то доказуемо, и поэтому Principia доказывают ложное

предложение. И так, и этак, доказуемость в Principia не то же самое, что истина.

Современникам было очень трудно понять доказательство Гёделя. С новизной трактовки символов и предложений как математических объектов соединились почти противоречивость предложения, которое выражает свою собственную недоказуемость (предложение, которое говорит «Это предложение не истинно» есть противоречие). Пост (1944) представил теорему Гёделя менее парадоксальным способом, выведя ее из классической диагональной аргументации. Ключ к подходу Поста — понятие рекурсивно перечислимого множества. Множество называется рекурсивно перечислимым, если список его членов можно вычислить, скажем, с помощью машины Тьюринга, которая напечатает их на ленте. (Конечно, если бесконечно, вычисление продолжится вечно.) Парадигма рекурсивно перечислимого множества — множество теорем формальной системы, такой как Principia Mathematica. Для такой системы можно вычислить список всех предложений, список всех конечных последовательностей предложений и, выбрав те предложения, которые являются доказательствами, список всех теорем, поскольку теорема — это просто последняя строка доказательства.

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

Эта «доказуемая часть» рекурсивно перечислима, потому что мы можем составить список теорем и выбрать теоремы вида предполагая, что X доказывает только верные предложения, но поскольку рекурсивно перечислимое множество, нет. Это сразу показывает, что в есть по, которого нет в то есть, по для которого «по не доказуемо.

Все же лучше, определенное по с этим свойством — это индекс рекурсивно перечислимого множества Если то по эквивалентно по которое означает, что доказуемо. Но тогда истинно, что по предполагая, что доказывает только верные предложения, и мы имеем противоречие. Поэтому по Это, в свою очередь, эквивалентно по которое означает, что не доказуемо. (Заметьте, между прочим, что последняя часть этого аргумента раскрывает, что «по предложение, которое выражает свою собственную недоказуемость.)

По-видимому, Пост знал об этом подходе к теореме Гёделя в 1920-х прежде чем появилось собственное доказательство Гёделя. Однако более общий взгляд Поста на неполноту как свойство произвольных рекурсивно перечислимых систем останавливал его, пока он не убедился, что вычислимость была математически определимым понятием. В декабре 1925 года Пост сформулировал план доказательства неполноты Principia Mathematica, но, как позже он писал: «План, однако, включал предыдущие упражнения на другой математической и логической работе, и не рассчитывал на появление Гёделя!» [Пост (1945), с. 418].

Теорема Гёделя возникает из размышления о природе доказательств в обычной математике. Еще более разительная теорема, известная как вторая теорема Гёделя, возникает из размышления о доказательстве самой теоремы Гёделя. Последнее доказательство, хотя и необычное, действительно, можно выразить на обыкновенном математическом языке.

Мы описали доказательство теоремы Гёделя Постом на неформальном языке машин Тьюринга, но, с некоторыми усилиями, его можно выразить на малом языке теории чисел, который называется арифметикой Пеано это язык сложения и умножения на с основной логической и математической индукцией в качестве механизма доказательства. Машины Тьюринга можно обсудить на интерпретируя последовательности символов на ленте как числительные, с тем чтобы изменения, которые они испытывают в процессе вычисления, стали операциями на числах. По этой интерпретации «по и «X не доказывает «по становятся предложениями

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

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

Эквивалентное предложение — просто

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

Теперь Гёдель заметил, что его доказательство можно выполнить на [Он не опубликовал детали, но довольно трудоемкая проверка была выполнена Гильбертом и Бернайсом Следовательно, если можно доказать на то «по тоже по основной логике. Но, если непротиворечива, «по нельзя доказать на ней, по теореме Гёделя, следовательно, тоже нельзя. [Гёдель, конечно, имел иное недоказуемое предложение, но его подобным же образом подразумевало и оно было эквивалентно своей собственной недоказуемости.].

Таким образом, утверждение что аксиомы непротиворечивы, в некотором отношении сильнее, чем сами аксиомы. Подобным же образом, если любая система, которая включает (такая как Principia Mathematica и другие системы теории множеств), то нельзя доказать в X, если X — непротиворечива. Это вторая теорема Гёделя.

Упражнения

(см. скан)