Тип (теория модели) - Type (model theory)

В теория моделей и смежные области математика, а тип это объект, который описывает, как (реальный или возможный) элемент или конечный набор элементов в математическая структура может вести себя. Точнее, это набор первый заказ формулы на языке L со свободными переменными Икс₁, Икс₂,…, Икс_п которые верны для последовательности элементов L-структура ${\displaystyle {\mathcal {M}}}$. В зависимости от контекста типы могут быть полный или же частичный и они могут использовать фиксированный набор констант, А, из структуры ${\displaystyle {\mathcal {M}}}$. Вопрос о том, какие типы представляют собой фактические элементы ${\displaystyle {\mathcal {M}}}$ приводит к идеям насыщенные модели и исключение типов.

Формальное определение

Рассмотрим структура ${\displaystyle {\mathcal {M}}}$ для язык L. Позволять M быть вселенная конструкции. Для каждого А ⊆ M, позволять L(А) быть языком, полученным из L добавив константу c_а для каждого а ∈ А. Другими словами,

${\displaystyle L(A)=L\cup \{c_{a}:a\in A\}.}$

А 1-тип (из ${\displaystyle {\mathcal {M}}}$) над А это набор п(Икс) формул в L(А) с не более чем одной свободной переменной Икс (поэтому 1-тип) такой, что для любого конечного подмножества п₀(Икс) ⊆ п(Икс) существует некоторое б ∈ M, в зависимости от п₀(Икс), с ${\displaystyle {\mathcal {M}}\models p_{0}(b)}$ (т.е. все формулы в п₀(Икс) верны в ${\displaystyle {\mathcal {M}}}$ когда Икс заменяется на б).

Аналогичным образом п-тип ${\displaystyle {\mathcal {M}}}$) над А определяется как набор п(Икс₁,…,Икс_п) = п(Икс) формул в L(А), каждая из которых имеет свободные переменные, встречающиеся только среди заданных п свободные переменные Икс₁,…,Икс_п, такое, что для любого конечного подмножества п₀(Икс) ⊆ п(Икс) есть некоторые элементы б₁,…,б_п ∈ M с ${\displaystyle {\mathcal {M}}\models p_{0}(b_{1},\ldots ,b_{n})}$.

А полный тип из ${\displaystyle {\mathcal {M}}}$ над А тот, который максимальный относительно включения. Равно как для каждого ${\displaystyle \phi ({\boldsymbol {x}})\in L(A,{\boldsymbol {x}})}$ либо ${\displaystyle \phi ({\boldsymbol {x}})\in p({\boldsymbol {x}})}$ или же ${\displaystyle \lnot \phi ({\boldsymbol {x}})\in p({\boldsymbol {x}})}$. Любой неполный тип называется частичный тип. Итак, слово тип вообще относится к любому п-тип, частичный или полный, по любому выбранному набору параметров (возможно, пустому набору).

An п-тип п(Икс) называется реализовано в ${\displaystyle {\mathcal {M}}}$ если есть элемент б ∈ M^п такой, что ${\displaystyle {\mathcal {M}}\models p({\boldsymbol {b}})}$. Существование такой реализации гарантируется для любого типа теорема компактности, хотя реализация может иметь место в некоторых элементарное расширение из ${\displaystyle {\mathcal {M}}}$, а не в ${\displaystyle {\mathcal {M}}}$ сам. Если полный тип реализуется б в ${\displaystyle {\mathcal {M}}}$, то тип обычно обозначается ${\displaystyle tp_{n}^{\mathcal {M}}({\boldsymbol {b}}/A)}$ и упоминается как полный тип б над А.

Тип п(Икс) называется изолированные от ${\displaystyle \varphi }$, за ${\displaystyle \varphi \in p(x)}$, если ${\displaystyle \forall \psi ({\boldsymbol {x}})\in p({\boldsymbol {x}}),\operatorname {Th} ({\mathcal {M}})\models \varphi ({\boldsymbol {x}})\rightarrow \psi ({\boldsymbol {x}})}$. Поскольку конечные подмножества типа всегда реализуются в ${\displaystyle {\mathcal {M}}}$, всегда есть элемент б ∈ M^п такой, что φ(б) верно в ${\displaystyle {\mathcal {M}}}$; т.е. ${\displaystyle {\mathcal {M}}\models \varphi ({\boldsymbol {b}})}$, таким образом б реализует весь изолированный тип. Таким образом, изолированные типы будут реализованы в каждой элементарной подструктуре или расширении. Из-за этого нельзя пропустить изолированные типы (см. Ниже).

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

Примеры типов

Рассмотрим язык с одной бинарной связкой, которую мы обозначим как ${\displaystyle \in }$. Позволять ${\displaystyle {\mathcal {M}}}$ быть структурой ${\displaystyle \langle \omega ,\in _{\omega }\rangle }$ для этого языка, который является порядковым ${\displaystyle \omega }$ со стандартной хорошей упорядоченностью. Позволять ${\displaystyle {\mathcal {T}}}$ обозначают теорию ${\displaystyle {\mathcal {M}}}$.

Рассмотрим набор формул ${\displaystyle p(x):=\{n\in _{\omega }x\mid n\in \omega \}}$. Во-первых, мы утверждаем, что это тип. Позволять ${\displaystyle p_{0}(x)\subseteq p(x)}$ быть конечным подмножеством ${\displaystyle p(x)}$. Нам нужно найти ${\displaystyle b\in \omega }$ который удовлетворяет всем формулам в ${\displaystyle p_{0}}$. Что ж, мы можем просто взять преемника самого большого порядкового номера, упомянутого в наборе формул ${\displaystyle p_{0}(x)}$. Тогда это будет явно содержать все ординалы, упомянутые в ${\displaystyle p_{0}(x)}$. Таким образом, мы имеем ${\displaystyle p(x)}$ это тип. Затем обратите внимание, что ${\displaystyle p(x)}$ не реализуется в ${\displaystyle {\mathcal {M}}}$. Ибо, если бы это было, были бы некоторые ${\displaystyle n\in \omega }$ который содержит каждый элемент ${\displaystyle \omega }$. Если бы мы хотели реализовать тип, у нас могло возникнуть соблазн рассмотреть модель ${\displaystyle \langle \omega +1,\in _{\omega +1}\rangle }$, которая действительно является супермоделью ${\displaystyle {\mathcal {M}}}$ который понимает тип. К сожалению, это расширение не элементарно, то есть данная модель не должна удовлетворять ${\displaystyle {\mathcal {T}}}$. В частности, приговор ${\displaystyle \exists x\forall y(y\in x\lor y=x)}$ доволен этой моделью, а не ${\displaystyle {\mathcal {M}}}$.

Итак, мы хотим реализовать тип в простейшем расширении. Мы можем сделать это, определив новую структуру на языке, которую мы обозначим ${\displaystyle {\mathcal {M}}'}$. Домен структуры будет ${\displaystyle \omega \cup \mathbb {Z} '}$ куда ${\displaystyle \mathbb {Z} '}$ набор целых чисел, украшенный таким образом, что ${\displaystyle \mathbb {Z} '\cap \omega =\emptyset }$. Позволять ${\displaystyle <}$ обозначают обычный порядок ${\displaystyle \mathbb {Z} '}$. Интерпретируем символ ${\displaystyle \in }$ в нашей новой структуре ${\displaystyle \in _{{\mathcal {M}}'}=\in _{\omega }\cup <\cup \,(\omega \times \mathbb {Z} ')}$. Идея состоит в том, что мы добавляем "${\displaystyle \mathbb {Z} }$-цепочка ", или копия целых чисел, прежде всего конечных ординалов. Очевидно, что любой элемент ${\displaystyle \mathbb {Z} '}$ понимает тип ${\displaystyle p(x)}$. Более того, можно убедиться, что это расширение элементарно.

Другой пример: полный тип числа 2 над пустым набором, рассматриваемым как член натуральных чисел, будет набором всех операторов первого порядка, описывающих переменную. Икс, что верно, когда Икс = 2. Этот набор будет включать такие формулы, как ${\displaystyle \,\!x\neq 1+1+1}$, ${\displaystyle x\leq 1+1+1+1+1}$, и ${\displaystyle \exists y(y<x)}$. Это пример изолированного типа, поскольку, работая над теорией натуральных чисел, формула ${\displaystyle x=1+1}$ подразумевает все остальные формулы, которые верны относительно числа 2.

В качестве дальнейшего примера утверждения

${\displaystyle \forall y(y^{2}<2\implies y<x)}$

и

${\displaystyle \forall y((y>0\land y^{2}>2)\implies y>x)}$

описывая квадратный корень из 2 согласуются с аксиомами упорядоченные поля, и может быть расширен до полного типа. Этот тип не реализуется в упорядоченном поле рациональных чисел, но реализуется в упорядоченном поле вещественных чисел. Точно так же бесконечный набор формул (над пустым набором) {x> 1, x> 1 + 1, x> 1 + 1 + 1, ...} не реализуется в упорядоченном поле действительных чисел, а реализуется в упорядоченном поле гиперреалы. Если мы разрешаем параметры, например все вещественные числа, мы можем указать тип ${\displaystyle \{0<x<r:r\in \mathbb {R} \}}$ что реализуется бесконечно малый гиперреальное, что нарушает Архимедова собственность.

Причина, по которой полезно ограничить параметры определенным подмножеством модели, заключается в том, что это помогает отличать типы, которые могут быть удовлетворены, от тех, которые не могут. Например, используя весь набор действительных чисел в качестве параметров, можно сгенерировать бесчисленное множество формул типа ${\displaystyle x\neq 1}$, ${\displaystyle x\neq \pi }$, ... это явно исключило бы все возможные реальные значения для Икс, и поэтому никогда не может быть реализовано в реальных числах.

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

Полезно рассматривать комплект полной п-типы более А как топологическое пространство. Рассмотрим следующее отношение эквивалентности формул в свободных переменных Икс₁,…, Икс_п с параметрами в А:

${\displaystyle \psi \equiv \phi \Leftrightarrow {\mathcal {M}}\models \forall x_{1},\ldots ,x_{n}(\psi (x_{1},\ldots ,x_{n})\leftrightarrow \phi (x_{1},\ldots ,x_{n})).}$

Можно показать, что ${\displaystyle \psi \equiv \phi }$ тогда и только тогда, когда они содержатся в точно таких же полных типах.

Набор формул в свободных переменных Икс₁,…,Икс_п над А с точностью до этого отношения эквивалентности является Булева алгебра (и канонически изоморфен множеству А-определяемые подмножества M^п). Полный п-типы соответствуют ультрафильтры этой булевой алгебры. Комплект полного п-типы могут быть преобразованы в топологическое пространство, взяв наборы типов, содержащие данную формулу, в качестве основных открытых множеств. Это создает Каменное пространство, который компактный, Хаусдорф, и полностью отключен.

Пример. Полная теория алгебраически замкнутые поля из характеристика 0 имеет исключение квантора, что позволяет показать, что возможные полные 1-типы (над пустым множеством) соответствуют:

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

Другими словами, 1-типы в точности соответствуют первичным идеалам кольца многочленов Q[Икс] над рациональными Q: если р является элементом модели типа п, то идеал, соответствующий п - множество многочленов с р как корень (который является нулевым многочленом, если р трансцендентно). В общем, полный п-типы соответствуют первичным идеалам кольца многочленов Q[Икс₁,...,Икс_п], другими словами, в точки простой спектр этого кольца. (Топологию пространства Стоуна фактически можно рассматривать как Топология Зарисского из Логическое кольцо индуцируется естественным образом из булевой алгебры. Хотя топология Зарисского в общем случае не хаусдорфова, она имеет место в случае булевых колец.) Например, если q(Икс,у) является неприводимым многочленом от двух переменных, существует 2-тип, реализации которого (неформально) пары (Икс,у) элементов с q(Икс,у)=0.

Теорема об исключении типов

Учитывая полное п-тип п можно спросить, существует ли модель теории, которая пропускает пДругими словами, нет п-комплект в модели, реализующий п. Если п является изолированная точка в пространстве Камня, т.е. если {п} - открытый набор, легко видеть, что каждая модель реализует п (по крайней мере, если теория полная). В теорема об исключении типов говорит, что наоборот, если п не изолирована, то существует счетная модель, исключающая п (при условии, что язык счетный).

Пример: В теории алгебраически замкнутых полей характеристики 0 существует 1-тип, представленный элементами, трансцендентными над основное поле. Это неизолированная точка пространства Стоуна (фактически единственная неизолированная точка). Поле алгебраических чисел - это модель, исключающая этот тип, и алгебраическое замыкание любого трансцендентное расширение из рациональных - это модель, реализующая этот тип.

Все остальные типы являются «алгебраическими числами» (точнее, они представляют собой наборы утверждений первого порядка, которым удовлетворяет некоторое заданное алгебраическое число), и все такие типы реализуются во всех алгебраически замкнутых полях характеристики 0.

Рекомендации

• Ходжес, Уилфрид (1997). Более короткая теория модели. Издательство Кембриджского университета. ISBN  0-521-58713-1.
• Чанг, К.; Кейслер, Х. Джером (1989). Модельная теория (третье изд.). Эльзевир. ISBN  0-7204-0692-7.
• Маркер, Дэвид (2002). Теория моделей: введение. Тексты для выпускников по математике 217. Springer. ISBN  0-387-98760-6.