Collapse results for expansions of Presburger's arithmetics

The full text of the section was published in [7].

We are considering the natural number as the domain, the addition and a unary function as the domain functions, and the usual ordering as the domain relation. So we are considering the universes
< N, <, +, f⁽¹⁾>

5.    A.L. Semenov.
       Logical theories of one-place functions on the natural number series.
       Izv. Akad. Nauk SSSR Ser. Mat.,
       47(3):623−658, 1983.
       Russian.

6.    S.M. Dudakov.
       Collapse results for expansions of Presburger's arithmetics
       by one concordant with addition unary function.
       Russian, 2001.

7.    M.A. Taitslin.
       Translation results in database theory.
       In Complex systems: data processing, simulation, and
       optimization, pages 5−23.
       Tver State University, Tver, 2002.
       Russian.

The key conditions for decidability of the first-order theories of these domains was pointed out by A.L.Semenov in [5].

It was proved by S.M.Dudakov in [6] that in the Semenov's case, locally generic extended queries express as well as pure order ones. So the collapse result is true for any f which is interpretable in a Semenov's domain.

Previous page
Next page