Логика предикатов (стр. 2 из 7)

Пусть формула U(A₁, ..., A_n), содержащая только символы предикатов A₁, ..., A_n, каждый из которых зависит от одного переменного, выполнима на некотором поле M. эту формулу мы можем предполагать представленной в нормальной форме, а все предметные переменные в ней связанными. В самом деле, какова бы ни была формула U, мы можем, произведя над ней преобразования, привести её к виду, в котором все кванторы предшествуют остальным символам формулы, при этом состав её предикатов и предметных переменных не изменяется. Если в U есть свободные предметные переменные, то можно связать их квантором общности.

Итак, допустим, что U – нормальная формула. Тогда мы можем представить её следующим образом:

(s x₁)(s x₂)...(s x_p) B(A₁, ..., A_n, x₁, ..., x_p),

где каждый из символов (s x_i) обозначает квантор ("x_i) или ($x_i), а формула

B(A₁, ..., A_n, x₁, ..., x_p)

кванторов не содержит.

В формуле B(A₁, ..., A_n, x₁, ..., x_p) все переменные x₁, ..., x_p входят в предикаты A₁, ..., A_n, и её можно записать в виде

B(A₁(

), ..., A_n( )),

где i₁, ..., i_n – числа от 1 до p. Однако, будет удобнее пользоваться выражением

B(A₁, ..., A_n, x₁, ..., x_p),

если иметь в виду, что B является логической функцией предикатов A_k, а каждый предикат A_k зависит от какого-то одного переменного

.

Покажем, что если для некоторого поля M существуют индивидуальные предикаты

,..., ,

для которых формула U(

,..., ) истинна, то эта формула истинна и на некотором подмножестве этого поля, содержащем не более элементов, так как иначе наше утверждение тривиально. Разобьём элементы множества M на классы следующим образом. Для каждой последовательности, содержащей n символов И и Л в произвольном порядке (И, Л, Л, ..., И,), существует часть (может быть, пустая) множества M, содержащая те и только те элементы x, для которых последовательность значений предикатов (x), (x), ..., (x) совпадает с данной последовательностью символов И и Л.

Обозначим через

₁, ₂, ..., _n

последовательность символов И и Л, где

_i представляет собой И или Л, а соответствующий этой последовательности класс элементов x обозначим

, , ..., .

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

₁, ₂, ..., _n не существует такого элемента, для которого предикаты , , ..., принимают соответствующие значения ₁, ₂, ..., _n . Вместе с тем каждый элемент множества M принадлежит одному из классов , и различные классы общих элементов не имеют. Число всех классов (пустых и непустых) равно числу последовательностей ₁, ₂, ..., _n, т. е. . Следовательно, число q непустых классов не превышает . Выберем из каждого непустого класса по одному элементу и обозначим эти элементы

a₁, a₂, ..., a_q.

Множество всех этих элементов обозначим

.докажем, что если формула U( , ..., ) истинна на поле M, то она истинна и на поле (так как – часть поля M, то предикаты определены на ). каждому элементу x поля M поставим в соответствие элемент из , принадлежащий тому же классу, что и х. В существует один и только один такой элемент. Элемент из , поставленный в соответствие х, обозначим (х). Можно сказать, что мы построили функцию, определённую на множестве M и принимающую значения из множества .

Легко видеть, что имеет место следующая равносильность:

(х) ~ ( (х)).

Действительно,

(x) принадлежит тому же классу , что и x. Но, по определению, для элементов одного и того же класса каждый предикат принимает одно и то же значение. Отсюда следует, что если в формуле U( , ..., ) для каждого предметного переменного t заменить каждое выражение (t) через ( (х)), то формула U( , ..., ) перейдёт в формулу ( , ..., ), равносильную первой. Написание формулы отличается от U только тем, что все предметные переменные x, y, z, …, u формулы U замещены соответственно через (х), (y), ..., (u). Это следует из того, что по условию формула U( , ..., ) содержит только предикаты , и поэтому всякое предметное переменное входит только под знаком одного из этих предикатов.