Эрнест Нагель, Джеймс Рой Ньюмен. Теорема Гёделя


Идея кодирования и ее использование в математике



Скачать 72.03 Kb.
страница6/7
Дата30.07.2018
Размер72.03 Kb.
ТипКнига
1   2   3   4   5   6   7
Идея кодирования и ее использование в математике

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

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

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

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

Исходя из такого упорядочения можно теперь расположить все определения рассматриваемого вида в последовательность, сопоставив каждому из них единственное натуральное число — номер в этой же последовательности. Тогда самое короткое (и стоящее ранее других в алфавитном порядке) определение получит номер 1, следующее за ним в этом «словаре определений» — номер 2 и т.д.

Поскольку каждому определению теперь сопоставлено некоторое натуральное число, то может оказаться, что в некоторых случаях число, сопоставленное какому-нибудь определению, само будет обладать определяемым свойством. Ситуация здесь в точности такова же, как в том случае, когда все слова в обычном орфографическом словаре делятся на два класса: односложные и многосложные; при этом слово «многосложное» само оказывается многосложным.

Пусть, например, определяющее выражение «не делиться ни на одно натуральное число, кроме самого себя и числа 1» оказалось в нашей последовательности на 17-м месте; ясно, что сопоставленное ему число 17 само подпадает под это определение. Пусть, с другой стороны, определяющее выражение «быть произведением некоторого натурального числа на то же самое число» получило номер 15; само число 15, очевидно, не является точным квадратом и потому данным свойством не обладает. Назовем числа, не обладающие свойствами, определяемыми предложениями, которым они соответствуют в описанной нами нумерации, ришаровыми. Таким образом, «ж — ришарово число» — это просто сокращение выражения «ж не обладает свойством, определяемым предложением, имеющим номер ж в данной словарной последовательности определяющих предложений». (Скажем, число 17 из нашего первого примера не является ришаровым, а число 15 из второго примера — ришарово.)

Теперь мы уже можем сформулировать парадокс Ришара. Определяющее выражение для свойства быть ришаровым числом описывает, очевидно, некоторое арифметическое свойство натуральных чисел. Значит, само определяющее выражение входит в описанную выше последовательность определяющих выражений. Но тогда оно имеет в этой последовательности некоторый номер, который мы обозначим через N. Зададим теперь вполне естественный вопрос (немедленно приводящий к антиномии Ришара): является ли число N ришаровым? Читатель, конечно, сразу увидит, что противоречие теперь неизбежно. В самом деле, число N является ришаровым в том и только в том случае, если оно не обладает свойством, описываемым предложением, имеющим номер N, т.е. не обладает свойством быть ришаровым! Короче говоря, N ришарово тогда и только тогда, когда оно не ришарово, т. е. утверждение «N — ришарово число» является одновременно истинным и ложным.

Использование идеи кодирования лежит в основе знаменитой работы Гёделя. Следуя схеме рассуждения, очень близкой к той, что проводится в парадоксе Ришара (но усовершенствуя ее при этом таким образом, что она становится неуязвимой по отношению к сформулированным выше критическим заключениям), Гёдель показывает, что метаматематические высказывания об арифметическом формализованном исчислении можно представить посредством некоторых арифметических формул внутри исчисления. Ему удалось найти такой метод арифметического кодирования метаматематических высказываний, что для некоторой формулы, выражающей истинное метаматематическое утверждение о формулах арифметики, ни она сама, ни ее отрицание не доказуемы в формальной арифметике. Поскольку одна из этих формул, выражающая истинное арифметическое высказывание, не выводима из арифметических аксиом, то аксиомы образуют неполную систему. Предложенный Гёделем метод кодирования позволил ему также построить арифметическую формулу, соответствующую метаматематическому высказыванию «арифметическое исчисление непротиворечиво», и показать, что эта формула недоказуема в (этом же!) арифметическом исчислении. Отсюда следует, что упомянутое метаматематическое высказывание не может быть установлено без привлечения некоторых дополнительных дедуктивных средств, не представимых (т. е. не кодируемых, не переводимых) в самом арифметическом исчислении, так что если это высказывание и можно доказать, то уж заведомо с привлечением средств, непротиворечивость которых не менее сомнительна, нежели сама по себе непротиворечивость арифметики. Все важнейшие выводы были получены Гёделем с использованием придуманной им чрезвычайно остроумной системы числового кодирования, или нумерации.




Каталог: wp-content -> uploads -> 2015
2015 -> Социальная философия
2015 -> Курсовая работа на тему: Наши эмоции друзья или враги? Их роль в конфликтоной ситуации
2015 -> Медиалогия как интегрированная наука информационной эпохи и ее роль в модернизации России Ключевые слова
2015 -> -
2015 -> Вопросы для подготовки к вступительному экзамену в аспирантуру по «Философии»
2015 -> Никколо Макиавелли
2015 -> Астрономия и современная картина мира
2015 -> Методы социологического исследования


Поделитесь с Вашими друзьями:
1   2   3   4   5   6   7


База данных защищена авторским правом ©znate.ru 2019
обратиться к администрации

    Главная страница