Geodesic
Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition
Matematičeskie zametki, Tome 76 (2004) no. 3, pp. 362-371 
S. M. Dudakov. Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition. Matematičeskie zametki, Tome 76 (2004) no. 3, pp. 362-371. http://geodesic.mathdoc.fr/item/MZM_2004_76_3_a5/
@article{MZM_2004_76_3_a5,
     author = {S. M. Dudakov},
     title = {Collapse {Result} for {Extensions} of the {Presburger} {Arithmetic} by {a~Unary} {Function} {Compatible} with {Addition}},
     journal = {Matemati\v{c}eskie zametki},
     pages = {362--371},
     year = {2004},
     volume = {76},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MZM_2004_76_3_a5/}
}
TY  - JOUR
AU  - S. M. Dudakov
TI  - Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition
JO  - Matematičeskie zametki
PY  - 2004
SP  - 362
EP  - 371
VL  - 76
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/MZM_2004_76_3_a5/
LA  - ru
ID  - MZM_2004_76_3_a5
ER  - 
%0 Journal Article
%A S. M. Dudakov
%T Collapse Result for Extensions of the Presburger Arithmetic by a Unary Function Compatible with Addition
%J Matematičeskie zametki
%D 2004
%P 362-371
%V 76
%N 3
%U http://geodesic.mathdoc.fr/item/MZM_2004_76_3_a5/
%G ru
%F MZM_2004_76_3_a5

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

Earlier, Belegradek, Stolboushkin, and Taitslin proved that the collapse result holds in the theory of natural numbers with addition, i.e., each locally generic query using addition can be written without it. In this paper, we use the sufficient conditions of the collapse result obtained by Taitslin to prove that it holds in any extensions of the Presburger arithmetic by a unary function compatible with addition. The notion of a function compatible with addition was proposed by A. L. Semenov.

[1] Belegradek O. V., Stolboushkin A. P., Taitslin M. A., “Extended order-generic queries”, Ann. Pure Appl. Logic, 97 (1999), 85–125 | DOI | MR | Zbl

[2] Semenov A. L., “Logicheskie teorii odnomestnykh funktsii na naturalnom ryade”, Izv. AN SSSR, 47:3 (1983), 623–658 | MR

[3] Semenov A. L., “O nekotorykh rasshireniyakh arifmetiki slozheniya naturalnykh chisel”, Izv. AN SSSR, 43:5 (1979), 1175–1195 | MR | Zbl

[4] Taitslin M. A., “A general condition for collapse results”, Ann. Pure Appl. Logic, 113 (2001), 323–330 | DOI | MR

[5] Keisler G., Chen Ch. Ch., Teoriya modelei, Mir, M., 1977

[6] Benedikt M., Dong G., Libkin L., Wong L., “Relational expressive power of constraint query languages”, Proc. 15th ACM Symp. on Principles of Database Systems, 1996, 5–16