Journal of Symbolic Logic 58 (2):672-687 (1993)
|Abstract||It is shown, assuming the linear case of Schinzel's Hypothesis, that the first-order theory of the structure $\langle \omega; +, P\rangle$ , where P is the set of primes, is undecidable and, in fact, that multiplication of natural numbers is first-order definable in this structure. In the other direction, it is shown, from the same hypothesis, that the monadic second-order theory of $\langle\omega; S, P\rangle$ is decidable, where S is the successor function. The latter result is proved using a general result of A. L. Semenov on decidability of monadic theories, and a proof of Semenov's result is presented|
|Keywords||No keywords specified (fix it)|
|Through your library||Configure|
Similar books and articles
James H. Schmerl (1980). Decidability and ℵ0-Categoricity of Theories of Partially Ordered Sets. Journal of Symbolic Logic 45 (3):585 - 611.
James F. Lynch (1982). On Sets of Relations Definable by Addition. Journal of Symbolic Logic 47 (3):659-668.
Paolo Casalegno (1985). On the T-Degrees of Partial Functions. Journal of Symbolic Logic 50 (3):580-588.
Patrick Simonetta (1998). Equivalence Elementaire Et Decidabilite Pour Des Structures du Type Groupe Agissant Sur Un Groupe Abelien. Journal of Symbolic Logic 63 (4):1255-1285.
Charles Rackoff (1976). On the Complexity of the Theories of Weak Direct Powers. Journal of Symbolic Logic 41 (3):561-573.
Françoise Point (2000). On Decidable Extensions of Presburger Arithmetic: From A. Bertrand Numeration Systems to Pisot Numbers. Journal of Symbolic Logic 65 (3):1347-1374.
Alexandra Shlapentokh (2002). On Diophantine Definability and Decidability in Some Rings of Algebraic Functions of Characteristic. Journal of Symbolic Logic 67 (2):759-786.
Patrick Cegielski, Yuri Matiyasevich & Denis Richard (1996). Definability and Decidability Issues in Extensions of the Integers with the Divisibility Predicate. Journal of Symbolic Logic 61 (2):515-540.
Alexis Bès (1997). Undecidable Extensions of Büchi Arithmetic and Cobham-Semënov Theorem. Journal of Symbolic Logic 62 (4):1280-1296.
Alexis Bés & Denis Richard (1998). Undecidable Extensions of Skolem Arithmetic. Journal of Symbolic Logic 63 (2):379-401.
Added to index2009-01-28
Total downloads2 ( #234,650 of 556,803 )
Recent downloads (6 months)1 ( #64,847 of 556,803 )
How can I increase my downloads?