Classical algebraic geometry studies the solution sets of algebraic equations over the fields of real and complex numbers. In the past 20 years, the so-called universal algebraic geometry, which studies systems of equations over arbitrary algebraic structures, has been actively developed. In this frameworks, universal and existential theories are very important, the prospect for constructing good algebraic geometry over algebraic systems depends on their complexity. In this paper, we prove that the existential and universal theories of the class of all finite orders are decidable.
Download file
Counter downloads: 190
- Title Decidability of the restricted theories of a class of partial orders
- Headline Decidability of the restricted theories of a class of partial orders
- Publesher
Tomsk State University
- Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 45
- Date:
- DOI 10.17223/20710410/45/1
Keywords
частично упорядоченное множество, частичные порядки, разрешимость универсальной теории, разрешимость экзистенциальной теории, классы, partial ly ordered set, poset, decidability of univarsal theory, decidability of existential theory, classesAuthors
References
Даниярова Э. Ю., Мясников А. Г., Ремесленников В. Н. Алгебраическая геометрия над алгебраическими системами. Новосибирск: Изд-во СО РАН, 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

Decidability of the restricted theories of a class of partial orders | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2019. № 45. DOI: 10.17223/20710410/45/1
Download full-text version
Counter downloads: 385