Randomness and semigenericity
Authors:
John T. Baldwin and Saharon Shelah
Journal:
Trans. Amer. Math. Soc. 349 (1997), 1359-1376
MSC (1991):
Primary 03C10, 05C80
DOI:
https://doi.org/10.1090/S0002-9947-97-01869-2
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, https://doi.org/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, https://doi.org/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