Definability and decidability issues in extensions of the integers with the divisibility predicate
DOI10.2307/2275673zbMATH Open0868.11061OpenAlexW2030664340WikidataQ56896689 ScholiaQ56896689MaRDI QIDQ4894724FDOQ4894724
Authors: Patrick Cégielski, Yu. Matiyasevich, D. Richard 
Publication date: 24 November 1996
Published in: Journal of Symbolic Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.2307/2275673
Recommendations
- scientific article; zbMATH DE number 221693
- scientific article; zbMATH DE number 3926911
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Decidability (number-theoretic aspects) (11U05) Model theory (number-theoretic aspects) (11U09)
Cites Work
- Recognition and parsing of context-free languages in time n3
- Definability and decision problems in arithmetic
- A uniform method for proving lower bounds on the computational complexity of logical theories
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
Cited In (15)
- Definability in terms of the successor function and the coprimeness predicate in the set of arbitrary integers
- Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
- Title not available (Why is that?)
- Title not available (Why is that?)
- First-order decidability and definability of integers in infinite algebraic extensions of the rational numbers
- Some new results in monadic second-order arithmetic
- Undecidable extensions of Skolem arithmetic
- The laws of integer divisibility, and solution sets of linear divisibility conditions
- The elementary theory of the natural lattice is finitely axiomatizable
- Universal theories of integers and the extended Bliznetsov hypothesis
- Definability, decidability, complexity
- All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
- A list of arithmetical structures complete with respect to the first-order definability
- Title not available (Why is that?)
- Arithmetic of divisibility in finite models
This page was built for publication: Definability and decidability issues in extensions of the integers with the divisibility predicate
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4894724)
