scientific article; zbMATH DE number 1302066
The reduction of the lambda calculus to the theory of combinators [\textit{M. Schönfinkel}, Math. Ann. 92, 305-316 (1924; JFM 50.0023.01)] applies to positive implicational logic, i.e. to the typed lambda calculus, where the types are built up from atomic types by means of the operation \(A\to B\), to show that the lambda operator can be eliminated in favour of combinators \(K\) and \(S\) of each type \(A\to (B\to A)\) and \((A\to (B\to C))\to ((A\to B)\to (A\to C))\), respectively. I will extend that result to the case in which the types are built up by means of the general function type \(\forall x: A.B(x)\) as well as the disjoint union type \(\exists x:A.B(x)\) -- essentially to the theory of Howard [\textit{W. Howard}, ``The formula-as-types notion of construction, in: J. P. Seldin et al. (eds.), To H. B. Curry: Essays on combinatory logic, lambda calculus and formalism (Academic Press, London), 479-490 (1980; Zbl 0469.03006)]. To extend the treatment of \(\to\) to \(\forall\) we shall need a generalized form of the combinators \(K\) and \(S\), and to deal with \(\exists\) we will need to introduce a new form of the combinator \(S\) (whose type turns out to be a general form of the axiom of choice). But also in the present context, if we are to eliminate variables, then not only the lambda operator for forming terms, but also quantification as a variable-binding operation for forming formulas must be analyzed away; so we will need an analogue of the combinators for formulas. For the entire collection see [Zbl 0899.00026].
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4247311)