Аксиоматизируемость и разрешимость универсальных теорий наследственных классов моделей конечных и бесконечных языков | Прикладная дискретная математика. 2024. № 66. DOI: 10.17223/20710410/66/2

Изучаются наследственные классы алгебраических систем языка L = Lfin ∪ L∞, где Lfin = ⟨R1,R2, . . . ,Rm,=⟩ и L∞ = ⟨Rm+1,Rm+2, . . .⟩, причём в L∞ число пре дикатов каждой местности конечно, все предикаты упорядочены по возрастанию своих местностей и обладают свойством неповторения элементов. Класс L-систем называется наследственным, если он замкнут относителвно подсистем. Доказано, что класс L-систем является наследственным тогда и толвко тогда, когда он может бытв определён в терминах запрещённых подсистем. Класс L-систем называется универсалвно аксиоматизируемым, если существует такое множество универсалвных предложений Z язык a L, что этот класс состоит из всех систем, удовлетворяющих множеству Z. Рассмотрены вопросы универсалвной аксиоматизируемости наследственных классов L-систем. Показано, что наследственный класс L-систем универсалвно аксиоматизируем, если и толвко если он может бытв определён в терминах конечных запрещённых подсистем. Доказана разрешимости универсалвной теории произволвного аксиоматизируемого наследственного класса L-систем, множество минимальных запрещённых подсистем которого рекурсивно.