Теория моделей

Теория моделей — раздел математической логики, который занимается изучением связи между формальными языками и их интерпретациями, или моделями. Название теория моделей было впервые предложено Альфредом Тарским в 1954 году. Основное развитие теория моделей получила в работах Тарского, Мальцева и Робинсона.

История возникновения

Теория моделей посвящена изучению фундаментальной взаимосвязи между синтаксисом и семантикой. При этом, первому в ней отвечает формальный язык, а второму — модель — математическая структура, допускающая некоторое описание этим языком. Теория моделей возникла как обобщение существующих подходов решения метаматематических проблем, связанных с алгеброй и математической логикой. Сами эти подходы существовали давно, но при этом долгое время не рассматривались во всей своей общности, в рамках единой логико-философской парадигмы. Естественным примером в этом контексте является проблема, связанная с пятым постулатом Евклида о параллельности линий. Веками математикам не удавалось доказать его истинность, пока в XIX веке Бойяи и Лобачевский не построили неевклидову геометрию, показав тем самым, что постулат параллельности не может быть ни доказан, ни опровергнут. С точки зрения теории моделей, это означает, что система аксиом без пятого постулата допускает несколько различных моделей, то есть в этом случае — несколько вариантов реализации геометрии.

Таким образом, первоначальная теория моделей выросла из таких разделов математики как логика, универсальная алгебра, теория множеств в качестве обобщения и укрупнения существующих знаний. Поэтому первые результаты теории моделей появились задолго до её «официального» возникновения. Первым таким результатом принято считать теорему Лёвенгейма — Сколема (1915). Другим крупным результатом стала теорема компактности, доказанная Гёделем (1930) и Мальцевым (1936).

Классическая теория моделей первого порядка

Теория моделей для классической логики первого порядка является исторически первым и наиболее развитым примером теоретико-модельного подхода. В роли моделей здесь выступают множества, представляющие область возможных значений переменных. Функциональные символы интерпретируются как операции соответствующей арности над ними, а предикаты — как отношения (более подробно, см. Логика первого порядка, интерпретация).

Теорема компактности

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

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

Из теоремы компактности следует, что некоторые понятия не являются выразимыми в логике первого порядка. Например, понятия конечности или счётности не могут быть выражены никакими формулами первого порядка и даже их множествами: если множество формул имеет сколь угодно большие конечные модели, то оно имеет и бесконечную модель. Аналогично, теория, имеющая бесконечную модель, мощность которой не меньше мощности сигнатуры, имеет модели и любой большей мощности.

Теорема компактности находит применение для конструирования нестандартных моделей классических теорий, например, элементарной арифметики или математического анализа.

Теории и элементарная эквивалентность

Теория [math]\displaystyle{ T }[/math] — это замкнутое относительно выводимости (сокращённо, замкнутое ) множество формул, то есть, такое множество [math]\displaystyle{ T }[/math], что если формула [math]\displaystyle{ \varphi }[/math] следует из [math]\displaystyle{ T }[/math], то [math]\displaystyle{ \varphi }[/math] принадлежит [math]\displaystyle{ T }[/math].

Теория, имеющая хотя бы одну модель, называется непротиворечивой, остальные теории — противоречивыми.

Теория [math]\displaystyle{ T }[/math] называется полной, если для любой формулы [math]\displaystyle{ \varphi }[/math] теория содержит [math]\displaystyle{ \varphi }[/math] или [math]\displaystyle{ \lnot\varphi }[/math]. Если [math]\displaystyle{ A }[/math] — алгебраическая система, то множество истинных на [math]\displaystyle{ A }[/math] замкнутых формул образует полную теорию — теорию системы [math]\displaystyle{ A }[/math], обозначаемую с помощью [math]\displaystyle{ Th(A) }[/math].

Если на алгебраических системах [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] истинны одни и те же замкнутые формулы, то [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] называются элементарно эквивалентными. Таким образом, [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] элементарно эквивалентны тогда и только тогда, когда они являются моделью одной и той же полной теории.

Если полная теория [math]\displaystyle{ T }[/math] имеет конечную модель [math]\displaystyle{ A }[/math], то все модели теории [math]\displaystyle{ T }[/math] изоморфны [math]\displaystyle{ A }[/math], в частности, все они содержат такое же количество элементов. Следовательно, для конечных алгебраических систем понятия элементарной эквивалентности и изоморфизма совпадают.

Подсистемы и теоремы Лёвенгейма — Скулема

Алгебраическая система [math]\displaystyle{ B }[/math] называется подсистемой алгебраической системы [math]\displaystyle{ A }[/math], если [math]\displaystyle{ |B|\subseteq|A| }[/math] и интерпретация каждого сигнатурного символа в [math]\displaystyle{ B }[/math] является ограничением его же интерпретации в [math]\displaystyle{ A }[/math] на множество [math]\displaystyle{ |B| }[/math]. Подсистема называется элементарной, если для любой формулы [math]\displaystyle{ \varphi(x_1,\;\ldots,\;x_n) }[/math] и для любых [math]\displaystyle{ b_1,\;\ldots,\;b_n\in |B| }[/math] выполнено: [math]\displaystyle{ A\models\varphi(b_1,\;\ldots,\;b_n) }[/math] тогда и только тогда, когда [math]\displaystyle{ B\models\varphi(b_1,\;\ldots,\;b_n) }[/math]. Система [math]\displaystyle{ A }[/math] называется в этих случаях (элементарным) расширением системы [math]\displaystyle{ B }[/math].

Элементарная подсистема [math]\displaystyle{ B }[/math] элементарно эквивалентна [math]\displaystyle{ A }[/math]. Теории, для моделей которых верно и обратное — каждая элементарно эквивалентная подсистема является элементарной — называются модельно полными. Модельная полнота теории [math]\displaystyle{ T }[/math] эквивалентна каждому из следующих свойств:

• любая формула в [math]\displaystyle{ T }[/math] эквивалентна экзистенциальной формуле,
• любая формула в [math]\displaystyle{ T }[/math] эквивалентна универсальной формуле,
• объединение [math]\displaystyle{ T }[/math] с диаграммой любой модели порождает полную теорию.

Если [math]\displaystyle{ X\subseteq|A| }[/math] — непустое множество, то среди всех подсистем [math]\displaystyle{ A }[/math], включающих [math]\displaystyle{ X }[/math], существует наименьшая, которая называется порождённой множеством [math]\displaystyle{ X }[/math]. Для элементарных подсистем в общем случае такое утверждение неверно.

Говорят, что теория [math]\displaystyle{ T }[/math] имеет термальные скулемовские функции, если для каждой формулы [math]\displaystyle{ \varphi(x,\;\bar y) }[/math] существует терм [math]\displaystyle{ t_\varphi(\bar y) }[/math] и из теории [math]\displaystyle{ T }[/math] следует формула [math]\displaystyle{ (\forall\bar y)((\exists x)\varphi(x,\;\bar y)\to \varphi(t_\varphi(\bar y),\;\bar y)) }[/math]. Иначе говоря, если существует элемент, на котором формула [math]\displaystyle{ \varphi(x,\;\bar y) }[/math] истинна, то в качестве этого элемента может быть взято [math]\displaystyle{ t(\bar y) }[/math]. Если теория имеет термальные скулемовские функции, то она модельно полна. Каждая теория [math]\displaystyle{ T }[/math] имеет расширение [math]\displaystyle{ T^s }[/math], имеющее термальные скулемовские функции. При этом каждая модель [math]\displaystyle{ A }[/math] теории [math]\displaystyle{ T }[/math] может быть обогащена до модели [math]\displaystyle{ A^s }[/math] теории [math]\displaystyle{ T^s }[/math].

Теорема Лёвенгейма — Скулема «вверх» утверждает, что если [math]\displaystyle{ A }[/math] — алгебраическая система мощности не меньше [math]\displaystyle{ \alpha=|Th(A)| }[/math], то [math]\displaystyle{ A }[/math] имеет элементарные расширения любой мощности больше или равной [math]\displaystyle{ \alpha }[/math].

Теорема Лёвенгейма — Скулема «вниз»: если [math]\displaystyle{ A }[/math] — алгебраическая система мощности [math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta=|Th(A)| }[/math], то [math]\displaystyle{ A }[/math] имеет элементарные подсистемы любой мощности между [math]\displaystyle{ \beta }[/math] и [math]\displaystyle{ \alpha }[/math].

Аксиоматизируемость и устойчивость

Множество формул [math]\displaystyle{ A }[/math] называется множеством аксиом для теории [math]\displaystyle{ T }[/math], если [math]\displaystyle{ T }[/math] является множеством следствий [math]\displaystyle{ A }[/math]. В частности, сама [math]\displaystyle{ T }[/math] является множеством аксиом для себя. Если для теории [math]\displaystyle{ T }[/math] существует конечное множество аксиом, то она называется конечно аксиоматизируемой.

Совокупности алгебраических систем называют классами. Класс алгебраических систем [math]\displaystyle{ K }[/math] называется аксиоматизируемым, если он является совокупностью моделей некоторой теории [math]\displaystyle{ T }[/math]. В этом случае множество аксиом для [math]\displaystyle{ T }[/math] называется также множеством аксиом для [math]\displaystyle{ K }[/math]. Класс [math]\displaystyle{ K }[/math] конечно аксиоматизируем тогда и только тогда, когда аксиоматизируемы сам [math]\displaystyle{ K }[/math] и его дополнение.

Теория [math]\displaystyle{ T }[/math] называется устойчивой относительно надсистем (соответственно, подсистем), если для любой алгебраической системы [math]\displaystyle{ A }[/math] из [math]\displaystyle{ A\models T }[/math] и [math]\displaystyle{ B\subseteq A }[/math] (соответственно, [math]\displaystyle{ A\subseteq B }[/math]) следует, что [math]\displaystyle{ B\models T }[/math]. Теория [math]\displaystyle{ T }[/math] устойчива относительно подсистем тогда и только тогда, когда она аксиоматизируема посредством универсальных формул. Теория [math]\displaystyle{ T }[/math] устойчива относительно надсистем тогда и только тогда, когда она аксиоматизируема посредством экзистенциальных формул.

Теория [math]\displaystyle{ T }[/math] называется устойчивой относительно гомоморфизмов, если для любой алгебраической системы [math]\displaystyle{ A }[/math] из [math]\displaystyle{ A\models T }[/math] следует, что [math]\displaystyle{ B\models T }[/math], если [math]\displaystyle{ B }[/math] — гомоморфный образ [math]\displaystyle{ A }[/math]. Теория [math]\displaystyle{ T }[/math] устойчива относительно гомоморфизмов тогда и только тогда, когда она аксиоматизируема посредством позитивных формул (то есть формул, не содержащих импликацию и отрицание).

Цепи

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

Объединение цепи алгебраических систем даёт новую систему той же сигнатуры, которая будет надсистемой для всех элементов цепи. При объединении элементарной цепи это объединение будет элементарной надсистемой и, следовательно, в нём будет сохраняться истинность всех формул.

При объединении любых цепей (в том числе неэлементарных) сохраняется истинность [math]\displaystyle{ \forall\exists }[/math]-формул, верно и обратное — если формула сохраняет свою истинность при объединении любых цепей, то она эквивалентна некоторой [math]\displaystyle{ \forall\exists }[/math]-формуле.

Теории, которые могут быть аксиоматизируемы посредством [math]\displaystyle{ \forall\exists }[/math]-формул называются индуктивными. Согласно теореме Ченя — Лося — Сушко теория [math]\displaystyle{ T }[/math] является индуктивной тогда и только тогда, когда она устойчива относительно объединения цепей. Важный пример индуктивной теории — теория полей фиксированной характеристики.

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

Ультрапроизведения

Пусть [math]\displaystyle{ L }[/math] — язык. [math]\displaystyle{ \{\mathcal{A}_i\}_{i\in I} }[/math] — семейство алгебраических систем, [math]\displaystyle{ \mathcal{A}_i=\langle M_i,\;L\rangle }[/math]. Прямым произведением алгебраических систем [math]\displaystyle{ \mathcal{A}_i }[/math], [math]\displaystyle{ i\in I }[/math], называется алгебраическая система [math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i=\left\langle\prod_{i\in I}A_i,\;L\right\rangle }[/math], где для каждого предикатного символа [math]\displaystyle{ P\in L }[/math]

[math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i\models P(a_1,\;\ldots,\;a_{n_P})\Leftrightarrow\mathcal{A}_i\models P(a_{1i},\;\ldots,\;a_{n_Pi}) }[/math] для каждого [math]\displaystyle{ i \in I }[/math];

для каждого функционального символа [math]\displaystyle{ f\in L }[/math]

[math]\displaystyle{ (f(a_1,\;\ldots,\;a_{n_f}))_i=f(a_{1i},\;\ldots,\;a_{n_fi}) }[/math]

и для каждого константного символа [math]\displaystyle{ c\in L }[/math]

[math]\displaystyle{ (c)_i=c. }[/math]

Пусть [math]\displaystyle{ D }[/math] — фильтр над [math]\displaystyle{ I }[/math]. Определим на [math]\displaystyle{ \prod_{i\in I}A_i }[/math] отношение [math]\displaystyle{ a\sim_D b\Leftrightarrow\{i\in I\mid a_i=b_i\}\in D }[/math]. Введём обозначения:

[math]\displaystyle{ a/D=\{b\mid b\sim_D a\} }[/math], [math]\displaystyle{ \prod_{i\in I}A_i/D=\left\{a/D\mid a\in\prod_{i\in I}A_i\right\}. }[/math]

Определим алгебраическую систему [math]\displaystyle{ \mathcal{A}=\left\langle\prod_{i\in I}A_i/D,\;L\right\rangle }[/math] следующим образом.

Положим для предикатного символа [math]\displaystyle{ P\in L }[/math]

[math]\displaystyle{ \mathcal{A}\models P(a_1,\;\ldots,\;a_{n_P})\Leftrightarrow\{i\mid\mathcal{A}_i\models P(a_{1_i},\;\ldots,\;a_{n_Pi})\}\in D, }[/math]

для каждого функционального символа [math]\displaystyle{ f\in L }[/math]

[math]\displaystyle{ f(a_1/D,\;\ldots,\;a_{n_f}/D)=f(a_1,\;\ldots,\;a_n)/D }[/math]

и для константных символов [math]\displaystyle{ c\in L }[/math]

[math]\displaystyle{ c=c/D. }[/math]

Определённая таким образом алгебраическая система [math]\displaystyle{ \mathcal{A} }[/math] называется фильтрованным произведением систем [math]\displaystyle{ \mathcal{A}_i }[/math] по фильтру [math]\displaystyle{ D }[/math] и обозначается [math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i/D }[/math]. Если [math]\displaystyle{ D }[/math] — ультрафильтр, то [math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i/D }[/math] называется ультрапроизведением, если все [math]\displaystyle{ \mathcal{A}_i }[/math] совпадают и равны [math]\displaystyle{ \mathcal{A} }[/math], то [math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i/D }[/math] называется ультрастепенью [math]\displaystyle{ \mathcal{A} }[/math] и обозначается [math]\displaystyle{ \mathcal{A}^I/D }[/math].

Основное свойство ультрапроизведений состоит в том, что они сохраняют все предложения:

Теорема Лося. Пусть [math]\displaystyle{ L }[/math] — язык, [math]\displaystyle{ \{\mathcal{A}_i\}_{i\in I} }[/math] — семейство алгебраических систем языка [math]\displaystyle{ L }[/math], [math]\displaystyle{ D }[/math] — ультрафильтр над [math]\displaystyle{ I }[/math]. Тогда для любой формулы [math]\displaystyle{ \varphi(\overline{x}) }[/math] языка [math]\displaystyle{ L }[/math] и любой последовательности [math]\displaystyle{ \overline{a} }[/math] элементов из [math]\displaystyle{ \prod_{i\in I} A_i }[/math]

[math]\displaystyle{ \prod_{i\in I}\mathcal{A}_i/D\models\varphi(\overline{a}/D)\Leftrightarrow\{i\in I\mid\mathcal{A}_i\models\varphi(\overline{a}_i)\}\in D. }[/math]

Также теорему компактности можно сформулировать следующим образом.

Теорема компактности. Если множество формул локально выполнимо в некотором классе [math]\displaystyle{ \mathbf{K} }[/math], то оно выполнимо в некотором ультрапроизведении систем из [math]\displaystyle{ \mathbf{K} }[/math].

Категоричность

Теория [math]\displaystyle{ T }[/math] с равенством, имеющая конечную или счётную сигнатуру, называется категоричной в счётной мощности, если все её счётные нормальные модели изоморфны. Категоричность в данной несчётной мощности определяется аналогично.

Литература

• Ершов Ю. Л., Палютин Е. А. Математическая логика. — М.: Наука, 1987. — 336 с.
• Справочная книга по математической логике. Часть 1. Теория моделей / под ред. Дж. Барвайса. — М.: Наука, 1982. — 392 с.
• Кейслер, Г.Дж.; Чень-Чунь, Чэн. Теория непрерывных моделей. — М.: Мир, 1971. — 184 с.
• Кейслер, Г.Дж.; Чень-Чунь, Чэн. Теория моделей. — М.: Мир, 1977. — 616 с.