P n ( ω ).
Мы можем допустить, чтобы наша нумерация по желанию была несколько «либеральна» в отношении синтаксически некорректных выражений. (Это позволит значительно упростить перевод системы на язык арифметических операций по сравнению со случаем, когда мы будем стараться исключить из рассмотрения синтаксически некорректные выражения.) Если P n (ω) синтаксически корректно, то оно будет представлять из себя некоторое совершенно определенное арифметическое выражение, в котором фигурируют два натуральных числа п и ад. Каков будет конкретный вид этого выражения — зависит от особенностей системы нумерации, которую мы выбрали. Но эти детали рассматриваются в «сложной» части и сейчас нас не касаются. Пусть П n будет n -м доказательством. (Опять же мы можем использовать «либеральную нумерацию», когда для некоторых значений n выражение П n не является синтаксически корректным и, тем самым, не доказывает никакую теорему.)
А теперь рассмотрим следующую функцию исчисления высказываний от натурального числа ω :
— E к.с. x [ П x доказывает P ω ( ω )].
В выражении в квадратных скобках частично присутствуют слова, но, тем не менее, это — абсолютно точно определенное выражение. Оно говорит о том, что доказательство номер х является доказательством утверждения Р ω (), примененного к самому ω . Находящийся за скобками квантор существования с отрицанием позволяет исключить из рассмотрения одну из переменных («не существует такого х , что…»), приводя нас в конечном счете к арифметической функции исчисления высказываний, зависящей только от ω . В целом данное выражение утверждает, что не существует доказательства Р ω ( ω ). Я буду предполагать, что оно оформлено синтаксически корректным образом (даже если Р n ( ω ) некорректно — поскольку тогда выражение было бы истинным за невозможностью существования доказательства синтаксически некорректного утверждения). На самом деле, в результате сделанного нами перевода на язык арифметики, написанное выше будет в действительности неким арифметическим выражением, включающим натуральное число ω (тогда как в квадратных скобках окажется четко определенное арифметическое выражение, связывающее два натуральных числа х и ω ). Конечно, возможность представления этого выражения в арифметическом виде далеко не очевидна, но она существует. Рассуждения, приводящие к этому заключению, составляют наиболее трудную задачу в «сложной» части доказательства Геделя. Как и ранее, непосредственный вид арифметического выражения будет зависеть от способа нумерации и в еще большей степени от конкретной структуры аксиом и правил вывода, принятых в нашей системе. Поскольку все это входит в «сложную» часть доказательства, то в данном случае нас не интересует.
Мы пронумеровали все функции исчисления высказываний, зависящие от одной переменной, поэтому той, которую мы ввели выше, также должен быть приписан номер. Пусть этот номер будет k . Наша функция будет в таком случае k -й в общем списке. То есть
— E к.с. x [ П х доказывает P ω ( ω )] = Р k ( ω ).