zbMATH — the first resource for mathematics

Admissible rules and the Leibniz hierarchy. (English) Zbl 1357.03041
The admissibility of inference rules for a deductive system is a topic covering many interesting problems of logic. For example, as is well-known, the admissibility of disjunctive syllogism proved by R. K. Meyer and J. M. Dunn [J. Symb. Log. 34, 460–474 (1969; Zbl 0274.02008)] affirmatively was one of the main problems of relevance logic for a long time. The cut-elimination problem for Gentzen systems is also considered as one of such. The notion itself has been studied comprehensively for sentential deductive systems by V. V. Rybakov [Admissibility of logical inference rules. Amsterdam: Elsevier (1997; Zbl 0872.03002)] in the framework of abstract algebraic logic established by Blok, Pigozzi, Czelakowski, and others. Also for non-algebraizable deductive systems such as equational system, fuzzy logic, etc., on the other hand, several related observations have been reported by Wronski, Prucnal, Cintula, Metcalfe, and others.
This paper provides a semantic analysis of admissible rules and associated completeness conditions for arbitrary sentential deductive systems, in particular, for those non-algebraizable systems which are known to be classified by the Leibniz hierarchy. The author first establishes the characterization of admissibility of a rule for an arbitrary deductive system by means of reduced matrix models and then shows how it can be simplified according to the additional conditions depending on the level of the Leibniz hierarchy. Some completeness conditions such as structural completeness are also examined along the similar line in parallel. Thus, the main issues are developed on the global standpoint. However, the author clarifies how the known results are located there as well as the difference between respective meanings depending on the level by several concrete examples. Moreover, as a case study, an approach to the structural completeness problem of BCIW, which remains open, is discussed taking account of the results thus obtained. Some remarks are also added on extending the analysis to Gentzen systems, for which the counterparts of main observations including the basic characterization are indeed available.

03B22 Abstract deductive systems
03G27 Abstract algebraic logic
03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
08C10 Axiomatic model classes
Full Text: DOI Euclid