Available in electronic format
Available in print format
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(e) ISSN 0002-9947(p)
     

Randomness and semigenericity

Author(s): John T. Baldwin; Saharon Shelah
Journal: Trans. Amer. Math. Soc. 349 (1997), 1359-1376.
MSC (1991): Primary 03C10, 05C80
Retrieve article in: PDF
This article is available free of charge

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:

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:

John T. Baldwin
Affiliation: Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, Illinois 60607-7405

Saharon Shelah
Affiliation: Department of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel

DOI: 10.1090/S0002-9947-97-01869-2
PII: S 0002-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.
Copyright of article: Copyright 1997, American Mathematical Society


  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement
Search the AMSPowered by Google