Admissible rule

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 rules in propositional non-classical logics, which we will describe next.
Let a set of basic propositional connectives be fixed (for instance, formula_1 in the case of superintuitionistic logics, or formula_2 in the case of monomodal logics). Well-formed formulas are built freely using these connectives from a countably infinite set of propositional variables "p"0, "p""1", ... A substitution σ is a function from formulas to formulas which commutes with the connectives, i.e.,
for every connective "f", and formulas "A"1, ..., "A""n". (We may also apply substitutions to sets Γ of formulas, making ) A Tarski-style consequence relation is a relation formula_4 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 formula_4 if formula_6.
For example, we identify a superintuitionistic logic "L" with its standard consequence relation formula_7 axiomatizable by modus ponens and axioms, and we identify a normal modal logic with its global consequence relation formula_7 axiomatized by modus ponens, necessitation, and axioms.
A structural inference rule (or just rule for short) is given by a pair (Γ,"B"), usually written as
where Γ = {"A"1, ..., "A""n"} 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 formula_4, if formula_12. It is admissible if for every instance of the rule, σ"B" is a theorem whenever all formulas from σΓ are theorems. In other words, a rule is admissible if, when added to the logic, does not lead to new theorems. We also write formula_13 if Γ/"B" is admissible. (Note that formula_14 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., formula_15.
In logics with a well-behaved conjunction connective (such as superintuitionistic or modal logics), a rule formula_16 is equivalent to formula_17 with respect to admissibility and derivability. It is therefore customary to only deal with unary rules "A"/"B".
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 formula_25 (i.e., its complement is recursively enumerable). For instance, it is known that admissibility in the bimodal logics "K""u" and "K"4"u" (the extensions of "K" or "K"4 with the universal modality) is undecidable. 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. A modal rule in variables "p"0, ..., "p""k" is called reduced if it has the form
where each formula_27 is either blank, or negation formula_28. 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 formula_29 be a reduced rule as above. We identify every conjunction formula_30 with the set formula_31 of its conjuncts. For any subset "W" of the set formula_32 of all conjunctions, let us define a Kripke model formula_33 by
Then the following provides an algorithmic criterion for admissibility in "K"4:
Theorem. The rule formula_29 is "not" admissible in "K"4 if and only if there exists a set formula_37 such that
Similar criteria can be found for the logics "S"4, "GL", and "Grz". Furthermore, admissibility in intuitionistic logic can be reduced to admissibility in "Grz" using the Gödel–McKinsey–Tarski translation:
Rybakov (1997) developed much more sophisticated techniques for showing decidability of admissibility, which apply to a robust (infinite) class of transitive (i.e., extending "K"4 or "IPC") modal and superintuitionistic logics, including e.g. "S"4.1, "S"4.2, "S"4.3, "KC", "T""k" (as well as the above-mentioned logics "IPC", "K"4, "S"4, "GL", "Grz").
Despite being decidable, the admissibility problem has relatively high computational complexity, even in simple logics: admissibility of rules in the basic transitive logics "IPC", "K"4, "S"4, "GL", "Grz" is coNEXP-complete. This should be contrasted with the derivability problem (for rules or formulas) in these logics, which is PSPACE-complete.
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 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 which 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 a mgu of "A". In transitive modal and superintuitionistic logics with the finite model property (fmp), one can characterize projective formulas semantically as those whose set of finite "L"-models has the extension property: if "M" is a finite Kripke "L"-model with a root "r" whose cluster is a singleton, and the formula "A" holds in all points of "M" except for "r", then we can change the valuation of variables in "r" so as to make "A" true in "r" as well. Moreover, the proof provides an explicit construction of a mgu for a given projective formula "A".
In the basic transitive logics "IPC", "K"4, "S"4, "GL", "Grz" (and more generally in any transitive logic with the fmp whose set of finite frame satisfies another kind of extension property), we can effectively construct for any formula "A" its projective approximation Π("A"): a finite set of projective formulas such that
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
for any formula "B". Thus we obtain the following effective characterization of admissible rules:
Bases of admissible rules.
Let "L" be a logic. A set "R" of "L"-admissible rule is called a basis 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 formula_60 is the smallest structural consequence relation which includes formula_7 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 rule is a recursive basis if admissibility is decidable. On the other hand, the set of admissible rules is always co-r.e., and if we further have an r.e. basis, it is also r.e., 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 σ which unifies "A" but not "B", and one for a derivation of "A"/"B" from "R" and formula_7. 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.
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 has an independent basis: a basis "R" such that no proper subset of "R" is a basis.
In general, very little can be said about existence of bases with desirable properties. For example, while tabular logics are generally well-behaved, and always finitely axiomatizable, there exist tabular modal logics without a finite or independent basis of rules. Finite bases are relatively rare: even the basic transitive logics "IPC", "K"4, "S"4, "GL", "Grz" do not have a finite basis of admissible rules, though they have independent bases.
Semantics for admissible rules.
A rule Γ/"B" is valid in a modal or intuitionistic Kripke frame formula_68, if the following is true for every valuation formula_69 in "F":
Let "X" be a subset of "W", and "t" a point in "W". We say that "t" is
We say that a frame "F" has reflexive (irreflexive) tight predecessors, if for every "finite" subset "X" of "W", there exists a reflexive (irreflexive) tight predecessor of "X" in "W".
We have:
Note that apart from a few trivial cases, frames with tight predecessors must be infinite, hence admissible rules in basic transitive logics do not enjoy the finite model property.
Structural completeness.
While a general classification of structurally complete logics is not an easy task, we have a good understanding of some special cases.
Intuitionistic logic itself is not structurally complete, but its "fragments" may behave differently. Namely, any disjunction-free rule or implication-free rule admissible in a superintuitionistic logic is derivable. On the other hand, the Mints rule
is admissible in intuitionistic logic but not derivable, and contains only implications and disjunctions.
We know the "maximal" structurally incomplete transitive logics. A logic is called hereditarily structurally complete, if any extension is structurally complete. For example, classical logic, as well as the logics "LC" and "Grz".3 mentioned above, are hereditarily structurally complete. A complete description of hereditarily structurally complete superintuitionistic and transitive modal logics was given respectively by Citkin and Rybakov. Namely, a superintuitionistic logic is hereditarily structurally complete if and only if it is not valid in any of the five Kripke frames
Similarly, an extension of "K"4 is hereditarily structurally complete if and only if it is not valid in any of certain twenty Kripke frames (including the five intuitionistic frames above).
There exist structurally complete logics that are not hereditarily structurally complete: for example, Medvedev's logic is structurally complete, but it is included in the structurally incomplete logic "KC".
Variants.
A rule with parameters is a rule of the form
whose variables are divided into the "regular" variables "p""i", and the parameters "s""i". The rule is "L"-admissible if every "L"-unifier σ of "A" such that σ"s""i" = "s""i" for each "i" is also a unifier of "B". The basic decidability results for admissible rules also carry to rules with parameters.
A multiple-conclusion rule is a pair (Γ,Δ) of two finite sets of formulas, written as
Such a rule is admissible if every unifier of Γ is also a unifier of some formula from Δ. For example, a logic "L" is consistent iff it admits the rule
and a superintuitionistic logic has the disjunction property iff it admits the rule
Again, basic results on admissible rules generalize smoothly to multiple-conclusion rules. In logics with a variant of the disjunction property, the multiple-conclusion rules have the same expressive power as single-conclusion rules: for example, in "S"4 the rule above is equivalent to
Nevertheless, multiple-conclusion rules can often be employed to simplify arguments.
In proof theory, admissibility is often considered in the context of sequent calculi, where the basic objects are sequents rather than formulas. For example, one can rephrase the cut-elimination theorem as saying that the cut-free sequent calculus admits the cut rule
(By abuse of language, it is also sometimes said that the (full) sequent calculus admits cut, meaning its cut-free version does.) However, admissibility in sequent calculi is usually only a notational variant for admissibility in the corresponding logic: any complete calculus for (say) intuitionistic logic admits a sequent rule if and only if "IPC" admits the formula rule which we obtain by translating each sequent formula_80 to its characteristic formula formula_81.