Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Admissible rule
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
==Projectivity and unification== Admissibility in propositional logics is closely related to unification in the [[equational theory]] of [[modal algebra|modal]] or [[Heyting algebra]]s. 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 :<math>\vdash_L\sigma p\leftrightarrow \upsilon\tau p</math> 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 :<math>A\vdash_L B\leftrightarrow\sigma B</math> for every formula ''B''. Note that ''Ο'' is an MGU of ''A''. In transitive modal and superintuitionistic logics with the [[Kripke semantics#Finite model property|finite model property]], one can characterize projective formulas semantically as those whose set of finite ''L''-models has the '''extension property''':<ref>Ghilardi (2000), Thm. 2.2</ref> if ''M'' is a finite Kripke ''L''-model with a root ''r'' whose cluster is a [[singleton (mathematics)|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'', ''K''4, ''S''4, ''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''):<ref>Ghilardi (2000), p. 196</ref> a finite set of projective formulas such that #<math>P\vdash_L A</math> for every <math>P\in\Pi(A),</math> #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 :<math>P\,|\!\!\!\sim_L B</math> if and only if <math>P\vdash_L B</math> for any formula ''B''. Thus we obtain the following effective characterization of admissible rules:<ref>Ghilardi (2000), Thm. 3.6</ref> :<math>A\,|\!\!\!\sim_L B</math> if and only if <math>\forall P\in\Pi(A)\,(P\vdash_L B).</math>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)