Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-15T05:21:16.079Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  12 March 2014

Henk Barendregt
Affiliation:
Faculty of Mathematics and Computer Science, Catholic University, Nijmegen, The Netherlands, E-mail: henk@cs.kun.nl
Martin Bunder
Affiliation:
Faculty of Informatics, Department of Mathematics, University of Wollongong, NSW Australia, E-mail: Martin_Bunder@info-gw.uow.edu.au
Wil Dekkers
Affiliation:
Faculty of Mathematics and Computer Science, Catholic University, Nijmegen, The Netherlands, E-mail: wil@cs.kun.n

Abstract

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

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable