Social and Behavioral Sciences Commons^™

Systems Of Illative Combinatory Logic Complete For First Order Propositional And Predicate Calculus, Henk Barendregt, Martin Bunder, Wil Dekkers

Faculty of Engineering and Information Sciences - Papers: Part A

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 …