On decidability and axiomatizability of some ordered structures

DOI10.1007/S00500-018-3247-1MaRDI QIDQ2318170zbMATH OpenOpenAlexWikidataFDO

Authors Ziba Assadi, Saeed Salehi

Publication date 14 August 2019

Published in Soft Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1709.05157

zbMATH Keywords

completenessdecidabilityfirst-order theoryincompletenessordered structuresquantifier eliminationundecidability

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Undecidability and degrees of sets of sentences (03D35) First-order arithmetic and fragments (03F30)

Abstract: The ordered structures of natural, integer, rational and real numbers are studied here. It is known that the theories of these numbers in the language of order are decidable and finitely axiomatizable. Also, their theories in the language of order and addition are decidable and infinitely axiomatizable. For the language of order and multiplication, it is known that the theories of $mathbbN$ and $mathbbZ$ are not decidable (and so not axiomatizable by any computably enumerable set of sentences). By Tarski's theorem, the multiplicative ordered structure of $mathbbR$ is decidable also; here we prove this result directly and present an axiomatization. The structure of $mathbbQ$ in the language of order and multiplication seems to be missing in the literature; here we show the decidability of its theory by the technique of quantifier elimination and after presenting an infinite axiomatization for this structure we prove that it is not finitely axiomatizable.

Recommendations

• On Axiomatizability of the Multiplicative Theory of Numbers
• When is scalar multiplication decidable?
• On ordering and multiplication of natural numbers
• Expansions of the ordered additive group of real numbers by two discrete subgroups
• Decidability in the Constructive Theory of Reals as an Ordered ℚ‐vectorspace

Cites work

• A mathematical introduction to logic.
• Computability and Logic
• Definability and decision problems in arithmetic
• Elementary properties of Abelian groups
• Elementary Properties of Ordered Abelian Groups
• scientific article; zbMATH DE number 3550662 (Why is no real title available?)
• scientific article; zbMATH DE number 3997750 (Why is no real title available?)
• scientific article; zbMATH DE number 3348095 (Why is no real title available?)
• scientific article; zbMATH DE number 2232435 (Why is no real title available?)
• scientific article; zbMATH DE number 3052795 (Why is no real title available?)
• Logical number theory I. An introduction
• Mathematical logic and model theory. A brief introduction
• Model Theory
• New Proof of the Generalized Chinese Remainder Theorem
• On \(\mathsf{Q}\)
• On Axiomatizability of the Multiplicative Theory of Numbers
• On direct products of theories
• The General Chinese Remainder Theorem

Cited in

(12)

• The common order-theoretic structure of version spaces and ATMSs
• Axiomatic (and non-axiomatic) mathematics
• On the well-foundedness of adequate orders used for construction of complete unfolding prefixes
• Generalized ordinal sums and the decidability of BL-chains
• Expansions of the ordered additive group of real numbers by two discrete subgroups
• scientific article; zbMATH DE number 5015958 (Why is no real title available?)
• A decidable two-sorted quantified fragment of set theory with ordered pairs and some undecidable extensions
• scientific article; zbMATH DE number 935103 (Why is no real title available?)
• scientific article; zbMATH DE number 7340151 (Why is no real title available?)
• A generalization of the Keisler‐Morley theorem to recursively saturated ordered structures
• On ordering and multiplication of natural numbers
• \(\langle\mathbb{R},+,<,1\rangle\) is decidable in \(\langle \mathbb{R},+,<,\mathbb{Z}\rangle\)

This page was built for publication: On decidability and axiomatizability of some ordered structures

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2318170)