A collapse result for extensions of the Presburger arithmetic by a one-place function compatible with addition. (Q556528)

A linearly ordered structure \((M,<,\dots)\) is said to exhibit collapse to order if every query about finite states over \(M\), which is first-order in the structure and invariant under partial \(<\)-isomorphisms, is first-order already in \((M,<)\). The reviewer, \textit{A. P. Stolboushkin} and \textit{M. A. Taitslin} [Ann. Pure Appl. Logic 97, 85--125 (1999; Zbl 0956.03035)] showed that \((\omega,<,+)\) exhibits collapse to order. The main result of the paper under review is that the structure \((\omega,<,+,f)\) exhibits collapse to order, for an arbitrary unary function \(f\) compatible with addition in the sense of \textit{A. L. Semenov} [Izv. Akad. Nauk SSSR, Ser. Mat. 47, No. 3, 623--658 (1983; Zbl 0541.03005)] who proved that such a structure has a decidable theory. A motivation for the study is the still open question of whether there is an expansion of \((\omega,<,+)\) that exhibits collapse to order but has an undecidable theory.