Nino Salibra (Univ. Venezia)

Problem 19

Abstract: The TLCA list of open problems is a list of twenty-two problems that aims at collecting unresolved questions in the subject areas of the TLCA (Typed Lambda Calculi and Applications) series of conferences. Problem 19 in the TLCA list was posed by Fabio Alessi and Mariangiola Dezani-Ciancaglini in 2002.

A closed lambda term M is easy if, for any other closed term N, the lambda theory generated by M = N is consistent, while it is simple easy if, given an arbitrary intersection type t, one can find a suitable pre-order on types which allows to derive t for M. Simple easiness implies easiness. The question whether easiness implies simple easiness constitutes Problem 19 in the TLCA list. We negatively answer the question providing a nonempty co-r.e. (complement of a recursively enumerable) set of easy, but non simple easy, lambda terms.