In logic, a rule of inference is admissible in a formal system if the set of theorems of the system does not change when that rule is added to the existing rules of the system. In other words, every formula that can be derived using that rule is already derivable without that rule, so, in a sense, it is redundant. The concept of an admissible rule was introduced by Paul Lorenzen (1955).
Definitions
Admissibility has been systematically studied only in the case of structural (i.e. substitution-closed) rules in propositional non-classical logics, which we will describe next.
Let a set of basic propositional connectives be fixed (for instance, in the case of superintuitionistic logics, or in the case of monomodal logics). Well-formed formulas are built freely using these connectives from a countably infinite set of propositional variables p0, p1, .... A substitution σ is a function from formulas to formulas that commutes with applications of the connectives, i.e.,
for every connective f, and formulas A1, ... , An. (We may also apply substitutions to sets Γ of formulas, making ) A Tarski-style consequence relationBlok & Pigozzi (1989), Kracht (2007) is a relation between sets of formulas, and formulas, such that
for all formulas A, B, and sets of formulas Γ, Δ. A consequence relation such that
for all substitutions σ is called structural. (Note that the term "structural" as used here and below is unrelated to the notion of structural rules in sequent calculi.) A structural consequence relation is called a propositional logic. A formula A is a theorem of a logic if .
For example, we identify a superintuitionistic logic L with its standard consequence relation generated by modus ponens and axioms, and we identify a normal modal logic with its global consequence relation generated by modus ponens, necessitation, and (as axioms) the theorems of the logic.
A structural inference ruleRybakov (1997), Def. 1.1.3 (or just rule for short) is given by a pair (Γ, B), usually written as
where Γ = {A1, ... , An} is a finite set of formulas, and B is a formula. An instance of the rule is
for a substitution σ. The rule Γ/B is derivable in , if . It is admissible if for every instance of the rule, σB is a theorem whenever all formulas from σΓ are theorems.Rybakov (1997), Def. 1.7.2 In other words, a rule is admissible if it, when added to the logic, does not lead to new theorems.From de Jongh’s theorem to intuitionistic logic of proofs We also write if Γ/B is admissible. (Note that is a structural consequence relation on its own.)
Every derivable rule is admissible, but not vice versa in general. A logic is structurally complete if every admissible rule is derivable, i.e., .Rybakov (1997), Def. 1.7.7
In logics with a well-behaved conjunction connective (such as superintuitionistic or modal logics), a rule is equivalent to with respect to admissibility and derivability. It is therefore customary to only deal with unary rules A/B.
Examples
Classical propositional calculus (CPC) is structurally complete.Chagrov & Zakharyaschev (1997), Thm. 1.25 Indeed, assume that A/B is a non-derivable rule, and fix an assignment v such that v(A) = 1, and v(B) = 0. Define a substitution σ such that for every variable p, σp = if v(p) = 1, and σp = if v(p) = 0. Then σA is a theorem, but σB is not (in fact, ¬σB is a theorem). Thus the rule A/B is not admissible either. (The same argument applies to any multi-valued logic L complete with respect to a logical matrix all of whose elements have a name in the language of L.) The Kreisel–Putnam rule (also known as Harrop's rule, or independence of premise rule) is admissible in the intuitionistic propositional calculus (IPC). In fact, it is admissible in every superintuitionistic logic.Prucnal (1979), cf. Iemhoff (2006) On the other hand, the formula is not an intuitionistic theorem; hence KPR is not derivable in IPC. In particular, IPC is not structurally complete. The rule is admissible in many modal logics, such as K, D, K4, S4, GL (see this table for names of modal logics). It is derivable in S4, but it is not derivable in K, D, K4, or GL. The rule is admissible in normal logic .Rybakov (1997), p. 439 It is derivable in GL and S4.1, but it is not derivable in K, D, K4, S4, or S5. Löb's rule is admissible (but not derivable) in the basic modal logic K, and it is derivable in GL. However, LR is not admissible in K4. In particular, it is not true in general that a rule admissible in a logic L must be admissible in its extensions. The Gödel–Dummett logic (LC), and the modal logic Grz.3 are structurally complete.Rybakov (1997), Thms. 5.4.4, 5.4.8 The product fuzzy logic is also structurally complete.Cintula & Metcalfe (2009)
Decidability and reduced rules
The basic question about admissible rules of a given logic is whether the set of all admissible rules is decidable. Note that the problem is nontrivial even if the logic itself (i.e., its set of theorems) is decidable: the definition of admissibility of a rule A/B involves an unbounded universal quantifier over all propositional substitutions. Hence a priori we only know that admissibility of rule in a decidable logic is (i.e., its complement is recursively enumerable). For instance, it is known that admissibility in the bimodal logics Ku and K4u (the extensions of K or K4 with the universal modality) is undecidable.Wolter & Zakharyaschev (2008) Remarkably, decidability of admissibility in the basic modal logic K is a major open problem.
Nevertheless, admissibility of rules is known to be decidable in many modal and superintuitionistic logics. The first decision procedures for admissible rules in basic transitive modal logics were constructed by Rybakov, using the reduced form of rules.Rybakov (1997), §3.9 A modal rule in variables p0, ... , pk is called reduced if it has the form
where each is either blank, or negation . For each rule r, we can effectively construct a reduced rule s (called the reduced form of r) such that any logic admits (or derives) r if and only if it admits (or derives) s, by introducing extension variables for all subformulas in A, and expressing the result in the full disjunctive normal form. It is thus sufficient to construct a decision algorithm for admissibility of reduced rules.
Let be a reduced rule as above. We identify every conjunction with the set of its conjuncts. For any subset W of the set of all conjunctions, let us define a Kripke model by
Then the following provides an algorithmic criterion for admissibility in K4:Rybakov (1997), Thm. 3.9.3
Theorem. The rule is not admissible in K4 if and only if there exists a set such that for some for every for every subset D of W there exist elements such that the equivalences if and only if for every if and only if and for every
Similar criteria can be found for the logics S4, GL, and Grz.Rybakov (1997), Thms. 3.9.6, 3.9.9, 3.9.12; cf. Chagrov & Zakharyaschev (1997), §16.7 Furthermore, admissibility in intuitionistic logic can be reduced to admissibility in Grz using the Gödel–McKinsey–Tarski translation:Rybakov (1997), Thm. 3.2.2 if and only if
Rybakov (1997) developed much more sophisticated techniques for showing decidability of admissibility, which apply to a robust (infinite) class of transitive (i.e., extending K4 or IPC) modal and superintuitionistic logics, including e.g. S4.1, S4.2, S4.3, KC, Tk (as well as the above-mentioned logics IPC, K4, S4, GL, Grz).Rybakov (1997), §3.5
Despite being decidable, the admissibility problem has relatively high computational complexity, even in simple logics: admissibility of rules in the basic transitive logics IPC, K4, S4, GL, Grz is coNEXP-complete.Jeřábek (2007) This should be contrasted with the derivability problem (for rules or formulas) in these logics, which is PSPACE-complete.Chagrov & Zakharyaschev (1997), §18.5
Projectivity and unification
Admissibility in propositional logics is closely related to unification in the equational theory of modal or Heyting algebras. The connection was developed by Ghilardi (1999, 2000). In the logical setup, a unifier of a formula A in the language of a logic L (an L-unifier for short) is a substitution σ such that σA is a theorem of L. (Using this notion, we can rephrase admissibility of a rule A/B in L as "every L-unifier of A is an L-unifier of B".) An L-unifier σ is less general than an L-unifier τ, written as σ ≤ τ, if there exists a substitution υ such that
for every variable p. A complete set of unifiers of a formula A is a set S of L-unifiers of A such that every L-unifier of A is less general than some unifier from S. A most general unifier (MGU) of A is a unifier σ such that {σ} is a complete set of unifiers of A. It follows that if S is a complete set of unifiers of A, then a rule A/B is L-admissible if and only if every σ in S is an L-unifier of B. Thus we can characterize admissible rules if we can find well-behaved complete sets of unifiers.
An important class of formulas that have a most general unifier are the projective formulas: these are formulas A such that there exists a unifier σ of A such that
for every formula B. Note that σ is an MGU of A. In transitive modal and superintuitionistic logics with the finite model property, one can characterize projective formulas semantically as those whose set of finite L-models has the extension property:Ghilardi (2000), Thm. 2.2 if M is a finite Kripke L-model with a root r whose cluster is a singleton, and the formula A holds at all points of M except for r, then we can change the valuation of variables in r so as to make A true at r as well. Moreover, the proof provides an explicit construction of an MGU for a given projective formula A.
In the basic transitive logics IPC, K4, S4, GL, Grz (and more generally in any transitive logic with the finite model property whose set of finite frame satisfies another kind of extension property), we can effectively construct for any formula A its projective approximation Π(A):Ghilardi (2000), p. 196 a finite set of projective formulas such that for every every unifier of A is a unifier of a formula from Π(A). It follows that the set of MGUs of elements of Π(A) is a complete set of unifiers of A. Furthermore, if P is a projective formula, then if and only if for any formula B. Thus we obtain the following effective characterization of admissible rules:Ghilardi (2000), Thm. 3.6 if and only if
Bases of admissible rules
Let L be a logic. A set R of L-admissible rules is called a basisRybakov (1997), Def. 1.4.13 of admissible rules, if every admissible rule Γ/B can be derived from R and the derivable rules of L, using substitution, composition, and weakening. In other words, R is a basis if and only if is the smallest structural consequence relation that includes and R.
Notice that decidability of admissible rules of a decidable logic is equivalent to the existence of recursive (or recursively enumerable) bases: on the one hand, the set of all admissible rules is a recursive basis if admissibility is decidable. On the other hand, the set of admissible rules is always co-recursively enumerable, and if we further have a recursively enumerable basis, set of admissible rules is also recursively enumerable; hence it is decidable. (In other words, we can decide admissibility of A/B by the following algorithm: we start in parallel two exhaustive searches, one for a substitution σ that unifies A but not B, and one for a derivation of A/B from R and . One of the searches has to eventually come up with an answer.) Apart from decidability, explicit bases of admissible rules are useful for some applications, e.g. in proof complexity.Mints & Kojevnikov (2004)
For a given logic, we can ask whether it has a recursive or finite basis of admissible rules, and to provide an explicit basis. If a logic has no finite basis, it can nevertheless have an independent basis: a basis R such that no proper subset of R is a basis.