Admissibility of rules of inference, and logical equations, in modal logics axiomatizing provability

V. V. Rybakov

Izvestiya. Mathematics , Tome 36 (1991) no. 2, pp. 369-390.

Résumé

This paper examines the modal logics of Gödel-Löb (GL) and Solovay (S) – the smallest and the largest modal representations of arithmetic theories. The problem of recognizing the admissibility of inference rules with parameters (and, in particular, without parameters) in GL and S is shown to be decidable; that is, a positive solution is obtained to analogues of a problem of Friedman. The analogue of a problem of Kuznetsov on finite bases of admissible rules for S and GL is solved in the negative sense. Algorithms are found for recognizing the solvability in GL and S of logical equations and for constructing solutions for them.

Bibliographie

[1] Artemov S. N., “Prilozheniya modalnoi logiki v teorii dokazatelstv”, Neklassicheskie logiki i ikh primenenie. Voprosy kibernetiki, Nauka, M., 1982, 3–22

[2] Artemov S. N., “O modalnykh, logikakh, aksiomatiziruyuschikh dokazuemost”, Izv. AN SSSR. Ser. matem., 49:6 (1985), 1123–1154 | MR | Zbl

[3] Artemov S. N., “Numericheski korrektnye logiki dokazuemosti”, Dokl. AN SSSR, 290:6 (1986), 1289–1292 | MR

[4] Kuznetsov A. V., Muravitskii A. Yu., “Dokazuemost kak modalnost”, Aktualnye problemy logiki i metodologii nauki, Nauk. dumka, Kiev, 1980, 193–230

[5] Rybakov V. V., “Dopustimye pravila dlya logik, vklyuchayuschikh $S4$”, Sib. matem. zhurn., 25 (1984), 141–145 | MR | Zbl

[6] Rybakov V. V., “Kriterii dopustimosti pravil v modalnoi sisteme $S4$ i intuitsionistskoi logike”, Algebra i logika, 23:5 (1984), 546–572 | MR | Zbl

[7] Rybakov V. V., “Bazisy dopustimykh pravil logiki $S4$ i $\operatorname{Int}$”, Algebra i logika, 24:1 (1985), 87–107 | MR | Zbl

[8] Rybakov V. V., “Razreshimost po dopustimosti modalnoi sistemy $\operatorname{Grz}$ i intuitsionistskoi logiki”, Izv. AN SSSR. Ser. matem., 50:3 (1986), 598–616 | MR

[9] Rybakov V. V., “Bazisy dopustimykh pravil modalnoi sistemy $\operatorname{Grz}$ i intuitsionistskoi logiki”, Matem. sb., 128:3 (1985), 321–339 | MR

[10] Rybakov V. V., “Uravneniya v svobodnoi topobulevoi algebre”, Algebra i logika, 25:2 (1986), 172–204 | MR | Zbl

[11] Rybakov V. V., “Algoritm raspoznavaniya dopustimosti pravil vyvoda v modalnoi sisteme $G$”, IV Vses. konf. “Primenenie metodov matem. logiki. Tez. dokl. Sektsiya – algoritmika trudnykh zadach”, Tallinn, 1986, 175–177

[12] Tsitkin A. I., “O dopustimosti pravil v intuitsionistskoi logike vyskazyvanii”, Matem. sb., 102:2 (1977), 314–323 | MR | Zbl

[13] Logicheskaya tetrad. Nereshennye voprosy matematicheskoi logiki, In-t matematiki SO AN SSSR, Novosibirsk, 1986

[14] Boolos G., “The logic of provability”, American Math. Montly, 91:8 (1984), 470–480 | DOI | MR | Zbl

[15] Goldblatt R., “Arithmetical necessity, provability and intuitionistic logic”, Theoria, 44:1 (1978), 38–46 | MR | Zbl

[16] Friedman H., “One hundred and two problems in mathematical logic”, J. of Symbolic Logic, 40 (1975), 113–130 | DOI | MR

[17] Segerberg K., “An escay in classical modal logic”, Filosofiska Studier, Uppsala, Sweden, 1971 | MR | Zbl

[18] Solovay R. M., “Provability interpretations of modal logic”, Israel J. Math., 25 (1976), 287–304 | DOI | MR | Zbl

[19] Visser A., Aspects of diagonalization and provability, Ph. D. Thesis, Utrecht, 1981