Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-23T06:29:52.699Z Has data issue: false hasContentIssue false
  • English
  • Français

Constructive interpolation in hybrid logic

Published online by Cambridge University Press:  12 March 2014

Patrick Blackburn  and
Maarten Marx
Patrick Blackburn
Affiliation:
Inria Lorraine, 615 Rue du Jardin Botanique, 54602 Villers les Nancy Cedex, France, E-mail: [email protected]
Maarten Marx
Affiliation:
Universiteit van Amsterdam, ILLC, Nieuwe Achtergracht 166, 1018 WV Amsterdam, The Netherlands, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Craig's interpolation lemma (if φ → ψ is valid, then φ → θ and θ → ψ are valid, for θ a formula constructed using only primitive symbols which occur both in φ and ψ) fails for many propositional and first order modal logics. The interpolation property is often regarded as a sign of well-matched syntax and semantics. Hybrid logicians claim that modal logic is missing important syntactic machinery, namely tools for referring to worlds, and that adding such machinery solves many technical problems. The paper presents strong evidence for this claim by defining interpolation algorithms for both propositional and first order hybrid logic. These algorithms produce interpolants for the hybrid logic of every elementary class of frames satisfying the property that a frame is in the class if and only if all its point-generated subframes are in the class. In addition, on the class of all frames, the basic algorithm is conservative: on purely modal input it computes interpolants in which the hybrid syntactic machinery does not occur.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 68 , Issue 2 , June 2003 , pp. 463 - 480
Copyright
Copyright © Association for Symbolic Logic 2003

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

REFERENCES

[1]Areces, C., Blackburn, P., and Marx, M., Hybrid logics: Characterization, interpolation and complexity, this Journal, vol. 66 (2001), no. 3, pp. 977–1010.Google Scholar
[2]Areces, C., Blackburn, P., and Marx, M., Repairing the interpolation lemma in quantified modal logic, Technical Report PP-2001-19, Institute for Language, Logic and Computation, 2001, To appear in Annals of Pure and Applied Logic.Google Scholar
[3]Blackburn, P., de Rijke, M., and Venema, Y., Modal logic, Cambridge University Press, 2001.CrossRefGoogle Scholar
[4]Blackburn, P. and Marx, M., Tableaux for quantified hybrid logic, Automated reasoning with analytic tableaux and related methods, TABLEAUX 2002 (Egly, U. and Fermüller, C., editors), LNAI, vol. 2381, Springer Verlag, 2002, pp. 38–52.CrossRefGoogle Scholar
[5]de Rijke, M., The modal logic of inequality, this Journal, vol. 57 (1992), pp. 566–584.Google Scholar
[6]Fine, K., Failures of the interpolation lemma in quantified modal logic, this Journal, vol. 44 (1979), no. 2, pp. 201–206.Google Scholar
[7]Fitting, M., Proof methods for modal and intuitionistic logics, Synthese Library, vol. 169, Reidel, Dordrecht, 1983.CrossRefGoogle Scholar
[8]Fitting, M., First order logic and automated theorem proving, second ed., Springer Verlag, 1996.CrossRefGoogle Scholar
[9]Fitting, M., Interpolation for first order S5, this Journal, vol. 67 (2002), pp. 621–634.Google Scholar
[10]Maksimova, L., Amalgamation and interpolation in normal modal logics, Studia Logica, vol. L (1991), no. 3/4, pp. 457–471.CrossRefGoogle Scholar
[11]Marx, M. and Venema, Y., Multi-dimensional modal logic, Applied Logic Series, Kluwer Academic Publishers, 1997.CrossRefGoogle Scholar
[12]Rautenberg, W., Modal tableau calculi and interpolation, Journal of Philosophical Logic, vol. 12 (1983), pp. 403–423.CrossRefGoogle Scholar
[13]Smullyan, R., First order logic, Springer-Verlag, 1968.CrossRefGoogle Scholar