Decidability and undecidability of theories with a predicate for the primes
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) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,865 |
| External links |
 |
| Through your library | Configure |
Similar books and articlesJames 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.
Analytics
Monthly downloads |
Added to index2009-01-28Total downloads2 ( #234,650 of 556,803 )Recent downloads (6 months)1 ( #64,847 of 556,803 )How can I increase my downloads? |
My notes
Discussion
