|
Теоретические основы прикладной дискретной математики
Аксиоматизируемость и разрешимость универсальных теорий наследственных классов моделей конечных и бесконечных языков
А. В. Ильев Институт математики им. С. Л. Соболева СО РАН, г. Омск, Россия
Аннотация:
Изучаются наследственные классы алгебраических систем языка ${{\rm L} = {\rm L_{fin}} \cup {\rm L_\infty}}$, где ${{\rm L_{fin}} = \langle R_1,R_2,\ldots, R_m, = \rangle}$ и ${{\rm L_\infty} = \langle R_{m+1}, R_{m+2}, \ldots \rangle}$, причём в ${\rm L_\infty}$ число предикатов каждой местности конечно, все предикаты упорядочены по возрастанию своих местностей и обладают свойством неповторения элементов. Класс ${\rm L}$-систем называется наследственным, если он замкнут относительно подсистем. Доказано, что класс ${\rm L}$-систем является наследственным тогда и только тогда, когда он может быть определён в терминах запрещённых подсистем. Класс ${\rm L}$-систем называется универсально аксиоматизируемым, если существует такое множество универсальных предложений $Z$ языка ${\rm L}$, что этот класс состоит из всех систем, удовлетворяющих множеству $Z$. Рассмотрены вопросы универсальной аксиоматизируемости наследственных классов ${\rm L}$-систем. Показано, что наследственный класс ${\rm L}$-систем универсально аксиоматизируем, если и только если он может быть определён в терминах конечных запрещённых подсистем. Доказана разрешимость универсальной теории произвольного аксиоматизируемого наследственного класса ${\rm L}$-систем, множество минимальных запрещённых подсистем которого рекурсивно.
Ключевые слова:
алгебраическая система, наследственный класс, универсальная теория, универсальная аксиоматизируемость, разрешимость.
Образец цитирования:
А. В. Ильев, “Аксиоматизируемость и разрешимость универсальных теорий наследственных классов моделей конечных и бесконечных языков”, ПДМ, 2024, № 66, 14–29
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/pdm852 https://www.mathnet.ru/rus/pdm/y2024/i4/p14
|
| Статистика просмотров: |
| Страница аннотации: | 269 | | PDF полного текста: | 81 | | Список литературы: | 85 |
|