Gustavo Pineiro - У интуиции есть своя логика. Гёдель. Теоремы о неполноте.
Эти логические правила находятся вне арифметики, они справедливы для любой области математики, поэтому выражающие их высказывания называются универсально справедливыми высказываниями (или логическими аксиомами, поскольку они выражают правила логических рассуждений).
Мы уже упомянули одно из этих правил. Другие примеры: «если х = у, то у = х» и «если два числовых выражения равны, то любое из них может быть заменено на другое». Именно это — последнее — правило оправдывает переход от шага 2 к шагу 3, где S(1) заменяется на 2.
Схема механической проверки доказательства.
Но когда существует потенциально бесконечное число универсально справедливых высказываний, как мы можем загрузить их все в память компьютера? Если это нельзя сделать, то компьютер неспособен проверить справедливость любого рассуждения, и, следовательно, программа Гильберта оказывается неосуществимой. При этом ни один компьютер не способен содержать бесконечное число высказываний.
ФОРМАЛЬНЫЙ ЯЗЫК
Как программа Гильберта, так и доказательство Гёделя предполагают, что все арифметические высказывания написаны на формальном языке с помощью заранее установленных символов. Существуют возможные варианты символов, один из наборов которых следующий.
Квантор всеобщности , читается «для каждого». Указывает, что обозначаемое свойство справедливо для любого числа.
=>: Символ импликации; «Р => Q» означает «если Р, то Q».
┐:Символ отрицания;"┐ Р" означает "не-Р".
=: Знак равенства.
1: Число один.
S: Означает "последующий элемент".
+; Символ суммы.
(·): Символ произведения.
(): Скобки.
х₁ х₂, х₃,...: Переменные.
В некоторых представлениях предпочитается брать в качестве первого элемента 0, но это не является существенным. При использовании символов, которые мы привели, число 2 записывается как S(1), то есть следующий за 1. Число 3 записывается как S[S(1)], то есть следующий за следующим за 1. И так далее.
К счастью, в теореме о полноте Гёдель доказал, что хотя количество логических правил потенциально бесконечно, любое рассуждение можно осуществить, используя только 12 из них. Если загрузить в память компьютера эти 12 правил, он будет способен проверить правильность любого доказательства.
Когда в начале 1930 года эта теорема была опубликована, казалось, что необходимая логическая основа для программы Гильберта обеспечена: можно механически проверить правильность арифметических доказательств. Проблема, которую оставалось решить, состояла в том, чтобы найти множество аксиом, которое (на основе этих 12 правил) позволило бы доказать все арифметические истины.
Теорема о полноте не произвела на математический мир большого эффекта. Считалось, что Гёдель просто подробно описал доказательство того, что все и так считали верным, — такой большой была вера в успешную реализацию программы Гильберта. Оставалась только проблема нахождения аксиом арифметики.
ТЕОРЕМА О НЕПОЛНОТЕ
Когда была установлена логическая база, дававшая возможность осуществлять доказательства, проверяемые алгоритмически, оставалось только найти аксиомы, которые позволили бы доказать все арифметические истины. К несчастью для программы Гильберта, эта цель недостижима. Теорема, в которой изложена эта невозможность, известна как первая теорема Гёделя о неполноте, или просто теорема Гёделя:
"Если выбрать в качестве аксиом любое множество истинных арифметических высказываний и требовать, чтобы доказательства, которые можно сделать на их основе, могли быть проверены алгоритмически, то будет по крайней мере одно истинное высказывание, которое не может быть доказано на основе этих аксиом".
Гёдель доказал эту теорему в 1930 году и, как мы уже знаем, впервые открыто изложил ее на конгрессе в Кёнигсберге 7 сентября того же года. Статья с выведением доказательства была послана в журнал Monatshefte für Mathematik und Physik ("Ежемесячник по математике и физике") в ноябре и появилась в томе 38 (1931). Значение этой публикации для логики сравнимо только с "Метафизикой" Аристотеля. Изложение доказательства было таким ясным и прозрачным, что не вызвало ни малейшей полемики.
12 ЛОГИЧЕСКИХ ПРАВИЛ
В своей докторской диссертации, представленной в 1930 году, Гёдель доказал, что любое рассуждение, которое можно проверить алгоритмически, может быть построено всего на 12 логических правилах, которые мы приводим ниже. Далее выражение "Р => Q" означает "если Р, то Q", а " x Р(х)" — "каждое х выполняет свойство Р".
1. Если справедливо высказывание Q, то, каким бы ни было Р, справедливо высказывание "Р => Q".
2. Если справедливо "Р => (Q => R)" и также справедливо "Р => Q", то справедливо "Р=> R".
3. Если справедливо "не-Q => не-Р", то также справедливо "Р => О".
4. Если справедливо" x P(x)", то справедливо "Р(n)", где n — любое число.
5. Если справедливо " x Р => Q(x)", то справедливо "Р => [ x Q(x)]", если только х не используется в Р.
6. Каким бы ни было число х, справедливо, что х = х.
7. Какими бы ни были числа х и у, справедливо, что если х = у, то у = х.
8. Какими бы ни были числа х, у, z, справедливо, что если х = у и у = z, то х = z.
9. Если х = у, то можно заменить х на у в любом числовом выражении.
10. Если х = у, то можно заменить х на у в любом высказывании.
11. Если справедливо Р и справедливо "Р => Q", то справедливо Q.
12. Если справедливо Р(х) для произвольного х, то справедливо" x P(х)".
В целом первые десять правил представлены как универсально справедливые высказывания, в то время как два последних представлены отдельно как правила вывода. Это разграничение чисто техническое и не имеет значения для наших целей.
Но как можно доказать факт такого масштаба? Как можно доказать, что каким бы ни было множество выбранных аксиом (если рассуждения проверяются алгоритмически), то всегда найдется истина, недоказуемая на их основе? Сейчас мы перейдем к объяснению доказательства и для этого рассмотрим, шаг за шагом, основные моменты рассуждений Гёделя.
Ханс Хан, руководитель докторской диссертации Гёделя. Этот австрийский философ и математик внес значительный вклад в формирование Венского кружка.
Немецкий математик Филипп Фуртвенглер, преподаватель Гёделя в Венском университете.
Курт Гёдель в 1935 году, через пять лет после защиты докторской диссертации в Венском университете.
ОБЩАЯ ИДЕЯ ДОКАЗАТЕЛЬСТВА
Предположим, что в качестве аксиом были выбраны некоторые истинные арифметические высказывания. Для начала заметим: тот факт, что аксиомы — это истинные утверждения, гарантирует истинность всех высказываний, которые можно будет доказать на их основе, поскольку из истинных предпосылок (при правильных методах рассуждения) можно сделать только истинные выводы. Это гарантирует, что ни одно доказываемое высказывание не будет ложным, однако это ни в коем случае не означает, что все истины доказуемы. Действительно, наша цель — доказать, что существует истинное арифметическое высказывание, которое не может быть доказано на основе этих аксиом (если мы будем придерживаться методов доказательства программы Гильберта).
Главная идея доказательства состоит в том, чтобы получить высказывание G, в котором будет говориться: "G недоказуемо". Другими словами, G может быть записано так: "Это утверждение недоказуемо".
Высказывание G самореферентно и говорит о самом себе, что оно недоказуемо (в дальнейшем слово "доказуемый" всегда должно пониматься как "доказуемый на основе предложенных аксиом"). Докажем, что это высказывание G является недоказуемой истиной.
Для начала заметим, что G либо истинно, либо ложно. Если бы G было ложно, в связи с тем, что в G говорится о самом себе, можно было бы сделать вывод, что G доказуемо. Следовательно, G было бы одновременно ложным и доказуемым, но это невозможно (ведь мы сказали, что исходя из истинных аксиом можно доказать только истинные высказывания). Следовательно, G не может быть ложным.
