Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

формулы были доказуемы, все равно и для такой расширенной системы всегда существует истинная, но неразрешимая (нельзя ни доказать, ни опровергнуть) формула. Теорема Геделя утверждает, что такое расширение теории не может сделать ее полной. Теорема Геделя показывает, что множество теорем теории (множество Ts) содержится во множестве всех истинных арифметических формул Vg {Т^ а V^) и в то же время нельзя построить непротиворечивое эффективно аксиоматизированное расширение для S так, чтобы полученное множество теорем покрыло все V^. Отсюда следует, что формальный аксиоматический подход к арифметике натуральных чисел не в состоянии охватить всю область истинных арифметических суждений (формул). Таким образом, результат Геделя указывает на некоторую принципиальную ограниченность возможностей аксиоматического метода. Вторая теорема Геделя. В этой теореме Гедель показал, что никакое предложение, которое можно точным образом интерпретировать как выражаюш,ее непротиворечивость какой-либо непротиворечивой формальной аксиоматической теории К, содержаш,ей арифметику, не может быть доказано в рамках этой теории К. Более вольно излагая эту теорему, можно сказать, что «если теория К, содержаш,ая арифметику, непротиворечива, то непротиворечивость ее нельзя доказать средствами самой теории К». Конечно, неплохо, если получим доказательство на основе более богатой теории. Но нам нужно знать, непротиворечива ли эта более богатая теория. Теорема Геделя утверждает, что если она непротиворечива, то непротиворечивость ее нельзя доказать средствами самой теории, т.е. придется привлекать еш,е более богатую теорию, непротиворечивость которой тоже нельзя доказать в ней самой, и т.д. Доказательство непротиворечивости арифметики натуральных чисел с привлечением новых правил вывода было впервые получено Генценом в 1936г., а впоследствии были получены еш,е несколько доказательств. Эти доказательства имеют относительную ценность. Они сводят доказательство непротиворечивости арифметики к доказательству непротиворечивости более богатых теорий. В то же время эти доказательства демонстрируют, какие новые правила вывода следует допустить (принять), если нужно установить непротиворечивость арифметики. § 16. Значение аксноматнческого метода Говоря об ограниченности аксиоматических подходов, нельзя умолчать о достоинствах и большом значении аксиоматического подхода. 129