Уловка Гёделя
Существует целое семейство анекдотов о пассажирах в купе поезда — иногда они бывают еще пациентами психиатрической больницы или заключенными в тюремной камере, — которые называют анекдоты по номерам. В одном из вариантов этой истории оказавшийся в такой группе новичок называет наугад случайный номер и остальные пассажиры набрасываются на него за то, что он рассказал непристойный анекдот. В другом варианте все они покатываются со смеху, потому что этого анекдота они раньше не слышали.
Блестящая идея Гёделя заключалась в присвоении номеров всем математическим утверждениям. Такая операция вряд ли покажется кому-нибудь особенно уморительной, но тем не менее она осуществима, а получив возможность называть утверждения по номерам, мы достигаем важного уровня математической формализации. Нумерация утверждений означает внесение их в некий упорядоченный перечень. Сначала отметим, что любое математическое утверждение может быть выражено в виде формулы — например, в рамках системы «Принципов математики», которая упоминается в заголовке статьи Гёделя[33]. Поэтому мы можем начать с утверждений, состоящих всего из одного символа, а когда они закончатся (а они непременно закончатся, так как система должна содержать конечное количество символов), перейти к утверждениям, состоящим из двух символов, и так далее. Рано или поздно должно стать ясно, что любое возможное утверждение войдет в этот перечень и, следовательно, ему будет присвоен номер. Свой номер получит и теорема Пифагора, и утверждение «2 + 2 = 4», и теорема о разложении на множители разности двух квадратов: a2 — b2 = (a + b)(a — b). Разумеется, номера будут присвоены и всем ложным утверждениям, например утверждениям «2 > 3» и «2 + 2 = 5», а также неправильному разложению (a + b)(a + b) = a2 + b2.
Затем Гёдель прошел еще на шаг дальше и отдельно пронумеровал все верные доказательства. Точно так же, как это было сделано для утверждений, доказательство, которое устанавливает справедливость математического утверждения, может быть представлено в виде последовательности логических формул, подчиняющихся определенным правилам. Гёдель применил к ним тот же метод, который он использовал для формул: он начал с доказательств из одного символа, затем перешел к доказательствам двухсимвольным и так далее. В результате каждый возможный правильный вывод получил номер, обозначающий его положение в последовательности верно составленных доказательств. Поскольку доказательства расставлены в порядке возрастания длины, любое доказательство, каким бы длинным оно ни было, рано или поздно должно появиться в этом перечне.
Это несколько упрощенное описание того, что на самом деле сделал Гёдель. Исходя из некоторых формальных соображений, он использовал для нумерации формул и доказательств гораздо более сложную систему. Но то описание, которое я привел выше, отражает основную идею. Вся эта нумерация утверждений и доказательств преследовала одну-единственную цель: гарантировать существование в перечне Гёделя одного очень странного утверждения — впоследствии это утверждение получило в честь Гёделя название «утверждение G». Если перевести утверждение G с математического языка на человеческий, его можно сформулировать следующим образом: Не существует такого натурального числа х, что доказательство с номером x есть доказательство утверждения G. Другими словами: Перечень всех возможных доказательств не содержит доказательства того утверждения, которое вы сейчас читаете.
Мастерский ход Гёделя заключался в выражении этой странной, логически закольцованной формулы математически точным образом. Затем он доказал, что утверждение G не может быть доказано (то есть в его перечне доказательств нет доказательства G). Не может быть доказано и обратное ему утверждение (потому что, как мы увидим дальше, оно на самом деле ложно). Если бы утверждение G было одним из нумерованных анекдотов, которые рассказывают пассажиры поезда, пассажиры могли спорить до скончания времен, следует ли смеяться над анекдотом G или возмущаться, услышав его, потому что обосновать ту или другую точку зрения было бы невозможно.
Следует иметь в виду, что G — очевидно, «хороший» анекдот в том смысле, что это утверждение истинно: если бы оно не было истинным, то истинным должно было бы быть утверждение, опровергающее его. В этом случае существовало бы натуральное число х, такое, что доказательство с номером x доказывало бы утверждение G. Но поскольку само G утверждает, что такого числа не существует, это означало бы, что доказательство x доказывает собственное небытие. Значит, утверждение G должно быть истинным — но если это так, тогда возможно представить вот этот самый абзац в виде конечного набора математических символов и тем обеспечить его включение в перечень доказательств, а из этого следует, что утверждение G должно быть ложным. Так кто же бреет брадобрея?
33
Полное доказательство теоремы Гёделя см., например, в Hofstadter (1979), гл. 4–8; Nagel and Newman (1983).