Введение

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

Определение

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

Конфликтная и альтернативная терминология

В то время как вышеописанное в настоящее время является стандартной терминологией в теории бесконечных моделей, несколько отличающиеся более ранние определения все еще используются в теории конечных моделей, где элементарный класс может называться Δ-элементарным классом, а термины «элементарный класс» и «аксиоматизируемый класс первого порядка» зарезервированы для основных элементарных классов (Ebbinghaus et al. 1994, Эббингхаус и Флам 2005). Ходжес называет элементарные классы аксиоматизируемыми классами, а основные элементарные классы – определяемыми классами. Он также использует соответствующие синонимы EC-класс и EC-класс (Hodges, 1993). Существуют веские причины для такого различия в терминологии. Подписи, рассматриваемые в общей теории моделей, часто бесконечны, в то время как единственное предложение первого порядка содержит лишь конечное число символов. Поэтому основные элементарные классы нетипичны для теории бесконечных моделей. Теория конечных моделей, напротив, практически исключительно имеет дело с конечными подписями. Легко показать, что для каждой конечной подписи σ и для каждого класса K структур σ, замкнутого относительно изоморфизма, существует элементарный класс структур σ, содержащий ровно те же конечные структуры, что и K. Следовательно, элементарные классы не представляют большого интереса для теоретиков конечных моделей.

Легкие отношения между понятиями

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

Основной класс начальной школы

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

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

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

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

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