Isomorphisms and Nonisomorphisms of Graph Models
Schellinx, Harold
J. Symbolic Logic, Tome 56 (1991) no. 1, p. 227-249 / Harvested from Project Euclid
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 $\mathbf{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 $\mathscr{P}\omega$-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.
Publié le : 1991-03-14
Classification: 
@article{1183743563,
     author = {Schellinx, Harold},
     title = {Isomorphisms and Nonisomorphisms of Graph Models},
     journal = {J. Symbolic Logic},
     volume = {56},
     number = {1},
     year = {1991},
     pages = { 227-249},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183743563}
}
Schellinx, Harold. Isomorphisms and Nonisomorphisms of Graph Models. J. Symbolic Logic, Tome 56 (1991) no. 1, pp.  227-249. http://gdmltest.u-ga.fr/item/1183743563/