Понятие о теории моделей

Л е к ц и я 10

Теория моделей возникла на стыке между алгеброй и математической логикой. Она занимается в основном изучением таких свойств классов алгебраических систем, которые могут быть записаны формулами какого-либо логического исчисления (чаще всего, исчисления предикатов). При этом сами алгебраические системы изучаемого класса становятся интерпретациями или моделями соответствующего исчисления. Из анализа связей между формальным языком (формальными выводами, доказательствами и т.п.) и его интерпретациями черпает теория моделей и главные средства исследований. В самостоятельную область математики теория моделей выделилась в 50-е годы XX века благодаря работам Мальцева, Тарского, Геделя, Левенгейма, Скулема, Биркгофа и др.

К настоящему моменту теория моделей является достаточно развитой областью математики со своей проблематикой и собственными методами исследований. Многие из разработанных в ней методов успешно используются в других областях математики.

С некоторыми такими методами мы познакомимся в данной лекции.

Предварительно сделаем одно замечание о предикате равенства и дадим несколько определений. Пусть К — некоторый класс алгебраических систем сигнатуры σ. Тогда можно построить язык логического исчисления в сигнатуре σ и записать свойства систем из класса К формулами полученного исчисления. Однако формализация свойств систем зачастую существенно облегчается, если в сигнатуру исчисления ввести еще двухместный предикат равенства «=». Полученную сигнатуру будем обозначать в виде σ^. Сразу отметим, что, введя предикат равенства, мы должны пополнить и систему аксиом исчисления, введя в нее аксиомы, характеризующие предикат равенства. В качестве таких аксиом выбираются формулы:

" x (x = x),

" x ₁, x ₂ (x ₁ = x ₂ ® x ₂ = x ₁),

" x ₁, x ₂, x ₃ (x ₁ = x ₂ & x ₂ = x ₃ ® x ₁ = x ₃),

характеризующие отношение равенства как отношение эквивалентности, а также все формулы вида

" x ₁, …, x_k, y ₁, …, y_k (x ₁ = y ₁ & … & x_k =

= y_k ® h (x ₁, …, x_k) = h (y ₁, …, y_k));

" x ₁, …, x_n, y ₁,…, y_n (x ₁ = y ₁ & … & x_n = = y_n ® (p (x ₁, …, x_n) = p (y ₁, …, y_n))),

где h — функциональный, а р — предикативный символы из σ. Последние формулы характеризуют согласованность отношения равенства со всеми предикатами и операциями из σ. Ниже мы будем рассматривать лишь исчисления с равенством и аксиомы равенства будут автоматически включаться в соответствующие системы аксиом.

Определение 10.1. Пусть K — класс алгебраических системсигнатуры σ. Множество замкнутых формул исчисления предикатов сигнатуры σ^, истинных во всех системах из K, называется элементарной теорией класса K и обозначается th(K) или th(А), если K состоит из одной алгебраической системы А.

Например, можно говорить об элементарной теории арифметики натуральных чисел, об элементарной теории групп, об элементарной теории конечных полей и т.д. Заметим, что слово «элементарная» в термине «элементарная теория» объясняется тем, что любая формула исчисления предикатов выражает свойства систем через указание связей между их элементами, поскольку кванторы навешиваются лишь на предметные переменные.

Задача описания элементарной теории th(K) для разных классов K является важнейшей задачей теории моделей. В частности, теория th(K) является разрешимой, если существует алгоритм, позволяющий для любой формулы исчисления в сигнатуре σ^ выяснить, содержится она в th(K) или нет. В противном случае элементарная теория называется неразрешимой. В решении вопросов о разрешимости или неразрешимости элементарных теорий теория моделей смыкается с теорией алгоритмов, которая будет изучаться в последующих лекциях.

Определение 10.2. Пусть F — произвольное множество формул исчисления предикатов сигнатуры σ^. Алгебраическая система А сигнатуры σ, на которой истинны все формулы из F, называется моделью для F, что записывается в виде

А ╞═ F.

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

В связи с этим укажем на одну из долго стоящих и широко известных проблем А. Тарского (проблему о полноте для элементарной теории свободных групп): будут ли элементарно эквивалентными свободные группы рангов m и n при m > n > 1.

Определение 10.3. Класс К алгебраических систем сигнатуры σ называется аксиоматизируемым (конечно аксиоматизируемым), если существует такое множество (конечное множество) формул F исчисления предикатов сигнатуры σ^, что А Î К Û А ╞═ F. При этом множество F называется системой аксиом класса К.

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

1. Класс всех групп в сигнатуре σ = <·, 1> конечно аксиоматизируем. Системой аксиом может служить множество формул A_gr:

1) " x ₁, x ₂, x ₃ ((x ₁ · x ₂) · x ₃ = x ₁ · (x ₂ · x ₃)),

2) " x ₁ (x ₁ · 1 = x ₁),

3) " x ₁ $ x ₂ (x ₁ · x ₂ = 1).

Добавление к ним формулы

4) " x ₁, x ₂ (x ₁ · x ₂ = x ₂ · x ₁)

приводит к аксиоматике класса всех абелевых групп.

2. Класс всех полей в сигнатуре σ = <+, ·, 0, 1> конечно аксиоматизируем. Его система аксиом A_f может быть получена добавлением к аксиомам абелевых групп в сигнатуре <+, 0>, выписанных в примере 1, формул 1, 2, 4, характеризующих коммутативные полугруппы с единицей, и формулы

" x ₁ (x ₁ ¹ 0 ® $ x ₂(x ₁ · x ₂ = 1)).

Добавив к системе аксиом A_f еще аксиому

,

(р — простое число), мы выделим из всех полей класс полей характеристики р.

Класс полей характеристики 0 задается системой аксиом, полученных добавлением к системе А_f отрицаний аксиом Ф _p по всем простым числам р. Эта система аксиом бесконечна. Можно доказать, что класс полей характеристики 0 не является конечно аксиоматизируемым.

3. Арифметику натуральных чисел можно рассматривать как алгебру сигнатуры σ _A = {+, ·, `, 1}, где «`» есть символ унарной операции. Объединяя систему аксиом Пеано с требованием к операциям сложения и умножения по Грассману, получим следующую систему аксиом — формул:

" x ₁(x ₁` = 1),

" x ₁, x ₂ (x ₁ = x ₂ ® x ₁` = x <sub>2</sub>`),

" x ₁, x ₂ (x ₁` = x <sub>2</sub>` ® x ₁ = x ₂),

" x ₁ (x ₁ + 1 = x `),

" x ₁, x ₂ (x ₁ + x ₂`) = (x <sub>1</sub> + x <sub>2</sub>)`,

" x ₁(x ₁ · 1 = x ₁),

" x ₁, x ₂ (x ₁ · x ₂` = x ₁ · x ₂ + x ₁),

A (1) &" x ₁(A (x ₁) ® A (x ₁`)) ® " yA (y),

где А — произвольная формула сигнатуры σ _A.

Пусть K — произвольный аксиоматизируемый класс алгебраических систем сигнатуры σ, и А — его система аксиом. Тогда, добавив к аксиомам исчисления предикатов аксиомы равенства и все аксиомы из А, мы построим новое логическое исчисление α _К. В нем, как и в изученном нами исчислении предикатов α, можно определить понятия формулы, выводимой из заданной системы формул, доказуемой формулы и т.д.

Алгебраические системы класса К будут являться такими интерпретациями исчисления α _К, в которых истинны все формулы из А, т.е. будут моделями множества А. Для исчисления α _К, как и для исчисления α, доказывается следующая теорема о полноте. Если Ф — замкнутая формула исчисления α _К, то

Ф Î th(K) Û	├─ Ф.
	α К

Эту теорему, с одной с стороны, можно использовать для проверки истинности формулы Ф на системах класса K, а с другой стороны, из нее следует ряд общих методов получения утверждений об алгебраических системах. Один из этих методов, называемый методом компактности, основан на локальной теореме Мальцева для любого исчисления α _К, называемой также теоремой компактности.

Множество формул исчисления α _К выполнимо тогда и только тогда, когда выполнимо любое его конечное подмножество.

Первые примеры по применению этой теоремы были указаны в теории групп самим Мальцевым. Ниже мы приводим один его результат.

Пусть G — группа и G ₂ < G ₁ < G. Охарактеризуем сначала формулами утверждения:

1. G_i < G – G_i — подгруппа группы G.

2. G ₂ < G ₁.

3. G ₂ G ₁ – G ₂ — нормальный делитель группы G ₁.

4. — факторгруппа.

С этой целью введем на G два одноместных предиката R ₁ и R ₂, положив:

R_i (x) = и Û x Î G_i, i = 1, 2.

Тогда утверждения 1 – 3 запишутся формулами:

" x ₁, x ₂, x ₃(R_i (x ₁) R_i (x ₂)(x ₂ x ₃ = 1) ® R_i (x ₁ x ₃)),

" x (R ₂(x) ® R ₁(x)),

" x ₁, x ₂, x ₃(R ₁(x ₁) R ₂(x ₂)(x ₁ x ₃ = 1) ® R ₂(x ₃ x ₂ x ₁)).

На элементы фактор-группы можно смотреть как на элементы группы G ₁, определив иначе предикат равенства E (x, y) элементов x, y из G ₁ (как принадлежность их к одному смежному классу по G ₂):

E (x ₁, x ₂) Û $ x ₃(R ₂(x ₃)(x ₃ x ₂ = x ₁)).

И несколько иначе, чем в G ₁ определим операцию «°» умножения элементов из G ₁

x ₁ ° x ₂ = x ₃ Û $ x ₄ (R ₂(x ₄)(x ₁ x ₂ = x ₃ x ₄)).

Легко видеть, что операция «°» определена корректно, и если какое-либо групповое свойство Р группы G ₁ выражено формулой В в сигнатуре σ = { R ₁, R ₂, =, ·, 1}, то, заменив в В предикат «=» на Е и операцию · на °, мы получим формулу Р *, выражающую групповое свойство факторгруппы (т.е. если Р истинна на G ₁, то Р * истинна на ).

Пусть теперь Р = [ P ₁, …, P_k ] — набор свойств группы G, записываемых конечными системами замкнутых формул и сохраняющихся при переходе к подгруппам.

Пусть группа G имеет тип Р, т.е. в ней существует нормальный ряд

(10.1)

такой, что обладает свойством P_i, i = 1, …, k.

Как и выше, введем на группе G одноместные предикаты R ₁, R ₂, …, R_k, характеризующие подгруппы G ₁, G ₂, …, G_k и образуем множество формул А_G в сигнатуре σ₁, состоящей из предикатов R ₁, R ₂, …, R_k, «=», бинарной операции · и нуль-арных операций, отвечающих всем элементам группы G, т.е. всех констант из группы G, включив в него:

1) систему аксиом А_gr;

2) формулы " x ₁, x ₂ (x ₁ = x ₂ ® R_i (x ₁) = R_i (x ₂));

3) формулы, характеризующие утверждения , i = = 0, …, k – 1;

4) формулу " x (R_k (x) ® x = 1), утверждающую, что G_k = 1;

5) формулы для записи того факта, что фактор-группа обладает свойством Р_i.

Введем еще для группы G систему формул D (G), называемую диаграммой группы G. Для любых элементов g_i, g_j, g_r Î G D (G) содержит формулу g_ig_j = g_r, если она истинна в G, и формулу g_ig_j ¹ g_r — в противном случае. Объединение систем А_G и D (G) обозначим через K_G.

Очевидно, что G имеет тип Р тогда и только тогда, когда множество формул K_G выполнимо, т.е. имеет модель.

Теорема 10.4. Если каждая конечно порожденная подгруппа H < G имеет тип Р, то и G имеет тип Р.

Доказательство. Согласно локальной теореме Мальцева для выполнимости множества формул K_G достаточно доказать выполнимость любого его конечного подмножества. При этом из конечных систем достаточно рассматривать лишь подсистемы, содержащие А_G.

Итак, пусть D ` — конечная подсистема из D (G), G ` — множество элементов из G, участвующих в соотношениях из D `, и Н — подгруппа в G, порожденная множеством G `. Так как Н — подгруппа типа Р, то множество формул А_G U D (H), а потому и А_G È D 1’ выполнимо, и теорема доказана.

Дата добавления: 2014-12-29