В теории моделей , разделе математической логики , элементарный класс (или аксиоматизируемый класс ) — это класс, состоящий из всех структур , удовлетворяющих фиксированной теории первого порядка .
Класс K структур сигнатуры σ называется элементарным классом , если существует теория первого порядка T сигнатуры σ, такая, что K состоит из всех моделей T , т. е. всех σ-структур, удовлетворяющих T. Если T можно выбрать как теорию, состоящую из одного предложения первого порядка, то K называется базовым элементарным классом .
В более общем случае K является псевдоэлементарным классом , если существует теория первого порядка T сигнатуры, которая расширяет σ, такая, что K состоит из всех σ-структур, которые являются редуктами к σ моделей T. Другими словами, класс K σ-структур является псевдоэлементарным тогда и только тогда, когда существует элементарный класс K' такой, что K состоит в точности из редуктов к σ структур в K' .
По понятным причинам элементарные классы также называются аксиоматизируемыми в логике первого порядка , а базовые элементарные классы называются конечно аксиоматизируемыми в логике первого порядка . Эти определения очевидным образом распространяются на другие логики, но поскольку случай первого порядка является наиболее важным, аксиоматизируемый неявно относится к этому случаю, когда не указано никакой другой логики.
Хотя вышеизложенное в настоящее время является стандартной терминологией в теории «бесконечных» моделей , несколько отличающиеся более ранние определения все еще используются в теории конечных моделей , где элементарный класс может быть назван Δ-элементарным классом , а термины элементарный класс и аксиоматизируемый класс первого порядка зарезервированы для базовых элементарных классов (Ebbinghaus et al. 1994, Ebbinghaus and Flum 2005). Ходжес называет элементарные классы аксиоматизируемыми классами , а базовые элементарные классы он называет определяемыми классами . Он также использует соответствующие синонимы класс EC и класс EC (Hodges, 1993).
Для этой расходящейся терминологии есть веские причины. Сигнатуры , которые рассматриваются в общей теории моделей, часто бесконечны, в то время как одно предложение первого порядка содержит только конечное число символов. Поэтому базовые элементарные классы нетипичны в теории бесконечных моделей. С другой стороны, теория конечных моделей имеет дело почти исключительно с конечными сигнатурами. Легко видеть, что для каждой конечной сигнатуры σ и для каждого класса 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 даже не является псевдоэлементарным классом.
Этот пример демонстрирует ограничения выразительной силы, присущие логике первого порядка , в отличие от гораздо более выразительной логики второго порядка . Однако логика второго порядка не сохраняет многие желательные свойства логики первого порядка, такие как теоремы о полноте и компактности .
