No label defined (Q4247311)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1302066
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1302066

      Statements

      15 February 2000
      0 references
      combinators
      0 references
      JFM 50.0023.01
      0 references
      positive implicational logic
      0 references
      typed lambda calculus
      0 references
      general function type
      0 references
      disjoint union type
      0 references
      0 references
      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].
      0 references

      Identifiers