Невыразимость в логике первого порядка

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

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

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

высказывание S ⁺(a, b) истинно ⇔ существует натураль-

ное число n и элементы c ₀, …, c_n множества M такие, что a

= c ₀, c_n = b и все высказывания S (c ₀, c ₁), S (c ₁, c ₂), …, S (c_{n -1}, c_n) истинны.

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

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

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

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

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

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

Доказательство теоремы компактности будет приведено в следующей главе.

Приведем доказательство теоремы 2.5. Предположим противное: существует формула F (x, y) логики первого порядка такая, что для любой интерпретации ϕ с областью M и любых a, b ∈ M выполняется эквиваленция (ϕ F)(a, b) ⇔ (ϕ P)⁺(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 (z ₁, 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.

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

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

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