Свойства дедуктивных теорий

Выберем один из трех способов задания теорем дедуктивной теории. Из-

меняя аксиомы или правила вывода (в случае, когда они задаются), можно

по-лучать различные множества теорем Т. Это множество Т - множество

теорем (множество доказуемых формул) является существенной

характеристикой дедуктивной теории.

Может оказаться, что множество теорем Т покрывает все множество формул

(правильно построенных выражений) теории. Иначе, это означает, что до-

казуема любая формула (правильно построенное выражение) и если в теории

есть отрицание, то из доказуемости какой-то формулы тут же следует

доказуемость ее отрицания. Следовательно, в этом случае доказуем какой-то

факт и его отрицание. Ясно, что теории, в которых можно доказать, что

угодно, не представляют интерес с многих позиций.

Дедуктивные теории, в которых множество теорем покрывает все множество

формул (правильно построенных выражений) называются противоречивыми,

в противном случае – непротиворечивыми. Выяснение непротиворечивости

дедуктивной теории является одной из важнейших проблем. К сожалению,

эта проблема оказывается и одной из очень сложных.

Пусть множество теорем Т является частью, не совпадающей со всем

множеством формул (правильно построенных выражений) Ф, т.е. наша дедук-

тивная теория непротиворечива. Тогда можно уже интересоваться, а какую

часть Ф занимают теоремы. Для этого вводят свойство полноты теории. Свой-

ство полноты дедуктивной теории характеризует достаточность теорем для

каких-то целей. В зависимости от того, для каких целей должно быть

достаточно теорем, будем в дальнейшем вводить различные понятия

полноты.

Рассмотренные свойства - непротиворечивость и полнота, являются важ-

нейшими свойствами дедуктивной теории. Кроме этих свойств, имеется и ряд

других свойств. Рассмотрим еще два свойства дедуктивной теории.

Независимость аксиом теории. Отдельная аксиома дедуктивной теории,

называется независимой, если эту аксиому нельзя вывести в этой теории из

ос-тальных аксиом. Система аксиом называется независимой, если каждую из

них нельзя вывести из остальных.

Разрешимость теории. Дедуктивная теория называется разрешимой, если в

этой теории понятие теоремы эффективно, т.е. существует правило (метод),

позволяющее для произвольной формулы за конечное число действий выяс-

нить, является она теоремой или нет.

Пусть заданы две дедуктивные теории B 1 и B 2 такие, что:

1) алфавит теории B 1 содержится в алфавите теории B 2 или эти алфавиты

совпадают,

2) каждая формула из B 1 является формулой из B 2

3) каждая теорема из B 1 является теоремой в B 2

При выполнении этих условий говорят, что теория B 2 является расшире-нием

теории B 1.

В следующих разделах изучим более подробно каждую из дедуктивных

теорий (полуформальную и формальную аксиоматическую теорию,

естествен-ный вывод), их свойства, а также примеры таких теорий.