Systems of illative combinatory logic complete for first-order propositional and predicate calculus

Journal of Symbolic Logic 58 (3):769-788 (1993)
  Copy   BIBTEX


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)



    Upload a copy of this work     Papers currently archived: 93,745

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles


Added to PP

71 (#80,786)

6 months
19 (#786,843)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Typed lambda calculus.Henk P. Barendregt, Wil Dekkers & Richard Statman - 1977 - In Jon Barwise (ed.), Handbook of mathematical logic. New York: North-Holland. pp. 1091--1132.
Circular languages.Hannes Leitgeb & Alexander Hieke - 2004 - Journal of Logic, Language and Information 13 (3):341-371.

Add more citations

References found in this work

The Lambda Calculus. Its Syntax and Semantics.E. Engeler - 1984 - Journal of Symbolic Logic 49 (1):301-303.
The Calculi of Lambda-Conversion.Barkley Rosser - 1941 - Journal of Symbolic Logic 6 (4):171-171.
Propositional and predicate calculuses based on combinatory logic.M. W. Bunder - 1974 - Notre Dame Journal of Formal Logic 15 (1):25-34.
A deduction theorem for restricted generality.M. W. Bunder - 1973 - Notre Dame Journal of Formal Logic 14 (3):341-346.
Introduction to Combinators and λ-Calculus.J. Roger Hindley & Jonathan P. Seldin - 1988 - Journal of Symbolic Logic 53 (3):985-986.

View all 8 references / Add more references