В теории моделей, ветви математической логики, элементарный класс (или аксиоматизируемый класс ) - это класс, состоящий из всех структур, удовлетворяющих фиксированной теории первого порядка .
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 class (Hodges, 1993).
Для такого расхождения в терминологии есть веские причины. сигнатуры, которые рассматриваются в общей теории моделей, часто бесконечны, в то время как одно предложение first-order содержит только конечное число символов. Таким образом, базовые элементарные классы нетипичны в теории бесконечных моделей. С другой стороны, теория конечных моделей имеет дело почти исключительно с конечными сигнатурами. Легко видеть, что для любой конечной сигнатуры σ и для любого замкнутого относительно изоморфизма класса K σ-структур существует элементарный класс таких σ-структур, что K и содержат точно такие же конечные структуры. Следовательно, элементарные классы не очень интересны теоретикам конечных моделей.
Ясно, что каждый базовый элементарный класс является элементарным классом, а каждый элементарный класс является псевдоэлементарным классом. Более того, как простое следствие из теоремы компактности, класс σ-структур является базисным элементарным тогда и только тогда, когда он элементарен, и его дополнение также элементарно.
Пусть σ будет сигнатурой, состоящей только из унарной функции символа f. Класс K σ-структур, в котором f взаимно однозначно, является базовым элементарным классом. Об этом свидетельствует теория T, которая состоит только из одного предложения
Пусть σ - произвольная сигнатура. Класс K всех бесконечных σ-структур элементарен. Чтобы увидеть это, рассмотрим предложения
и т. д.. (Таким образом, предложение говорит, что существует по крайней мере n элементов.) Бесконечные σ-структуры являются в точности моделями теории
Но K не является базовым элементарным классом. В противном случае бесконечные σ-структуры были бы в точности такими, которые удовлетворяли бы некоторому предложению первого порядка τ. Но тогда множество будет несовместимым. По теореме компактности для некоторого натурального числа n множество будет несовместимым. Но это абсурд, потому что этой теории удовлетворяет любая σ-структура с или более элементами.
Однако в сигнатуре есть базовый элементарный класс K ': σ' = σ {f}, где f - унарный функциональный символ., такая, что K состоит в точности из редуктов к σ σ'-структур в K '. K 'аксиоматизируется одним предложением , который выражает, что f инъективен, но не сюръективен. Следовательно, K является элементарным и то, что можно было бы назвать базовым псевдоэлементарным, но не базовым элементарным.
Наконец, рассмотрим сигнатуру σ, состоящую из одного унарного символа отношения P. Каждая σ-структура разделена на две подмножества: те элементы, для которых выполняется P, и остальные. Пусть K - класс всех σ-структур, для которых эти два подмножества имеют одинаковую мощность, т.е. между ними существует биекция. Этот класс не является элементарным, потому что σ-структура, в которой множество реализаций P и ее дополнение счетно бесконечны, удовлетворяет в точности тем же предложениям первого порядка, что и σ-структура, в которой одно из множеств счетно бесконечно и другое неисчислимо.
Теперь рассмотрим сигнатуру , которая состоит из P вместе с унарным функциональным символом f. Пусть будет классом всех -структур, таких что f является биекцией и P выполняется для x тогда и только тогда, когда P не выполняется для f (x). явно является элементарным классом, и поэтому K является примером псевдоэлементарного класса, который не является элементарным.
Пусть σ - произвольная сигнатура. Класс K всех конечных σ-структур не является элементарным, потому что (как показано выше) его дополнение элементарно, но не элементарно элементарно. Поскольку это также верно для любой сигнатуры, расширяющей σ, K даже не является псевдоэлементарным классом.
Этот пример демонстрирует пределы выразительной силы, присущие логике первого порядка, в отличие от гораздо более выразительной логики второго порядка. Однако логика второго порядка не может сохранить многие желательные свойства логики первого порядка, такие как теоремы полноты и компактности.