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

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

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

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

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

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

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