zbMATH — the first resource for mathematics

Semantic universality of theories over a superlist. (English. Russian original) Zbl 0780.03013
Algebra Logic 31, No. 1, 30-48 (1992); translation from Algebra Logika 31, No. 1, 47-73 (1992).
Summary: We study the expressive power of formulas of the first-order predicate logic over a list PL of model-theoretic properties, which is more extensive than MTL figuring in two earlier papers [the author, Dokl. Akad. Nauk SSSR 308, No. 4, 788-791 (1989; Zbl 0703.03014); “Immersing recursively enumerable theories in finitely axiomatizable ones” (Russian), Tr. Inst. Mat. (1991)]. Characterization of generalized Lindenbaum L-algebras is obtained for semantically universal finitely axiomatizable model classes under inclusion \(\text{L}\subseteq\text{PL}\). As an immediate consequence, the existence of a recursive isomorphism (preserving properties from the list PL) between Lindenbaum algebras of the predicate calculus with two diverse finite signatures is proved. This gives a positive answer to question 1 posed by the author in Algebra Logika 30, No. 4, 414-431 (1991; Zbl 0777.03010).
03C57 Computable structure theory, computable model theory
Full Text: DOI
[1] M. G. Peretyat’kin, ”Similarity of properties of recursively enumerable and finitely axiomatizable theories,” Dokl. Akad. Nauk SSSR,308, No. 4, 788–791.
[2] M. G. Peretyat’kin, ”Immersing recursively enumerable theories in finitely axiomatizable ones,” Tr. Inst. Mat. Akad. Nauk SSSR (1991).
[3] M. G. Peretyat’kin, ”Semantically universal classes of models,” Algebra Logika,30, No. 4, 414–431 (1991).
[4] C. C. Chang and H. J. Keisler, Model Theory, 2nd edn., North Holland (1977). · Zbl 0423.03041
[5] H. Rogers, Theory of Recursive Functions and Effective Computability, MIT Press (1987). · Zbl 0183.01401
[6] R. I. Soare, Recursively Enumerable Sets and Degrees, Springer-Verlag (1987). · Zbl 0667.03030
[7] Yu. L. Ershov, Problems of Decidability and Constructive Models [in Russian], Nauka, Moscow, (1980).
[8] J. Shoenfield, Mathematical Logic [Russian translation], Nauka, Moscow (1975).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.