Это означает, что не существует доказательства G; следовательно, ни одно число не является кодом доказательства G: число 1 — не код доказательства G, так же как 2,3 и так далее.
Получается, что высказывания
"1 — не код доказательства высказывания с кодом m",
"2 — не код доказательства высказывания с кодом m", "k — не под доказательства высказывания с кодом т" и так далее являются финитными истинными высказываниями. Раз они финитные и истинные, они доказуемы. Следовательно,
"существует у, являющееся кодом доказательства высказывания с кодом m" недоказуемо. Но это высказывание — не-G, следовательно, не-G не будет доказуемым; однако это противоречит предположению того, что не-G доказуемо. От противного получили, что не-G в итоге недоказуемо (см. схему).
Итак, синтаксически доказано, что как G, так и не-G, ни одно из двух, недоказуемо. Таким образом, доказательство первой теоремы о неполноте может быть полностью переведено в синтаксические аргументы и понятия, как этого требует программа Гильберта. Этот способ представления доказательства, основанный исключительно на синтаксических аргументах, проверяемых механически, спас от любых споров.
В программе Гильберта требовалось, как мы уже сказали, найти непротиворечивое множество аксиом арифметики таким образом, чтобы каждое высказывание Р (либо его отрицание) было доказуемым. Но также требовалось, чтобы непротиворечивость этих аксиом проверялась алгоритмически, — это придавало уверенности, что аксиомы не приведут к парадоксу. В своей статье 1931 года Гёдель доказал вторую теорему, так называемую вторую теорему о неполноте. В ней доказывается, что эта цель также неосуществима.
Эта теорема часто формулируется следующим образом:
ни одно непротиворечивое множество аксиом не содержит арифметики, достаточной для того, чтобы доказать свою собственную непротиворечивость.
В выражении "содержит арифметики, достаточной..." речь идет об уже упомянутом условии того, что множество аксиом, о котором мы говорим, способно доказать все финитные истинные высказывания. Но как же может множество доказать или не доказать собственную непротиворечивость? Для начала арифметические аксиомы позволяют доказать только те высказывания, в которых говорится о числах, но не такие, в которых говорится о непротиворечивости множества аксиом. Мы уже сталкивались с подобной проблемой в предыдущей главе, когда хотели записать арифметическое высказывание, которое говорило бы о себе самом. Как добиться того, чтобы арифметическое высказывание, в котором говорится о числах, начало говорить о самом себе? Способом достижения этого была идентификация высказываний с помощью их кодов, так чтобы разговор о высказывании был равносилен разговору о его коде.
Для доказательства непротиворечивости аксиом арифметики необходим прямой метод.
Давид Гильберт на инаугурационном докладе на Втором Международном математическом конгрессе в Париже в 1900 году
В нашем случае, когда мы хотим записать арифметическое высказывание, в котором говорилось бы о непротиворечивости множества аксиом, нумерация Гёделя снова приходит нам на помощь.
Как уже говорилось, если множество аксиом противоречиво, то любое высказывание доказуемо на его основе. Наоборот, если множество непротиворечиво, всегда найдется высказывание, являющееся недоказуемым (поскольку для любого Р либо оно, либо его отрицание, по крайней мере одно из двух, недоказуемо). Следовательно, непротиворечивость множества аксиом равносильна тому, что есть по крайней мере одно высказывание, которое не является доказуемым на его основе. То, что система непротиворечива, равносильно следующему:
"существует некоторое высказывание, не являющееся доказуемым".
Вновь возьмем гипотетический пример из предыдущей главы, в котором мы предположили, что всем высказываниям соответствуют коды, являющиеся простыми числами, а доказуемым высказываниям, в частности, соответствуют простые числа, являющиеся суммой или разностью трех последовательных простых чисел. В данном контексте в предыдущем высказывании утверждалось бы, что "существует некоторое простое число, не являющееся суммой или разностью трех последовательных простых чисел", что на другом уровне прочтения означало бы: "существует код высказывания, не являющийся кодом доказуемого высказывания", то есть "существует недоказуемое высказывание" или "множество аксиом непротиворечиво".