<< Пред. стр.

стр. 6
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>

эквивалентных термов). Обозначая класс термов, эквивалентных данному терму
t, за [t], положим cM := c для каждого символа предметной константы c ? Const,
?
f M ([t1 ], [t2 ], . . . , [tn ]) := [f (t1 , t2 , . . . , tn )] для каждого n-арного функционального
символа f ? Funcn ,

1, A (t1 , t2 , . . . , tn ) ? ??
AM ([t1 ] , [t2 ] , . . . , [tn ]) :=
0, иначе

для каждого n-арного предикатного символа A ? Predn , и, наконец, ?? ([x]) := [x]
для любого символа предметной переменной x ? V ar. Осталось проверить, что
данное определение корректно и действительно задает модель всех одновременно
формул множества ?? , а значит, и меньшего множества ?. Проведите эту провер-
ку самостоятельно в качестве упражнения, фактически только слегка поправляя
доказательство леммы 6.2.
48 Основы теории моделей


7 Основы теории моделей

Из самого факта существования корректных и полных формальных систем для
языков логики первого порядка следует целый ряд весьма нетривиальных выво-
дов о семантике этих языков. А именно, о том какие модели и сколько моделей (с
точностью до изоморфизма) могут иметь множества формул языков логики пер-
вого порядка. В этой главе мы рассмотрим основные нетривиальные результаты
о семантике языков логики первого порядка.


Теорема 7.1 (О семантической компактности)



(i) Множество формул ? ? L? выполнимо (то есть имеет модель) тогда и
только тогда, когда любое его конечное подмножество выполнимо.

(ii) ? логически выводит P тогда и только тогда, когда найдется такое ко-
нечное ? ? ?, что ? |= P.


Доказательство:

(i) Докажем, что если ? выполнимо, то любое его конечное подмножество вы-
полнимо. Если ? выполнимо, то существует такая интерпретация, в кото-
рой все одновременно формулы ? истинны. Значит, эта же интерпретация
является моделью любого подмножества ? ? ?. Необходимость доказана.
Теперь докажем достаточность. Пусть ? невыполнимо, а все конечные под-
множества ? выполнимы, тогда, по теореме о модели, ? несовместно, то
есть ? ?. Но, в силу определения формальной системы, найдется такое
конечное подмножество ? (листья дерева вывода псевдоформулы ?), что
? ?. По теореме о корректности естественной дедукции ? невыполнимо,
что противоречит предположению.

(ii) Для доказательства этого пункта заметим, что в силу теоремы о коррект-
ности и полноте естественной дедукции ? |= P, если и только если ? P,
последнее же, в силу определения формальной системы, возможно, если, и
только если найдется такое конечное ? ? ? (листья дерева доказательства
формулы P), что ? ND P. Снова применяя теорему о корректности и пол-
ноте естественной дедукции получаем, что последнее эквивалентно ? |= P.
49


Займемся теперь вопросом о том, какие модели и сколько разных (с точностью
до изоморфизма) моделей может иметь множество формул ? ? L? языка логики
первого порядка. Здесь и далее мы будем говорить о конечных, счетных, более
чем счетных моделях, имея в виду, соответственно, модели с конечным, счетным,
более чем счетным универсумом. Вообще под мощностью модели будем понимать
мощность универсума.

Теорема 7.2 (Лёвенгейма Скулема “сверху вниз”
или о понижении мощности модели)
Пусть множество формул ? ? L? выполнимо. Тогда оно имеет модель мощно-
сти не превышающей мощность языка.

Доказательство: Так как множество ? выполнимо, то оно совместно (в силу
теоремы о корректности естественной дедукции). Рассмотрим теперь более по-
дробно доказательство теоремы о модели. Эта теорема утверждает что любое вы-
полнимое множество имеет модель. Там модель “кроилась” из термов расширен-
ного языка L?? . В силу конструкции, #L?? ? #L? , а значит и #T ER(L?? ) ? #L? .
Таким образом, в силу конструкции, использованной в доказательстве теоремы
о модели, можно утверждать существование модели с мощностью, не превыша-
ющей #T ER(L?? ), а значит и #L? .

Теорема 7.3 (О переходе от конечной к бесконечной мощности)
Если множество формул ? ? L? выполнимо в моделях сколь угодно большой
конечной мощности, ? выполнимо и в бесконечной модели.

Доказательство: Рассмотрим ? := ? ? {P?i }? , где
i=1

P?k := ?x1 . . . ?xk (¬x1 = x2 ? ¬x2 = x3 ? . . . ? ¬x1 = xk ) . (7.1)

Заметим, что формула P?k выполнима во всех моделях, универсум которых со-
держит по меньшей мере k элементов, и только в них. В силу теоремы о ком-
пактности, для проверки выполнимости ? достаточно проверить выполнимость
любого его конечного подмножества ? ? ? . Однако, если ? ? ? конечно, то
? ? ? ? {P?i }n , для конечного n ? N. Множество ? ? {P?i }n выполнимо в
i=1 i=1
той модели ?, которая содержит не менее k элементов. Существование такой мо-
дели предполагается в условии теоремы. Следовательно, в этой же модели тем
более выполнимо и меньшее множество формул ?, а значит и ? выполнимо.
Выполнимость же ? тривиально следует из выполнимости ? .
50 Основы теории моделей


Теорема 7.4 (Лёвенгейма Скулема “снизу вверх”
или о повышении мощности модели)
Пусть ? ? L? имеет бесконечную модель. Тогда, для любого множества A, ?
имеет модель, универсум которой имеет мощность не меньше #A.

Доказательство: Дополним сигнатуру ? языка L? новыми символами кон-
стант вида ca , для всех a ? A, так, чтобы среди добавленных символов не было
бы символов исходной сигнатуры и разным элементам множества A соответство-
вали разные добавленные символы констант. Получим новую сигнатуру ? , такую
что #? ? #A. Таким образом #L? ? #A.
Рассмотрим множество ? := ? ? {¬ca = cb : a, b ? A, a = b}. Рассмотрим произ-
вольное конечное подмножество ? ? ? . В силу конечности ?, имеем

? ? ? ? {¬cai = cbj : i, j ? n}

для некоторого n ? N. По условию теоремы множество формул ? имеет модель
M с бесконечным универсумом. В этой модели закрепим за символами констант
cai элементы M таким образом, чтобы cM = cM при ai = bj . В полученной алгеб-
ai bj
раической системе все формулы множества ? будут истинны, иначе говоря, ?
выполнимо. Следовательно, по теореме о компактности, выполнимо и ? . Заме-
тим теперь, что любая модель множества ? должна иметь мощность не меньшую,
чем #A, так как в ней истинны все формулы вида ca = cb , где a, b ? A и a = b.
Но эта же модель будет автоматически и моделью меньшего множества ?, что и
завершает доказательство теоремы.
Первое весьма нетривиальное приложение доказанных утверждений к арифме-
тике Пеано отвечает на вопрос о существовании нестандартных моделей ариф-
метики.

|=
Следствие 7.1 Формальная арифметика Пеано первого порядка P AI имеет
модели, неизоморфные стандартной, в том числе и модели сколь угодно большой
мощности.

Нетривиальность данного утверждения заключается в том, что арифметика Пе-
ано первого порядка допускает бесконечное число разных версий натуральных
чисел и действий над ними, в том числе и несчетных. Предлагаем читателю са-
мому разобраться с тем, как устроен этот несчетный натуральный ряд. Автор не
может себе этого представить. Несколько успокаивает то, что доказанные теоре-
мы неконструктивны, поскольку они опираются на теорему о модели, для доказа-
тельства которой существенно использовалась аксиома выбора. Таким образом,
51


как и в теореме о модели модель совместного множества формул, существование
которой утверждается в теореме, не может быть предъявлена в силу неконструк-
тивности доказательства, так и здесь “странные” модели, существование которых
утверждается теоремами Левенгейма–Скулема далеко не всегда могут быть яв-
ным образом сконструированы.
Интересно также сравнить утверждения следствия с теоремой Дедекинда для
арифметики Пеано второго порядка. Приведенное следствие позволяет догадать-
ся, что языки логики первого порядка обладают намного меньшей выразительной
силой, например, охарактеризовать модель с точностью до изоморфизма при по-
мощи аксиом языка логики первого порядка (как это было для языков второго
порядка) невозможно. Действительно, по теореме Левенгейма–Скулема, любое
множество аксиом для арифметических формул арифметики первого порядка,
если только оно выполнимо в стандартной модели, будет выполнимо и в моделях
со сколь угодно большими мощностями.


Теорема 7.5 (Лёвенгейма Скулема Тарского) Пусть ? ? L? имеет бес-
конечную модель, пусть A произвольное множество, такое что #A ? #L? (то
есть #A не меньше мощности языка). Тогда ? имеет модель с универсумом,
равномощным A.


Доказательство: Дополним сигнатуру ? новыми символами констант вида
ca для каждого a ? A, таким образом, чтобы разные элементам множества A
соответствовали разным символам констант. Обозначим

? = ? ? {ca : a ? A}

? = ? ? {¬ca = cb : a, b ? A, a = b} ,
заметим, что ? ? L? . Множество ? в силу предположения имеет бесконечную
модель, следовательно, по теореме Левенгейма-Скулема “снизу вверх”, оно име-
ет модель мощности, превосходящей #A. Иначе говоря, в универсуме найдется
достаточное количество различных элементов, которые можно поставить в со-
ответствие новым константам вида ca , чтобы таким образом получить модель
множества ? .
Поскольку множество ? , таким образом, выполнимо, у него найдется модель
(M, ?), такая что #M < #L? . С другой стороны, #M ? #A, поскольку в
(M, ?) истинны все формулы вида ¬ca = cb , где a, b ? A, a = b. Таким образом,
получим
#A ? #M ? #L? ? #A,
52 Основы теории моделей


иначе говоря #M = #A.
Обратимся ещё раз к вопросу о моделях формальной арифметики Пеано первого
порядка, неизоморфных стандартной. Существование таких моделей уже утвер-
ждалось в следствии 7.1. Сейчас мы докажем несколько более сильное утвер-
ждение, а именно, что формальная арифметика Пеано первого порядка имеет
счетную модель, неизоморфную стандартной.

Теорема 7.6 Существует счетная нестандартная модель арифметики Пеано
|=
первого порядка P AI .

Доказательство:
Дополним формальную арифметику Пеано всеми формулами вида ¬x = n, где
1 := s(0), 2 := s(1), n := s(n ? 1), а именно, определим
|=
? := P AI ? {¬x = n}? ,
n=0


где x – символ предметной переменной. Докажем выполнимость ? , для чего вос-
пользуемся теоремой о компактности. Рассмотрим произвольное конечное под-
множество ? ? ? . Имеем
|=
? ? P AI ? {¬x = n}k
n=0

для некоторого конечного k ? N. Очевидно, что множество {¬x = n}k имеет
n=0
модель (N , ?), где ?(x) := k + 1, а N – стандартная модель арифметики. Эта же
интерпретация является, тем более, и моделью меньшего множества ?. Мы до-
казали, таким образом, выполнимость любого конечного ? ? ? , а значит, в силу
теоремы о компактности, и выполнимость ? . Рассмотрим модель ? , существова-
ние которой мы только что доказали. Она не может быть конечной в силу того,
что в ней должны быть одновременно истинны (P A1 ) и (P A2 ), то есть долж-
на существовать инъективная, но не сюръективная функция, определенная на
универсуме этой модели. Следовательно, по теореме Левенгейма-Скулема “свер-
ху вниз” найдется и счетная модель (M, ?) множества ? (она не может быть
конечной по той же причине).
Осталось доказать, что M неизоморфна N , то есть не существует биекции ?
между натуральным рядом и универсумом M. Предположим, что она существу-
ет, а именно, существует биекция ? : N > M , такая, что и для любого терма n
выполнено ? nN = nM . Тогда ? (x) ? Im (?), иначе в данной модели не была бы
/
верна одна из формул вида ¬x = k, но последнее противоречит сюрьективности
?. Следовательно, M неизморфна N .
53


В отличие от результатов, сформулированных в следствии 7.1, утверждение тео-
ремы 7.6 можно сравнительно легко проинтерпретировать. А именно, “версия”
натурального ряда, существование которой утверждается в этой теореме, вы-
глядит следующим образом. Сначала идут “обычные” натуральные числа, затем
идет число ? M (x), которое не следует ни за каким “обычным” натуральным чис-
лом (заметим, что в стандартной модели таким свойством обладает только число
0). И далее, вслед за числом ? M (x) идут числа sM (? M (x)), sM (sM (? M (x))) . . . Та-
ким образом, естественно считать такого рода числа, которые в этой “версии”
натурального ряда находятся “правее” всех “обычных” натуральных чисел, бес-
конечно большими (они “больше” любого “обычного” натурального числа). На
основе полученного таким образом натурального ряда можно построить, также
как это делается с использованием привычного нам натурального ряда N, новую
версию целых, рациональных и вещественных чисел. Естественно, что в постро-
енной таким образом версии вещественной оси найдутся как бесконечно большие,
так и бесконечно малые числа (соответственно большие и меньшие по модулю
всех “обычных” вещественных чисел). Использовать такую “необычную” ( при-
нято говорить нестандартную) версию чисел очень удобно для альтернативного
построения математического анализа. Например, с использованием нестандарт-
ной вещественной оси можно “изгнать” из анализа “неудобоваримые” определения
предела, бесконечно малой величины, а пользоваться лишь бесконечно малыми
числами. При этом все определения, которые обычно даются с использованием
достаточно тяжелого “языка , ?” существенно упрощаются. Математический ана-
лиз, построенный при помощи этого подхода, называется нестандартным ана-
лизом.



8 Сравнение языков логики разных порядков

Сформулированные нами в предыдущей главе результаты о моделях множества
формул языков логики первого порядка позволяют получить нетривиальные вы-
воды о сравнении выразительной силы логических языков. Начнем со следую-
щего простого вопроса: можно ли при помощи формул языка логики первого
или второго порядка охарактеризовать свойство модели быть конечной? Строгая
постановка этого вопроса такова:


Вопрос 1 Cуществует ли множество формул языка логики первого (соответ-
ственно, второго) порядка, истинное во всех конечных моделях и только в них?
Напомним, что, говоря о мощности модели, мы имеем в виду мощность со-
ответствующего универсума. То есть модель называется конечной (счетной,
54 Сравнение языков логики разных порядков


не более чем счетной), если соответствующим свойством обладает универсум
модели.


Ответ на заданный выше вопрос для языков логики первого порядка, очевидно,
отрицательный вследствие теоремы 7.3: если множество формул верно во всех
конечных моделях, то оно будет иметь и бесконечную модель. В то же время в
языке логики второго порядка данный факт можно выразить всего лишь одним
предложением:


P?n := ?f (?x?y (f (x) = f (y) > x = y) > ?x?y (x = f (y)))

Здесь использован квантор всеобщности по “функциональной переменной”, а
именно, данная формула “говорит”, что во всех моделях, в которых она истин-
на, любая инъекция является сюръекцией. Это и означает, что в универсуме
модели данной формулы не может быть бесконечного числа элементов. Стоит
напомнить, что, строго говоря, согласно нашему определению, в алфавите языка
логики второго порядка нет специальных символов для функциональных пере-
менных, а есть только символы для предикатных переменных, поэтому формулу
P?n нужно понимать как сокращенную запись формулы

?F (f unc(F ) ? ?x?y?z(F (x, z) ? F (y, z) > x = y) > ?x?y(F (y, x))),

где
f unc(F ) := ?x?!y F (x, y),
(иначе говоря, формула f unc(F ) “говорит” о том, что отношение, записанное
символом предикатной переменной F , является графиком функции)
Вопрос, аналогичный вопросу 1, можно сформулировать и для других свойств
модели, например, для свойства модели быть не более чем счетной. А именно:

Вопрос 2 Cуществует ли множество формул языка логики первого (соответ-
ственно второго) порядка, истинное во всех не более чем счетных моделях и
только в них?

Опять-таки, ответ на этот вопрос для языков логики первого порядка отрица-
тельный в силу теоремы Левенгейма–Скулема–Тарского 7.5, а именно, если у
множества формул есть счетная модель, то у него есть и модель сколь угодно
большой мощности. В то же время, для языков логики второго порядка можно
55


охарактеризовать свойство модели быть не более чем счетной одним предложе-
нием, а именно, предложением

Pcount := ?z?f ?X (X (z) ? ?x (X (x) > X (f (x))) > ?x (X (x)))

Здесь f снова символ “функциональной переменной”, которая, строго говоря, в
силу нашего определения, в языке логики второго порядка отсутствует, так что
формулу Pcount нужно понимать как сокращенную запись другой формулы, в ко-
торой вместо символа f присутствует символ предикатной переменной. Запиши-
те соответствующую формулу самостоятельно, по аналогии с тем, как это было
сделано для формулы Pf in .
Можно предъявить сколь угодно много свойств моделей, которые не могут быть
охарактеризованы никакими формулами языков логики первого порядка, но мо-
гут быть легко охарактеризованы формулами языков логики второго порядка.
Например, формула Pcount ? ¬Pf in характеризует свойство модели быть счетной.
В то же время соответствующее свойство не может быть охарактеризовано фор-
мулами языка логики первого порядка.

Упражнение 8.1 Напишите предложение, которое характеризует свойство
модели иметь более чем счетный универсум, иначе говоря, предложение, кото-
рое было бы верно во всех более чем счетных моделях и только в них. Можно ли
охарактеризовать соответствующее свойство при помощи языка логики пер-
вого порядка с не более чем счетным алфавитом? С любым алфавитом?

Любопытно отметить, что, тем не менее, свойство модели иметь заданное конеч-
ное число элементов может быть охарактеризовано и при помощи языка логики
первого порядка. Например формула ?x?y(x = y) верна во всех моделях, уни-
версум которых содержит ровно один элемент, и только в них.

Упражнение 8.2 На языке логики первого порядка напишите предложения,
характеризующие свойства модели иметь не более чем k элементов (k – задан-
ное число), ровно k элементов, не менее чем k элементов.

Приведенных рассуждений вполне достаточно, чтобы сформулировать следую-
щие весьма сильные утверждения.

Теорема 8.1 Для языков логики второго порядка теорема о компактности
неверна.
56 Сравнение языков логики разных порядков


Доказательство: Предположим противное и рассмотрим множество формул

? := P?n ? {P?k }? ,
k=1

где формулы P?k определены в (7.1). Пусть ? ? ? конечно, тогда

? ? P?n ? {P?k }m
k=1

для некоторого конечного m ? N. Однако последнее множество формул истинно
в любой модели, универсум которой имеет хотя бы m элементов, а значит, выпол-
нимо и множество формул ?. Тогда, в силу предположения о верности теоремы
о компактности и произвольности подмножества ? заключаем, что множество ?
также является выполнимым. Но тогда в модели ? должно быть не менее чем k
элементов для любого k ? N (так как в этой модели истинны все формулы P?k ).
И в то же время число элементов этой модели должно быть конечно, так как в
ней верна формула Pf in . Так как одновременно эти два условия невыполнимы,
то мы пришли к противоречию.


Теорема 8.2 Для языков логики второго порядка неверны теоремы Левенгей-
ма–Скулема о повышении мощности модели 7.4 и о понижении мощности мо-
дели 7.2.


Доказательство: Если бы для языков логики второго порядка была верна тео-
рема Левенгейма–Скулема о повышении мощности модели, то нельзя было бы на-
писать множество формул, выражающее счетность модели. Если бы для языков
логики второго порядка была верна теорема Левенгейма–Скулема о понижении
мощности модели, то нельзя было бы написать множество формул, выражающее
более чем счетность модели.
Завершим эту главу наиболее сильным, на наш взгляд, результатом.


Теорема 8.3 Для логики второго порядка не существует одновременно полной
и корректной формальной системы.


Доказательство: Предположение о существовании одновременно корректной
и полной формальной системы влечет справедливость теоремы о компактности
(в доказательстве теоремы о компактности для языков логики первого поряд-
ка использовался лишь факт существования одновременно корректной и полной

<< Пред. стр.

стр. 6
(общее количество: 9)

ОГЛАВЛЕНИЕ

След. стр. >>