Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem
Alexis Bès · Journal of Symbolic Logic · 1997
Abstract Letkandlbe two multiplicatively independent integers, and letL⊆ ℕnbe al-recognizable set which is not definable in 〈ℕ; +〉. We prove that the elementary theory of 〈ℕ; +,Vk, L〉, whereVk(x)denotes the greatest power ofkdividingx, is undecidable. This result leads to a new proof of the Cobham-Semënov theorem.