The algebraic $\lambda$-calculus is a conservative extension of the ordinary $\lambda$-calculus

Abstract

The algebraic $\lambda$-calculus is an extension of the ordinary $\lambda$-calculus with linear combinations of terms. We establish that two ordinary $\lambda$-terms are equivalent in the algebraic $\lambda$-calculus iff they are $\beta$-equal. Although this result was originally stated in the early 2000's (in the setting of Ehrhard and Regnier's differential $\lambda$-calculus), the previously proposed proofs were wrong: we explain why previous approaches failed and develop a new proof technique to establish conservativity.

Accepted at HOR 2023