Теорема о полноте исчисления предикатов

Предложение 2.7. Во всяком исчислений предикатов первого порядка всякая теорема является логически общезначимой.

Доказательство. В силу свойства (VII) понятия истинной формулы, аксиомы, задаваемые схемами (1)-(3), логически общезначимы. В силу свойств (Х) (следствие) и (ХI), логически верны аксиомы, порождаемые схемами (4)-(5). В силу (III) и (VI), правила вывода МР и Gen сохраняют свойство логической общезначимости. Таким образом, всякая теорема любого исчисления предикатов логически общезначима.

(VII) Всякий частный случай всякой тавтологии истинен во всякой интерпретации. (Частным случаем данной пропозициональной формы мы называем всякую формулу, получаемую подстановкой формул в эту пропозициональную форму вместо пропозициональных букв с тем условием, чтобы вместо всех вхождений одной и той же пропозициональной буквы подставлялась одна и та же формула.

(Х) Лемма. Пусть t и v – термы, s – последовательность из ∑, t’ получается из t подстановкой v вместо всех вхождений х_i и s’ получается из s заменой в ней ее i-й компоненты на s*(v); тогда s*(t’)= (s’) *(t).

(ХI) Если формула А не содержит х_i в качестве свободной переменной, то формула

истинна во всякой интерпретации.