Geodesic
Decidability of the restricted theories of a class of~partial orders
Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 6-12.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: partially ordered set, poset, decidability of univarsal theory, decidability of existential theory
Mots-clés : classes. 
@article{PDM_2019_3_a1,
     author = {A. Yu. Nikitin},
     title = {Decidability of the restricted theories of a class of~partial orders},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {6--12},
     publisher = {mathdoc},
     number = {3},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_3_a1/}
}
TY  - JOUR
AU  - A. Yu. Nikitin
TI  - Decidability of the restricted theories of a class of~partial orders
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 6
EP  - 12
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_3_a1/
LA  - ru
ID  - PDM_2019_3_a1
ER  - 
%0 Journal Article
%A A. Yu. Nikitin
%T Decidability of the restricted theories of a class of~partial orders
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 6-12
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_3_a1/
%G ru
%F PDM_2019_3_a1
A. Yu. Nikitin. Decidability of the restricted theories of a class of~partial orders. Prikladnaâ diskretnaâ matematika, no. 3 (2019), pp. 6-12. http://geodesic.mathdoc.fr/item/PDM_2019_3_a1/

[1] Daniyarova E. Y., Myasnikov A. G., Remeslennikov V. N., Algebraic Geometry over Algebraic Systems, SB RAS Publ., Novosibirsk, 2016, 288 pp. (in Russian)

[2] Matiyasevich Yu. V., “Diophantineity of enumerable sets”, Doklady Akademii Nauk USSR, 191:2 (1970), 279–282 (in Russian) | Zbl

[3] Mayr E. W., Meyer A. R., “The complexity of the word problems for commutative semigroups and polynomial ideals”, Adv. Math., 46:3 (1982), 305–329 | DOI | MR | Zbl

[4] Cook S. A., “The complexity of theorem proving procedures”, Proc. 3d Ann. ACM Symp. Theory of Computing (N.Y., USA, 1971), 151–158 | Zbl

[5] Nikitin A. Yu., Rybalov A. N., “On complexity of the satisfiability problem of systems over finite posets”, Prikladnaya Diskretnaya Matematika, 2018, no. 39, 94–98 (in Russian)

[6] Tarski A., “Undecidability of the theory of lattices and projective geometries”, J. Symbolic Logic, 15 (1949), 77–78

[7] Ax J., “The elementary theory of finite fields”, Ann. Math., 88:2 (1968), 239–271 | DOI | MR | Zbl

[8] Lavrov I. A., “Effective inseparability of the set of identically true and finitely refutable formulas of some elementary theories”, Algebra i Logica, 2:1 (1963), 5–18 (in Russian) | Zbl

[9] Il'ev A. V., “Decidability of universal theories and axiomatizability of hereditary classes of graphs”, Trudi Instituta Matematiki i Mehaniki UrO RAN, 22, no. 1, 2016, 100–111 (in Russian) | MR

[10] Gratzer G., General Lattice Theory, Birkhauser, 1998, 663 pp. | MR | Zbl

[11] Ore O., Theory of Graphs, American Mathematical Soc., 1962, 270 pp. | MR | Zbl

[12] Marker D., Model Theory: An Introduction, Springer, N.Y., 2002, 342 pp. | MR | Zbl