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

Abstract: Let contain only the equality symbol and let be an arbitrary finite symmetric relational language containing . Suppose probabilities are defined on finite structures with `edge probability' . By , the almost sure theory of random -structures we mean the collection of -sentences which have limit probability 1. denotes the theory of the generic structures for (the collection of finite graphs with hereditarily nonnegative).

. *, the almost sure theory of random -structures, is the same as the theory of the -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. *

**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 -categorical pure group. 1992.**3.**E. Hrushovski. A stable -categorical pseudoplane. preprint, 1988.**4.**D. W. Kueker and M. C. Laskowski,*On generic structures*, Notre Dame J. Formal Logic**33**(1992), no. 2, 175–183. MR**1167973**, 10.1305/ndjfl/1093636094**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.**Saharon Shelah and Joel Spencer,*Zero-one laws for sparse random graphs*, J. Amer. Math. Soc.**1**(1988), no. 1, 97–115. MR**924703**, 10.1090/S0894-0347-1988-0924703-8**9.**F. Wagner. Relational structures and dimensions. In*Automorphisms of first order structures*, pages 153-181. Clarendon Press, Oxford, 1994. CMP**95:10**

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

DOI:
https://doi.org/10.1090/S0002-9947-97-01869-2

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