Decidable modal logic with undecidable admissibility problem

DOI10.1007/BF02259858MaRDI QIDQ2366361zbMATH OpenOpenAlexFDO

Authors Alexander Vasil'evich Chagrov

Publication date 29 June 1993

Published in Algebra and Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02259858

zbMATH Keywords

admissible ruledecidabilityinference rulenormal modal logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Modal logic (including the logic of norms) (03B45)

Review text

The admissibility problem for a given logic \(L\) is to determine whether an arbitrary given inference rule \(A_ 1(p_ 1,\dots,p_ n),\dots,A_ m(p_ 1,\dots,p_ n)/B(p_ 1,\dots,p_ n)\) is admissible in \(L\), i.e., for all formulas \(C_ 1,\dots,C_ n\), \(B(C_ 1,\dots,C_ n)\in L\) whenever \(A_ 1(C_ 1,\dots,C_ n)\in L,\dots,A_ m(C_ 1,\dots,C_ n)\in L\). As is known, V. Rybakov proved the decidability of the admissibility problem for a number of intermediate and modal logics. In this paper, the author constructs a decidable normal modal logic for which the admissibility problem is undecidable. The logic is an extension of K4 of width 3 and has infinitely many axioms.

Recommendations

• Complexity of admissible rules
• Criteria for admissibility of inference rules. Modal and intermediate logics with the branching property
• The decidability of admissibility problems for modal logics S4.2 and S4.2Grz and superintuitionistic logic KC
• Proof theory for admissible rules

Cites work

• scientific article; zbMATH DE number 4130350 (Why is no real title available?)
• Logics containing K4. Part I

Cited in

(14)

• Proof theory for admissible rules
• The decidability of admissibility problems for modal logics S4.2 and S4.2Grz and superintuitionistic logic KC
• Criteria for admissibility of inference rules. Modal and intermediate logics with the branching property
• On rules
• Tutorial on admissible rules in Gudauri
• Canonical rules
• scientific article; zbMATH DE number 2024620 (Why is no real title available?)
• DECIDABILITY OF ADMISSIBILITY: ON A PROBLEM BY FRIEDMAN AND ITS SOLUTION BY RYBAKOV
• The context of inference
• Multiple conclusion rules in logics with the disjunction property
• The Deduction Theorem (Before and After Herbrand)
• Decidable and Undecidable Problems for First-Order Definability and Modal Definability
• Undecidability of admissibility in the product of two \textbf{Alt} logics
• Complexity of admissible rules

This page was built for publication: Decidable modal logic with undecidable admissibility problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2366361)