Начальный класс

В теории моделей , разделе математической логики , элементарный класс (или аксиоматизируемый класс ) — это класс, состоящий из всех структур , удовлетворяющих фиксированной первого порядка теории .

Определение

Класс из K структур , т. е. из всех σ-структур , сигнатуры K σ называется элементарным классом, если существует первого порядка теория T сигнатуры σ такая, что состоит всех моделей T удовлетворяющих T . Если T можно выбрать как теорию, состоящую из одного предложения первого порядка, то K называется базовым элементарным классом .

В более общем смысле, K является псевдоэлементарным классом , если существует теория T первого порядка сигнатуры, расширяющая σ, такая, что K состоит из всех σ-структур, которые сводятся к σ моделей T . Другими словами, класс K σ-структур является псевдоэлементарным тогда и только тогда, когда существует элементарный класс K' такой, что K состоит именно из редуктов к σ структур из K' .

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

Противоречивая и альтернативная терминология

Хотя вышеизложенное в настоящее время является стандартной терминологией в «бесконечной» теории моделей , несколько другие более ранние определения все еще используются в теории конечных моделей , где элементарный класс можно назвать Δ-элементарным классом , а термины «элементарный класс» и «первый порядок» аксиоматизируемые классы зарезервированы для основных начальных классов (Эббингауз и др., 1994, Эббингауз и Флум, 2005). Ходжес называет элементарные классы аксиоматизируемыми классами , а базовые элементарные классы он называет определяемыми классами . Он также использует соответствующие синонимы EC. $_{\Delta }$ класс и класс EC (Hodges, 1993).

Для такого расхождения в терминологии есть веские причины. Сигнатуры , рассматриваемые в общей теории моделей, часто бесконечны, а одно первого порядка предложение содержит лишь конечное число символов. Поэтому базовые элементарные классы нетипичны для теории бесконечных моделей. С другой стороны, теория конечных моделей имеет дело почти исключительно с конечными сигнатурами. Легко видеть, что для каждой конечной сигнатуры σ и для каждого класса K σ-структур, замкнутых относительно изоморфизма, существует элементарный класс $K'$ σ-структур таких, что K и $K'$ содержат точно такие же конечные структуры. Следовательно, элементарные классы не очень интересны для теоретиков конечных моделей.

Простые отношения между понятиями

Очевидно, что каждый базовый элементарный класс является элементарным классом, а каждый элементарный класс — псевдоэлементарным классом. Более того, как простое следствие теоремы о компактности , класс σ-структур является базисным элементарным тогда и только тогда, когда он элементарен и его дополнение также элементарно.

Примеры

Базовый элементарный класс

Пусть σ — подпись, состоящая только из унарного функционального символа f . Класс K σ-структур, в которых f является взаимно однозначен, базовым элементарным классом. Об этом свидетельствует теория Т , состоящая только из одного предложения

$\forall x\forall y((f(x)=f(y))\to (x=y))$.

Элементарный, базовый псевдоэлементарный класс, который не является базовым элементарным

Пусть σ — произвольная подпись. Класс K всех бесконечных σ-структур элементарен. Чтобы убедиться в этом, рассмотрим предложения

$\rho _{2}={}$ " $\exists x_{1}\exists x_{2}(x_{1}\not =x_{2})$",

$\rho _{3}={}$ " $\exists x_{1}\exists x_{2}\exists x_{3}((x_{1}\not =x_{2})\land (x_{1}\not =x_{3})\land (x_{2}\not =x_{3}))$",

и так далее. (Итак, предложение $\rho _{n}$ говорит, что существует по крайней мере n элементов.) Бесконечные σ-структуры являются в точности моделями теории

$T_{\infty }=\{\rho _{2},\rho _{3},\rho _{4},\dots \}$.

Но К — это не базовый элементарный класс. В противном случае бесконечные σ-структуры были бы именно теми, которые удовлетворяют некоторому предложению первого порядка τ. Но тогда набор $\{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots \}$ было бы противоречиво. По теореме компактности для некоторого натурального числа n множество $\{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots ,\rho _{n}\}$ было бы противоречиво. Но это абсурдно, поскольку этой теории удовлетворяет любая конечная σ-структура с $n+1$ или более элементов.

существует базовый элементарный класс K'. Однако в сигнатуре σ' = σ $\cup$ { f }, где f — унарный функциональный символ, такой, что K состоит в точности из редукций к σ σ'-структур в K' . К' аксиоматизируется одним предложением $(\forall x\forall y(f(x)=f(y)\rightarrow x=y)\land \exists y\neg \exists x(y=f(x))),$, которое выражает, что f инъективен, но не сюръективен. Следовательно, K является элементарным и тем, что можно было бы назвать базовым псевдоэлементарным, но не базовым элементарным.

Псевдоэлементарный класс, который не является элементарным

состоящую из одного символа унарного отношения P. Наконец, рассмотрим подпись σ , Любая σ-структура разбивается на два подмножества: элементы, для которых выполняется P , и остальные. Пусть K — класс всех σ-структур, для которых эти два подмножества имеют одинаковую мощность , т. е. между ними существует взаимно однозначное соответствие. Этот класс не является элементарным, поскольку σ-структура, в которой как множество реализаций P , так и его дополнение счетно бесконечны, удовлетворяет точно тем же предложениям первого порядка, что и σ-структура, в которой одно из множеств счетно бесконечно, а другое неисчислимо.

Теперь рассмотрим подпись $\sigma '$, который состоит из P вместе с символом унарной функции f . Позволять $K'$ быть классом всех $\sigma '$-структуры такие, что f является биекцией и P выполняется для x тогда и только тогда, когда P не выполняется для f(x) . $K'$ очевидно, является элементарным классом, и поэтому K является примером псевдоэлементарного класса, который не является элементарным.

Непсевдоэлементарный класс

Пусть σ — произвольная подпись. Класс K всех конечных σ-структур не является элементарным, поскольку (как показано выше) его дополнение элементарно, а не базисно элементарно. Поскольку это также верно для любой сигнатуры, расширяющей σ, K даже не является псевдоэлементарным классом.

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

Ссылки

• Чанг, Чен Чунг ; Кейслер, Х. Джером (1990) [1973], Теория моделей , Исследования по логике и основам математики (3-е изд.), Elsevier , ISBN  978-0-444-88054-3
• Эббингауз, Хайнц-Дитер ; Флум, Йорг (2005) [1995], Теория конечных моделей , Берлин, Нью-Йорк: Springer-Verlag , с. 360, ISBN  978-3-540-28787-2
• Эббингауз, Хайнц-Дитер; Флум, Йорг; Томас, Вольфганг (1994), Математическая логика (2-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-0-387-94258-2
• Ходжес, Уилфрид (1997), Более короткая теория модели , Cambridge University Press , ISBN  978-0-521-58713-6
• Пуаза, Бруно (2000), Курс теории моделей: введение в современную математическую логику , Берлин, Нью-Йорк: Springer-Verlag , ISBN  978-0-387-98655-5