= Solution
Let $T_e$ be the theory of the <extension axioms for an unrestricted binary relation>. It has <quantifier elimination>. To prove this, consider a conjunction of literals $\theta(y,\mathbf x)$. A witness $y$ equal to one of the parameters is handled by substitution. A witness distinct from them is governed entirely by a finite pattern of incoming edges, outgoing edges and its loop. For each equality pattern of the parameter tuple, incompatible literals make the pattern impossible, and every compatible pattern is supplied by the appropriate extension axiom. Thus existence of a witness is a finite disjunction of quantifier-free conditions on the parameters. Disjunctive normal form and induction on formulas eliminate all remaining quantifiers.
Given any formula $\phi(\mathbf x)$, choose a quantifier-free $\psi(\mathbf x)$ with
$$
T_e\models\forall\mathbf x\,[\phi(\mathbf x)\leftrightarrow\psi(\mathbf x)].
$$
By <compactness theorem>, finitely many extension axioms $\sigma_1,\ldots,\sigma_s$ already entail this particular universally quantified equivalence. Each has asymptotic probability one by the assumption. The union bound gives
$$
\Pr\!\left(\bigwedge_{j=1}^s\sigma_j\right)
\ge1-\sum_{j=1}^s\Pr(\neg\sigma_j)\longrightarrow1.
$$
Therefore the universal equivalence also has asymptotic probability one. We obtain \b[asymptotic equivalence to a <quantifier-free formula>], uniformly over every tuple in each structure satisfying those finitely many axioms. An infinite conjunction of probability-one events is not used; the finite consequence supplied by compactness is essential.
Back to article page
