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

Теорема 29.1. Если в алгебраической системе  выполняются все формулы из множества  и из  синтаксически выводима формула  , то  также выполняется в  и  .
Доказательство разделим на три этапа. На первом этапе отметим, что каждая аксиома ФИП есть тождественно истинная формула. Что касается аксиом  исчисления высказываний, то их тождественная истинность установлена нами в алгебре высказываний (см. теоремы 3.1 з, 3.3, а, л). Общезначимость аксиом  и  установлена в теореме 21.13.
На втором этапе покажем, что все три правила вывода, используемые в ФИП, обладают следующим семантическим свойством. Если алгебраическая система  служит моделью для всех посылок правила вывода, то  будет моделью и для формулы, получаемой из данных формул с помощью данного правила вывода. Докажем это утверждение для трех из правил вывода.
Правило MP. Допустим, что  и  . Докажем, что тогда  . Возьмем любую подстановку  констант из  . Тогда, по условию, каждое из высказываний  и  , получаемых соответственно из формул  и  в результате подстановки предметных констант  , будет истинным. Тогда истинным будет и высказывание  , то есть  . Это и означает, что  .
∀-правило. Допустим, что  , где  не входит свободно в формулу  , а  обозначает все свободные предметные переменные в формулах  и  (в  — кроме  ). Тогда сделанное допущение означает, что для любых элементов  (где  — носитель алгебраической системы  ) высказывание  истинно в  . Рассмотрим теперь высказывание  и покажем, что оно истинно в  при любом  . В самом деле, если  ложно, то рассматриваемое высказывание истинно. Если же  истинно, то, по отмеченному выше, истинным будет и высказывание  . Поскольку оно будет истинным при любом  , то отсюда вытекает истинность для таких  высказывания  . Это, в свою очередь, влечет истинность высказывания  для тех  , для которых  истинно. Итак, высказывание  истинно для любых  . Это и означает, что  .
∃-правило. Подобно предыдущему правилу, доказывается, что если  , то  .
Наконец, на третьем этапе докажем утверждение самой теоремы. Пусть  и  . Последнее означает, что имеется вывод  формулы  из множества формул  (в частности,  ). Покажем, что каждый элемент этой последовательности является формулой, выполняющейся в  . Доказательство проведем индукцией по номеру  формулы в рассматриваемом выводе. При  , если  , то, по условию,  . Если  — аксиома, то она общезначима и, в частности,  . Предположим теперь, что при всех  все формулы  выполняются в  , то есть  . Рассмотрим формулу  . Если  или  — аксиома, то, как отмечено выше,  . Если же  получена из предыдущих формул последовательности по одному из трех правил вывода, то (на основании выполнимости всех предыдущих формул в  ) в силу утверждений (см. второй этап) заключаем, что и  выполняется в  , то есть  . Окончательно заключаем, что все формулы последовательности  истинны в  , в частности  . Теорема полностью доказана.