Владимир Успенский – Апология математики (сборник статей) (страница 73)

3) (х′ = у′) ⇒ (х = y) [Ax. I];

4) (0′′′ = 0′) ⇒ (0′′ = 0) [3; C: x → 0′′, y → 0];

5) ¬ (0'' = 0) ⇒ ¬ (0''' = 0') [4; ⇒ ¬];

6) (0'''' = 0'') ⇒ (0''' = 0') [3; С: х → 0''', у → 0'];

7) ¬ (0''' = 0') ⇒ ¬ (0'''' = 0'') [6; ⇒ ¬];

8) ¬ (0''' = 0') [5, 2; MP];

9) ¬ (0'''' = 0'') [7, 8; MP].

Остаётся заметить, что последним в списке стоит интересующее нас предложение ¬ (0′′′′ = 0′′).

Если мы теперь запишем все эти 9 предложений друг за другом, разделив их каким-нибудь знаком (для определённости – решёткой #), получим то, что называется формальным доказательством предложения ¬ (0'''' = 0''):

¬ ∃ x (x' = 0) # ¬ (0'' = 0) # (x' = у') ⇒ (х = у) # (0''' = 0') ⇒ (0'' = 0) # ¬ (0'' = 0) ⇒ ¬ (0''' = 0') # (0'''' = 0'') ⇒ (0''' = 0') # ¬ (0''' = 0') ⇒ ¬ (0'''' = 0'') # ¬ (0''' = 0') # ¬ (0'''' = 0'').

На этом примере состоялось знакомство с важнейшим понятием формального доказательства. Неформальные доказательства (которые называют ещё содержательными или психологическими) представляют собою убедительные рассуждения, т. е. прежде всего тексты, состоящие из утверждений (не любые такие тексты, разумеется). Формальное же доказательство есть цепочка предложений, особым образом организованная. Читатель может возразить, что в начальном разделе статьи сообщалось, что формальное доказательство есть цепочка символов. Тут нет противоречия: ведь каждое предложение есть цепочка символов, и если составить их вместе, разделив каким-либо разделительным знаком, то снова возникнет не что иное, как цепочка символов, как это и видно из нашего примера. Таким образом, формальное доказательство есть слово, которое составлено из букв дополненного разделительным знаком алфавита.

Общее определение формального доказательства очевидно. Формальное доказательство есть такая цепочка предложений, каждое предложение которой либо является аксиомой, либо получено из каких-то предшествующих предложений цепочки применением одного из правил вывода.

Возьмём любое формальное доказательство, а в нём – какое-либо его подслово (т. е. часть слова, образованную подряд идущими буквами слова), не содержащее знака решётки и представляющее собой такую часть слова, которая ограничена решётками слева и справа, либо же начало слова, ограниченное решёткой справа, либо же конец слова, ограниченный решёткой слева, либо всё слово. Всякое такое подслово является доказуемым предложением. Если это предложение представляет собою конец формального доказательства, то это формальное доказательство называется формальным доказательством данного предложения. Ясно, что предложение тогда, и только тогда, является доказуемым, когда оно имеет формальное доказательство.

§ 13. Теорема Гёделя

Словосочетание «теорема Гёделя» довольно популярно, и не только в математической среде. И это совершенно заслуженно. Ведь теорема Гёделя (точнее, теорема Гёделя о неполноте) не только одна из самых замечательных и неожиданных теорем математической логики, да и всей математики, но и, пожалуй, единственная на сегодняшний день теорема теории познания.

Говоря совсем грубо, теорема Гёделя утверждает, что не всё можно доказать, говоря чуть более точно – что существуют истинные утверждения, которые нельзя доказать, а подробнее – что такие утверждения найдутся даже среди утверждений о натуральных числах. Но эта формулировка заключает в себе некое противоречие. В самом деле, если мы обнаружили истинное утверждение, которое невозможно доказать, то откуда, спрашивается, мы знаем, что оно истинное? Ведь, чтобы убеждённо заявлять о его истинности, мы должны эту истинность доказать. Но тогда как же можно говорить о его недоказуемости?

Разгадка в том, что в грубых, подобно приведённым, формулировках теоремы Гёделя смешиваются два понятия доказательства – содержательное (неформальное, психологическое) и формальное. Теорему Гёделя надлежит понимать в следующем смысле: существуют не имеющие формального доказательства утверждения, являющиеся тем не менее истинными, причём истинность их подтверждается содержательными доказательствами. Иными словами, эти утверждения доказуемы содержательно и недоказуемы формально. Отметим, что в применении к какому бы то ни было утверждению более корректно было бы говорить о формальных доказательствах не самого этого утверждения, а предложения, служащего записью этого утверждения в виде слова, составленного из букв подходящего алфавита. Однако мы этого делать не будем, чтобы не утяжелять изложения.

Указанный смысл нуждается в дальнейшем уточнении. Ведь понятие формального доказательства осмысленно лишь тогда, когда предъявлены аксиомы и правила вывода. Достаточно взять любое утверждение и включить его в число аксиом – и оно тут же сделается доказуемым формально. Чтобы не осложнять изложение, ограничимся ситуациями, при которых ни одно утверждение, не являющееся истинным, не может оказаться доказуемым (для этого достаточно, чтобы аксиомы выражали истинные утверждения, а правила вывода сохраняли истинность). Тогда точная, хотя и требующая разъяснений, формулировка теоремы Гёделя такова: если язык достаточно богат, то какой бы список аксиом и какой бы список правил вывода ни были предъявлены, в этом языке найдётся истинное утверждение о натуральных числах, не имеющее формального доказательства.

Жанр очерка не позволяет дать предложенной «точной» формулировке исчерпывающих объяснений. Но некоторые намётки всё же сделаем.

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

Под достаточным богатством языка понимается его способность выражать некоторые утверждения о натуральных числах. Чтобы было понятно, чтó имеется в виду, заметим, что тот язык, на примере которого выше демонстрировался формальный аксиоматический метод, является «бедным»: в нём можно выразить лишь очень простые утверждения о натуральных числах, а именно такие утверждения, которые можно сформулировать, используя лишь обозначения чисел (т. е. нумералы), переменные x и y, операцию «'» и общелогические понятия «равно», «существует», «неверно, что», «если… то»). Богатство же языка означает его способность выражать более сложные утверждения о числах: требуется, чтобы для любого перечислимого множества натуральных чисел в языке имелась формула, выражающая принадлежность к этому множеству натурального числа. Дальнейшие объяснения потребовали бы изложения основ математической логики и теории алгоритмов, а потому здесь мы остановимся.

Семь размышлений на темы философии математики

1. Действительно ли в математике всё определяется и доказывается?

Математики, как правило, очень гордятся тем, что они математики. Источник гордости они видят в своей науке: причём не столько в той пользе, которую приносит математика, сколько в том, что это такая уникальная, ни на какую другую не похожая область знаний. И с этой исключительностью согласны и нематематики (так что величие математиков, к удовольствию этих последних, осознаётся не только ими самими, но и окружающими). В самом деле, считается общепризнанным, что математика имеет по крайней мере три присущие только ей черты. Во-первых, в математике, в отличие от других наук, все понятия строго определяются. Во-вторых, в математике – опять-таки в отличие от других наук – всё строго доказывается из аксиом. В-третьих, математика непонятна в такой вызывающей уважительный трепет степени, какая недоступна ни одной другой науке. Непонятна даже в школе (репетиторов по математике едва ли не больше, чем по всем другим школьным предметам, вместе взятым). А уж о современной математической науке и говорить нечего: достаточно раскрыть любую монографию, а тем более журнальную статью. (Заметим, что третья из перечисленных черт вступает в известное противоречие с первыми двумя, хотя над этим мало кто задумывается.)

Когда что-то общеизвестно, закрадывается подозрение, не миф ли это (ведь общественное мнение обладает автономным механизмом самоподдержания). Постараемся непредвзятым, по возможности, образом критически рассмотреть три только что названные общеизвестные черты математики.

Тогда, во-первых, обнаружим, что определить все математические понятия невозможно. Одно определяется через другое, другое – через третье и т. д.; где-то мы должны остановиться. («Портной учился у другого, другой у третьего, да первоет портной у кого же учился?» – справедливо замечает г-жа Простакова.) Рассказывают, что известный одесский математик С. И. Шатуновский, приводя определение всё новых и новых понятий в ответ на повторные вопросы «А что такое то-то и то-то?», наконец не выдерживал и сам спрашивал: «А что такое "что такое"?»

Давайте задумаемся о принципах толкования слов в словаре какого-либо языка – русского, английского и т. д. В нём одни слова определяются через другие, другие – через третьи и т. п. Но поскольку слов в языке конечное число, то неизбежно возникает круг (т. е. ситуация, в которой слово определяется в конечном счёте через само себя)[143]. Избежать такого круга можно лишь одним способом: оставить некоторые слова без объяснений. В некоторых словарях так и делают[144]. Так же, разумеется, обстоит дело и с понятиями математики. А именно: если только не допускать порочного круга, некоторые понятия должны остаться без определения. Спрашивается, как же могут быть усвоены эти понятия. Ответ: из непосредственного наблюдения, из опыта, из интуиции. Нет нужды напоминать, что формирование общих, абстрактных понятий в мозгу человека – сложный процесс, принадлежащий более психологии, нежели логике. Эти понятия, усваиваемые не из словесного определения, а из непосредственного личного опыта, естественно называть первичными понятиями, или категориями, математики. К числу таких категорий относятся, например, понятия точки, прямой, множества, натурального числа.