Logical equations and admissible rules of inference with parameters in modal provability logics.

*(English)*Zbl 0729.03012The aim of this paper is to study admissible inference rules for the modal provability logics GL and S. It is proved that none of these logics has a basis for admissible rules in a finite number of variables, in particular, they do not have finite bases. It is proved that GL and S are decidable by admissibility, some algorithms are found which recognize admissibility of usual inference rules and inference rules in generalized form - inference rules with parameters (or metavariables). By using recognizability of admissibility of inference rules with parameters, we can recognize solvability of logical equations in GL and S and construct some of their solutions. Thus, the analogues of H. Friedman’s problem for GL and S are affirmatively solved, the analogues of A. Kuznetsov’s problem of finiteness of a basis for admissible rules for GL and S have negative solutions, and the problems of solvability of logical equations in GL and S have positive solutions.

Reviewer: V.V.Rybakov

##### MSC:

03B45 | Modal logic (including the logic of norms) |

03F40 | Gödel numberings and issues of incompleteness |

03B25 | Decidability of theories and sets of sentences |

##### Keywords:

Gödel-Löb logic; admissible inference rules; modal provability logics; algorithms; solvability of logical equations
Full Text:
DOI

##### References:

[1] | S. N. Artemov,Modal logics axiomatizing provability,Izvestia AN SSSR, ser. matem. 49, no 6 (1985), pp. 1123-1154 (in Russian). · Zbl 0598.03012 |

[2] | G. Boolos,The logic of provability,Amer. Math. Monthly 91, no 8 (1984), pp. 470-480. · Zbl 0562.03007 · doi:10.2307/2322568 |

[3] | R. Goldblatt,Arithmetical necessity, provability and intuitionistic logic,Theoria 44, no 1 (1978), pp. 38-46. · Zbl 0409.03011 · doi:10.1111/j.1755-2567.1978.tb00831.x |

[4] | H. Friedman,One hundred and two problems of mathematical logic,Journal of Symbolic Logic 40 (1975), pp. 113-130. · Zbl 0318.02002 · doi:10.2307/2271891 |

[5] | A. V. Kuznetsov andA. U. Muravitsky,Provability as modality, In book:Actual Problems of Logic and Methodology of Science, Naukova dumka, Kiev, USSR, 1980, pp. 193-230. |

[6] | J. ?o? andR. Suszko,Remarks on sentential logic,Indagationes Mathematicae 20 (1985), pp. 117-183. |

[7] | V. V. Rybakov,Admissible rules in pretabular modal logics,Algebra i logika 20 (1981), pp. 440-464 (in Russian). · Zbl 0489.03005 |

[8] | V. V. Rybakov,Admissible rules for logics containing S4.3,Sibirsky Math. Jour. 25, no 5 (1984), pp. 141-145 (in Russian). · Zbl 0582.03009 |

[9] | V. V. Rybakov,Criterion of admissibility for modal system S4 and intuitionistic logic,Algebra i logika 23 (1984), pp. 546-572 (in Russian). |

[10] | V. V. Rybakov,The bases for admissible rules of logics S4 and Int,Algebra i logika 24 (1985), pp. 87-107 (in Russian). |

[11] | V. V. Rybakov,Decidability of admissibility in the modal system Grz and intuitionistic logic,Math. USSR Izvestia 28, no 3 (1987), pp. 589-608. · Zbl 0624.03009 · doi:10.1070/IM1987v028n03ABEH000902 |

[12] | V. V. Rybakov,Bases of admissible rules of the modal system Grz and intuitionistic logic,Math. USSR Sbornik 56, no 2 (1987), pp. 311-331. · Zbl 0617.03007 · doi:10.1070/SM1987v056n02ABEH003038 |

[13] | V. V. Rybakov,The equations in the free topoboolean algebras,Algebra i logika 25 no 2 (1986), pp. 172-204 (in Russian). |

[14] | V. V. Rybakov,An algorithm for recognition of admissibility the rules of inference in modal system G, In book:Applications of Method Mathematical Logic, Section algorithms for difficult problems, Institute of Cybernetics Acad. Sc. Est. SSR, Tallin, 1986, pp. 175-177 (in Russian). |

[15] | K. Segerberg,An Essay in Classical Modal Logic, V. 1-3, Filosofiska studier, Uppsala 1971. · Zbl 0311.02028 |

[16] | R. M. Solovay,Provability interpretations of modal logic,Israel J. Math. 25 (1976), pp. 287-304. · Zbl 0352.02019 · doi:10.1007/BF02757006 |

[17] | A. I. Tsitkin,An admissible rule for intuitionistic propositional calculus,Mathemat. Sbornik 102, no 2 (1977), pp. 314-323 (in Russian, there exists an English translation). · Zbl 0386.03011 |

[18] | A. Visser,Aspects of diagnolization and provability, Ph. D. Thesis, Utrecht, 1981. |

[19] | R. W?jcicki,Investigations into methodology of sentential calculi (1), Inst. of Phil, and Soc. PAS, Warsaw 1971. |

[20] | Logical Note-Book. Unsolved Questions of Mathematical Logic, Mathematical Inst. SO AN SSSR, Novosibirsk, 1986 (in Russian). |

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.