Geodesic
Finite quantifier hierarchies in relational algebras
Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 291-296 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

For a given structure of finite signature, one can construct a hierarchy of classes of relations definable in this structure according to the number of quantifier alternations in the formulas expressing the relations. In ordinary examples, this hierarchy is either infinite (as in the arithmetic of addition and multiplication of natural numbers) or stabilizes very rapidly (in structures with decidable theories, such as the field of real numbers). In the present paper, we construct a series of examples showing that the above-mentioned hierarchy may have an arbitrary finite length. The proof employs a modification of the Ehrenfeucht game. 
@article{TM_2011_274_a15,
     author = {A. L. Semenov and S. F. Soprunov},
     title = {Finite quantifier hierarchies in relational algebras},
     journal = {Trudy Matematicheskogo Instituta imeni V.A. Steklova},
     pages = {291--296},
     year = {2011},
     volume = {274},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TM_2011_274_a15/}
}
TY  - JOUR
AU  - A. L. Semenov
AU  - S. F. Soprunov
TI  - Finite quantifier hierarchies in relational algebras
JO  - Trudy Matematicheskogo Instituta imeni V.A. Steklova
PY  - 2011
SP  - 291
EP  - 296
VL  - 274
UR  - http://geodesic.mathdoc.fr/item/TM_2011_274_a15/
LA  - ru
ID  - TM_2011_274_a15
ER  - 
%0 Journal Article
%A A. L. Semenov
%A S. F. Soprunov
%T Finite quantifier hierarchies in relational algebras
%J Trudy Matematicheskogo Instituta imeni V.A. Steklova
%D 2011
%P 291-296
%V 274
%U http://geodesic.mathdoc.fr/item/TM_2011_274_a15/
%G ru
%F TM_2011_274_a15
A. L. Semenov; S. F. Soprunov. Finite quantifier hierarchies in relational algebras. Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 291-296. http://geodesic.mathdoc.fr/item/TM_2011_274_a15/

[1] Semenov A.L., “Usloviya konechnosti dlya algebr otnoshenii”, Tr. MIAN, 242, 2003, 103–107 | Zbl

[2] Vereschagin N.K., Shen A., Yazyki i ischisleniya, MTsNMO, M., 2000