Abstract
The results of this paper extend some of the intimate relations that are known to obtain between combinatory logic and certain substructural logics to establish a general characterization theorem that applies to a very broad family of such logics. In particular, I demonstrate that, for every combinator X, if LX is the logic that results by adding the set of types assigned to X (in an appropriate type assignment system, TAS) as axioms to the basic positive relevant logic B∘T, then LX is sound and complete with respect to the class of frames in the Routley-Meyer relational semantics for relevant and substructural logics that meet a first-order condition that corresponds in a very direct way to the structure of the combinator X itself.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, A. R., N. D. Belnap, Jr., and J. M. Dunn, Entailment: The Logic of Relevance and Entailment, Vol. II, Princeton University Press, 1992.
Barbanera F., Dezani-Ciancaglini M. and de’Liguoro U. (1995). ‘Intersection and Union Types: Syntax and Semantics’ . Information and Computation 119: 202–230
Barendregt H., Coppo M., and Dezani-Ciancaglini M. (1983). ‘A Filter Lambda Model and the Completeness of Type Assignment’. Journal of Symbolic Logic 48: 931–940
Bimbo K., (2004). ‘Semantics for Dual and Symmetric Combinatory Calculi’. Journal of Philosophical Logic 33: 125–153
Bimbo K. and Dunn J.M. (1998). ‘Two Extensions of the Structurally Free Logic LC’. Logic Journal of the IGPL 6: 403–424
Curry, H. and R. Feys, Combinatory Logic, North Holland, 1958.
Dezani-Ciancaglini M., and Hindley J.R. (1992). ‘Intersection Types for Combinatory Logic’, Theoretical Computer Science 100: 303–324
Dezani-Ciancaglini M., Meyer R.K., and Motohama Y. (2002). ‘The Semantics of Entailment Omega’. Notre Dame Journal of Formal Logic 43: 129–145
Dunn, J. M., ‘Relevance Logic and Entailment’, in D. Gabbay and F. Guenthner (eds.), Handbook of Philosophical Logic, 1st ed., vol. III, Kluwer, 1986, pp. 117–224.
Dunn J.M., and Meyer R.K. (1997). ‘Combinators and Structurally Free Logic’. Logic Journal of IGPL 5: 505–537
Goble L. (2004). ‘Combinator Logics’. Studia Logica76: 17–66
Hindley, J. R., and J. P. Seldin, Introduction to Combinators and λ-Calculus, Cambridge University Press, 1986.
Mares, E. D., and R. K. Meyer, ‘Relevant Logic’, in L. Goble (ed.), The Blackwell Guide to Philosophical Logic, Blackwell Publishers, 2001, pp. 280–308.
Meyer R.K. (2004). ‘Ternary Relations and Relevant Logics’. Annals of Pure and Applied Logic 127: 195–217
Meyer R.K., and Routley R. (1972). ‘Algebraic Analysis of Entailment I’. Logique et Analyse 15: 407–428
Pal, K., and R. K. Meyer ‘Basic Relevant Theories for Combinators at Levels I and II’, Australasian Journal of Logic, 3: 14–32, 2005; http://www.philosophy.unimelb.edu.au/ajl/2005.
Routley R., and Meyer R.K. (1972). ‘The Semantics of Entailment III’. Journal of Philosophical Logic 1: 192–208
Routley R., R. K., Meyer, V. Plumwood, and R. Brady, Relevant Logics and their Rivals, Ridgeview Pub. Co., 1982.
Author information
Authors and Affiliations
Corresponding author
Additional information
Presented by Rob Goldblatt
Rights and permissions
About this article
Cite this article
Goble, L. Combinatory Logic and the Semantics of Substructural Logics. Stud Logica 85, 171–197 (2007). https://doi.org/10.1007/s11225-007-9027-z
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11225-007-9027-z