A concise guide to finitary and infinitary levels of expressive power of first-order logic

AUTHOR(S):

TITLE

A concise guide to finitary and infinitary levels of expressive power of first-order logic

ABSTRACT

In this work, we give a short review of recent results concerning expressive power of first-order logic. We characterize the isomorphism type of the Tarski-Lindenbaum algebra of predicate calculus of a finite rich signature under finitary and infinitary semantic layers of model-theoretic properties. Results presented in this work characterize two levels of expressive power of first-order predicate logic. Author’s statement (just for the reviewer): Currently, a number of absolutely new results is obtained by the author. They characterize expressive power of first-order logic. A few preliminary works have been already published; a few must appear soon; a series of works is prepared for publication. Purpose of this work is to give a short review of used technical methods and basic results in this direction obtained recently by the author.

KEYWORDS

First-order logic, incomplete theory, Tarski-Lindenbaum algebra, model-theoretic property, semantic type of a theory.

REFERENCES

[1] W. HODGES, A shorter model theory, Cambridge University Press, Cambridge, 1997.

[2] H.J. ROGERS, Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York, 1967.

[3] YU.L. ERSHOV and S.S. GONCHAROV, Constructive models, Transl. from the Russian. (English) Siberian School of Algebra and Logic. New York, NY: Consultants Bureau. XII, 293 pp.

[4] M.G. PERETYAT’KIN. First-order combinatorics and model-theoretical properties that can be distinct for mutually interpretable theories. Siberian Advances in Mathematics, 2016, Vol. 26, No 3, pp. 196-214.

[5] J.R. SHOENFIELD, Mathematical logic, Addison-Wesley, Massachusetts, 1967.

[6] M.G. PERETYAT’KIN, Invertible multidimensional interpretations versus virtual isomorphisms of first-order theories, Mathematical Journal, No. 4, 2016, 36 pp.

[7] M.G. PERETYAT’KIN, Finitely axiomatizable theories, Plenum, New York, 1997, 297 pp.

[8] L. KALMAR, Die Z¨uruckf¨uhrung des Entscheidungsproblems auf den Fall von Formeln mit einer einzigen, bin¨aren Funktionsvariablen, Composito Mathematica, v. 4, 1936, p. 137–144 (cf. Ref. 445 in Sect. 47 at: A. Church, Introduction in Mathematical Logic, Vol. 1, Princenton, 1956).

[9] R.L. VAUGHT, Sentences true in all constructive models, J. Symbolic Logic, v. 25, No. 1, 1961, p. 39–59.

[10] W. HANF, Isomorphism in elementary logic, Notices of American Mathematical Society, 9 (1962), p.146–147.

[11] M.G. PERETYAT’KIN, Introduction in firstorder combinatorics providing a conceptual framework for computation in predicate logic, In: Computation tools 2013, IARIA, 2013, pp. 31- 36.

[12] M.G. PERETYAT’KIN, Canonical mini construction of finitely axiomatizable theories as a weak release of the universal construction, Mathematical Journal, No. 3, 2014, p. 48–89.

[13] M.G. PERETYAT’KIN,There is a virtual isomorphism between any two undecidable predicate calculi of finite signatures, International conference ”Maltsev’s readings”, Russia, Novosibirsk, 21-25 November 2016, Abstracts, p. 208.

[14] D.MYERS, An interpretive isomorphism between binary and ternary relations, Structures in Logic and Computer Science: A Selection of Essays in Honor of Andrzej Ehrenfeucht, 1997, p. 84–105

[15] W. HANF, Primitive Boolean algebras, Proceedings of Symposium in Honor of Alfred Tarski (Berkeley, 1971), Proc. Symp. Pure Math., vol 25, Amer. Math. Soc. Providence, R.I., 1974, p. 75–90.

[16] W. HANF, The Boolean algebra of Logic, Bull. American Math. Soc., v. 31, 1975, p. 587–589.

[17] W. HANF, Model-theoretic methods in the study of elementary logic, Symposium on Theory of Models, North-Holland, Amsterdam, 1965, p. 33–46.

[18] W. HANF, D.MYERS, Boolean sentence algebras: Isomorphism constructions, J. Symbolic Logic, v. 48, No. 2, 1983, p. 329–339.

[19] D.MYERS, Lindenbaum–Tarski algebras, Handbook of Boolean algebras, Ed: J.D. Monk, R.Bonnet, Elsevier Science Publishers, 1989, p. 1167–1199.

[20] M.G. PERETYAT’KIN, Finitely axiomatizable theories, in: Proceedings of International Congress of Mathematicians, Berkeley, California, USA (1986) vol. 1, p. 322–330 (Russian). English translation in: Amer. Math. Soc. Transl. 2, v. 147, 1990, p. 11–19.

[21] M.G. PERETYAT’KIN, Semantic universal classes of models, Algebra and Logic, 1991, v.30, No 4, p. 414–434.

[22] M.G. PERETYAT’KIN, Semantic universality of theories over superlist, Algebra and Logic, 1992, v.30, No 5, p. 517–539.

Cite this paper

Mikhail G. Peretyat’kin. (2017) A concise guide to finitary and infinitary levels of expressive power of first-order logic. International Journal of Mathematical and Computational Methods, 2, 107-119