|
Published Articles >> Table of Contents >> Abstract
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06)
pp. 317-326
Boolean Algebras for Lambda Calculus
G. Manzonetto, Universite Paris 7, France
A. Salibra, Universita Ca’Foscari di Venezia, Italy
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/LICS.2006.16
Send link to a friend
| Abstract |
|
In this paper we show that the Stone representation theorem
for Boolean algebras can be generalized to combinatory
algebras. In every combinatory algebra there is a
Boolean algebra of central elements (playing the role of
idempotent elements in rings), whose operations are defined
by suitable combinators. Central elements are used to represent
any combinatory algebra as a Boolean product of
directly indecomposable combinatory algebras (i.e., algebras
which cannot be decomposed as the Cartesian product
of two other nontrivial algebras). Central elements are
also used to provide applications of the representation theorem
to lambda calculus. We show that the indecomposable
semantics (i.e., the semantics of lambda calculus given in
terms of models of lambda calculus, which are directly indecomposable
as combinatory algebras) includes the continuous,
stable and strongly stable semantics, and the term
models of all semisensible lambda theories. In one of the
main results of the paper we show that the indecomposable
semantics is equationally incomplete, and this incompleteness
is as wide as possible: for every recursively enumerable
lambda theory T , there is a continuum of lambda theories
including T which are omitted by the indecomposable
semantics.
|
 Additional Information
|
Citation:
G. Manzonetto, A. Salibra,
"Boolean Algebras for Lambda Calculus,"
lics,
pp. 317-326,
21st Annual IEEE Symposium on Logic in Computer Science (LICS'06),
2006
|
|
