×

How to construct extensional combinatory algebras. (English) Zbl 0619.03013

In this paper, a new idea for constructing combinatory algebras having the extensionality property is given. The construction of an extensional M(A) starting from a carrier set A generally follows the way in which E. Engeler succeeded to construct ”graph algebras”. The essential difference is the replacement of set inclusion by a certain set preorder relation ”\(\leq ''\). Many interesting properties of M(A) are proved. It is also proved that M(A) is isomorphic with the classical combinatory algebra, constructed from a complete lattice, as suggested by D. Scott. Finally, extensional substructures of graph algebras and \(P\omega\)-models are constructed.
Reviewer: C.Masalagiu

MSC:

03B40 Combinatory logic and lambda calculus
03C65 Models of other mathematical theories
06A06 Partial orders, general
68Q60 Specification and verification (program logics, model checking, etc.)