Undecidable extensions of Büchi arithmetic and Cobham-Semënov Theorem

Journal of Symbolic Logic 62 (4):1280-1296 (1997)
  Copy   BIBTEX

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.

Categories

Keywords

Reprint years

DOI

10.2307/2275643

Other Versions

No versions found

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 101,505

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

An extension of the Cobham-Semënov Theorem.Alexis Bès - 2000 - Journal of Symbolic Logic 65 (1):201-211.
Presburger arithmetic and recognizability of sets of natural numbers by automata: New proofs of Cobham's and Semenov's theorems.Christian Michaux & Roger Villemaire - 1996 - Annals of Pure and Applied Logic 77 (3):251-277.
On a Theorem of Cobham Concerning Undecidable Theories.Robert L. Vaught, Ernest Nagel, Patrick Suppes & Alfred Tarski - 1969 - Journal of Symbolic Logic 34 (1):126-127.
Robert L. Vaught. On a theorem of Cobham concerning undecidable theories. Logic, methodology and philosophy of science, Proceedings of the 1960 International Congress, edited by Ernest Nagel, Patrick Suppes, and Alfred Tarski, Stanford University Press, Stanford, Calif., 1962, pp. 14–25. [REVIEW]Verena H. Dyson - 1969 - Journal of Symbolic Logic 34 (1):126-127.
Undecidable extensions of Skolem arithmetic.Alexis Bes & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
On Σ1‐definable Functions Provably Total in I ∏ 1−.Teresa Bigorajska - 1995 - Mathematical Logic Quarterly 41 (1):135-137.
Decidability and undecidability of theories with a predicate for the primes.P. T. Bateman, C. G. Jockusch & A. R. Woods - 1993 - Journal of Symbolic Logic 58 (2):672-687.
On external Scott algebras in nonstandard models of peano arithmetic.Vladimir Kanovei - 1996 - Journal of Symbolic Logic 61 (2):586-607.
A Topological Approach to Undefinability in Algebraic Extensions Of.Kirsten Eisenträger, Russell Miller, Caleb Springer & Linda Westrick - 2023 - Bulletin of Symbolic Logic 29 (4):626-655.
Generic Complexity of Undecidable Problems.Alexei G. Myasnikov & Alexander N. Rybalov - 2008 - Journal of Symbolic Logic 73 (2):656 - 673.

Analytics

Added to PP
2009-01-28

Downloads
235 (#111,500)

6 months
23 (#133,093)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Add more citations

References found in this work

Weak Second‐Order Arithmetic and Finite Automata.J. Richard Büchi - 1960 - Mathematical Logic Quarterly 6 (1-6):66-92.

Add more references