Uniqueness typing for intersection types

Abstract

Working in a variant of the intersection type assignment system of Coppo, Dezani-Ciancaglini and Veneri [1981], we prove several facts about sets of terms having a given intersection type. Our main result is that every strongly normalizing term $M$ admits a *uniqueness typing*, which is a pair $(\Gamma ,A)$ such that 1) $\Gamma ⊢M:A$ 2) $\Gamma ⊢N:A⟹M{=}_{\beta \eta }N$ We also discuss several presentations of intersection type algebras, and the corresponding choices of type assignment rules.

Superseded by arXiv:1809.08169v2