Теория моделей - Model theory

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

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

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

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

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

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

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

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

ветви

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

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

Примеры ранних теорем из классической теории модели включают законченность теорему Гёделя , вверх и вниз Löwenheim-сколемовские теоремы , Вота «теорему два-кардинального s, Scott » s изоморфизм теоремы, то опуская типы теоремы , и теорема Рыль-Нардзевский . Примеры ранних результатов теории моделей применительно к полю Тарского «s устранение кванторов для реальных замкнутых полей , Ax » s теорема о псевдоконечных полях , и Робинсон развития «s в нестандартном анализе . Важный шаг в развитии классической теории модели произошел с рождением теории устойчивости (по теореме Морела на неисчислиме категоричных теорий и Шели программы классификации «s), который разработал исчисление независимости и ранга на основе синтаксических условий , удовлетворенных теориями.

В течение последних нескольких десятилетий теория прикладных моделей неоднократно сливалась с более чистой теорией устойчивости. Результат этого синтеза в данной статье называется теорией геометрической модели (которая включает, например, о-минимальность, а также классическую геометрическую теорию устойчивости). Примером доказательства из теории геометрических моделей является доказательство Грушовским гипотезы Морделла – Лэнга для функциональных полей. Задача теории геометрических моделей состоит в том, чтобы обеспечить географию математики , приступив к детальному изучению определяемых множеств в различных математических структурах, опираясь на существенные инструменты, разработанные при изучении чистой теории моделей.

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

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

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

${\ Displaystyle {\ varphi \; = \; \ forall u \ forall v (\ существует w (x \ times w = u \ times v) \ rightarrow (\ существует w (x \ times w = u) \ lor \ exists w (x \ times w = v))) \ land x \ neq 0 \ land x \ neq 1,}}$

${\ Displaystyle \ psi \; = \; \ forall u \ forall v ((u \ times v = x) \ rightarrow (u = x) \ lor (v = x)) \ land x \ neq 0 \ land x \ neq 1.}$

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

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

${\ displaystyle {\ mathcal {N}} \ models \ psi (n) \ iff n}$ неприводимо.

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

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

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

Подпись или язык представляет собой набор нелогических символов таким образом, что каждый символ является либо символом функции или символ отношения и имеет заданную Арность . Структура представляет собой набор вместе с интерпретациями каждого из символов подписи в качестве отношений и функций на (не следует путать с интерпретацией одной структуры в другую). Распространенной сигнатурой для упорядоченных колец является , где и - нулевые функциональные символы (также известные как константные символы), и являются двоичными функциональными символами, являются унарными функциональными символами и являются символами двоичных отношений. Затем, когда эти символы интерпретируются как соответствующие их обычному значению на (так что eg является функцией от до и является подмножеством ), получается структура . Говорят, что структура моделирует набор предложений первого порядка на данном языке, если каждое предложение истинно в отношении интерпретации подписи, ранее указанной для . ${\ displaystyle M}$${\ displaystyle M}$${\ Displaystyle \ sigma _ {или} = \ {0,1, +, \ раз, -, <\}}$${\ displaystyle 0}$${\ displaystyle 1}$${\ displaystyle +}$${\ displaystyle \ times}$${\ displaystyle -}$${\ displaystyle <}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle +}$${\ Displaystyle \ mathbb {Q} ^ {2}}$${\ displaystyle \ mathbb {Q}}$${\ displaystyle <}$${\ Displaystyle \ mathbb {Q} ^ {2}}$${\ Displaystyle (\ mathbb {Q}, \ sigma _ {или})}$${\ Displaystyle {\ mathcal {N}}}$${\ displaystyle T}$${\ displaystyle T}$${\ Displaystyle {\ mathcal {N}}}$${\ Displaystyle {\ mathcal {N}}}$

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

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

${\ displaystyle {\ mathcal {A}} \ models \ varphi (a_ {1}, ..., a_ {n})}$если и только если .${\ displaystyle {\ mathcal {B}} \ models \ varphi (a_ {1}, ..., a_ {n})}$

В частности, если φ предложение и элементарная подструктура , то тогда и только тогда, когда . Таким образом, элементарная подструктура является моделью теории именно тогда, когда надстройка является моделью. Следовательно, в то время как поле алгебраических чисел является элементарной подструктурой поля комплексных чисел , рациональное поле таковым не является, поскольку мы можем выразить «есть квадратный корень из 2» как предложение первого порядка, удовлетворяющее, но не удовлетворяющее . ${\ displaystyle {\ mathcal {A}}}$${\ displaystyle {\ mathcal {B}}}$${\ displaystyle {\ mathcal {A}} \ models \ varphi}$${\ Displaystyle {\ mathcal {B}} \ models \ varphi}$${\ displaystyle {\ overline {\ mathbb {Q}}}}$${\ Displaystyle \ mathbb {C}}$${\ displaystyle \ mathbb {Q}}$${\ Displaystyle \ mathbb {C}}$${\ displaystyle \ mathbb {Q}}$

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

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

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

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

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

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

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

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

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

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

${\ Displaystyle \ forall u \ forall v (\ существует w (x \ times w = u \ times v) \ rightarrow (\ существует w (x \ times w = u) \ lor \ exists w (x \ times w = v) ))) \ земля x \ neq 0 \ земля x \ neq 1}$

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

${\ Displaystyle \ существует у (2 \ раз у = х)}$

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

${\ Displaystyle у = х \ раз х}$

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

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

${\ Displaystyle у = х \ раз х + \ пи}$

использует параметр from для определения кривой. ${\ displaystyle \ pi}$${\ Displaystyle \ mathbb {R}}$

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

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

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

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

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

${\ Displaystyle \ существует v_ {1} \ точки \ существует v_ {m} \ psi (x_ {1}, \ dots, x_ {n}, v_ {1}, \ dots, v_ {m})}$,

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

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

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

${\ Displaystyle х = а_ {1} \ ви \ точки \ ви а_ {п}}$.

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

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

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

${\ Displaystyle \ varphi (х) \; = \; \ существует у (у \ раз у = х)}$.

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

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

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

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

Типы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\ displaystyle \ omega}$-категория

${\ displaystyle \ omega}$-категориальные теории можно охарактеризовать свойствами своего пространства типов:

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

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

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

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

Полная теория первого порядка T в конечной или счетной сигнатуре является -категоричной тогда и только тогда, когда ее группа автоморфизмов олигоморфна.${\ displaystyle \ omega}$

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

В комбинаторных сигнатурах общим источником -категориальных теорий являются пределы Фраиссе , которые получаются как предел объединения всех возможных конфигураций класса конечных реляционных структур. ${\ displaystyle \ omega}$

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

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

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

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

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

Теория, которая является одновременно -категоричной и бесчисленно категоричной, называется полностью категоричной . ${\ displaystyle \ omega}$

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

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

В 1960 - е годы, соображения вокруг насыщенных моделей и ультрапроизведение строительства привести к Abraham Robinson развития «s в нестандартном анализе .

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

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

В 2011 году Джонатан Пила применил методы о-минимальности, чтобы доказать гипотезу Андре-Оорта для произведений модульных кривых.

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

История

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

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

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

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

Теория конечных моделей (FMT) - это часть теории моделей (MT), которая имеет дело с ее ограничением интерпретациями конечных структур, которые имеют конечную вселенную.

Поскольку многие центральные теоремы теории моделей не выполняются, когда они ограничиваются конечными структурами, FMT сильно отличается от MT своими методами доказательства. Центральные результаты классической теории моделей , которые не для конечных структур в рамках ДРМА включают теорему компактности , теорему Гёделя о полноте , и метод ультрапроизведений для логики первого порядка .

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

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

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

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

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

Смотрите также

Примечания

использованная литература

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

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

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

• Белл, Джон Л .; Сломсон, Алан Б. (2006) [1969]. Модели и ультрапродукты: введение (переиздание изд. 1974 г.). Dover Publications . ISBN 0-486-44979-3.
• Эббингаус, Хайнц-Дитер; Флум, Йорг; Томас, Вольфганг (1994). Математическая логика . Springer . ISBN 0-387-94258-0.
• Хинман, Питер Г. (2005). Основы математической логики . А.К. Петерс . ISBN 1-56881-262-0.
• Ходжес, Уилфрид (1993). Теория моделей . Издательство Кембриджского университета . ISBN 0-521-30442-3.
• Манзано, Мария (1999). Теория моделей . Издательство Оксфордского университета . ISBN 0-19-853851-0.
• Poizat, Бруно (2000). Курс теории моделей . Springer. ISBN 0-387-98655-3.
• Раутенберг, Вольфганг (2010). Краткое введение в математическую логику (3-е изд.). Нью-Йорк : Springer Science + Business Media . DOI : 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.

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

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