Логика предикатов с одним переменным (стр. 2 из 4)

Пусть формула 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(, ..., ) содержит только предикаты , и поэтому всякое предметное переменное входит только под знаком одного из этих предикатов.

Пусть R (x, y, ..., u) – предикат, определённый на поле M. Введём обозначение

R (x, y, ..., u).

Под этим выражением мы будем понимать предикат, зависящий от y, z, ..., u (или высказывание, если, y, z, ..., u отсутствуют) и принимающий значение И, когда R (y, z, ..., u) имеет значение И для данных y, z, ..., u и для всех x, принадлежащих полю

, и принимающий значение Л в противоположном случае. Введём также выражение

R (x, y, ..., u),

которое представляет собой предикат от y, ..., u и принимает значение И, когда R (x, y, ..., u) имеет значение И для y, ..., u и по крайней мере для одного значения x из поля

, и значение Л в противоположном случае. Знаки и будем называть ограниченными кванторами. Если мы все переменные предиката R (x, y, ..., u) свяжем ограниченными кванторами, например

... R (x, y, ..., u),

то получим формулу, отнесённую к полю

. покажем, что выражение

("x) R ((х), y, ..., u)

равносильно выражению

R (x, y, ..., u).

Пусть ("x) R ((х), y, ..., u) имеет значение И. В таком случае R ((х), y, ..., u) имеет значение И для данных y, ..., u и для каждого x. Но так как функция (х) пробегает всё поле

, когда x пробегает поле M, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для всех x из . В силу определения R (x, y, ..., u) также принимает значение И. Обратно, если R (x, y, ..., u) принимает значение И, то R (x, y, ..., u) имеет значение И для данных y, ..., u и для каждого x из . В таком случае выражение R ((х), y, ..., u) имеет значение И для данных y, ..., u и для каждого x из M, так как (х) для любого x принадлежит .

Аналогичным образом можно показать, что выражения

() R ((х), y, ..., u) и () R (x, y, ..., u)

также равносильны.

Рассмотрим формулу U(, ..., ), которую можно представить в форме

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

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

представляет собой предикат, определённый на поле M и зависящий от p переменных x₁, ..., x_p. Каждое из этих переменных входит в формулу B только через предикаты , ..., . С другой стороны, мы видели, что предикаты (х) и ((х)) равносильны. Поэтому если в формуле B(, ..., , x₁, ..., x_p) мы заменим x_i на (х_i), то получим равносильное выражение:

B(, ..., , x₁, ..., x_p) ~ B(, ..., ,(x₁), ..., (x_p)).

Отсюда следует, что

(s x_p) B(, ..., , x₁, ..., x_p) ~ (s x_p) B(, ..., , (x₁), ..., (x_p)).

Далее можно заключить, что

(s x_p) B(, ..., , (x₁), ..., (x_p)) ~

~ B(, ..., , (x₁), ..., (x_p-1), x_p).

Рассуждая аналогичным образом, мы получим

(s x_p-1) (s x_p) B(, ..., , x₁, ..., x_p-1 , x_p) ~

~ B(, ..., , (x₁), ..., (x_p-2), x_p-1, x_p)