Не является ли абсурдным предполагать, что множество в действительности может быть членом самого себя? Ничуть. Рассмотрим, к примеру, множество I, состоящее из бесконечных множеств (множеств с бесконечным числом членов). С очевидностью, существует бесконечное число различных бесконечных множеств, и само множество I, таким образом, является бесконечным. И, таким образом, оно, действительно, принадлежит самому себе! Но как же, в таком случае, рассуждения Рассела дают нам парадоксальное утверждение? Давайте спросим: является ли множество Рассела R членом самого себя или нет? Если нет, то оно должно принадлежать себе, ибо R состоит как раз из таких множеств, которые не являются членами самих себя. То есть, в конечном счете, R принадлежит R - противоречие! С другой стороны, если R есть член самого себя, то, поскольку "самое себя" - это R, оно в то же время принадлежит множеству, члены которого, по определению, не могут быть составляющими самих себя, т. е. все-таки не принадлежит самому себе - и вновь противоречие!
Этот парадоксальный вывод не был праздной игрой ума: Рассел использовал - хотя и в крайней форме - тот же тип весьма общих теоретико-множественных методов, которые математики начинали использовать в то время для своих доказательств. Становилось очевидным, что казавшаяся незыблемой почва ускользает из-под ног, и поэтому необходимо было как можно точнее определить, какие рассуждения считать допустимыми. Ясно было, что такие рассуждения должны быть свободны от внутренних противоречий, и что утверждения, которые будут выводиться с их помощью как следствия из априори верных посылок, должны быть также верными. Рассел, совместно со своим коллегой Альфредом Нортом Уайтхедом, взялся за развитие такой полностью формализованной системы аксиом и правил вывода, на язык которой стало бы возможным перевести все виды корректных математических рассуждений. Все правила подвергались тщательному отбору, дабы избежать "ложных" путей рассуждений, могущих привести к парадоксам, подобным упомянутому выше. Однако схема, появившаяся на свет в результате этих усилий, была очень громоздка и оказалась весьма ограниченной по диапазону различных типов математических рассуждений, которые она охватывала. Великий математик Давид Гильберт (которого мы впервые встретили в главе 2) задался целью создать более практичную и универсальную систему. В нее должны были войти все типы математических рассуждений из всех областей математики. Более того, Гильберт стремился сделать возможным строгое доказательство отсутствия противоречий в своей схеме. Тогда математика раз и навсегда смогла бы встать на прочную и неколебимую основу.
Однако надежды Гильберта и его последователей были перечеркнуты, когда в 1931 году блестящий австрийский логик математики Курт Гедель выдвинул поразительную теорему, которая до основания разрушала программу Гильберта. Гедель показал, что любая подобная точная ("формальная") система аксиом и правил вывода, если только она достаточна широка, чтобы содержать в себе описания простых арифметических теорем (как, например, "последняя теорема Ферма", рассмотренная в главе 2), и если она свободна от противоречий - то такая система должна включать утверждения, которые не являются ни доказуемыми, ни недоказуемыми в рамках формализма данной системы. Истинность таких "неразрешимых" утверждений, следовательно, не может быть выяснена с помощью методов, допускаемых самой системой. Более того, Гедель смог показать, что даже утверждение о непротиворечивости системы аксиом, будучи переведенным в форму соответствующей теоремы, само по себе является "неразрешимым". Для нас будет очень важным понять природу этой неразрешимости. Тогда мы увидим, почему выводы Геделя опровергали самое основание программы Гильберта. Мы также увидим, каким образом они дают нам возможность, воспользовавшись интуицией, выходить за пределы любой рассматриваемой формализованной математической системы. Это понимание будет решающим для того, чтобы, в свою очередь, лучше понять обсуждаемое далее.
Формальные математические системы
Необходимо будет несколько уточнить, что мы понимаем под "формальными математическими системами аксиом и правил вывода". Мы должны предположить наличие некоторого алфавита символов, через которые будут записываться математические выражения. Эти символы в обязательном порядке должны быть адекватны для записи натуральных чисел с тем, чтобы в нашу систему могла быть включена "арифметика". По желанию, мы можем использовать общепринятую арабскую запись 0, 1, 2, 3…, 9, 10, 11, 12… хотя при этом конкретные выражения для правил вывода становятся несколько более сложными, чем требуется. Гораздо более простые выражения получаются, скажем, при использовании записи вида 0, 01, 011, 0111, 01111… для обозначения последовательности натуральных чисел (или, в качестве компромисса, мы могли бы использовать двоичную запись). Однако, поскольку это могло бы стать источником разночтений в дальнейших рассуждениях, я буду для простоты придерживаться обычной арабской записи независимо от способа обозначения, которая может на самом деле использоваться в данной системе. Нам мог бы понадобиться символ "пробел" для разделения различных "слов" или "чисел" в нашей системе, но, так как это тоже может вызвать путаницу, то мы будем по мере необходимости использовать для этих целей просто запятую (,). Произвольные ("переменные") натуральные числа (равно как и целые, рациональные и т. д.; но давайте здесь ограничимся натуральными) мы станем обозначать буквами, например, t, u, v, ω, х, у, z, t', t'', t''' и т. п. Штрихованные буквы t', t'',… вводятся нами в употребление, дабы не ограничивать число переменных, которые могут встретиться в произвольном выражении. Мы будем считать штрих (' ) отдельным символом формальной системы, так что действительное количество символов в системе остается конечным. Помимо этого нам также потребуются символы для базовых арифметических операций =, +, х ("умножить") и т. д.; для различных видов скобок (,), [,], и для обозначения логических операций, таких как & ("и"), => ("следует"), V ("или"), <=> ("тогда и только тогда"), ~ ("не"). Дополнительно нам будут нужны еще и логические "кванторы": квантор существования Eк.с.("существует… такое, что") и квантор общности Aк.о. ("для любого… выполняется"). Тогда мы сможем такие утверждения, как, например, "последняя теорема Ферма", привести к виду:
- Eк.с.ω, х, у, z [(x + 1)+
+ (у + 1) = (z+1)]
(см. главу 2, "Неразрешимость проблемы Гильберта"). (Я мог бы написать "0111" для "3", и, возможно, использовать для "возведения в степень" обозначение, более подходящее к рассматриваемому формализму; но, как уже говорилось, я буду придерживаться стандартной системы записи во избежании ненужной путаницы.) Это утверждение (если читать его до левой квадратной скобки) звучит как:
"Не существует таких натуральных чисел ω, х, у, z, что…".
Мы можем также переписать последнюю теорему Ферма при помощи Aк.о.:
Aк.о.ω, х, у, z [~ (х + 1)+ (у + 1) = (z+1)],
которое будет читаться следующим образом (заканчивая символом "не" после левой квадратной скобки):
"Для любых натуральных чисел ω, х, у, z не может быть выполнено…",
что логически эквивалентно написанному ранее.
Нам понадобятся еще и буквы, обозначающие целые утверждения, для чего я буду использовать заглавные буквы Р, Q, R, S… Таким утверждением может, к примеру, служить и вышеприведенная теорема Ферма:
F = ~ Eк.с.ω, х, у, z [(x + 1)+ (у + 1) = (z+1) ].
Утверждение может также зависеть от одной или более переменных; например, нас может интересовать формулировка теоремы Ферма для некоторого конкретного значения степени ω + 3
G(ω) =~ Eк.с.x, y,z[(x + 1)+ (y+ 1) = (z+1)],
так что G(0) утверждает, что "куб не может быть суммой кубов положительных чисел"; G(1) говорит о том же применительно к четвертым степеням и так далее. (Обратите внимание на отсутствие ω после символа Eк.с.). Тогда теорема Ферма гласит, что G(ω) выполняется для любого ω :
F = Aк.о.ω[G(ω)].
G() является примером так называемой функции исчисления высказываний, т. е. утверждением, которое зависит от одной или более переменных.
Аксиомы нашей системы будут представлять из себя перечень утверждений общего характера, чья справедливость в рамках принятого символизма предполагается самоочевидной. Например, для произвольных утверждений или функций исчисления высказыванийР, Q, R() мы могли бы указать среди прочих аксиом системы такие, как
(P&Q) => Р,
- (~ Р) <=> Р,
- Eк.с.х[R(x)] <=>Aк.о.x[~ R(x)],
"априорная истинность" которых уже заключена в их смысловых значениях. (Первое утверждение означает лишь, что "если выполняется Р и Q, то выполняется и Р"; второе устанавливает равносильность утверждений "неверно, что не выполняется Р" и "Р выполняется"; а третье может быть проиллюстрировано эквивалентностью двух способов формулировки теоремы Ферма, данных выше.) Мы можем также включить основные аксиомы арифметики:
Aк.о.х, у[х + у = у + х],
Aк.о.х, у, z[(x + у) х z = (x х z) + (у х z)],
хотя некоторые предпочитают определять арифметические операции через более простые понятия и выводить вышеуказанные утверждения как теоремы. Правила вывода могут вводиться в виде (самоочевидных) процедур типа
"Из Р и Р => Q следует Q".
"Из Aк.о.x[R(x)] мы можем вывести любое утверждение, получающееся путем подстановки конкретного натурального числа x в R(x)".
Такие правила являются инструкциями, следуя которым, можно с помощью утверждений, чья истинность уже доказана, получать новые утверждения.
Теперь, отталкиваясь от системы аксиом и раз за разом применяя правила вывода, мы имеем возможность построить достаточно длинные цепочки новых утверждений. На любой стадии этого процесса мы можем использовать снова и снова любую из аксиом, а также обратиться к любому из уже выведенных нами производных утверждений. Каждое утверждение из корректно выстроенной цепочки называется теоремой (несмотря на то, что многие из них достаточно тривиальны и неинтересны с точки зрения математики). Если у нас есть некое утверждение Р, которое мы хотим доказать, то мы должны подобрать такую цепочку, выстроенную в согласии с действующими правилами вывода, которая заканчивается утверждением Р. Такая цепочка предоставит нам доказательство Р в рамках системы; а Р тогда будет являться, соответственно, теоремой.
Идея программы Гильберта состояла в том, чтобы найти применительно к любой отдельно взятой области математики набор аксиом и правил вывода, который был бы достаточно полным для всех возможных в данной области корректных математических рассуждений. Пусть такой областью будет арифметика (с добавленными кванторами Eк.с. и Aк.о., позволяющими формулировать утверждения, подобные последней теореме Ферма). То, что мы не рассматриваем более общую область математики, не умаляет нашу задачу: арифметика и сама по себе обладает общностью, достаточной для применения процедуры Геделя. Если мы допустим, что благодаря программе Гильберта мы действительно располагаем такой всеобъемлющей системой аксиом и правил вывода для арифметики, то мы тем самым обретаем и определенный критерий для выявления "корректности" математического доказательства любого утверждения в области арифметики. Возлагались надежды на то, что подобная система аксиом и правил может быть полной в смысле предоставляемой нам принципиальной возможности решать, истинно или ложно произвольное утверждение, сформулированное в рамках этой системы.
Гильберт рассчитывал, что для любой строки символов, представляющих математическое утверждение, скажем, Р, можно будет доказать либо Р, либо ~ Р, если Р истинно или ложно, соответственно. Здесь мы в обязательном порядке оговариваем, что строка должна быть синтаксически корректна, где "синтаксически корректна" по сути означает "грамматически корректна" - то есть удовлетворяет всем правилам записи, принятым в данном формализме, среди которых будет правильное попарное соответствие скобок и т. п. - так чтобы Р всегда имело четко определенное значение "ложь" или "истина". Если бы надежды Гильберта оправдались, то можно было бы вообще не задумываться о том, что означает то или иное утверждение! Р было бы просто-напросто синтаксически корректной строкой символов. Строке было бы приписано значение ИСТИНА, если бы Р являлось теоремой (другими словами, если бы Р было доказуемо в рамках системы); или же ЛОЖЬ, если бы теоремой было ~ Р. Чтобы такой подход имел смысл, мы должны дополнительно к условию полноты наложить еще и условие непротиворечивости, гарантирующее отсутствие такой строки символов Р, для которой как Р, так и ~ Р были бы теоремами. Ведь в противном случае Р могло бы быть одновременно и ИСТИНОЙ, и ЛОЖЬЮ!