“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 15446
School of Mathematics
  Title:   On decidability and axiomatizability of some ordered structures
  Author(s):  Saeed Salehi (Joint with Z. Assadi)
  Status:   Published
  Journal: Soft Computing
  Vol.:  23
  Year:  2019
  Pages:   3615�??3626
  Supported by:  IPM
  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 N and Z are not decidable (and so not axiomatizable by any computably enumerable set of sentences). By Tarski�??s theorem, the multiplicative ordered structure of R is decidable also; here we prove this result directly and present an axiomatization. The structure of Q 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.

Download TeX format
back to top
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
Clients Logo
scroll left or right