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

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

В математической логике теория моделей — это исследование взаимосвязей между формальными теориями (набором предложений на формальном языке, выражающих утверждения о математической структуре ) и их моделями (теми структурами , в которых выполняются утверждения теории). Исследуемые аспекты включают количество и размер моделей теории, взаимосвязь различных моделей друг с другом и их взаимодействие с самим формальным языком. В частности, теоретики моделей также исследуют множества, которые могут быть определены в модели теории, и взаимосвязь таких определимых множеств друг с другом. Как отдельная дисциплина теория моделей восходит к Альфреду Тарскому , который впервые использовал термин «Теория моделей» в публикации в 1954 году. С 1970-х годов этот предмет решающим образом определялся Сахарона Шелаха теорией стабильности .

По сравнению с другими областями математической логики, такими как теория доказательств , теория моделей часто менее озабочена формальной строгостью и ближе по духу к классической математике.Это привело к высказыванию о том, что «если теория доказательств касается священного, то теория моделей — профанного» . Приложения теории моделей к алгебраической и диофантовой геометрии отражают эту близость к классической математике, поскольку они часто включают интеграцию алгебраических и теоретико-модельных результатов и методов. Следовательно, теория доказательств имеет синтаксическую природу, в отличие от теории моделей, которая имеет семантическую природу.

Наиболее известной научной организацией в области теории моделей является Ассоциация символической логики .

Обзор

Эта страница посвящена финитной теории моделей первого порядка бесконечных структур.

Относительный акцент, уделяемый классу моделей теории в отличие от класса определяемых множеств внутри модели, менялся в истории предмета, и эти два направления резюмируются содержательными характеристиками 1973 и 1997 годов соответственно:

теория моделей = универсальная алгебра + логика

где универсальная алгебра означает математические структуры, а логика — логические теории; и

теория моделей = алгебраическая геометрия − поля .

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

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

Основные понятия теории моделей первого порядка

Логика первого порядка

Основная статья: Логика первого порядка

первого порядка Формула состоит из атомарных формул, таких как $R(f(x,y),z)$ или $y=x+1$ с помощью булевых связок $\neg ,\land ,\lor ,\rightarrow$ и префикс кванторов $\forall v$ или $\exists v$. Предложение — это формула, в которой каждое вхождение переменной находится в области действия соответствующего квантора. Примеры формул: $\varphi$ (или $\varphi (x)$ указать $x$ это несвязанная переменная в $\varphi$) и $\psi$ (или $\psi (x)$), определяемый следующим образом:

${\begin{array}{lcl}\varphi &=&\forall u\forall v(\exists w(x\times w=u\times v)\rightarrow (\exists w(x\times w=u)\lor \exists w(x\times w=v)))\land x\neq 0\land x\neq 1,\\\psi &=&\forall u\forall v((u\times v=x)\rightarrow (u=x)\lor (v=x))\land x\neq 0\land x\neq 1.\end{array}}$

(Обратите внимание, что символ равенства здесь имеет двоякое значение.) Интуитивно понятно, как перевести такие формулы в математический смысл. В σ _smr -структуре ${\mathcal {N}}$ натуральных чисел, например, элемент $n$ удовлетворяет формуле $\varphi$ тогда и только тогда, когда $n$ является простым числом. Формула $\psi$ аналогично определяет неприводимость . Тарский дал строгое определение, иногда называемое «определением истины Тарского» , для отношения удовлетворения. $\models$, так что легко доказывается:

${\mathcal {N}}\models \varphi (n)\iff n$ является простым числом.

${\mathcal {N}}\models \psi (n)\iff n$ является нередуцируемым.

Набор $T$ предложений называется теорией (первого порядка) , которая принимает предложения из множества в качестве своих аксиом. Теория выполнима, если у нее есть модель. ${\mathcal {M}}\models T$, т.е. структура (соответствующей сигнатуры), которая удовлетворяет всем предложениям в наборе $T$. Полная теория — это теория, содержащая каждое предложение или его отрицание.Полная теория всех предложений, которым удовлетворяет структура, также называется теорией этой структуры .

Следствием теоремы Гёделя о полноте (не путать с его теоремами о неполноте ) является то, что теория имеет модель тогда и только тогда, когда она непротиворечива , т. е. теория не доказывает никаких противоречий.Поэтому теоретики моделей часто используют слово «последовательный» как синоним слова «выполнимый».

Основные теоретико-модельные концепции

Сигнатура , каждый из или язык — это набор нелогических символов которых является либо постоянным символом, либо символом функции или отношения с заданной арностью . Обратите внимание, что в некоторой литературе постоянные символы рассматриваются как функциональные символы с нулевой арностью и, следовательно, опускаются. Структура набор – ​​это $M$ вместе с интерпретациями каждого из символов подписи как отношений и функций на $M$ (не путать с формальным понятием « интерпретации » одной структуры в другой).

Пример: Обычная подпись для упорядоченных колец: $\sigma _{or}=(0,1,+,\times ,-,<)$, где $0$ и $1$ являются 0-арными функциональными символами (также известными как постоянные символы), $+$ и $\times$ являются двоичными (= 2-мерными) функциональными символами, $-$ является унарным (= 1-арным) функциональным символом, а $<$ является символом бинарного отношения. Затем, когда эти символы интерпретируются как соответствующие их обычному значению на $\mathbb {Q}$ (так что, например, $+$ это функция от $\mathbb {Q} ^{2}$ к $\mathbb {Q}$ и $<$ является подмножеством $\mathbb {Q} ^{2}$), получается структура $(\mathbb {Q} ,\sigma _{or})$.

Структура ${\mathcal {N}}$ Говорят, что он моделирует набор предложений первого порядка. $T$ на данном языке, если каждое предложение в $T$ верно в ${\mathcal {N}}$ относительно толкования подписи, ранее указанной для ${\mathcal {N}}$. (Опять же, не путать с формальным понятием « интерпретации » одной структуры в другой) Модель . $T$ это структура, которая моделирует $T$.

Подструктура ​ ${\mathcal {A}}$ σ-структуры ${\mathcal {B}}$ является подмножеством своей области определения, замкнутым относительно всех функций в его сигнатуре σ, которое рассматривается как σ-структура путем ограничения всех функций и отношений в σ этим подмножеством.Это обобщает аналогичные понятия из алгебры; например, подгруппа — это подструктура в сигнатуре с умножением и обратным.

Подструктуру называют элементарной , если для любой формулы первого порядка $\varphi$ и любые элементы a ₁ , n _из , ... ${\mathcal {A}}$,

${\mathcal {A}}\models \varphi (a_{1},...,a_{n})$ тогда и только тогда, когда ${\mathcal {B}}\models \varphi (a_{1},...,a_{n})$.

В частности, если $\varphi$ это предложение и ${\mathcal {A}}$ элементарная подструктура ${\mathcal {B}}$, затем ${\mathcal {A}}\models \varphi$ тогда и только тогда, когда ${\mathcal {B}}\models \varphi$. Таким образом, элементарная подструктура является моделью теории именно тогда, когда надстройка является моделью.

Пример: Хотя поле алгебраических чисел ${\overline {\mathbb {Q} }}$ является элементарной подструктурой поля комплексных чисел $\mathbb {C}$, рациональное поле $\mathbb {Q}$ это не так, поскольку мы можем выразить фразу «Существует квадратный корень из 2» как предложение первого порядка, удовлетворяющее $\mathbb {C}$ но не через $\mathbb {Q}$.

Вложение структуры σ- ${\mathcal {A}}$ в другую σ-структуру ${\mathcal {B}}$ — это отображение f : A → B между областями, которое можно записать как изоморфизм ${\mathcal {A}}$ с подструктурой ${\mathcal {B}}$. Если его можно записать как изоморфизм с элементарной подструктурой, то его называют элементарным вложением. Каждое вложение является инъективным гомоморфизмом, но обратное справедливо только в том случае, если сигнатура не содержит символов отношения, например, в группах или полях.

Поле или векторное пространство можно рассматривать как (коммутативную) группу, просто игнорируя некоторые элементы ее структуры. Соответствующее понятие в теории моделей — это приведение структуры к подмножеству исходной сигнатуры. Противоположное отношение называется расширением - например, (аддитивная) группа рациональных чисел , рассматриваемая как структура сигнатуры {+,0}, может быть расширена до поля с сигнатурой {×,+,1,0} или в упорядоченную группу с сигнатурой {+,0,<}.

Аналогично, если σ' является сигнатурой, расширяющей другую сигнатуру σ, то полная σ'-теория может быть ограничена σ путем пересечения множества ее предложений с набором σ-формул. И наоборот, полную σ-теорию можно рассматривать как σ'-теорию, и ее можно расширить (более чем одним способом) до полной σ'-теории. К этому отношению иногда также применяются термины сокращение и расширение.

Компактность и теорема Левенхайма-Скулема

Теорема о компактности утверждает, что набор предложений S выполним, если каждое конечное подмножество S выполнимо. Аналогичное утверждение с непротиворечивым вместо выполнимого тривиально, поскольку каждое доказательство может иметь только конечное число антецедентов, используемых в доказательстве. Теорема о полноте позволяет перенести это на выполнимость. Однако существует и несколько прямых (семантических) доказательств теоремы о компактности.Как следствие (т. е. противоположное) теорема компактности утверждает, что каждая невыполнимая теория первого порядка имеет конечное невыполнимое подмножество. Эта теорема имеет центральное значение в теории моделей, где слова «по компактности» являются обычным явлением.

Еще одним краеугольным камнем теории моделей первого порядка является теорема Левенхайма-Скулема . Согласно теореме Левенхайма-Скулема, каждая бесконечная структура счетной сигнатуры имеет счетную элементарную подструктуру. И наоборот, для любого бесконечного кардинала κ каждая бесконечная структура счетной сигнатуры, мощность которой меньше κ, может быть элементарно вложена в другую структуру мощности κ (существует прямое обобщение на несчетные сигнатуры). В частности, из теоремы Левенхайма-Скулема следует, что любая теория счетной сигнатуры с бесконечными моделями имеет счетную модель, а также модели сколь угодно больших размеров.

В определенном смысле, уточненном теоремой Линдстрема , логика первого порядка является наиболее выразительной логикой, для которой справедливы как теорема Левенхайма-Скулема, так и теорема о компактности.

Определимость

Определяемые наборы

В теории моделей определяемые множества являются важными объектами исследования. Например, в $\mathbb {N}$ формула

$\forall u\forall v(\exists w(x\times w=u\times v)\rightarrow (\exists w(x\times w=u)\lor \exists w(x\times w=v)))\land x\neq 0\land x\neq 1$

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

$\exists y(2\times y=x)$

определяет подмножество четных чисел.Аналогичным образом формулы с n свободными переменными определяют подмножества ${\mathcal {M}}^{n}$. Например, в поле формула

$y=x\times x$

определяет кривую всех $(x,y)$ такой, что $y=x^{2}$.

Оба упомянутых здесь определения не содержат параметров , то есть в определяющих формулах не упоминаются какие-либо элементы фиксированной области. Однако можно рассматривать и определения с параметрами из модели .Например, в $\mathbb {R}$, формула

$y=x\times x+\pi$

использует параметр $\pi$ от $\mathbb {R}$ определить кривую.

Устранение кванторов

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

Это делает исключение кванторов важным инструментом для анализа определяемых множеств: Теория T имеет устранение кванторов, если каждая формула первого порядка φ( x ₁ , ..., x _n ) в ее сигнатуре эквивалентна по модулю T формуле первого порядка ψ( x ₁ , ..., x _n ) без кванторы, т.е. $\forall x_{1}\dots \forall x_{n}(\phi (x_{1},\dots ,x_{n})\leftrightarrow \psi (x_{1},\dots ,x_{n}))$ выполняется во всех моделях T . Если теория структуры допускает исключение кванторов, каждое множество, определяемое в структуре, можно определить с помощью формулы без кванторов по тем же параметрам, что и исходное определение.Например, теория алгебраически замкнутых полей в сигнатуре σ- _кольца = (×,+,−,0,1) допускает устранение кванторов. Это означает, что в алгебраически замкнутом поле каждая формула эквивалентна булевой комбинации уравнений между многочленами.

Если в теории нет исключения кванторов, можно добавить к ее сигнатуре дополнительные символы, чтобы это было сделано. Результаты аксиоматизируемости и исключения кванторов для конкретных теорий, особенно в алгебре, были одними из первых знаковых результатов теории моделей. Но часто вместо исключения квантора достаточно более слабого свойства:

Теория Т называется модельно-полной, если каждая подструктура модели Т , которая сама является моделью Т, является элементарной подструктурой. Существует полезный критерий проверки того, является ли подструктура элементарной подструктурой, называемый тестом Тарского-Вота . Из этого критерия следует, что теория T является модельно полной тогда и только тогда, когда каждая формула первого порядка φ( x ₁ , ..., x _n ) по ее сигнатуре эквивалентна по модулю T экзистенциальной формуле первого порядка, т.е. формула следующего вида:

$\exists v_{1}\dots \exists v_{m}\psi (x_{1},\dots ,x_{n},v_{1},\dots ,v_{m})$,

где ψ свободен от кванторов. Теория, которая не является модельно-полной, может иметь модельное завершение , которое представляет собой связанную модельно-полную теорию, которая, как правило, не является расширением исходной теории. Более общее понятие – это модель компаньона .

Минимальность

В каждой структуре каждое конечное подмножество $\{a_{1},\dots ,a_{n}\}$ определяется параметрами: просто используйте формулу

$x=a_{1}\vee \dots \vee x=a_{n}$.

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

Это приводит к концепции минимальной структуры . Структура ${\mathcal {M}}$ называется минимальным, если каждое подмножество $A\subseteq {\mathcal {M}}$ определяемый параметрами из ${\mathcal {M}}$ либо конечен, либо коконечен.Соответствующее понятие на уровне теорий называется сильной минимальностью :Теория T называется сильно минимальной, если каждая модель T минимальна.Структура называется сильно минимальной, если теория этой структуры сильно минимальна. Эквивалентно, структура является строго минимальной, если каждое элементарное расширение минимально.Поскольку теория алгебраически замкнутых полей допускает устранение кванторов, каждое определимое подмножество алгебраически замкнутого поля можно определить с помощью бескванторной формулы с одной переменной. Бескванторные формулы с одной переменной выражают булевы комбинации полиномиальных уравнений с одной переменной, а поскольку нетривиальное полиномиальное уравнение с одной переменной имеет лишь конечное число решений, теория алгебраически замкнутых полей сильно минимальна.

С другой стороны, поле $\mathbb {R}$ действительных чисел не является минимальным: рассмотрим, например, определимое множество

$\varphi (x)\;=\;\exists y(y\times y=x)$.

Это определяет подмножество неотрицательных действительных чисел, которое не является ни конечным, ни конечным.Фактически можно использовать $\varphi$ определить произвольные интервалы на прямой числовой линии.Оказывается, их достаточно, чтобы представить любое определимое подмножество $\mathbb {R}$. Это обобщение минимальности оказалось очень полезным в модельной теории упорядоченных структур. структура Плотно упорядоченная ${\mathcal {M}}$ в сигнатуре, содержащей символ отношения порядка, называется o-минимальным, если каждое подмножество $A\subseteq {\mathcal {M}}$ определяемый параметрами из ${\mathcal {M}}$ представляет собой конечное объединение точек и интервалов.

Определяемые и интерпретируемые структуры

Основная статья: Интерпретация (теория моделей)

Особенно важны те определяемые множества, которые также являются подструктурами, т.е. содержат все константы и замыкаются при применении функции. Например, можно изучить определяемые подгруппы определенной группы.Однако не нужно ограничиваться подструктурами в одной сигнатуре. Поскольку формулы с n свободными переменными определяют подмножества ${\mathcal {M}}^{n}$, n -арные отношения также могут быть определимы. Функции определимы, если график функции представляет собой определимое отношение, а константы $a\in {\mathcal {M}}$ определимы, если существует формула $\varphi (x)$ такой, что a является единственным элементом ${\mathcal {M}}$ такой, что $\varphi (a)$ это правда.Таким способом можно изучать, например, определимые группы и поля в общих структурах, что важно в теории геометрической устойчивости.

Можно даже пойти еще дальше и выйти за рамки непосредственных подструктур.Учитывая математическую структуру, очень часто существуют связанные структуры, которые можно построить как частное части исходной структуры с помощью отношения эквивалентности. Важным примером является факторгруппа группы. Можно сказать, что для понимания всей структуры необходимо понять эти частные. Когда отношение эквивалентности определимо, мы можем придать предыдущему предложению точный смысл. Мы говорим, что эти структуры интерпретируемы .Ключевым фактом является то, что можно переводить предложения с языка интерпретируемых структур на язык исходной структуры. Таким образом, можно показать, что если структура ${\mathcal {M}}$ интерпретирует другого, чья теория неразрешима, то ${\mathcal {M}}$ само по себе неразрешимо.

Типы

Основная статья: Тип (теория моделей)

Основные понятия

Для последовательности элементов $a_{1},\dots ,a_{n}$ структуры ${\mathcal {M}}$ и подмножество A из ${\mathcal {M}}$, можно рассмотреть совокупность всех формул первого порядка $\varphi (x_{1},\dots ,x_{n})$ с параметрами в A, которым удовлетворяет $a_{1},\dots ,a_{n}$. Это называется полным (n-)типом, реализуемым $a_{1},\dots ,a_{n}$ над А. существует автоморфизм Если ${\mathcal {M}}$ который постоянен на A и отправляет $a_{1},\dots ,a_{n}$ к $b_{1},\dots ,b_{n}$ соответственно, тогда $a_{1},\dots ,a_{n}$ и $b_{1},\dots ,b_{n}$ реализовать один и тот же полный тип над A .

Действительная числовая линия $\mathbb {R}$, рассматриваемая как структура, содержащая только отношение порядка {<}, будет служить в этом разделе рабочим примером.Каждый элемент $a\in \mathbb {R}$ удовлетворяет тому же 1-типу на пустом множестве. Это понятно, поскольку любые два действительных числа a и b связаны порядковым автоморфизмом, сдвигающим все числа на ba . Полный 2-тип над пустым множеством, реализованный парой чисел $a_{1},a_{2}$ зависит от их порядка: либо $a_{1}<a_{2}$, $a_{1}=a_{2}$ или $a_{2}<a_{1}$.Над подмножеством $\mathbb {Z} \subseteq \mathbb {R}$ среди целых чисел 1-тип нецелого действительного числа a зависит от его значения, округленного до ближайшего целого числа.

В более общем смысле, всякий раз, когда ${\mathcal {M}}$ является структурой, а A является подмножеством ${\mathcal {M}}$(частичный) n-тип над A — это набор формул p с не более чем n свободными переменными, которые реализуются в элементарном расширении ${\mathcal {N}}$ из ${\mathcal {M}}$. Если p содержит каждую такую ​​формулу или ее отрицание, то p является полным . Набор полных n -типов над A часто записывается как $S_{n}^{\mathcal {M}}(A)$. Если A — пустое множество, то пространство типов зависит только от теории $T$ из ${\mathcal {M}}$. Обозначения $S_{n}(T)$ обычно используется для набора типов поверх пустого набора, соответствующего $T$. Если существует одна формула $\varphi$ такова, что теория ${\mathcal {M}}$ подразумевает $\varphi \rightarrow \psi$ для каждой формулы $\psi$ в p , то p называется изолированным .

Поскольку реальные цифры $\mathbb {R}$ являются архимедовыми , не существует действительного числа, большего любого целого числа. Однако аргумент компактности показывает, что существует элементарное расширение линии действительных чисел, в котором есть элемент, больший любого целого числа.Следовательно, набор формул $\{n<x|n\in \mathbb {Z} \}$ является 1-типом над $\mathbb {Z} \subseteq \mathbb {R}$ это не реализуется в действительной числовой строке $\mathbb {R}$.

Подмножество ${\mathcal {M}}^{n}$ которые могут быть выражены как именно те элементы ${\mathcal {M}}^{n}$ реализация определенного типа над A называется определяемым типом над A .В качестве алгебраического примера предположим $M$ — алгебраически замкнутое поле . Теория допускает устранение кванторов. Это позволяет нам показать, что тип определяется именно содержащимися в нем полиномиальными уравнениями. Таким образом, набор полных $n$-типы над подполем $A$ соответствует множеству простых идеалов кольца полиномов $A[x_{1},\ldots ,x_{n}]$, а определяемые по типу множества — это в точности аффинные многообразия.

Структуры и типы

Хотя не каждый тип реализуется в каждой структуре, каждая структура реализует свои отдельные типы.Если единственными типами в пустом множестве, которые реализованы в структуре, являются изолированные типы, то структура называется атомарной .

С другой стороны, ни одна структура не реализует каждый тип для каждого набора параметров; если взять все ${\mathcal {M}}$ в качестве набора параметров, то каждый 1-тип ${\mathcal {M}}$ реализовано в ${\mathcal {M}}$ выделяется формулой вида a = x для $a\in {\mathcal {M}}$. Однако любое правильное элементарное расширение ${\mathcal {M}}$ содержит элемент, которого нет в ${\mathcal {M}}$. Поэтому было введено более слабое понятие, отражающее идею структуры, реализующей все типы, которые можно было бы реализовать.Структура называется насыщенной , если она реализует каждый тип по набору параметров. $A\subset {\mathcal {M}}$ то есть меньшей мощности, чем ${\mathcal {M}}$ сам.

Хотя автоморфизм, постоянный на A, всегда сохраняет типы над A , обычно неверно, что любые две последовательности $a_{1},\dots ,a_{n}$ и $b_{1},\dots ,b_{n}$ которые удовлетворяют одному и тому же типу над A, могут быть отображены друг в друга с помощью такого автоморфизма. Структура ${\mathcal {M}}$ в котором это обратное справедливо для всех A меньшей мощности, чем ${\mathcal {M}}$ называется однородным .

Линия действительных чисел является атомарной на языке, который содержит только порядок $<$, поскольку все n -типов в пустом множестве реализуются $a_{1},\dots ,a_{n}$ в $\mathbb {R}$ изолированы отношениями порядка между $a_{1},\dots ,a_{n}$. Однако он не является насыщенным, поскольку не реализует ни одного 1-типа на счетном множестве. $\mathbb {Z}$ это означает, что x больше любого целого числа.Рациональная числовая линия $\mathbb {Q}$ насыщен, напротив, поскольку $\mathbb {Q}$ само по себе счетно и, следовательно, должно реализовывать типы только для конечных подмножеств, чтобы быть насыщенным.

Каменные пространства

Набор определяемых подмножеств ${\mathcal {M}}^{n}$ по некоторым параметрам $A$ является булевой алгеброй . По теореме Стоуна о представлении булевых алгебр существует естественное двойственное топологическое пространство , состоящее в точности из полного $n$-перебирает $A$. Топология, порожденная множествами вида $\{p|\varphi \in p\}$ для отдельных формул $\varphi$. Это называется пространством Стоуна n-типов над A . Эта топология объясняет некоторые термины, используемые в теории моделей: теорема о компактности говорит, что пространство Стоуна является компактным топологическим пространством, а тип p изолирован тогда и только тогда, когда p является изолированной точкой в ​​топологии Стоуна.

В то время как типы в алгебраически замкнутых полях соответствуют спектру кольца полиномов, топология в пространстве типов является конструктивной топологией : набор типов является базовым открытым тогда и только тогда, когда он имеет вид $\{p:f(x)=0\in p\}$ или формы $\{p:f(x)\neq 0\in p\}$. Это тоньше, чем топология Зариского .

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

Реализация и исключение типов

Построение моделей, реализующих одни типы и не реализующих другие, является важной задачей теории моделей.Нереализация типа называется его пропуском и обычно возможна согласно теореме о (счетных) исключениях типов :

Позволять ${\mathcal {T}}$ — теория счетной сигнатуры и пусть $\Phi$ быть счетным множеством неизолированных типов над пустым множеством.

Тогда есть модель ${\mathcal {M}}$ из ${\mathcal {T}}$ который опускает каждый тип в $\Phi$.

Это означает, что если теория счетной сигнатуры имеет только счетное число типов на пустом множестве, то эта теория имеет атомарную модель.

С другой стороны, всегда существует элементарное расширение, в котором реализуется любой набор типов с фиксированным набором параметров:

Позволять ${\mathcal {M}}$ быть структурой и пусть $\Phi$ быть набором полных типов для заданного набора параметров $A\subset {\mathcal {M}}.$

Тогда существует элементарное расширение ${\mathcal {N}}$ из ${\mathcal {M}}$ который реализует каждый тип в $\Phi$.

Однако, поскольку набор параметров фиксирован и здесь не упоминается мощность ${\mathcal {N}}$, это не означает, что каждая теория имеет насыщенную модель.Фактически, вопрос о том, имеет ли каждая теория насыщенную модель, не зависит от аксиом Цермело-Френкеля теории множеств и является верным, если верна обобщенная гипотеза континуума .

Ультрапродукты

Ультрапродукты используются как общий метод построения моделей, реализующих определенные типы.Ультрапродукт которые согласуются получается из прямого произведения набора структур по набору индексов I почти по всем записям, причем почти все уточняется с помощью ультрафильтра U на I. путем идентификации тех кортежей , Ультрапродукт копий одной и той же структуры известен как ультрастепень .Ключом к использованию ультрапроизведений в теории моделей является теорема Лоша :

Позволять ${\mathcal {M}}_{i}$ — набор σ -структур, индексированных набором индексов I , а U — на I. ультрафильтр Тогда любая σ -формула $\varphi ([(a_{i})_{i\in :I}])$ верно в ультрапроизведении ${\mathcal {M}}_{i}$ к $U$ если совокупность всех $i\in I$ для чего ${\mathcal {M}}_{i}\models \varphi (a_{i})$ в У. лежит

В частности, любой ультрапродукт моделей теории сам по себе является моделью этой теории, и, таким образом, если две модели имеют изоморфные ультрастепени, они элементарно эквивалентны. Теорема Кейслера -Шела обеспечивает обратное:

Если M и N элементарно эквивалентны, то существует множество I и ультрафильтр U на I , что ультрастепени M и N : такие изоморфны.

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

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

Основная статья: Категориальная теория

Теорию первоначально называли категоричной , если она определяет структуру с точностью до изоморфизма. Оказывается, это определение бесполезно из-за серьезных ограничений в выразительности логики первого порядка. Теорема Левенхайма-Скулема подразумевает, что если теория T имеет бесконечную модель для некоторого бесконечного кардинального числа , то она имеет модель размера κ для любого достаточно большого кардинального числа κ . Поскольку две модели разных размеров не могут быть изоморфными, категорической теорией можно описать только конечные структуры.

Однако более слабое понятие κ -категоричности для кардинала κ стало ключевым понятием в теории моделей. Теория T называется κ -категоричной , если любые две модели T мощности κ изоморфны. Оказывается, вопрос о κ -категоричности критически зависит от того, превышает ли κ мощность языка (т.е. $\aleph _{0}+|\sigma |$, где | σ | — мощность подписи). Для конечных или счетных подписей это означает, что существует фундаментальная разница между ω -мощностью и κ -мощностью для несчетного κ .

ω- категоричность

ω -категоричные теории могут быть охарактеризованы свойствами их пространства типов:

первого порядка Для полной теории T в конечной или счетной сигнатуре следующие условия эквивалентны:

1. T является ω -категоричным.
2. Каждый тип в Sn _. ( T ) изолирован
3. Для любого натурального числа Sn n ( _. T ) конечно
4. Для каждого натурального числа n количество формул φ ( x ₁ , ..., x _n ) от n свободных переменных с точностью до эквивалентности по модулю T конечно.

Теория $(\mathbb {Q} ,<)$, что также является теорией $(\mathbb {R} ,<)$, является ω -категоричным, так как каждый n -тип $p(x_{1},\dots ,x_{n})$ над пустым множеством изолировано попарным отношением порядка между $x_{i}$.Это означает, что каждый счетный плотный линейный порядок порядково-изоморфен прямой рациональной числа. С другой стороны, теории ℚ, ℝ и ℂ как полей не являются $\omega$-категоричный. Это следует из того, что во всех этих полях любое из бесконечного числа натуральных чисел можно определить по формуле вида $x=1+\dots +1$.

$\aleph _{0}$-категоричные теории и их счетные модели также имеют прочные связи с олигоморфными группами :

первого порядка Полная теория T в конечной или счетной сигнатуре является ω -категоричной тогда и только тогда, когда ее группа автоморфизмов олигоморфна.

Эквивалентные характеристики этого подраздела, независимо от Энгелера , Рилла-Нардзевского и Свенониуса , иногда называют теоремой Рилла-Нардзевского.

В комбинаторных сигнатурах общим источником ω -категоричных теорий являются пределы Фрэссе , которые получаются как предел объединения всех возможных конфигураций класса конечных реляционных структур.

Неисчислимая категоричность

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

Теорема о категоричности Морли

первого порядка Если теория T в конечной или счетной сигнатуре является κ -категоричной для некоторого несчетного кардинала κ , то T является κ-категоричной для всех несчетных кардиналов κ .

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

Теория, которая одновременно ω -категорична и несчетно категорична, называется вполне категоричной .

Теория стабильности

Основная статья: Стабильная теория

Ключевым фактором в структуре класса моделей теории первого порядка является ее место в иерархии устойчивости .

Полная теория T называется $\lambda$-стабильный для кардинала $\lambda$ если для любой модели ${\mathcal {M}}$ T параметров и любого набора $A\subset {\mathcal {M}}$ мощности, не превышающей $\lambda$, есть максимум $\lambda$ полные T над A. - типы

Теория называется устойчивой, если она $\lambda$-стабилен для некоторого бесконечного кардинала $\lambda$. Традиционно теории, которые $\aleph _{0}$-стабильные называются $\omega$-стабильный .

Иерархия стабильности

Фундаментальным результатом теории устойчивости является теорема о спектре устойчивости : откуда следует, что каждая полная теория T в счетной сигнатуре относится к одному из следующих классов:

1. Кардиналов нет. $\lambda$ такой, T что $\lambda$-стабильный.
2. Т это $\lambda$-стабилен тогда и только тогда, когда $\lambda ^{\aleph _{0}}=\lambda$ (см. кардинальное возведение в степень для объяснения $\lambda ^{\aleph _{0}}$).
3. Т это $\lambda$-стабилен для любого $\lambda \geq 2^{\aleph _{0}}$ (где $2^{\aleph _{0}}$ — мощность континуума ) .

Теория первого типа называется неустойчивой , теория второго типа — строго стабильной , теория третьего типа — сверхстабильной .Более того, если теория $\omega$-стабильный, он устойчив по каждому бесконечному кардиналу, так $\omega$-стабильность сильнее сверхстабильности.

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

Первоначальная мотивация Шела к изучению стабильных теорий заключалась в том, чтобы решить, сколько моделей имеет счетная теория любой несчетной мощности. Если теория несчетно категорична, то она $\omega$-стабильный. В более общем смысле, теорема о главном разрыве подразумевает, что если существует несчетный кардинал $\lambda$ такая, что теория T имеет меньше, чем $2^{\lambda }$ модели мощности $\lambda$, то T сверхстабильна.

Геометрическая теория устойчивости

Иерархия устойчивости также имеет решающее значение для анализа геометрии определимых множеств в модели теории. В $\omega$В стабильных теориях ранг Морли является важным понятием размерности для определимых множеств S внутри модели. Это определяется трансфинитной индукцией :

• Ранг Морли не меньше 0, если S непусто.
• Для α, ординала -преемника , ранг Морли равен α, если в некотором элементарном расширении N множества M множество S имеет бесконечно много непересекающихся определимых подмножеств, каждое из которых имеет ранг не менее α − 1.
• Если α ненулевой предельный ординал , ранг Морли равен не менее α , если он равен не менее β для всех β, меньших α .

Теория Т , в которой каждое определимое множество имеет четко определенный ранг Морли, называется полностью трансцендентной ; если T счетно, то T вполне трансцендентно тогда и только тогда, T когда $\omega$-стабильный.Ранг Морли можно распространить на типы, установив ранг Морли типа как минимальный из рангов Морли формул в этом типе. Таким образом, можно также говорить о ранге Морли элемента a над множеством параметров A определяемом как ранг Морли типа a над A. , Существуют также аналоги ранга Морли, которые четко определены тогда и только тогда, когда теория является суперстабильной ( U-ранг ) или просто стабильной ( теория Шелаха ). $\infty$-классифицировать).Эти понятия измерений можно использовать для определения понятий независимости и общих расширений.

Совсем недавно стабильность была разложена на простоту, а не на «свойство независимости» (NIP). Простые теории — это те теории, в которых можно определить правильное понятие независимости, в то время как теории NIP обобщают o-минимальные структуры.Они связаны со стабильностью, поскольку теория стабильна тогда и только тогда, когда она NIP и проста. и различные аспекты теории устойчивости были обобщены на теории одного из этих классов.

Неэлементарная теория моделей

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

Теория моделей в логиках высшего порядка или бесконечных логиках затруднена тем фактом, что полнота и компактность , как правило, не соблюдаются для этих логик. Это конкретизируется в теореме Линдстрема , грубо утверждающей, что логика первого порядка, по сути, является самой сильной логикой, в которой соблюдаются как теоремы Левенхайма-Скулема, так и компактность. Однако для этих логик также широко разработаны методы теории моделей. Однако оказывается, что большая часть теории моделей более выразительных логических языков не зависит от теории множеств Цермело-Френкеля .

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

Выбранные приложения

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

В 1960-х годах введение конструкции ультрапроизведения привело к новым приложениям в алгебре. Сюда входит работа Акса о псевдоконечных полях , доказывающая разрешимость теории конечных полей. и доказательство Акса и Кохена как частного случая гипотезы Артина о диофантовых уравнениях, теоремы Акса-Кохена . Конструкция ультрапродукта также привела к Абрахамом Робинсоном развитию нестандартного анализа , целью которого является обеспечение строгого исчисления бесконечно малых .

Совсем недавно связь между стабильностью и геометрией определимых множеств привела к нескольким приложениям из алгебраической и диофантовой геометрии, включая доказательство Эхуда Грушовского 1996 года геометрической гипотезы Морделла-Ланга во всех характеристиках. В 2001 году аналогичные методы были использованы для доказательства обобщения гипотезы Манина-Мамфорда.В 2011 году Джонатан Пила применил методы o-минимальности , чтобы доказать гипотезу Андре-Оорта для произведений модульных кривых.

В отдельном направлении исследований, также выросших вокруг стабильных теорий, Ласковски в 1992 году показал, что теории NIP описывают именно те определяемые классы, которые в теории машинного обучения могут быть изучены с помощью PAC . Это привело к нескольким взаимодействиям между этими отдельными областями. В 2018 году переписка расширилась, поскольку Хантер и Чейз показали, что стабильные теории соответствуют онлайн-классам .

История

Теория моделей как предмет существует примерно с середины 20-го века, а название было придумано Альфредом Тарским , членом Львовско-Варшавской школы , в 1954 году. Однако некоторые более ранние исследования, особенно в области математической логики , в ретроспективе часто рассматриваются как имеющие теоретико-модельный характер. Первым значительным результатом в том, что сейчас называется теорией моделей, был частный случай нисходящей теоремы Левенгейма-Скулема, опубликованный Леопольдом Левенхаймом в 1915 году. Теорема о компактности была неявно заложена в работе Торальфа Скулема : но впервые она была опубликована в 1930 году как лемма в доказательстве Куртом Гёделем его теоремы о полноте . Теорема Левенхайма-Скулема и теорема о компактности получили свои общие формы в 1936 и 1941 годах от Анатолия Мальцева .Развитие теории моделей как самостоятельной дисциплины было начато Альфредом Тарским в межвоенный период . Работа Тарского включала, логические выводы , дедуктивные системы , алгебру логики, теорию определимости и семантическое определение истины среди прочего, . Его семантические методы завершились разработкой теории моделей, которую он и ряд его студентов из Беркли разработали в 1950-х и 60-х годах.

В дальнейшей истории дисциплины стали возникать разные направления, смещался фокус темы. В 1960-х годах методы ультрапроизведения стали популярным инструментом в теории моделей. В то же время такие исследователи, как Джеймс Акс, исследовали теорию моделей первого порядка различных алгебраических классов, а другие, такие как Х. Джером Кейслер, распространяли концепции и результаты теории моделей первого порядка на другие логические системы. Затем, вдохновленный проблемой Морли , Шела разработал теорию устойчивости . Его работа над стабильностью изменила облик теории моделей, породив совершенно новый класс концепций. Это известно как смена парадигмы. В течение следующих десятилетий стало ясно, что полученная иерархия устойчивости тесно связана с геометрией множеств, которые можно определить в этих моделях; это привело к возникновению субдисциплины, ныне известной как геометрическая теория устойчивости. Примером влиятельного доказательства из теории геометрических моделей является гипотезы доказательство Грушовского Морделла-Ланга для функциональных полей.

Связи со смежными разделами математической логики.

Теория конечных моделей

Основная статья: Теория конечных моделей

Теория конечных моделей , которая концентрируется на конечных структурах, значительно расходится с изучением бесконечных структур как по изучаемым проблемам, так и по используемым методам. В частности, многие центральные результаты классической теории моделей терпят неудачу, если ограничиться конечными структурами. Сюда входят теорема о компактности , теорема Гёделя о полноте и метод ультрапроизведений для логики первого порядка . На стыке теории конечных и бесконечных моделей находятся алгоритмическая или вычислимая теория моделей и изучение законов 0–1 , где бесконечные модели общей теории класса структур предоставляют информацию о распределении конечных моделей. Выдающимися областями применения FMT являются описательная теория сложности , теория баз данных и теория формального языка .

Теория множеств

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

Теоретико-модельная точка зрения оказалась полезной в теории множеств ; например, в работе Курта Гёделя о конструируемой вселенной, которая, наряду с методом принуждения, разработанным Полом Коэном, может быть показана как доказательство (опять же интересная с философской точки зрения) независимости аксиомы выбора и гипотезы континуума от других аксиом. теории множеств.

С другой стороны, теория моделей сама формализуется в рамках теории множеств Цермело-Френкеля. Например, развитие основ теории моделей (таких как теорема о компактности) основано на аксиоме выбора и фактически эквивалентно теории множеств Цермело-Френкеля без выбора булевой теореме о простых идеалах. Другие результаты в теории моделей зависят от теоретико-множественных аксиом, выходящих за рамки стандартной структуры ZFC. Например, если гипотеза континуума верна, то каждая счетная модель имеет насыщенную сверхстепень (по своей мощности). Аналогично, если верна обобщенная гипотеза континуума, то каждая модель имеет насыщенное элементарное расширение. Ни один из этих результатов невозможно доказать только в ZFC. Наконец, было показано, что некоторые вопросы, возникающие из теории моделей (например, компактность бесконечной логики), эквивалентны большим кардинальным аксиомам.

См. также

• Абстрактная теория моделей
• Алгебраическая теория
• Аксиоматизируемый класс
• Теорема о компактности
• Описательная сложность
• Элементарная эквивалентность
• Теории первого порядка
• Гиперреальное число
• Теория институциональной модели
• Семантика Крипке
• Теорема Левенхайма – Скулема
• Теоретико-модельная грамматика
• Теория доказательств
• Насыщенная модель
• Шолем нормальная форма

Ссылки

Канонические учебники

• Чанг, Чен Чунг ; Кейслер, Х. Джером (1990) [1973]. Теория моделей . Исследования по логике и основам математики (3-е изд.). Эльзевир. ISBN  978-0-444-88054-3 .
• Чанг, Чен Чунг ; Кейслер, Х. Джером (2012) [1990]. Теория моделей . Дуврские книги по математике (3-е изд.). Дуврские публикации . п. 672. ИСБН  978-0-486-48821-9 .
• Ходжес, Уилфрид (1997). Более короткая модель теории . Кембридж: Издательство Кембриджского университета . ISBN  978-0-521-58713-6 .
• Копперман, Р. (1972). Теория моделей и ее приложения . Бостон: Аллин и Бэкон .
• Маркер, Дэвид (2002). Теория моделей: Введение . Тексты для аспирантов по математике 217. Спрингер. ISBN  0-387-98760-6 .

Другие учебники

• Белл, Джон Л.; Сломсон, Алан Б. (2006) [1969]. Модели и ультрапродукты: введение (перепечатка изд. 1974 г.). Дуврские публикации . ISBN  0-486-44979-3 .
• Эббингауз, Хайнц-Дитер; Флум, Йорг; Томас, Вольфганг (1994). Математическая логика . Спрингер . ISBN  0-387-94258-0 .
• Хинман, Питер Г. (2005). Основы математической логики . АК Петерс . ISBN  1-56881-262-0 .
• Ходжес, Уилфрид (1993). Модельная теория . Издательство Кембриджского университета . ISBN  0-521-30442-3 .
• Мансано, Мария (1999). Модельная теория . Издательство Оксфордского университета . ISBN  0-19-853851-0 .
• Пуаза, Бруно (2000). Курс теории моделей . Спрингер. ISBN  0-387-98655-3 .
• Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science + Business Media . дои : 10.1007/978-1-4419-1221-3 . ISBN  978-1-4419-1220-6 .
• Ротмалер, Филипп (2000). Введение в теорию моделей (новое изд.). Тейлор и Фрэнсис . ISBN  90-5699-313-5 .
• Тент, Катрин ; Зиглер, Мартин (2012). Курс теории моделей . Издательство Кембриджского университета . ISBN  9780521763240 .
• Кирби, Джонатан (2019). Приглашение к теории моделей . Издательство Кембриджского университета . ISBN  978-1-107-16388-1 .

Бесплатные онлайн-тексты

• Хацидакис, Зоэ (2001). Введение в теорию моделей (PDF) . стр. 26 стр.
• Пиллэй, Ананд (2002). Конспект лекций – Теория моделей (PDF) . стр. 61 страница.
• «Теория моделей» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Ходжес, Уилфрид , Теория моделей . Стэнфордская энциклопедия философии, Э. Залта (ред.).
• Ходжес, Уилфрид , Теория моделей первого порядка . Стэнфордская энциклопедия философии, Э. Залта (ред.).
• Симмонс, Гарольд (2004), Введение в старую добрую теорию моделей . Конспект вводного курса для аспирантов (с упражнениями).
• Дж. Барвайз и С. Феферман (редакторы), Теоретико-модельная логика , Перспективы математической логики, Том 8, Нью-Йорк: Springer-Verlag, 1985.