Dual combinators emerge from the aim of assigning formulas containing ← as types to combinators. This paper investigates formally some of the properties of combinatory systems that include both combinators and dual combinators. Although the addition of dual combinators to a combinatory system does not affect the unique decomposition of terms, it turns out that some terms might be redexes in two ways (with a combinator as its head, and with a dual combinator as (...) its head). We prove a general theorem stating that no dual combinatory system possesses the Church-Rosser property. Although the lack of confluence might be problematic in some cases, it is not a problem per se. In particular, we show that no damage is inflicted upon the structurally free logics, the system in which dual combinators first appeared. (shrink)

The dissertation deals with problems in "logic", more precisely, it deals with particular formal systems aiming at capturing patterns of valid reasoning. Sequent calculi were proposed to characterize logical connectives via introduction rules. These systems customarily also have structural rules which allow one to rearrange the set of premises and conclusions. In the "structurally free logic" of Dunn and Meyer the structural rules are replaced by combinatory rules which allow the same reshuffling of formulae, and additionally introduce (...) an explicit marker for the application of the rule---the combinator. The dissertation gives syntactic extensions of such systems introducing conjunction and disjunction . Cut elimination is proved for these systems. ;Syntactic systems as a rule are accompanied by a semantics which interprets them. The extended systems are supplied with semantics using algebraic methods. First, the Lindenbaum algebras are formed, and then these algebras are represented in an algebra of sets. This gives a so called Kripke-style semantics for the systems. The representation for the distributive extension utilizes well-known techniques; it uses sets of prime filters and set theoretical operations on them to deal with conjunction and disjunction, plus a ternary accessibility relation to accommodate the intensional operators as fusion and implication. The representation theorem is proven generally, i.e., for arbitrary sets of combinators using the "squeeze lemma" of Routley and Meyer. ;The non-distributive calculi require a different representation since union and intersection are distributive. Two previous representations for lattices are overviewed, and a modification of the Hartonas-Dunn representation is successfully augmented with the intensional operations. Instead of sets of filters, sets of pairs of minimally inconsistent filters and ideals are used and the representation theorem is proven. The representation results provide soundness and completeness for the systems. The dissertation also investigates properties of dual combinators , proving a series of lemmas about dual combinatory systems not being Church-Rosser and being inconsistent. Combinatorially definable classes of lambda-terms are considered as well. (shrink)

Symmetic combinatory logic with the symmetric analogue of a combinatorially complete base (in the form of symmetric λ-calculus) is known to lack the Church-Rosser property. We prove a much stronger theorem that no symmetric combinatory logic that contains at least two proper symmetric combinators has the Church-Rosser property. Although the statement of the result looks similar to an earlier one concerning dual combinatory logic, the proof is different because symmetric combinators may form redexes (...) in both left and right associated terms. Perhaps surprisingly, we are also able to show that certain symmetric combinatory logics that include just one particular constant are not confluent. This result (beyond other differences) clearly sets apart symmetric combinatory logic from dual combinatory logic, since all dual combinatory systems with a single combinator or a single dual combinator are Church-Rosser. Lastly, we prove that a symmetric combinatory logic that contains the fixed point and the one-place identity combinator has the Church-Rosser property. (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)

We define dual and symmetric combinatory calculi (inequational and equational ones), and prove their consistency. Then, we introduce algebraic and set theoretical relational and operational - semantics, and prove soundness and completeness. We analyze the relationship between these logics, and argue that inequational dual logics are the best suited to model computation.

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)

CHAPTER Addenda to Pure Combinatory Logic This chapter will treat various additions to, and modifications of, the subject matter of Chapters-7. ...

We examine the Dual Ramsey Theorem and two related combinatorial principles VW(k,l) and OVW(k,l) from the perspectives of reverse mathematics and effective mathematics. We give a statement of the Dual Ramsey Theorem for open colorings in second order arithmetic and formalize work of Carlson and Simpson [1] to show that this statement implies ACA 0 over RCA 0 . We show that neither VW(2,2) nor OVW(2,2) is provable in WKL 0 . These results give partial answers to questions (...) posed by Friedman and Simpson [3]. (shrink)

Introduction Combinatory logic deals with a class of formal systems designed for studying certain primitive ways in which functions can be combined to form ...

This paper discusses the relation between the minimal positive relevant logic B and intersection and union type theories. There is a marvelous coincidence between these very differently motivated research areas. First, we show a perfect fit between the Intersection Type Discipline ITD and the tweaking BT of B, which saves implication and conjunction but drops disjunction . The filter models of the -calculus (and its intimate partner Combinatory Logic CL) of the first author and her coauthors then (...) become theory models of these calculi. (The logician's "theory" is the algebraist's "filter".) The coincidence extends to a dual interpretation of key particles—the subtype translates to provable , type intersection to conjunction , function space to implication, and whole domain to the (trivially added but trivial) truth T. This satisfying ointment contains a fly. For it is right, proper, and to be expected that type union should correspond to the logical disjunction of B. But the simulation of functional application by a fusion (or modus ponens product) operation on theories leaves the key Bubbling lemma of work on ITD unprovable for the -prime theories now appropriate for the modeling. The focus of the present paper lies in an appeal to Harrop theories which are (a) prime and (b) closed under fusion. A version of the Bubbling lemma is then proved for Harrop theories, which accordingly furnish a model of and CL. (shrink)

Reader-friendly without compromising the precision of exposition, the book includes many new research results not found in the available literature.

Natural language does not express all connectives definable in classical logic as simple lexical items. Coordination in English is expressed by conjunction and, disjunction or, and negated disjunction nor. Other languages pattern similarly. Non-lexicalized connectives are typically expressed compositionally: in English, negated conjunction is typically expressed by combining negation and conjunction (not both). This is surprising: if $$\wedge$$ ∧ and $$\vee$$ ∨ are duals, and the negation of the latter can be expressed lexically (nor), why not the (...) negation of the former? I present a two-tiered model of the semantics of the binary connectives. The first tier captures the expressive power of the lexicon: it is a bilateral state-based semantics that, under a restriction, can express all and only the distinctions that can be expressed by the lexicon of natural language (and, or, nor). This first tier is characterized by rejection as non-assertion and a Neglect Zero assumption. The second tier is obtained by dropping the Neglect Zero assumption and enforcing a stronger notion of rejection, thereby recovering classical logic and thus definitions for all Boolean connectives. On the two-tiered model, we distinguish the limited expressive resources of the lexicon and the greater combinatorial expressive power of the language as a whole. This gives us a logic-based account of compositionality for the Boolean fragment of the language. (shrink)

Sections 1 through 4 define, in the usual inductive style, various classes of object including one which is called the “combinatory terms of polymorphic type”. Section 5 defines a reduction relation on these terms. Section 6 shows that the weak normalizability of the combinatory terms of polymorphic type entails the weak normalizability of the lambda terms of polymorphic type. The entailment is not vacuous, because the combinatory terms of polymorphic type are indeed weakly normalizable, as is proven (...) in Sect. 7 using Tait and Girard’s computability predicates. The remainder of the paper is devoted to arguing that interesting consequences would follow from the existence of an “ordinally informative” proof, i.e. one which uses transfinite induction over recursive ordinal numbers and otherwise finitary methods, of normalizability for as large a class of the terms as possible. (shrink)

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. (shrink)

We characterize the polynomial time operations as those which are provably total in a first order system, which comprises (untyped) combinatory logic with extensionality, together with positive “safe induction” on the set of binary strings. The formalization of safe induction is inspired by Leivants idea of ramification. We also show how to replace ramification by means of modal logic.

In this paper, I present a modified and extended version of combinatory logic. Schönfinkel originated the study of combinatory logic (in [2]), but its development is primarily due to H. B. Curry. In the present paper, I will make use of both the symbolism (with some modification) and the results of Curry, as found in [1].What is novel about my version of combinatory logic is a kind of combinators which I call discriminators. These combinators (...) discriminate between different symbols, and yield values which are determined by the symbols which are their arguments. If the normal combinators investigated by Curry are considered as functions taking (combinations of) symbols as arguments and yielding symbols as values, these combinators can rearrange and cancel their arguments or introduce new symbols. (shrink)

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators or, in a more direct way, in which derivations are (...) not translated. Both translations are closely related in a canonical way. The two direct translations turn out to be complete. The paper fulfills the program of Church [1932], [1933] and Curry [1930] to base logic on a consistent system of λ-terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). (shrink)

Systems TRC and TRCU of illative combinatory logic are introduced and shown to be equivalent in consistency strength and expressive power to Quine's set theory ‘New Foundations’ and the fragment NFU + Infinity of NF described by Jensen, respectively. Jensen demonstrated the consistency of NFU + Infinity relative to ZFC; the question of the consistency of NF remains open. TRC and TRCU are presented here as classical first-order theories, although they can be presented as equational theories; they are (...) not constructive. (shrink)

Let $R$ be a convergent term rewriting system, and let $CR$-equality on combinatory logic terms be the equality induced by $\beta \eta R$-equality on terms of the lambda calculus under any of the standard translations between these two frameworks for higher-order reasoning. We generalize the classical notion of strong reduction to a reduction relation which generates $CR$-equality and whose irreducibles are exactly the translates of long $\beta R$-normal forms. The classical notion of strong normal form in combinatory (...) logic is also generalized, yielding yet another description of these translates. Their resulting tripartite characterization extends to the combined first-order algebraic and higher-order setting the classical combinatory logic descriptions of the translates of long $\beta$-normal forms in the lambda calculus. As a consequence, the translates of long $\beta R$-normal forms are easily seen to serve as canonical representatives for $CR$-equivalence classes of combinatory logic terms for non-empty, as well as for empty, $R$. (shrink)

The first volume of a projected two-volume treatise which will provide for the first time a systematic and comprehensive exposition of an important branch of mathematical logic. Previously published research is integrated and revised in the light of later results, and much new material is presented. Highly technical and, even in introductory sections, extraordinarily dense in style, this is a work for specialists. An important contribution.--L. K. B.

This paper extends the results of an earlier paper by the author . New subsystems of the combinatory logic TRC shown in that paper to be equivalent to NF are introduced; these systems are analogous to subsystems of NF with predicativity restrictions on set comprehension introduced and shown to be consistent by Crabbé. For one of these systems, an exact equivalence in consistency strength and expressive power with the analogous subsystem of NF is established.

In this paper I wish to reformulate in my own way some parts of Whitehead's theory of prehensions. This reformulation will deviate in various respects from Whitehead's own detailed views and terminology, but the main inspiration is from Whitehead.

We study Artemov’s Reflective Combinatory Logic . We provide the explicit definition of types for and prove that every well-formed term has a unique type. We establish that the typability testing and detailed type restoration can be done in polynomial time and that the derivability relation for is decidable and PSPACE-complete. These results also formalize the intended semantics of the type t:F in . Terms store the complete information about the judgment “t is a term of type F”, (...) and this information can be extracted by the type restoration algorithm. (shrink)

Translations from Lambda calculi into combinatory logics can be used to avoid some implementational problems of the former systems. However, this scheme can only be efficient if the translation produces short output with a small number of combinators, in order to reduce the time and transient storage space spent during reduction of combinatory terms. In this paper we present a combinatory system and an abstraction algorithm, based on the original bracket abstraction operator of Schonfinkel [9]. The algorithm (...) introduces at most one combinator for each abstraction in the initial Lambda term. This avoids explosive term growth during successive abstractions and makes the system suitable for practical applications. We prove the correctness of the algorithm and establish some relations between the combinatory system and the Lambda calculus. (shrink)

Combinatory logic started as a programme in the foundation of mathematics and in an historical context at a time when such endeavours attracted the most gifted among the mathematicians. This small volume arose under quite differ ent circumstances, namely within the context of reworking the mathematical foundations of computer science. I have been very lucky in finding gifted students who agreed to work with me and chose, for their Ph. D. theses, subjects that arose from my own attempts (...) 1 to create a coherent mathematical view of these foundations. The result of this collaborative work is presented here in the hope that it does justice to the individual contributor and that the reader has a chance of judging the work as a whole. E. Engeler ETH Zurich, April 1994 lCollected in Chapter III, An Algebraization of Algorithmics, in Algorithmic Properties of Structures, Selected Papers of Erwin Engeler, World Scientific PubJ. Co. , Singapore, 1993, pp. 183-257. I Historical and Philosophical Background Erwin Engeler In the fall of 1928 a young American turned up at the Mathematical Institute of Gottingen, a mecca of mathematicians at the time; he was a young man with a dream and his name was H. B. Curry. He felt that he had the tools in hand with which to solve the problem of foundations of mathematics mice and for all. His was an approach that came to be called "formalist" and embodied that later became known as Combinatory Logic. (shrink)

Pure Type Systems, PTSs, were introduced as a generalization of the type systems of Barendregt's lambda cube and were designed to provide a foundation for actual proof assistants which will verify proofs. Systems of illative combinatory logic or lambda calculus, ICLs, were introduced by Curry and Church as a foundation for logic and mathematics. In an earlier paper we considered two changes to the rules of the PTSs which made these rules more like ICL rules. This led (...) to four kinds of PTSs. Most importantly PTSs are about statements of the form M:A, where M is a term and A a type. In ICLs there are no explicit types and the statements are terms. In this paper we show that for each of the four forms of PTS there is an equivalent form of ICL, sometimes if certain conditions hold. (shrink)

What is the meaning of language expressions and how to compute or calculate it? In this paper, we give an answer to this question by analysing the meanings of aspects and tenses in natural languages inside the formal model of an grammar of applicative, cognitive and enunciative operations , using the applicative formalism, functional types of categorial grammars and combinatory logic . In the enunciative theory and following , an utterance can be decomposed into two components: a modus (...) and a dictum . In GRACE, the modus is a complex operator applied to a proposition and is generated from more elementary operators of the categories of tense, aspect, and modality. The dictum is a proposition generated by a predicative relation. In this way, we can attribute a semantic meaning to different grammatical aspecto-temporal operators. The applicative expressions of CL can be easily translated into a functional programming language such as HASKELL or CAML. (shrink)

The system of combinatory logic presented in this essay differs from usual systems of combinatory logic by its addition of Boolean operators and a theory of quantification. It differs from Fitch's previous systems in containing a strong extensionality principle. The system is claimed to provide adequate foundations for a major part of mathematical analysis. In this Report the elementary theory of natural numbers is developed in detail. An excellent introduction to Fitch's work; the exposition is clear (...) and well developed.--J. R. W. (shrink)

Propositional logic has been recognized throughout the centuries as one of the cornerstones of reasoning in philosophy and mathematics. Over time, its formalization into Boolean algebra was accompanied by the recognition that a wide range of combinatorial problems can be expressed as propositional satisfiability (SAT) problems. Because of this dual role, SAT developed into a mature, multi-faceted scientific discipline, and from the earliest days of computing a search was underway to discover how to solve SAT problems in an (...) automated fashion. This book, the Handbook of Satisfiability, is the second, updated and revised edition of the book first published in 2009 under the same name. The handbook aims to capture the full breadth and depth of SAT and to bring together significant progress and advances in automated solving. Topics covered span practical and theoretical research on SAT and its applications and include search algorithms, heuristics, analysis of algorithms, hard instances, randomized formulae, problem encodings, industrial applications, solvers, simplifiers, tools, case studies and empirical results. SAT is interpreted in a broad sense, so as well as propositional satisfiability, there are chapters covering the domain of quantified Boolean formulae (QBF), constraints programming techniques (CSP) for word-level problems and their propositional encoding, and satisfiability modulo theories (SMT). An extensive bibliography completes each chapter. This second edition of the handbook will be of interest to researchers, graduate students, final-year undergraduates, and practitioners using or contributing to SAT, and will provide both an inspiration and a rich resource for their work. Edmund Clarke, 2007 ACM Turing Award Recipient: "SAT solving is a key technology for 21st century computer science." Donald Knuth, 1974 ACM Turing Award Recipient: "SAT is evidently a killer app, because it is key to the solution of so many other problems." Stephen Cook, 1982 ACM Turing Award Recipient: "The SAT problem is at the core of arguably the most fundamental question in computer science: What makes a problem hard?". (shrink)

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. In a preceding paper, [2], we considered 4 systems of illative combinatory logic that are sound for first order intuitionistic propositional and predicate logic. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in (...) a more direct way, in which derivations are not translated. Both translations are closely related in a canonical way. In the cited paper we proved completeness of the two direct translations. In the present paper we prove that also the two indirect translations are complete. These proofs are direct whereas in another version, [3], we proved completeness by showing that the two corresponding illative systems are conservative over the two systems for the direct translations. Moreover we shall prove that one of the systems is also complete for predicate calculus with higher type functions. (shrink)

Illative combinatory logic consists of the theory of combinators or lambda calculus extended by extra constants (and corresponding axioms and rules) intended to capture inference. The paper considers 4 systems of illative combinatory logic that are sound for first-order propositional and predicate calculus. The interpretation from ordinary logic into the illative systems can be done in two ways: following the propositions-as-types paradigm, in which derivations become combinators, or in a more direct way, in which derivations (...) are not translated. Both translations are closely related in a canonical way. In a preceding paper, Barendregt, Bunder and Dekkers, 1993, we proved completeness of the two direct translations. In the present paper we prove completeness of the two indirect translations by showing that the corresponding illative systems are conservative over the two systems for the direct translations. In another version, DBB (1997), we shall give a more direct completeness proof. These papers fulfill the program of Church and Curry to base logic on a consistent system of $\lambda$ -terms or combinators. Hitherto this program had failed because systems of ICL were either too weak (to provide a sound interpretation) or too strong (sometimes even inconsistent). (shrink)