Skip Navigation



Journal of Logic and Computation Advance Access published online on November 6, 2007
Journal of Logic and Computation, doi:10.1093/logcom/exm061
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Carnielli, W.
Right arrow Articles by Sernadas, C.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author 2007. Published by Oxford University Press on behalf of the Association of Physicians. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

Original papers

Preservation of Interpolation Features by Fibring

Walter Carnielli, João Rasga and Cristina Sernadas

CLC and SQIG-IT, Department of Mathematics, IST, TU Lisbon, Portugal IFCH, UNICAMP, Brazil E-mail: csernadas{at}gmail.com

Received 29 March 2006.

Fibring is a metalogical constructor that permits to combine different logics by operating on their deductive systems under certain natural restrictions, as for example that the two given logics are presented by deductive systems of the same type. Under such circumstances, fibring will produce a new deductive system by means of the free use of inference rules from both deductive systems, provided the rules are schematic, in the sense of using variables that are open for application to formulas with new linguistic symbols (from the point of view of each logic component). Fibring is a generalization of fusion, a less general but wider developed mechanism which permits results of the following kind: if each logic component is decidable (or sound, or complete with respect to a certain semantics) then the resulting logic heirs such a property. The interest for such preservation results for combining logics is evident, and they have been achieved in the more general setting of fibring in several cases. The Craig interpolation property and the Maehara interpolation have a special significance when combining logics, being related to certain problems of complexity theory, some properties of model theory and to the usual (global) metatheorem of deduction. When the peculiarities of the distinction between local and global deduction interfere, justifying what we call careful reasoning, the question of preservation of interpolation becomes more subtle and other forms of interpolation can be distinguished. These questions are investigated and several (global and local) preservation results for interpolation are obtained for fibring logics that fulfill mild requirements.

Keywords: Interpolation; preservation of interpolation; fibring of logics



References

  1. Areces C, Blackburn P, Marx M. Hybrid logics: characterization, interpolation and complexity. Journal of Symbolic Logic (2001) 66:977–1010.[CrossRef][ISI]
  2. Areces C, Blackburn P, Marx M. Repairing the interpolation theorem in quantified modal logic. Annals of Pure and Applied Logic (2003) 124:287–299.[CrossRef][ISI]
  3. Baaz M, Veith H. Interpolation in fuzzy logic. Archive for Mathematical Logic (1999) 38:461–489.[CrossRef][ISI]
  4. Bicarregui J, Dimitrakos T, Gabbay D, Maibaum T. Interpolation in practical formal development. Logic Journal of the IGPL (2001) 9:231–243.[CrossRef]
  5. Blok WJ, Pigozzi D. Algebraizable logics. Memoirs of the American Mathematical Society (1989) 77:iv+78.
  6. Caleiro C, Carnielli WA, Coniglio ME, Sernadas A, Sernadas C. Fibring non-truth-functional logics: Completeness preservation. Journal of Logic, Language and Information (2003) 12:183–211.[CrossRef]
  7. Caleiro C, Carnielli WA, Rasga J, Sernadas C. Fibring of logics as a universal construction. In: Handbook of Philosophical Logic—Gabbay D, Guenthner F, eds. (2005) vol. 13, 2nd Edn. Dordrecht: Springer. 123–187.[CrossRef]
  8. Carbone A. The Craig interpolation theorem for schematic systems. In: Collegium Logicum (1996) vol. 2. Vienna: Springer. 87–100.
  9. Carbone A. Interpolants, cut elimination and flow graphs for the propositional calculus. Annals of Pure and Applied Logic (1997) 83:249–299.[CrossRef][ISI]
  10. Carnielli WA, Coniglio ME, Marcos J. Logics of formal inconsistency. In: Handbook of Philosophical Logic.—Gabbay D, Guenthner F, eds. vol. 14. Dordrecht: Kluwer Academic Publishers, Springer. in press.
  11. Carnielli WA, Dionísio FM, Mateus P, eds. Procs. CombLog'04: Workshop on Combination of Logics: Theory and Applications. (2004) IST, Lisbon: CLC, Department of Mathematics.
  12. Carnielli WA, Marcos J. A taxonomy of C-systems. Paraconsistency – The Logic Way to the Inconsistent. In: Vol. 228 of Lecture Notes in Pure and Applied Mathematics—Carnielli WA, Coniglio ME, Dapos;Ottaviano IML, eds. (2002) New York: Dekker. 1–94.
  13. Coniglio ME, Sernadas A, Sernadas C. Fibring logics with topos semantics. Journal of Logic and Computation (2003) 13:595–624.[Abstract/Free Full Text]
  14. Craig W. Linear reasoning. A new form of the Herbrand-Gentzen theorem. Journal of Symbolic Logic (1957) 22:250–268.[CrossRef]
  15. Czelakowski J, Pigozzi D. Amalgamation and interpolation in abstract algebraic logic. Models, Algebras, and Proofs. In: Vol. 203 of Lecture Notes in Pure and Applied Mathematics (1999) New York: Dekker. 187–265.
  16. Font JM, Jansana R, Pigozzi D. A survey of abstract algebraic logic. Studia Logica (2003) 74:13–97.[CrossRef]
  17. Gabbay D. Craig interpolation theorem for intuitionistic logic and extensions. III. Journal of Symbolic Logic (1977) 42:269–271.[CrossRef][ISI]
  18. Gabbay D. Fibred semantics and the weaving of logics: part 1. Journal of Symbolic Logic (1996) 61:1057–1120.[CrossRef][ISI]
  19. Gabbay D. Fibring Logics (1999) New York: Oxford University Press.
  20. Gabbay D, Maksimova L. Interpolation and Definability: Modal and Intuitionistic Logics. (2005) Oxford: Oxford University Press.
  21. Gottwald S. A Treatise on Many-Valued Logics. In: Vol. 9 of Studies in Logic and Computation (2001) Baldock: Research Studies Press Ltd.
  22. Governatori G, Padmanabhan V, Sattar A. On fibring semantics for BDI logics. In: JELIA—Flesca S, Ianni G, eds. (2002) Berlin: Springer Verlag. 198–210. Vol. 2424 of Lecture Notes in Artificial Intelligence.
  23. Henzinger T, Jhala R, Majumdar R, McMillan K. Abstractions from proofs. (2004) Proceedings of 31st Annual Symposium on Principles of Programming Languages POPL. New York: ACM Press. 232–244.
  24. Hoogland E. Definability and Interpolation: Model-theoretic Investigations. In: PhD Thesis (2001) ILLC, University of Amsterdam.
  25. Kracht M, Wolter F. Properties of independently axiomatizable bimodal logics. Journal of Symbolic Logic (1991) 56:1469–1485.[CrossRef][ISI]
  26. Krzystek PS, Zachorowski S. Lukasiewicz logics have not the interpolation property. Reports on Mathematical Logic (1977) 9:39–40.
  27. Maehara S. On the interpolation theorem of Craig. Sûgaku (1960–1961) 12:235–237.
  28. Maksimova L. Interpolation in superintuitionistic predicate logics with equality. Algebra i Logika (1997) 36:543–561, 600.
  29. Maksimova L. Complexity of interpolation and related problems in positive calculi. Journal of Symbolic Logic (2002) 67:397–408.[ISI]
  30. McMillan K. Interpolation and SAT-based model checking. In Computer Aided Verification CAV03. In: Vol. 2725 of Lecture Notes in Computer Science—Somenzi F, Hunt W, eds. (2003) Berlin: Springer Verlag. 1–13.
  31. Mundici D. Complexity of Craig's interpolation. Fundamenta Informaticae (1982) 5:261–278.
  32. Mundici D. NP and Craig's interpolation theorem. In Logic Colloquium '82. In: Vol. 112 of Studies in Logic and the Foundations of Mathematics (1984) Amsterdam: North-Holland. 345–358.
  33. Rasga J, Sernadas A, Sernadas C, Viganò L. Fibring labelled deduction systems. Journal of Logic and Computation (2002) 12:443–473.[Abstract/Free Full Text]
  34. Rosser JB, Turquette AR. Many-valued Logics. Studies in Logic and the Foundations of Mathematics. (1951) Amsterdam: North-Holland.
  35. Sernadas A, Sernadas C. Combining logic systems: Why, how, what for? CIM Bulletin (2003) 15:9–14.
  36. Sernadas A, Sernadas C, Caleiro C. Fibring of logics as a categorial construction. Journal of Logic and Computation (1999) 9:149–179.[Abstract/Free Full Text]
  37. Sernadas A, Sernadas C, Zanardo A. Fibring modal first-order logics: Completeness preservation. Logic Journal of the IGPL (2002) 10:413–451.[CrossRef][ISI]
  38. Sernadas C, Rasga J, Carnielli WA. Modulated fibring and the collapsing problem. Journal of Symbolic Logic (2002) 67:1541–1569.[ISI]
  39. Thomason RH. Combinations of tense and modality. In Handbook of Philosophical Logic, Vol. II. In: Vol. 165 of Synthese Library (1984) Dordrecht: Reidel. 135–165.
  40. Wójcicki R. Theory of Logical Calculi. In: Vol. 199 of Synthese Library (1988) Dordrecht: Kluwer.
  41. Wolter F. Fusions of modal logics revisited. In Advances in Modal Logic, Vol. 1. In: Vol. 87 of CSLI Lecture Notes (1998) Stanford University. 361–379.
  42. Zanardo A, Sernadas A, Sernadas C. Fibring: Completeness preservation. Journal of Symbolic Logic (2001) 66:414–439.[CrossRef][ISI]

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Carnielli, W.
Right arrow Articles by Sernadas, C.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?