Cтраница 4
Можно доказать, что всякое разрешимое множество перечислимо. В то же время удалось построить перечислимое, но не разрешимое множество. Этот первый конкретный пример ( опубликован амер. [46]
Отсюда следует, что теория Th ( N, , , х) не является конечно аксиоматизируемой. Более того, это же рассуждение показывает, что не существует разрешимого множества теорем этой теории, из которых бы выводились все другие теоремы. Отсюда следует, что классическая система аксиом формальной арифметики, называемая также арифметикой Пеано ( свойства арифметических операций плюс аксиомы индукции), не может быть полной: существуют истинные формулы, невыводимые в формальной арифметике. [47]
Теперь изложим в том же стиле доказательство теоремы Геделя. Таким образом, возникает некоторое перечислимое множество, которое обычно задают как проекцию разрешимого множества. Именно, вводят некоторое понятие доказательства. При этом доказательства являются словами в некотором алфавите. Множество доказательств разрешимо, то есть есть алгоритм, отличающий настоящие доказательства от текстов, который таковыми не являются. [48]
Если Т противоречива, то ее теоремами служат все предложения языка теории Т, которые, как мы только что заметили, образуют разрешимое множество. [49]
Покажем, что если свойство Л можно распознавать по [ / - номерам, то любые два непересекающихся перечислимых множества Р и Q отделимы разрешимым множеством. [50]