UNDECIDABLE EXTENSIONS OF BUCHI ARITHMETIC AND COBHAM-SEMENOV THEOREM

Authors
BES A
Citation
A. Bes, UNDECIDABLE EXTENSIONS OF BUCHI ARITHMETIC AND COBHAM-SEMENOV THEOREM, The Journal of symbolic logic, 62(4), 1997, pp. 1280-1296
Citations number
15
Journal title
The Journal of symbolic logic → ACNP
ISSN journal
00224812
Volume
62
Issue
4
Year of publication
1997
Pages
1280 - 1296
Database
ISI
SICI code
0022-4812(1997)62:4<1280:UEOBAA>2.0.ZU;2-B
Abstract
Let k and l be two multiplicatively independent integers, and let L. s ubset of or equal to N-n be a l-recognizable set which is not definabl e in [N; +]. we prove that the elementary theory of [N; +, V-k, L], wh ere 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.