ГлавнаяАрхивРазрешимость ограниченных теорий класса частичных порядков

Разрешимость ограниченных теорий класса частичных порядков | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/1

Классическая алгебраическая геометрия изучает множества решений алгебраических уравнений над полями вещественных и комплексных чисел. В последние 20 лет активно развивается так называемая универсальная алгебраическая геометрия, в которой изучаются системы уравнений над произвольными алгебраическими системами. При этом особое значение имеют универсальные и экзистенциальные теории - от их сложности зависят перспективы построения «хорошей» алгебраической геометрии над той или иной алгебраической системой. В работе доказывается, что экзистенциальная и универсальная теории класса всех частичных порядков являются разрешимыми.
  • Title Разрешимость ограниченных теорий класса частичных порядков
  • Headline Разрешимость ограниченных теорий класса частичных порядков
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 45
  • Date:
  • DOI 10.17223/20710410/45/1
Ключевые слова
частично упорядоченное множество, частичные порядки, разрешимость универсальной теории, разрешимость экзистенциальной теории, классы, partial ly ordered set, poset, decidability of univarsal theory, decidability of existential theory, classes
Авторы
Ссылки
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: Изд-во СО РАН, 2016. 288 с
Матиясевич Ю. В. Диофантовость перечислимых множеств // Доклады АН СССР. 1970. Т.191. №2. С. 279-282
Mayr E. W. and Meyer A. R. The complexity of the word problems for commutative semigroups and polynomial ideals // Adv. Math. 1982. V. 46(3). P. 305-329
Cook S. A. The complexity of theorem proving procedures // Proc. 3d Ann. ACM Symp. Theory of Computing. N.Y., USA, 1971. P. 151-158
Никитин А. Ю., Рыбалов А. Н. О сложности проблемы разрешимости систем уравнений над конечными частичными порядками // Прикладная дискретная математика. 2018. № 39. С. 94-98
Tarski A. Undecidability of the theory of lattices and projective geometries // J. Symbolic Logic. 1949. V. 15. P. 77-78
Ax J. The elementary theory of finite fields // Ann. Math. 1968. V. 88. No. 2. P. 239-271
Лавров И.А. Эффективная неотделимость множества тождественно истинных и конечно опровержимых формул некоторых элементарных теорий // Алгебра и логика. 1963. Т. 2. № 1. С. 5-18
Ильев А.В. Разрешимость универсальных теорий и аксиоматизируемость наследственных классов графов // Труды Института математики и механики УрО РАН. 2016. Т. 22. № 1. С. 100-111
Gratzer G. General Lattice Theory. Birkhauser, 1998. 663 p
Оре О. Теория графов. М.: Наука, 1980. 336 с
Marker D Model Theory: An Introduction. N.Y..: Springer, 2002. 342 p
Разрешимость ограниченных теорий класса частичных порядков | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/1
Разрешимость ограниченных теорий класса частичных порядков | Прикладная дискретная математика. 2019. № 45. DOI: 10.17223/20710410/45/1