The Lattice of Lambda Theories Lusin, Stefania; Salibra, Antonino
Journal of logic and computation,
06/2004, Letnik:
14, Številka:
3
Journal Article
Recenzirano
Odprti dostop
Lambda theories are equational extensions of the untyped lambda calculus that are closed under derivation. The set of lambda theories is naturally equipped with a structure of complete lattice, where ...the meet of a family of lambda theories is their intersection, and the join is the least lambda theory containing their union. In this paper we study the structure of the lattice of lambda theories by universal algebraic methods. We show that nontrivial quasi-identities in the language of lattices hold in the lattice of lambda theories, while every nontrivial lattice identity fails in the lattice of lambda theories if the language of lambda calculus is enriched by a suitable finite number of constants. We also show that there exists a sublattice of the lattice of lambda theories which satisfies: (i) a restricted form of distributivity, called meet semidistributivity; and (ii) a nontrivial identity in the language of lattices enriched by the relative product of binary relations.
We use intersection types as a tool for obtaining
λ-models. Relying on the notion of
easy intersection type theory, we successfully build a
λ-model in which the interpretation of an arbitrary simple ...easy term is any filter which can be described by a continuous predicate. This allows us to prove two results. The first gives a proof of consistency of the
λ-theory where the
λ-term (
λx.
xx)(
λx.
xx) is forced to behave as the join operator. This result has interesting consequences on the algebraic structure of the lattice of
λ-theories. The second result is that for any simple easy term, there is a
λ-model, where the interpretation of the term is the
minimal fixed point operator.
Plotkin has conjectured that there exists an absolutely unorderable combinatory algebra, namely a combinatory algebra which cannot be embedded in another combinatory algebra admitting a nontrivial ...compatible partial order. In this paper we prove that a wide class of combinatory algebras admits extensions with a nontrivial compatible partial order.
PDF
