On linear combinations of λ-terms

Abstract. We define an extension of λ-calculus with linear combinations, endowing the set of terms with a structure of R-module, where R is a fixed set of scalars. Terms are moreover subject to identities similar to usual pointwise definition of linear combinations of functions with values in a vector space. We then extend β-reduction on those algebraic λ-terms as follows: at + u reduces to at ′ + u as soon as term t reduces to t ′ and a is a non-zero scalar. We prove that reduction is confluent. Under the assumption that the set R of scalars is positive (i.e. a sum of scalars is zero iff all of them are zero), we show that this algebraic λcalculus is a conservative extension of ordinary λ-calculus. On the other hand, we show that if R admits negative elements, then every term reduces to every other term. We investigate the causes of that collapse, and discuss some possible fixes. Preliminary definitions and notations. Recall that a rig (also known as “semiring with zero and unit”) is the same as a ring, without the condition that every element admits an opposite for addition. Let R be a rig. We write R • for R \ {0}. We denote by letters a, b, c the elements of R, and say that R is positive if, for all a, b ∈ R, a + b = 0 implies a = 0 and b = 0. An example of positive rig is N, the set of natural numbers, with usual addition and multiplication. If i, j ∈ N, we write [i; j] for the set {k ∈ N; i ≤ k ≤ j}. Also, we write application of λ-terms à la Krivine: (s)t denotes the application of term s to term t.