Axiomatizability of non-normal and quasi-normal modal predicate logics of first-order definable classes of Kripke frames

M. N. Rybakov

Vestnik Tverskogo gosudarstvennogo universiteta. Seriâ Prikladnaâ matematika, no. 3 (2018), pp. 81-94

Résumé

The possibility of effective description of non-normal and quasi-normal predicate modal logics defined semantically by means of classes of Kripke frames with distinguished worlds is considered. It is proved that any non-normal or quasi-normal (in particular, normal) modal predicate logic, complete with respect to a certain first-order definable class of Kripke frames with distinguished worlds, can be embedded into the classical first-order logic. It is shown how to construct such an embedding based on the so called standard translation of modal predicate formulas into formulas of the first-order classical language. At the end of the work, we present some corollaries of this result and demonstrate the possibility of generalization for the described construction to classes of other systems, in particular, to classes of polymodal logics-temporal logic with a pair of modalities ‘always in past’ and ‘always in future’ and logics of knowledge with the operator of distributed knowledge. Some limitations for applicability of the described method are shown, relevant examples are given. Counterexamples are indicated when the conditions of the method applicability for the Kripke complete modal predicate logic are not met but the construction of an effective description of this logic is nevertheless possible.

Détail

Keywords: first-order logic, modal logic, non-normal logic, recursive enumerability, Kripke semantics.
Mots-clés : quasi-normal logic

Bibliographie

[1] Boolos G. S., Jeffrey R. C., Computability and Logic, Third Edition, Cambridge University Press, Cambridge, 1989 | MR | Zbl

[2] Rybakov M. N., “Decidability of intuitionistic first-order logic relative to classical first-order logic”, Proc. of VI International Conference “Modern logic: problems of theory, history, and application in science”, Saint-Petersburg State University Publ., SPb, 2000, 247–250 (in Russian)

[3] Rybakov M. N., “Decidability of logics of knowledge relative to classical first-order logic”, Proc. of the III International Conference “Smirnov Readings”, Izdatelstvo Instituta filosofii RAN, Moscow, 2001, 62–64 (in Russian)

[4] Rybakov M. N., “Enumerability of modal predicate logics and the condition of non-existence of infinite ascending chains”, Logical Investigations, 2001, no. 8, 155–167 (in Russian) | Zbl

[5] Rybakov M. N., “Decidability of some modal predicate logics relative to classical first-order logic”, Proceedings of Tver State University, 6 (2000), 8–12 (in Russian)

[6] Rybakov M. N., Chagrov A. V., “Standard Translations of Non-Classical Formulas and Relative Decidability of Logics”, Proceedings of the Research Seminar of the Logical Center of the Institute of Philosophy, RAS, v. XIV, Izdatel'stvo Instituta Filosofii RAN, Moscow, 2000, 81–98 (in Russian)

[7] Trakhtenbrot B. A., “The impossibility of an algorithm for the decidability problem on finite classes”, Proceedings of the USSR Academy of Sciences, 70:4 (1950), 569–572 (in Russian) | MR | Zbl

[8] Feys R., Modal Logic, Nauka Publ., Moscow, 1974 (in Russian) | MR

[9] Church A., “A note on the Entscheidungsproblem”, Journal of Symbolic Logic, 1 (1936), 40–41 | DOI

[10] Behmann H., “Beiträige zür algebra der logik, inbesondere zum entscheidungsproblem”, Mathematische Annalen, 86 (1922), 163–229 | DOI | MR | Zbl

[11] Börger E., Grädel E., Gurevich Yu., The Classical Decision Problem, Springer, 1997 | MR | Zbl

[12] Gabbay D. M., Skvortsov D. P., Shehtman V. B., Quantification in Nonclassical Logic, v. 153, Studies in Logic and the Foundations of Mathematics, Elsevier Science, 2009, 640 pp. | MR | Zbl

[13] Grädel E., Kolaitis P. G., Vardi M. Y., “On the decision problem for two-variable first-order logic”, Bulletin of Symbolic Logic, 3:1 (1997), 53–69 | DOI | MR | Zbl

[14] Gödel K., “Zum Entsheidungsproblem des logischen Funktionenkalküls”, Monatschefte für Mathematische Physika, 40 (1933), 433–443 | MR

[15] Kremer P., “On the complexity of propositional quantification in intuitionistic logic”, The Journal of Symbolic Logic, 62:2 (1997), 529–544 | DOI | MR | Zbl

[16] Kotikova E. A., Rybakov M. N., “First-Order Logics of Branching Time: On Expressive Power of Temporal Operators”, Logical Investigations, 2013, no. 19, 68–99 | MR | Zbl

[17] Montagna F., “The Predicate Modal Logic of Provability”, Notre Dame Journal of Formal Logic, 25:2 (1984), 179–189 | DOI | MR | Zbl

[18] Mortimer M., “On languages with two variables”, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1975, 135–140 | DOI | MR | Zbl

[19] Nerode A., Shore R. A., “Second order logic and first order theories of reducibility ordering”, The Kleene Symposium, eds. J. Barwise, H.J. Keisler, K. Kunen, North-Nolland, 1980, 181–200 | DOI | MR

[20] Rybakov M., Shkatov D., “A recursively enumerable Kripke complete first-order logic not complete with respect to a first-order definable class of frame”, Advances in Modal Logic, v. 12, eds. G. Bezhanishvili, G. D’Agostino, G. Metcalfe, T. Studer, College Publications, 2018, 531–540

[21] Segerberg K., An Essey in Classical Modal Logic, Uppsala, 1971 | MR

[22] Skvortsov D. P., “On The Predicate Logics of Finite Kripke Frames”, Studia Logica, 54:1 (1995), 79–88 | DOI | MR | Zbl

[23] Surányi J., “Zur Reduktion des Entscheidungsproblems des logischen Funktioskalküls”, Mathematikai és Fizikai Lapok, 50 (1943), 51–74 | MR | Zbl

[24] Wolter F., Zakharyaschev M. V., “Decidable fragments of First-order modal logics”, The Journal of Symbolic Logic, 66 (2001), 1415–1438 | DOI | MR | Zbl