Undecidable Extensions of Buchi Arithmetic and Cobham-Semenov Theorem
Bes, Alexis
J. Symbolic Logic, Tome 62 (1997) no. 1, p. 1280-1296 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
Let $k$ and $l$ be two multiplicatively independent integers, and let $L \subseteq \mathbb{N}^n$ be a $l$-recognizable set which is not definable in $\langle\mathbb{N}; +\rangle$. We prove that the elementary theory of $\langle\mathbb{N}; +, V_k, L\rangle$, where $V_k(x)$ denotes the greatest power of $k$ dividing $x$, is undecidable. This result leads to a new proof of the Cobham-Semenov theorem.
Publié le : 1997-12-14
Classification:  
@article{1183745382,
     author = {Bes, Alexis},
     title = {Undecidable Extensions of Buchi Arithmetic and Cobham-Semenov Theorem},
     journal = {J. Symbolic Logic},
     volume = {62},
     number = {1},
     year = {1997},
     pages = { 1280-1296},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183745382}
}

Bes, Alexis. Undecidable Extensions of Buchi Arithmetic and Cobham-Semenov Theorem. J. Symbolic Logic, Tome 62 (1997) no. 1, pp.  1280-1296. http://gdmltest.u-ga.fr/item/1183745382/