Isomorphisms and Non-Isomorphisms of Graph Models

摘要

In the paper the existence or non-existence of isomorphic mappings between graphmodels 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(omega)-type; from this some propositions regarding automorphisms are obtained. Also the authors 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.