Definability and decidability issues in extensions of the integers with the divisibility predicate

DOI10.2307/2275673MaRDI QIDQ4894724zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

definabilitydivisibility relationpositive integersdivisibility predicate

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Interpolation, preservation, definability (03C40) Decidability (number-theoretic aspects) (11U05) Model theory (number-theoretic aspects) (11U09)

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

Cites work

• A uniform method for proving lower bounds on the computational complexity of logical theories
• All arithmetical sets of powers of primes are first-order definable in terms of the successor function and the coprimeness predicate
• Answer to a problem raised by J. Robinson: The arithmetic of positive or negative integers is definable from successor and divisibility
• Definability and decision problems in arithmetic
• Recognition and parsing of context-free languages in time n3

Cited in

(15)

• Arithmetic of divisibility in finite models
• 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
• scientific article; zbMATH DE number 221693 (Why is no real title available?)
• scientific article; zbMATH DE number 4110684 (Why is no real title available?)
• 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
• scientific article; zbMATH DE number 3926911 (Why is no real title available?)

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)