Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)



Randomness and semigenericity

Authors: John T. Baldwin and Saharon Shelah
Journal: Trans. Amer. Math. Soc. 349 (1997), 1359-1376
MSC (1991): Primary 03C10, 05C80
MathSciNet review: 1407480
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information


Let $L$ contain only the equality symbol and let $L^+$ be an arbitrary finite symmetric relational language containing $L$. Suppose probabilities are defined on finite $L^+$ structures with ‘edge probability’ $n^{-\alpha }$. By $T^{\alpha }$, the almost sure theory of random $L^+$-structures we mean the collection of $L^+$-sentences which have limit probability 1. $T_{\alpha }$ denotes the theory of the generic structures for $\mathbb {K}_{\alpha }$ (the collection of finite graphs $G$ with $\delta _\alpha (G) = |G| - \alpha \cdot |\text {edges of $G$}|$ hereditarily nonnegative).

Theorem. $T^{\alpha }$, the almost sure theory of random $L^+$-structures, is the same as the theory $T_{\alpha }$ of the $\mathbb {K}_{\alpha }$-generic model. This theory is complete, stable, and nearly model complete. Moreover, it has the finite model property and has only infinite models so is not finitely axiomatizable.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (1991): 03C10, 05C80

Retrieve articles in all journals with MSC (1991): 03C10, 05C80

Additional Information

Saharon Shelah
MR Author ID: 160185
ORCID: 0000-0003-0462-3152

Keywords: Random graphs, 0-1-laws, stability
Received by editor(s): September 7, 1994
Additional Notes: Partially supported by NSF grant 9308768 and a visit to Simon Fraser University.
This is paper 528. Both authors thank Rutgers University and the Binational Science Foundation for partial support of this research.
Article copyright: © Copyright 1997 American Mathematical Society