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

Abstract | References | Similar Articles | Additional Information

Abstract: 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 ${\mathbf {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 ${\mathbf {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?)

  • 1. J.T. Baldwin and Niandong Shi. Stable generic structures. Annals of Pure and Applied Logic, 79: 1-35, 1996. CMP 96:13
  • 2. A. Baudisch. A new $\aleph _1$-categorical pure group. 1992.
  • 3. E. Hrushovski. A stable $\aleph _0$-categorical pseudoplane. preprint, 1988.
  • 4. D.W. Kueker and C. Laskowski. On generic structures. Notre Dame Journal of Formal Logic, 33:175-183, 1992. MR 93k:03032
  • 5. J. Lynch. Probabilities of sentences about very sparse random graphs. Random Structures and Algorithms, 3:33-53, 1992.
  • 6. S. Shelah. 0-1 laws. preprint 550, 199?
  • 7. S. Shelah. Zero-one laws with probability varying with decaying distance. Shelah 467, 199x.
  • 8. S. Shelah and J. Spencer. Zero-one laws for sparse random graphs. Journal of A.M.S., 1:97-115, 1988. MR 89i:05249
  • 9. F. Wagner. Relational structures and dimensions. In Automorphisms of first order structures, pages 153-181. Clarendon Press, Oxford, 1994. CMP 95:10

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

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

American Mathematical Society