The Theory of Integer Multiplication with Order Restricted to Primes is Decidable

Journal of Symbolic Logic 62 (1):123-130 (1997)
  Copy   BIBTEX

Abstract

We show here that the first order theory of the positive integers equipped with multiplication remains decidable when one adds to the language the usual order restricted to the prime numbers. We see moreover that the complexity of the latter theory is a tower of exponentials, of height $O$.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,829

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

The theory of integer multiplication with order restricted to primes is decidable.Françoise Maurin - 1997 - Journal of Symbolic Logic 62 (1):123-130.
On ordering and multiplication of natural numbers.Kamila Bendová - 2001 - Archive for Mathematical Logic 40 (1):19-23.
Decidability and undecidability of theories with a predicate for the primes.P. T. Bateman, C. G. Jockusch & A. R. Woods - 1993 - Journal of Symbolic Logic 58 (2):672-687.
On countable chains having decidable monadic theory.Alexis Bés & Alexander Rabinovich - 2012 - Journal of Symbolic Logic 77 (2):593-608.
Theories of arithmetics in finite models.Michał Krynicki & Konrad Zdanowski - 2005 - Journal of Symbolic Logic 70 (1):1-28.
On first-order theories with provability operator.Sergei Artëmov & Franco Montagna - 1994 - Journal of Symbolic Logic 59 (4):1139-1153.
On a decidable generalized quantifier logic corresponding to a decidable fragment of first-order logic.Natasha Alechina - 1995 - Journal of Logic, Language and Information 4 (3):177-189.
Undecidable extensions of Skolem arithmetic.Alexis Bès & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
Un Principe D'Ax-Kochen-Ershov Pour des Structures Intermediares Entre Groupes et Corps Values.Francoise Delon & Patrick Simonetta - 1999 - Journal of Symbolic Logic 64 (3):991-1027.
An Undecidable Linear Order That Is $n$-Decidable for All $n$.John Chisholm & Michael Moses - 1998 - Notre Dame Journal of Formal Logic 39 (4):519-526.
Un Principe d'ax-kochen-Ershov pour Des structures intermediares entre groupes et corps values.Françoise Delon & Patrick Simonetta - 1999 - Journal of Symbolic Logic 64 (3):991-1027.
Undecidable Extensions of Skolem Arithmetic.Alexis Bes & Denis Richard - 1998 - Journal of Symbolic Logic 63 (2):379-401.
Logical aspects of Cayley-graphs: the group case.Dietrich Kuske & Markus Lohrey - 2004 - Annals of Pure and Applied Logic 131 (1-3):263-286.
Degree Spectra of Prime Models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430 - 442.
Degree spectra of prime models.Barbara F. Csima - 2004 - Journal of Symbolic Logic 69 (2):430-442.

Analytics

Added to PP
2017-02-21

Downloads
0

6 months
0

Historical graph of downloads

Sorry, there are not enough data points to plot this chart.
How can I increase my downloads?

Citations of this work

On ordering and multiplication of natural numbers.Kamila Bendová - 2001 - Archive for Mathematical Logic 40 (1):19-23.

Add more citations

References found in this work

No references found.

Add more references