Математическая логика и теория алгоритмов

решимая (нельзя ни доказать, ни опровергнуть) формула. Теорема Геделя утверждает, что такое расширение теории не может сделать ее полной. Теорема Геделя показывает, что множество теорем теории (множество Ts) содержится во множестве всех истинных арифметиче­ ских формул Vs (Ts с Fs) и в то же время нельзя построить непротиво­ речивое эффективно аксиоматизированное расширение для 5 так, что­ бы полученное множество теорем покрыло все Fj. Отсюда следует, что формальный аксиоматический подход к арифметике натуральных чисел не в состоянии охватить всю область истинных арифметических суждений (формул). Таким образом, результат Геделя указывает на некоторую принципиальную ограни­ ченность возможностей аксиоматического метода. Вторая теорема Геделя. В этой теореме Гедель показал, что никакое предложение, которое можно точным образом интерпретиро­ вать как выражающее непротиворечивость какой-либо непротиворе­ чивой формальной аксиоматической теории К, содержащей арифме­ тику, не кюжет быть доказано в этой теории К. Более вольно излагая эту теорему, можно сказать, что «если теория К, содержащая арифметику, непротиворечива, то непротиворе­ чивость ее нельзя доказать средствами самой теории К». Конечно, неплохо, если получим доказательство на основе более богатой теории. Но нам нужно знать, непротиворечива ли эта более богатая теория. Теорема Геделя утвермодает, что если она непротиво­ речива, то непротиворечивость ее нельзя доказать средствами самой теории, т.е. придется привлекать еще более богатую теорию, непроти­ воречивость которой тоже нельзя доказать в ней самой, и т.д. Доказательство непротиворечивости арифметики натуральных чисел с привлечением новых правил вывода было впервые получено Ге1щеном в 1936 г., а впоследствии были получены еще несколько до­ казательств. Эти доказательства имеют относительную ценность. Они 177