В примерах, рассмотренных в предыдущих параграфах, мы видели, что логика первого порядка обладает значительными выразительными возможностями. Данный параграф посвящен доказательству того, что выразительные возможности этой логики ограничены.

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

Определение. Пусть S(x,y) – двухместный предикат, заданный на множестве М. Предикат S⁺(x,y) называется транзитивным замыканием предиката S(x,y), если для любых a,bÎM выполняется условие:

Если предикат представлять отношением, то транзитивное замыкание предиката – транзитивное замыкание бинарного отношения.

Рассмотрим пример. Пусть М – множество натуральных чисел, а S(x,y) – предикат «x непосредственно предшествует y», т.е. «y=x+1». Тогда транзитивным замыканием предиката S(x,y) будет предикат «x меньше y».

Оказывается, что не существует формулы логики первого порядка, которая выражала бы транзитивное замыкание двухместного предиката. Более точная формулировка содержится в следующем утверждении.

Теорема 3.5 Пусть P – символ двухместного предиката. Не существует формулы F(x,y) логики первого порядка такой, что для любой интерпретации j с областью М предикат (jF)(x,y) есть транзитивное замыкание предиката (jP)(x,y).

Доказательство теоремы 3.5 опирается на одно известное в логике первого порядка утверждение, которое называется теоремой компактности. В формулировке теоремы компактности используется понятие логического следствия бесконечного множества формул. Определение этого понятия легко получается из определения логического следствия множества формул F₁,…,F_k из §6 и поэтому не приводится.

Теорема компактности. Если формула G является логическим следствием бесконечного множества формул K, то G является логическим следствием некоторого конечного подмножества K′ множества K.

Доказательство теоремы компактности является довольно сложным, поэтому здесь не излагается. С ним можно познакомиться по книге Ерщова Ю.Л. и Палютина Е., включенной в список литературы.

Приведем доказательство теремы 3.5. Предположим противное, т.е. предположим, что существует формула F(x,y) логики первого порядка такая, что для любой интерпретации j с областью М и любых a,bÎM выполняется эквиваленция

(jF)(a,b)Û(jP)⁺(a,b).

Рассмотрим следующее множество формул

K={E₀(x,y), E₁(x,y),…, E_n(x,y),…}:

E₀=(x,y)=ØP(x,y)

E₁(x,y)=Ø($z₁)[P(x,z₁)&P(z₁,y)],

E₂(x,y)=Ø($z₁)($z₂)[P(x,z₁)&P(z,z₂)&P(z₂,y)],

E_n(x,y)=Ø($z₁)…($z_n)[p(x,z₁)&P(x,z₂)&…&P(z_n,y)],

. . .

Используя определение транзитивного замыкания и предположение о том, что формула F(x,y) определяет транзитивное замыкание, получаем, что формула ØF(x,y) есть логическое следствие множества формул K. По тереме компактности ØF(x,y) есть логическое следствие некоторого конечного подмножества K′ множества K. Можно считать, что

K′={E₀(x,y), E₁(x,y),…, E_d(x,y)}

для некоторого d.

Пусть М={0,1,…,d+1,d+2}. На множестве М определим двухместный предикат S следующим образом:

S(u,v)Ûu+1 равно v

Например, высказывания S(0,1), S(1,2) истинны, а высказывание S(0,2) ложно. Отметим, что высказывание S⁺(0,d+2) истинно. Рассмотрим интерпретацию j, для которой (jP)(u,v)=S(u,v). Все высказывания (jE₀)(0,d+2), (jE₁)(0,d+2),…(jE_d)(0, d+2) истинны. Так как формула ØF(x,y) есть логическое следствие множества формул K′, то истинно высказывание Ø(jF)(0, d+2). С другой стороны, поскольку F(x,y) определяет транзитивное замыкание и истинно высказывание S⁺(0, d+2) (другими словами, высказывание (jP⁺)(0, d+2)), то истинно высказывание (jF)(0, d+2). Мы доказали, что истинно и последнее высказывание, и его отрицание. Полученное противоречие показывает, что не существует формулы логики первого порядка, определяющей транзитивное замыкание предиката.

Теорема доказана.