Дискретка

Еще раз отметим, что в последнем правиле c символ константы,

не связанный никакими дополнительными ограничениями; вообще говоря, суждение ((A(c)) ! (8xA(x))) не обязано быть верным.

2. Выводимые суждения универсально верны. В этом пункте

мы покажем, что все выводимые суждения, построенные по правилам

(1)-(6), универсально верны.

Теорема 1. Всякое выводимое суждение является универсально верным (то есть истинным при любой интерпретации символов констант и предикатов).

Доказательство. Напомним, что при переходе к интерпретации суждения превращаются в высказывания: каждое из них истинно или ложно в этой интерпретации. Правила (1) и (2) как раз и являются переформулировками соответствующих правил исчисления высказываний. Совершенно очевидно, что по правилам (3)-(5) получаются суждения, истинные при любой интерпретации символов констант и предикатов. Осталось показать, что и по правилу (6) получаются универсально верные суждения. Пусть fM; cM ; PM g любая интер-

претация множеств констант и предикатов, и пусть m 2 M. Предпо-

ложим, что мы уже убедились в универсальной верности выводимого суждения A(c). Значение истинности выражения A(m) в интерпрета-

ции M совпадает совпадает со значением истинности суждения A(c) в интерпретации, отличающейся от интерпретации M только тем, что символу константы c ставится в соответствие не элемент cM , à ýëå- мент m. Но суждение A(c) истинно в любой интерпретации; поэтому формуле A(m) истинно в интерпретации M для любого m 2 M, то есть суждение 8xA(x) истинно в интерпретации M.

Обратное утверждение значительно глубже и будет доказано ниже как следствие теоремы Геделя о полноте.

3. Непротиворечивость. Теорема Геделя о полноте. Пусть теперь S некоторое множество суждений; мы говорим, что суждение

A выводимо из S, если существуют суждения X1; : : : ; Xm 2 S, такие что суждение (X1& : : : &Xm) ! A выводимо (то есть выводимо из пустого множества суждений). Система суждений S называется непро-

тиворечивой, если тождественно ложное суждение л не выводимо из

S.

Ясно, что если для множества суждений существует модель, то это множество суждений непротиворечиво. Оказывается, верно и обратное.

Теорема 2 (теорема Геделя о полноте). Пусть S A(C; P)

некоторое непротиворечивое множество суждений. Тогда существует модель этого множества суждений. Более того, если множества P, C конечны, то существует не более чем счетная модель

21

S, а если хотя бы одно из них бесконечно, существует модель множества S, мощность которой не превосходит максимума мощностей множеств P, C.

Доказательство этой теоремы будет дано в следующем параграфе. То же самое ограничение на мощность, что и в теореме Геделя, будет встречаться у нас еще несколько раз. Для сокращения речи будем называть множества, мощность которых удовлетворяет этому условию, множествами малой мощности (по отношению к множествам символов констант и предикатов C, P). В этих терминах теорема Ге-

деля гарантирует существование модели малой мощности.

4. Следствия теоремы Геделя. В этом пункте мы укажем несколько важных следствий теоремы Геделя.

Теорема 3. Пусть X A(C; P) непротиворечивое множество суждений. Если суждение A 2 A(C; P) не выводимо из X, то существует модель множества суждений X, в которой суждение A ложно. Иначе говоря, суждение A 2 A(C; P) выводимо из X тогда и

только тогда, когда оно истинно во всех моделях множества суждений X. В частности, суждение выводимо (то есть выводимо из

пустого множества) тогда и только тогда, когда оно универсально верно.

Доказательство. Заметим сначала, что высказывание

((X2&:X1) ! (ë)) ! (X2 ! X1)

тождественно истинно. Пусть суждение A 2 A(C; P) не выводимо из X. Если бы множество суждений X [ f:Ag было противоречивым,

то существовало бы конечное множество суждений Y1; : : : ; Yn 2 X, такое что суждение (Y1& : : : &Yn&:A) ! (л) было бы выводимым. Подставляя в указанное выше тождественно истинное высказывание суждение Y1& : : : &Yn вместо X2 и A вместо X1

ponens, мы увидели бы, что (Y1& : : : &Yn) ! A выводимое суждение , то есть что суждение A выводимо из X вопреки предположению. Итак, множество суждений X[ f:Ag непротиворечиво, и по теореме

Г¼деля о полноте существует его модель. Эта модель является моделью множества суждений X, но суждение A в этой модели ложно,

поскольку в ней выполняется суждение :A.

Последнее утверждение только что доказанной теоремы показывает, что для построения всех универсально верных суждений достаточно пользоваться лишь правилами (1)-(6). Иначе говоря, эти правила составляют полную систему правил вывода универсально верных суждений; этим объясняется название теоремы Геделя: это по существу теорема о полноте системы правил вывода (1)-(6).

Теорема 4 (теорема компактности). Если для всякого конечного подмножества множества суждений X A(C; P) существует

модель, то существует и модель всего множества суждений X.

22

Доказательство. Если бы множество суждений X было противоре-

чивым, то существовали бы суждения X1; : : : ; Xn 2 X, такие что суждение

(X1& : : : &Xn) ! (ë)

было бы выводимым. Но тогда было бы противоречивым уже конеч- ное множество суждений fX1; : : : ; Xng X, и для него не существо-

вало бы модели, что противоречит предположению теоремы. Следовательно, множество суждений X непротиворечиво, и по теореме

Г¼деля о полноте существует модель этого множества суждений.

Теорема 5 (существование сколь угодно больших моделей).

Если для множества суждений X A(C; P) существует бесконеч-

ная модель или даже сколь угодно большие конечные модели, то существуют и модели множества суждений X сколь угодно большой

мощности.

Доказательство. Расширим множество символов констант C, добавив к нему произвольное множество D. Обозначим через X0 A(C [

D; P) множество суждений, полученное из X добавлением суждений :(d = d0) äëÿ âñåõ ïàð d; d0 2 D, d 6= d0.

Каждое конечное подмножество Y множества X0

дель. Действительно, в Y участвует лишь конечное число элементов d1; : : : ; dm 2 D. По условию, существует модель M множества суждений X, состоящая не менее чем из m элементов; сопоставляя символам констант d1; : : : ; dm различные элементы из множества M, мы превратим M в интерпретацию множества символов констант

C [ fd1; : : : ; dmg и символов предикатов P, в которой истинны все суждения из X и суждения :(di = dj), 1 i; j m, i 6= j. В частности, в M выполнены все суждения из Y, так что M модель

множества суждений Y.

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

X, а е¼ мощность не меньше мощности множества D, так как всем

символам констант из D должны соответствовать различные элементы из M0.

x 6. Доказательство теоремы Г¼деля о полноте

1. Максимальные непротиворечивые и экзистенциально пол-

ные множества суждений. Определим два важных класса множеств суждений. Подмножество S множества суждений A(C; P) на-

зывается экзистенциально полным, если для любого суждения вида 9x(A(x)), принадлежащего S, найдется символ константы c 2 C, та-

кой что суждение A(c) тоже принадлежит множеству S (здесь, как обычно, A(x) формула, в которую свободно входит только символ переменной x).

23

Множество суждений S A(C; P) называется максимальным непротиворечивым подмножеством A(C; P), если множество суждений S непротиворечиво, но любое его собственное расширение уже не является непротиворечивым.

Предложение 1. Пусть S максимальное непротиворечивое подмножество A(C; P), и пусть A любое суждение из A(C; P). Тогда одно и только одно из суждений A, :A содержится в S. Если суждение A выводимо из S, то A 2 S. В частности, все выводимые

суждения (то есть суждения, выводимые из пустого множества суждений) принадлежат S.

Доказательство. Оба суждения A, :A не могут содержаться в непротиворечивом множестве S, так как в противном случае тождественно ложное суждение A&:A было бы выводимо из S, что несовместимо с непротиворечивостью S. Пусть A; :A 2= S; поскольку S

максимальное непротиворечивое множество, оба множества суждений S [ fAg, S [ f:Ag не являются непротиворечивыми. Поэтому

существуют суждения B1; : : : ; Bm; Bm+1; : : : ; Bn 2 S, такие что суждения

(A&B1& : : : &Bm) ! (ë); (:A&Bm+1& : : : &Bn) ! (ë)

выводимы. Далее, высказывание

(((x&y) ! (ë))&((:x&z) ! (ë))) ! ((y&z) ! (ë))

является, тавтологией (см. x 2.2, (20)). Подставляя сюда вместо x; y; z

суждения A, B1& : : : &Bm è Bm+1& : : : &Bn и пользуясь modus ponens, находим, что и суждение

(B1& : : : &Bm&Bm+1& : : : &Bn) ! (ë)

выводимо, а это означает, что S противоречивое множество суждений. Следовательно, предположение о том, что ни суждение A, ни суждение :A не принадлежат S, было неверно.

Если бы выводимое из S суждение A не принадлежало S, то, как мы только что доказали, суждение :A принадлежало бы S, и, таким образом, оба суждения A, :A были бы выводимы из S. Вместе с ними, вопреки непротиворечивости множества суждений S, из S было бы выводимо тождественно ложное суждение A&:A. Итак, любое выводимое из S суждение A принадлежит S.

2. Интерпретации максимальных непротиворечивых экзистенциально полных множеств суждений.

Теорема 1. Пусть M = fM; cM ; PM g интерпретация множеств символов констант C и символов предикатов P, такая что для любого элемента m 2 M существует символ константы c 2 C, для которого m = cM . Множество S всех суждений из A(C; P), истинных в интерпретации M, является максимальным непротиворечивым и экзистенциально полным. Обратно, пусть S A(C; P)

24

максимальное непротиворечивое и экзистенциально полное множество суждений; тогда существует такая интерпретация M =

fM; cM ; PM g множеств C, P, что для любого элемента m 2 M существует символ константы c 2 C, для которого m = cM , è суждение из A(C; P) истинно в M тогда и только тогда, когда оно

содержится в множестве S.

Доказательство. Пусть сначала S множество всех суждений из A(C; P), истинных в интерпретации M. Ясно, что оно непротиворе- чиво. Если суждение A 2 A(C; P) не принадлежит S, то оно не истинно в интерпретации M; это значит, что его отрицание :A истинно в M и потому принадлежит S. Таким образом, множество суждений S [ fAg содержит одновременно суждения A, :A, и потому противоречиво. Следовательно, S максимальное непротиворечивое множество суждений. Далее, если суждение 9x(A(x)) принадлежит S, то оно истинно в M, то есть найдется символ константы c 2 C, такой что суждение A(c) (точнее, суждение A(cM )) истинно в M и потому принадлежит множеству S. Итак, множество суждений S экзистен-

циально полно.

Сложнее доказывается обратное утверждение. Пусть S A(C; P)

максимальное непротиворечивое и экзистенциально полное множество суждений. Две константы c; d 2 C будем считать эквивалент-

ными и писать c d, если суждение c = d содержится в S.

Лемма 1. Отношение c d является отношением эквивалентности на множестве C. Если P символ n-местного предиката, c1; : : : ; cn; d1; : : : ; dn 2 C, c1 d1, . . . , cn dn и суждение P (c1; : : : ; cn)

содержится в S, то и суждение P (d1; : : : ; dn) содержится в S.

Доказательство. Суждение c = c выводимо и потому принадлежит S; значит, c c. Если c d, то суждение c = d принадлежит S, и из него и выводимого суждения (c = d) ! (d = c), тоже принадлежащего S, по modus ponens выводится суждение суждение d = c. По предложению из предыдущего пункта суждение d = c тоже принадлежит S, то есть d c. Точно так же, если c d, d e, то суждения c = d, d = e вместе с выводимым суждением ((c = d)&(d = e)) ! (c = e) принадлежат S; по предложению из предыдущего пункта выводимое из них суждение c = e тоже принадлежат S, то есть c e. Итак, отношение является эквивалентностью.

Аналогично доказывается и второе утверждение леммы. Если c1 d1, . . . , cn dn, то суждения c1 = d1, . . . , cn = dn принадлежат S. Из них, суждения P (c1; c2; : : : ; cn) и выводимых суждений

(c1 = d1) ! (P (c1; c2; : : : ; cn) ! P (d1; c2; : : : ; cn));

(c2 = d2) ! (P (d1; c2; : : : ; cn) ! P (d1; d2; : : : ; cn)); : : : ; (cn = dn) ! (P (d1; d2; : : : ; cn) ! P (d1; d2; : : : ; dn))

25

последовательно выводятся суждения

P (d1; c2; : : : ; cn); P (d1; d2; : : : ; cn); : : : ; P (d1; d2; : : : ; dn):

По предложению 1 последнее суждение P (d1; d2; : : : ; dn) принадлежит S.

Обозначим через M множество классов эквивалентности множества C по отношению . Для каждого символа константы c 2 C

обозначим через cM класс эквивалентности элемента c, а для каждого символа n-местного предиката P 2 P обозначим через PM подмножество декартовой степени Mn, состоящее из всех таких набо-

ðîâ (m1; : : : ; mn), что суждение P (c1; : : : ; cn) принадлежит S для любых элементов c1; : : : ; cn 2 C, классы эквивалентности которых равны соответственно m1; : : : ; mn 2 M. Таким образом, элементы cM и множества PM

S A(C; P).

Для доказательства теоремы осталось показать, что значения истинности суждения A 2 A(C; P) в интерпретации M = fM; cM ; PM g

и высказывания (A 2 S) совпадают. Пусть это не так, и пусть A 2 A(C; P) суждение наименьшей длины (как слово в алфавите из

символов констант, предикатов, переменных и других логических знаков), такое что его значение истинности в интерпретации M не

совпадает со значением истинности высказывания (A 2 S). Рассмотрим все возможные варианты (1)-(5) для суждения A и покажем, что

âкаждом из них мы приходим к противоречию.

(1)Суждение и истинно в любой интерпретации и принадлежит S,

а суждение л не истинно в любой интерпретации и не принадлежит непротиворечивому множеству суждений S. Поэтому суждение A не

совпадает ни с и, ни с л.

(2), (3) Интерпретация M построена так, что суждения видов c = d, P (c1; : : : ; cn) истинны в M тогда и только тогда, когда они принадлежат S. Поэтому суждение A не может совпадать с суждением

одного из видов c = d, P (c1; : : : ; cn).

(4) Пусть B; C 2 A(C; P). Суждение B&C выводимо из суждений B и C, и наоборот, суждения B и C выводимы из суждения B&C; поэтому (B&C) 2 S тогда и только тогда, когда B 2 S и C 2 S. Поэтому значения истинности высказываний (B 2 S)&(C 2 S) и (B&C) 2 S совпадают. Далее, очевидно, что совпадают значения истинности высказываний :(B 2 S) и (:B) 2 S. Отсюда, пользуясь тем, что значения истинности для B _ C, B ! C, B $ C совпадают со значениями истинности для :((:B)&(:C)), :(B&(:C)), :((:(B&C))&(:B)&(:C)), находим, что значения истинности высказываний (B 2 S)_(C 2 S), (B 2 S) ! (C 2 S), (B 2 S) $ (C 2 S) совпадают со значениями истинности высказываний (B _ C) 2 S,

(B ! C) 2 S, (B $ C) 2 S.

26

Если суждение A имеет один из видов B&C, :B, B _ C, B ! C, B $ C, то суждения B, C короче суждения A, и потому их значения истинности в интерпретации M совпадают со значениями истинности высказываний (B 2 S), (C 2 S). Из рассуждений предыдущего абзаца мы видим теперь, что и значения истинности суждения A и высказывания (A 2 S) совпадают, вопреки выбору суждения A.

(5) Пусть суждение A имеет вид 8xB(x). Если A 2 S, то для всех символов констант c 2 C суждения B(c), выводимые из суждения 8xB(x), принадлежат S, и, поскольку слово B(c) короче слова 8xB(x), все суждения B(c) истинны в интерпретации M. Следовательно, суждение 8xB(x) истинно в интерпретации M. Если же высказывание (A 2 S) ложно, то суждение 9x(:B(x)), равносильное суждению :A, принадлежит множеству суждений S, и, поскольку

это множество суждений экзистенциально полно, найдется символ константы c 2 C, такой что суждение :B(c) принадлежит S. Но

суждение :B(c) короче суждения A; поэтому оно истинно в интерпретации M, и, значит, суждение B(c) не истинно в интерпретации M. Следовательно, суждение A, имеющее вид 8xB(x), не истинно в M. Итак, в обоих случаях значение истинности суждения A в интерпретации M совпадает со значением истинности высказывания (A 2 S), что противоречит нашему предположению.

Двойственным образом разбирается случай, когда суждение A имеет вид 9xB(x). Если оно принадлежит S, то из экзистенциальной полноты S следует, что найдется символ константы c 2 C, такой что суждение B(c) принадлежит S; оно короче суждения A и потому истинно в интерпретации M. Следовательно, суждение 9xB(x) истинно в интерпретации M. Если же суждение A не принадлежит S, то суждение 8x(:B(x)), равносильное суждению :A, принадлежит множеству суждений S, и вместе с ним множеству S принадлежат все суждения :B(c), c 2 C. Отсюда следует, что ни одно из суждений B(c) не принадлежит S и, поскольку эти суждения короче суждения A, ни одно из них не истинно в интерпретации M. Поэтому суждение A, имеющее вид 9xB(x), не истинно в M. Снова мы получили, что значение истинности суждения A в интерпретации M совпадает со значением истинности высказывания (A 2 S).

Этим и завершается доказательство теоремы.

3. Существование максимальных непротиворечивых множеств суждений.

Теорема 2. Для всякого непротиворечивого множества суждений S 2 A(C) существует содержащее его максимальное непротиворе-

чивое множество суждений B 2 A(C).

Доказательство. Конечно, наиболее естественным при доказательстве подобных утверждений является использование леммы Цорна. Пусть M множество всех непротиворечивых множеств суждений

27

B A(C), содержащих множество S. Множество M естественным

образом упорядочено отношением включения; покажем, что оно индуктивно, то есть что любое линейно упорядоченное подмножество множества M имеет верхнюю грань, тоже принадлежащую M

Пусть fBi j i 2 Ig линейно упорядоченное подмножество M. Обозначим через B объединение всех подмножеств Bi множества A(C) (i 2 I). Множество B содержит все множества Bi, è äëÿ òîãî, чтобы показать, что B верхняя грань для семейства fBi j i 2 Ig, достаточно установить, что B 2 M, то есть что множество суж-

дений B непротиворечиво. Но это действительно так: в противном

случае нашлись бы суждения A1; : : : ; An 2 B, такие что суждение (A1& : : : &An) ! (л) выводимо; но конечное множество суждений A1; : : : ; An содержится уже в каком-то из множеств Bi, i 2 I, è, значит, это множество Bi не является непротиворечивым, то есть Bi 2= M вопреки предположению.

Итак, частично упорядоченное отношением включения множество M индуктивно, и по лемме Цорна в нем есть максимальный элемент

B. Множество B и будет максимальным непротиворечивым множеством суждений, содержащим S.

4. Существование экзистенциально полных расширений множества суждений.

Теорема 3. Для любого непротиворечивого множества суждений S A(C; P) существуют множество символов констант C0 C

малой мощности и экзистенциально полное максимальное непротиворечивое множество суждений S0 A(C0; P), содержащее S.

Доказательство. Пусть C0 = C, и пусть S0 A(C0) максимальное непротиворечивое множество суждений, содержащее S. Пусть уже

построены множество символов констант Ci и максимальное непро- тиворечивое множество суждений Si A(Ci). Обозначим через M множество всех формул A = A(x) с единственной свободной перемен-

ной x, таких что суждение 9x(A(x)) содержится в Si. Для каждого A 2 M введем новый символ константы cA и обозначим через Ci+1

множество, полученное из Ci добавлением всех новых символов констант cA, а через Si0+1 A(Ci+1) множество суждений, полученное из Si добавлением всех суждений A(cA), A 2 M.

Покажем, что множество суждений Si0+1 непротиворечиво. Если бы оно было противоречиво, то для некоторых суждений B1; : : : ; Bm 2 Si

и формул A1; : : : ; An 2 M суждение

(B1& : : : &Bm&A1(cA1 )& : : : &An(cAn )) ! (ë)

было бы выводимо. Обозначим через X суждение

(B1& : : : &Bm&(9x1(A1(x1)))& : : : &(9xn(An(xn)));

28

поскольку суждения B1,. . . ,Bm, 9x1(A1(x1)),. . . ,9(An(xn)) принадлежат множеству Si, суждение X выводимо из Si. Покажем, что суж- дение :X тоже выводимо из Si.

Из выводимости суждения

(B1& : : : &Bm&A1(cA1 )& : : : &An(cAn )) ! (ë)

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

:(B1& : : : &Bm&A1(cA1 )& : : : &An(cAn ));

которое в свою очередь эквивалентно суждению

:B1 _ _ :Bn _ :A1(cA1 ) _ _ :An(cAn )):

По правилу (6) отсюда следует выводимость суждения

8x1 : : : 8xn(:B1 _ _ :Bm _ :A1(x1) _ _ :An(xn));

из которого по другим правилам вывода получается суждение

:B1 _ _ :Bm _ :(9x1(A1(x1))) _ _ :(9(An(xn))):

По правилам исчисления высказываний последнее суждение эквивалентно суждению

:(B1& : : : &Bm&(9x1(A1(x1)))& : : : &(9xn(An(xn))));

то есть суждению :X.

Итак, предположив, что множество суждений Si0+1 противоречиво, мы нашли такое суждение X, что из Si выводимы и суждение X, и его отрицание :X, а значит, и тождественно ложное суждение X&:X.

Но это несовместимо с непротиворечивостью Si.

Таким образом, множество суждений Si0+1 A(Ci+1) непротиворе- чиво, и по теореме 2 его можно дополнить до максимального непротиворечивого множества суждений Si+1 A(Ci+1).

Обозначим теперь через C0 объединение всех множеств Ci, а через S0 A(C0) объединение всех множеств суждений Si, i = 0; 1; : : : . Покажем, что S0 экзистенциально полное и максимальное непроти-

воречивое множество суждений. Если суждение 9x(A(x)) содержит-

S0, то оно содержится уже в некотором Si, а тогда в множествеSi+1 S0 есть суждение A(cA), ãäå cA 2 Ci+1 C0. Таким об- разом, множество суждений S0 экзистенциально полно. Если бы это

множество не было максимальным непротиворечивым, то существовало бы суждение A 2 A(C0), такое что ни суждение A, ни суждение

:A не принадлежали бы S0. Но для записи суждения A используется лишь конечное число символов констант из C0, и потому существует

номер i, для которого A 2 A(Ci); по предложению 1 одно из суждений A, :A принадлежит максимальному непротиворечивому множеству

суждений Si S0, что противоречит выбору суждения A.

Из наших построений ясно, что C0 множество малой мощности. Теорема полностью доказана.

29

5. Доказательство теоремы Геделя. Теперь мы можем завершить доказательство теоремы Геделя о полноте. Пусть C A(C; P)

непротиворечивое множество суждений. По теореме 3 существует множество символов констант C0 C малой мощности и максималь-

ное непротиворечивое экзистенциально полное множество суждений S0 A(C0; P), содержащее S. Далее, по теореме 1 существует такая

интерпретация M = fM; cM ; PM g множеств C0, P, что для любого элемента m 2 M существует символ константы c 2 C0, для которого

m = cM (и потому мощность M не больше мощности C0), и суждение èç A(C0; P) истинно в M тогда и только тогда, когда оно содержится

в множестве S0. Таким образом, интерпретация M является моделью множества суждений S0

множества суждений S.

x 7. Теорема Л¼венгейма-Скулема

1. Элементарная эквивалентность. Пусть опять P, C какие-

то множества символов предикатов и констант. Две интерпретации M, N этих множеств называются элементарно эквивалентными, ес-

ли множество суждений из A(C; P), истинных в интерпретации M, совпадает с множеством суждений из A(C; P), истинных в интерпретации N.

Пусть M = fM; cM ; PM g интерпретация множества символов констант C и множества символов предикатов P, и пусть N под-

множество множества M, содержащее элементы cM äëÿ âñåõ ñèì- волов констант c 2 C. Если P 2 P символ n-местного предика-

та, то обозначим через PN пересечение множества PM Mn с n- й декартовой степенью Nn множества N; если c 2 C, то положим

cN = cM 2 N M. Набор N = fN; cN ; PN g представляет собой интерпретацию множества символов констант C и множества символов предикатов P; мы будем говорить, что N подинтерпретация интерпретации M (согласно правилам русской орфографии, следовало бы

писать подынтерпретация, но мы все же предпочт¼м вариант с и). Отметим, что подинтерпретация полностью определяется подмножеством N M, от которого требуется лишь, чтобы оно содержало все

элементы cM .

Подинтерпретация N интерпретации M называется элементарной

подинтерпретацией, если она не только элементарно эквивалентна M, но еще и удовлетворяет более сильному условию: если A(x1; : : : ; xs)любая формула (не обязательно суждение), в записи которой участвуют только символы предикатов, принадлежащие P, и символы кон-

стант, принадлежащие C, и n1; : : : ; ns любые элементы из N M, то значения истинности выражений A(n1; : : : ; ns) в интерпретациях M и N совпадают.

30