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.) |