Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T00:59:23.903Z Has data issue: false hasContentIssue false
  • English
  • Français

UNIFICATION IN SUPERINTUITIONISTIC PREDICATE LOGICS AND ITS APPLICATIONS

Published online by Cambridge University Press:  03 December 2018

WOJCIECH DZIK  and
PIOTR WOJTYLAK
WOJCIECH DZIK*
Affiliation:
Institute of Mathematics, University of Silesia in Katowice
PIOTR WOJTYLAK*
Affiliation:
Institute of Mathematics and Computer Science, University of Opole
*
*INSTITUTE OF MATHEMATICS, UNIVERSITY OF SILESIA BANKOWA 14, KATOWICE 40-132, POLAND E-mail: [email protected]
†INSTITUTE OF MATHEMATICS AND COMPUTER SCIENCE UNIVERSITY OF OPOLE OLESKA 48, OPOLE 45-052, POLAND E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We introduce unification in first-order logic. In propositional logic, unification was introduced by S. Ghilardi, see Ghilardi (1997, 1999, 2000). He successfully applied it in solving systematically the problem of admissibility of inference rules in intuitionistic and transitive modal propositional logics. Here we focus on superintuitionistic predicate logics and apply unification to some old and new problems: definability of disjunction and existential quantifier, disjunction and existential quantifier under implication, admissible rules, a basis for the passive rules, (almost) structural completeness, etc. For this aim we apply modified specific notions, introduced in propositional logic by Ghilardi, such as projective formulas, projective unifiers, etc.

Unification in predicate logic seems to be harder than in the propositional case. Any definition of the key concept of substitution for predicate variables must take care of individual variables. We allow adding new free individual variables by substitutions (contrary to Pogorzelski & Prucnal (1975)). Moreover, since predicate logic is not as close to algebra as propositional logic, direct application of useful algebraic notions of finitely presented algebras, projective algebras, etc., is not possible.

Keywords

03B5503B3503G25superintuitionistic logicpredicate logicunificationadmissible ruleHarrop formulaprojective formulastructural completenessunification type
Type
Research Article
Information
The Review of Symbolic Logic , Volume 12 , Issue 1 , March 2019 , pp. 37 - 61
Copyright
Copyright © Association for Symbolic Logic 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

BIBLIOGRAPHY

Aczel, P. H. G. (1968). Saturated intuitionistic theories. In Arnold Schmidt, H., Schütte, K., and Thiele, H.-J., editors. Contributions to Mathematical Logic: Proceeding of the Logic Colloquium, Hannover 1966. Amsterdam: North-Holland, pp. 1–11.Google Scholar
Baader, F. & Ghilardi, S. (2011). Unification in modal and description logics. Logic Journal of the IGPL, 19 (5), 705–730.CrossRefGoogle Scholar
Baader, F. & Snyder, J. (2001). Unification theory. In Robinson, A. and Voronkov, A., editors. Handbook of Automated Reasoning, Chapter 6. Amsterdam: Elsevier Science B.V., pp. 439–526.Google Scholar
Baaz, M., Preining, N., & Zach, R. (2007). First-order Gödel logics. Annals of Pure and Applied Logic, 147(1), 23–47.CrossRefGoogle Scholar
Beth, E. W. (1970). Aspects of Modern Logic. Dordrecht-Holland: D. Reidel Publishing Company.CrossRefGoogle Scholar
Cabrer, L. & Metcalfe, G. (2015). Exact unification and admissibility. Logical Methods in Computer Science, 11(3), 1–15.Google Scholar
Casari, E. & Minari, P. (1983). Negation-free intermediate predicate logics. Bolletino dell’Unione Matematica Italiana, 6(2-B), 499–536.Google Scholar
Church, A. (1956). Introduction to Mathematical Logic I . Princeton, New Jersey: Princeton University Press.Google Scholar
Corsi, G. (1992). Completeness theorem for Dummett’s LC quantified and some of its extensions. Studia Logica, 51, 317–335.CrossRefGoogle Scholar
Corsi, G. & Ghilardi, S. (1992). Semantical aspects of quantified modal logic. In Bicchieri, C. and Dalla Chiara, M. L., editors. Knowledge, Belief and Strategic Action. Cambridge: Cambridge University Press, pp. 167–195.CrossRefGoogle Scholar
Dzik, W. (1975). On structural completeness of some nonclassical predicate calculi. Reports on Mathematical Logic, 5, 19–26.Google Scholar
Dzik, W. (2004). Chains of structurally complete predicate logics with the application of Prucnal’s substitution. Reports on Mathematical Logic, 38, 37–48.Google Scholar
Dzik, W. (2006). Splittings of lattices of theories and unification types. Contributions to General Algebra, 17, 71–81.Google Scholar
Dzik, W. (2007). Unification Types in Logic. Katowice: Silesian University Press.Google Scholar
Dzik, W. & Wojtylak, P. (2012). Projective unification in modal logic. Logic Journal of the IGPL, 20(1), 121–153.CrossRefGoogle Scholar
Dzik, W. & Wojtylak, P. (2015). Infinitary modal logics extending S4.3. Logic Journal of the IGPL, 23(4), 640–661.CrossRefGoogle Scholar
Dzik, W. & Wojtylak, P. (2016) Modal consequence relations extending S4.3. An application of projective unification. Notre Dame Journal of Formal Logic, 57, 523–549.CrossRefGoogle Scholar
Gabbay, D., Shehtman, V., & Skvortsov, D. (2009). Quantification in Nonclassical Logic, Vol. 1. Studies in Logic and the Foundations of Mathematics, Vol. 153. Amsterdam: Elsevier Science B.V.Google Scholar
Ghilardi, S. (1997). Unification through projectivity. Journal of Symbolic Computation, 7, 733–752.Google Scholar
Ghilardi, S. (1999). Unification in intuitionistic logic. Journal of Symbolic Logic, 64(2), 859–880.CrossRefGoogle Scholar
Ghilardi, S. (2000). Best solving modal equations. Annals of Pure and Applied Logic, 102, 183–198.CrossRefGoogle Scholar
Ghilardi, S. & Sacchetti, L. (2004). Filtering unification and most general unifiers in modal logic. The Journal of Symbolic Logic, 69, 879–906.CrossRefGoogle Scholar
Goldblatt, R. (2011). Quantifiers, Propositions and Identity: Admissible Semantics for Quantified Modal and Substructural Logics. Lecture Notes in Logic No. 38. Cambridge: Cambridge University Press.CrossRefGoogle Scholar
Goudsmit, J. & Iemhoff, R. (2014). On unification and admissible rules in Gabbay-de Jongh logics. Annals of Pure and Applied Logic, 165(2), 652–672.CrossRefGoogle Scholar
Harrop, R. (1960). Concerning formulas of the types $A \to B \vee C,A \to \left( {Ex} \right)B\left( x \right)$ in intuitionistic formal systems. Journal of Symbolic Logic, 25(1), 27–32.CrossRefGoogle Scholar
Iemhoff, R. (2006). On the rules of intermediate logics. Archive for Mathematical Logic, 45, 581–599.CrossRefGoogle Scholar
Iemhoff, R. (2015). On rules. Journal of Philosophical Logic, 80(3), 713–729.Google Scholar
Iemhoff, R. & Roziere, P. (2015). Unification in intermediate logics. Journal of Symbolic Logic, 80(3), 713–729.CrossRefGoogle Scholar
Kleene, S. C. (1962). Disjunction and existence under implication in elementary intuitionistic formalism. Journal of Symbolic Logic, 27(1), 11–18.CrossRefGoogle Scholar
Kreisel, G. (1958). The non-derivability of $\neg \left( x \right)A\left( x \right) \to \left( {Ex} \right)\neg A\left( x \right)$, A primitive recursive, in intuitionistic formal systems. Journal of Symbolic Logic, 23, 456–457.Google Scholar
Minari, P. (1986). Disjunction and existence properties in intermediate predicate logics. In Abrusci, V. M., editor. Proceedings of the Meeting “Logica e Filosofia della Scienza, oggi”, Vol. I. Bologna: CLUEB, pp. 199–203.Google Scholar
Minari, P. & Wroński, A. (1988). The property (HD) in intuitionistic logic. A partial solution of a problem of H. Ono. Reports on Mathematical Logic, 22, 21–25.Google Scholar
Ono, H. (1972/73). A study of intermadiate predicate logics. Publications RIMS, Kyoto University, 8, 619–643.CrossRefGoogle Scholar
Ono, H. (1987). Some problems in intermediate predicate logics. Reports on Mathematical logic, 21, 55–67.Google Scholar
Pogorzelski, W. A. (1971). Structural completeness of the propositional calculus. Bulletin de l’Académie Polonaise des Sciences, série des Sciences Mathématiques, Astronomiques et Physiques, 19, 349–351.Google Scholar
Pogorzelski, W. A. & Prucnal, T. (1975). Structural completeness of the first-order predicate calculus. Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 21, 315–320.CrossRefGoogle Scholar
Prucnal, T. (1979). On two problems of Harvey Friedman. Studia Logica, 38, 257–262.CrossRefGoogle Scholar
Rasiowa, H. (1954). Algebraic models for axiomatics theories. Fundamenta Mathematicae, 4, 291–310.Google Scholar
Rybakov, V. V., Terziler, M., & Gencer, C. (1999). An essay on unification and inference rules for modal logic. Bulletin of the Section of Logic, 28(3), 145–157.Google Scholar
Skvortsov, D. P. (1988). On axiomatizability of some intermediate logics. Reports on Mathematical Logic, 22, 115–116.Google Scholar
Skvortsov, D. P. (2006). On non-axiomatizability of superintuitionistic predicate logics of some classes of well-founded and dually well-founded Kripke frames. Journal of Logic and Computation, 16, 685–695.CrossRefGoogle Scholar
Takano, M. (1987). Ordered sets R and Q as bases of Kripke models. Studia Logica, 46, 137–148.CrossRefGoogle Scholar
Umezawa, T. (1959). On logics intermediate between intuitionistic and classical predicate logic, Journal of Symbolic Logic, 24, 141–153.CrossRefGoogle Scholar
van Benthem, J. F. A. K. (2010). Frame correspondences in modal predicate logic. In Feferman, S. and Sieg, W., editors. Proofs, Categories and Computations: Essays in Honor of Grigori Mints. London: College Publications, pp. 287–310.Google Scholar
Wroński, A. (1995). Transparent unification problem. Reports on Mathematical Logic, 29, 105–107.Google Scholar
Wroński, A. (2008). Transparent verifiers in intermediate logics. Abstracts of the 54th Conference in History of Mathematics. Cracow: The Jagiellonian University Press, p. 16.Google Scholar