Элементарный класс

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

• 1 Определение
• 2 Противоречивая и альтернативная терминология
• 3 Простые связи между понятиями
• 4 Примеры
  • 4.1 Базовый элементарный класс
  • 4.2 Элементарный базовый псевдоэлементарный класс, не являющийся базовым ic elementary
  • 4.3 Псевдоэлементарный класс, который не является элементарным
  • 4.4 Непсевдоэлементарный класс
• 5 Ссылки

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

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

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

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

Для такого расхождения в терминологии есть веские причины. сигнатуры, которые рассматриваются в общей теории моделей, часто бесконечны, в то время как одно предложение first-order содержит только конечное число символов. Таким образом, базовые элементарные классы нетипичны в теории бесконечных моделей. С другой стороны, теория конечных моделей имеет дело почти исключительно с конечными сигнатурами. Легко видеть, что для любой конечной сигнатуры σ и для любого замкнутого относительно изоморфизма класса K σ-структур существует элементарный класс $K\; \prime \; \{\backslash \; displaystyle\; K\; \text{'}\}$таких σ-структур, что K и $K\; \prime \; \{\backslash \; displaystyle\; K\; \text{'}\}$содержат точно такие же конечные структуры. Следовательно, элементарные классы не очень интересны теоретикам конечных моделей.

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

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

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

$\forall \; x\; \forall \; y\; ((f\; (x)\; =\; f\; (y))\; \to \; (x\; =\; y))\; \{\backslash \; displaystyle\; \backslash \; forall\; x\; \backslash \; forall\; y\; ((f\; (x)\; =\; f\; (y))\; \backslash \; to\; (x\; =\; y))\}$.

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

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

$\rho \; 2\; =\; \{\backslash \; displaystyle\; \backslash \; rho\; \_\; \{2\}\; =\; \{\}\}$"$\exists \; x\; 1\; \exists \; x\; 2\; (x\; 1\; \ne \; x\; 2)\; \{\backslash \; displaystyle\; \backslash \; exists\; x\_\; \{1\; \}\; \backslash \; существует\; x\_\; \{2\}\; (x\_\; \{1\}\; \backslash \; not\; =\; x\_\; \{2\})\}$",

$\rho \; 3\; =\; \{\backslash \; displaystyle\; \backslash \; rho\; \_\; \{3\}\; =\; \{\}\}$"$\exists \; x\; 1\; \exists \; x\; 2\; \exists \; Икс\; 3\; ((Икс\; 1\; \ne \; Икс\; 2)\; \wedge \; (Икс\; 1\; \ne \; Икс\; 3)\; \wedge \; (Икс\; 2\; \ne \; Икс\; 3))\; \{\backslash \; Displaystyle\; \backslash \; существует\; x\_\; \{1\}\; \backslash \; существует\; x\_\; \{2\}\; \backslash \; существует\; x\_\; \{3\}\; ((\; x\_\; \{1\}\; \backslash \; not\; =\; x\_\; \{2\})\; \backslash \; land\; (x\_\; \{1\}\; \backslash \; not\; =\; x\_\; \{3\})\; \backslash \; land\; (x\_\; \{2\}\; \backslash \; not\; =\; x\_\; \{3\}))\}$",

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

$T\; \infty \; знак\; равно\; \{\rho \; 2,\; \rho \; 3,\; \rho \; 4,\dots \}\; \{\backslash \; displaystyle\; T\; \_\; \{\backslash \; infty\}\; =\; \backslash \; \{\backslash \; rho\; \_\; \{2\},\; \backslash \; rho\; \_\; \{3\},\; \backslash \; rho\; \_\; \{4\},\; \backslash \; dots\; \backslash \; \}\}$.

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

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

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

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

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

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

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

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

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