Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-16T07:47:59.074Z Has data issue: false hasContentIssue false

Classification of δ-invariant amalgamation classes

Published online by Cambridge University Press:  12 March 2014

Roman D. Aref'ev
Affiliation:
Informatics and Control Problems Institute, National Academy of Sciences, Almaty, Kazakstan
John T. Baldwin
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois At Chicago, Chicago, Illinois, USA, E-mail: jbaldwin@uic.edu
Marco Mazzucco
Affiliation:
Department of Mathematics, Statistics and Computer Science, University of Illinois At Chicago, Chicago. Illinois., USA, E-mail: marco@lac.uic.edu

Extract

Hrushovski's generalization of the Fraisse construction has provided a rich source of examples in model theory, model theoretic algebra and random graph theory. The construction assigns to a dimension function δ and a class K of finite (finitely generated) models a countable ‘generic’ structure. We investigate here some of the simplest possible cases of this construction. The class K will be a class of finite graphs; the dimension, δ(A), of a finite graph A will be the cardinality of A minus the number of edges of A. Finally and significantly we restrict to classes which are δ-invariant. A class of finite graphs is δ-invariant if membership of a graph in the class is determined (as specified below) by the dimension and cardinality of the graph, and dimension and cardinality of all its subgraphs. Note that a generic graph constructed as in Hrushovski's example of a new strongly minimal set does not arise from a δ-invariant class.

We show there are countably many δ-invariant (strong) amalgamation classes of finite graphs which are closed under subgraph and describe the countable generic models for these classes. This analysis provides ω-stable generic graphs with an array of saturation and model completeness properties which belies the similarity of their construction. In particular, we answer a question of Baizhanov (unpublished) and Baldwin [5] and show that this construction can yield an ω-stable generic which is not saturated. Further, we exhibit some ω-stable generic graphs that are not model complete.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1999

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable