Abstract

In this paper the existence or nonexistence of isomorphic mappings between graph models for the untyped lambda calculus is studied. It is shown that Engeler's D A is completely determined, up to isomorphism, by the cardinality of its `atom-set' A. A similar characterization is given for a collection of graph models of the Pω-type; from this some propositions regarding automorphisms are obtained. Also we give an indication of the complexity of the first-order theory of graph models by showing that the second-order theory of first-order definable elements of a graph model is first-order expressable in the model