Given any infinite structure \( \mathfrak{M} \) with a decidable first-order theory, we give a sufficient condition in terms of the Gaifman graph of \( \mathfrak{M} \) that ensures that \( \mathfrak{M} \) can be expanded with some nondefinable predicate in such a way that the first-order theory of the expansion is still decidable. Bibliography: 10 titles.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
A. Bès and P. Cégielski, “Weakly maximal decidable structures,” RAIRO — Theor. Inf. Appl., 42, No. 1, 137–145 (2008).
A. Blumensath, “Locality and modular Ehrenfeucht–Fraisse games,” preprint (2006).
C. C. Elgot and M. O. Rabin, “Decidability and undecidability of extensions of second (first) order theory of (generalized) successor,” J. Symbolic Logic, 31, No. 2, 169–181 (1966).
H. Gaifman, “On local and nonlocal properties,” in: Proceedings of the Herbrand Symposium (Marseille, 1981), Stud. Logic Found. Math., 107 (1982), pp. 105–135.
C. H. Langford, “Theorems on deducibility,” Ann. of Math. (2), 28, 459–471 (1927).
L. Libkin, Elements of Finite Model Theory, Springer-Verlag, Berlin (2004).
M. Presburger, “Über de vollständigkeit eines gewissen Systems der Arithmetic ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt,” in: Comptes Rendus du Premier Congrès des Mathématiciens des Pays Slaves, Warsaw (1927), pp. 92–101, 395. English translation: “On the completeness of a certain system of arithmetic of whole numbers in which addition occurs as the only operation,” Hist. Philos. Logic, 12, No. 2, 225–233 (1991).
A. L. Semenov, “Decidability of monadic theories,” Lecture Notes Comput. Sci., 176, 162–175 (1984).
V. S. Harizanov, “Computability-theoretic complexity of countable structures,” Bull. Symbolic Logic, 8, 457–477 (2002).
S. Soprunov, “Decidable expansions of structures,” Voprosy Kibernet., 134, 175–179 (1988).
Author information
Authors and Affiliations
Corresponding author
Additional information
Published in Zapiski Nauchnykh Seminarov POMI, Vol. 358, 2008, pp. 23–37.
Rights and permissions
About this article
Cite this article
Bès, A., Cégielski, P. Nonmaximal decidable structures. J Math Sci 158, 615–622 (2009). https://doi.org/10.1007/s10958-009-9399-x
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10958-009-9399-x