Abstract
We continue to develop a new first-order combinatorial approach presenting a conceptual framework for investigations concerning expressive power of first-order logic. In this work, we consider the case of infinitary first-order combinatorics. Based on the universal construction of finitely axiomatizable theories, we introduce some common scheme yielding finitely axiomatizable theories with pre-assigned sets of model-theoretic properties. At an initial stage, a maximum common Turing’s computation is performed (one can say, computable Brute Force). Starting from an input block of parameters, the computation yields a computably axiomatizable theory T. Finally, by applying an available version of the universal construction, the theory T is transformed into a finitely axiomatizable theory F that inherits model-theoretic properties of T within the infinitary semantic layer. We also give three demonstrations showing possibilities of this method.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Yu. L. Ershov and S. S. Goncharov, Constructive Models (Consultants Bureau, New York, 2000).
W. Hodges, A Shorter Model Theory (Cambridge University Press, Cambridge, 1997).
E. Mendelson, Introduction to Mathematical Logic (Princeton, 2nd ed., 1979).
S. P. Odintsov and V. L. Selivanov, Sib. Math. J. 30 (6), 140–149 (1989).
M. G. Peretyat’kin, Finitely Axiomatizable Theories (Plenum, New York, 1997).
M. G. Peretyat’kin, CiE 2013, LNCS 7921 (Springer, 2013), pp. 342–352.
M. G. Peretyat’kin, in: Computation Tools 2013 (IARIA, 2013), pp. 31–36.
H. J. Rogers, Theory of Recursive Functions and Effective Computability (McGraw-Hill Book Co., New York, 1967).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Peretyat’kin, M.G. A transformation scheme for infinitary first-order combinatorics presenting computational level of expressiveness in predicate logic. Lobachevskii J Math 36, 407–418 (2015). https://doi.org/10.1134/S1995080215040137
Received:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S1995080215040137