A 'Kripke-style' semantics is given for combinatory logic using frames with a ternary accessibility relation, much as in the Tourley-Meyer semantics for relevance logic. We prove by algebraic means a completeness theorem for combinatory logic, by proving a representation theorem for 'combinatory posets.' A philosophical interpretation is given of the models, showing that an element of a combinatory poset can be understood simultaneously as a set of states and as a set of actions on states. This double interpretation allows for (...) one such element to be applied to another . Application turns out to be modeled the same way as 'fusion' in relevance logic.We also introduce 'dual combinators' that apply from the right. We then explore relationships to some well-known substructural logics, showing that each can be embedded into the structurally free. non-associative Lambek calculus, with the embedding taking a theorem ω to a statement of the form Γ ⊨ ω, where Γ is some fusion of the combinators needed to justify the structural assumptions of the given substructural logic. This builds on earlier ideas from Belnap and Meyer about a Gentzen system wherein structural rules are replaced with rules for introducing combinators. We develop such a system and prove a cut theorem. (shrink)

The paper considers certain extensions of the system LC introduced in Dunn & Meyer 1997. LC is a structurally free system , but it has combinators as formulas in the place of structural rules. We consider two ways to extend LC with conjunction and disjunction depending on whether they distribute over each other or not. We prove the elimination theorem for the systems. At the end of the paper we give a Routley-Meyer style semantics for the distributive extension, including some (...) new definitions and an algorithm which are used in proving a representation theorem in general, i.e., for arbitrary combinators. (shrink)

Combinatory logic is known to be related to substructural logics. Algebraic considerations of the latter, in particular, algebraic considerations of two distinct implications, led to the introduction of dual combinators in Dunn & Meyer 1997. Dual combinators are "mirror images" of the usual combinators and as such do not constitute an interesting subject of investigation by themselves. However, when combined with the usual combinators, the whole system exhibits new features. A dual combinatory system with weak equality typically lacks the Church-Rosser (...) property, and in general it is inconsistent. In many subsystems terms "unexpectedly" turn out to be weakly equivalent. The paper is a preliminary attempt to investigate some of these issues, as well as, briefly compare function application in symmetric -calculus and dual combinatory logic. (shrink)