Refutation of Sallé’s Longstanding Conjecture
Giulio Manzonetto
LIPN, Université Paris 13
https://lipn.univ-paris13.fr/~gmanzonetto/
Date(s) : 15/02/2018 iCal
11h00 - 12h30
The lambda-calculus possesses a strong notion of extensionality, called « the omega-rule », which has been the subject of many investigations. It is a longstanding open problem whether the equivalence obtained by closing the theory of Böhm trees under the omega-rule is strictly included in Morris’s original observational theory, as conjectured by Sallé in the seventies. We will first show that Morris’s theory satisfies the omega-rule. We will then demonstrate that the two aforementioned theories actually coincide, thus disproving Sallé’s conjecture. The proof technique we develop is general enough to provide as a byproduct a new characterization, based on bounded eta-expansions, of the least extensional equality between Böhm trees.
Catégories
