Randomness and semigenericity

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 $\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.