Almost everywhere elimination of probability quantifiers. (English) Zbl 1187.03030

The authors study first-order logic with the addition of probability quantifiers \(\exists^{\geq r} \bar{y}\) for \(r \in (0,1)\). This language is denoted \(L_{\omega,P}\). If \(\bar{y}\) is an \(l\)-tuple of distinct variables, then \(\exists^{\geq r} \bar{y} \varphi(\bar{a},\bar{y}))\) is interpreted as true in a structure with the universe \(\{1, \ldots, n\}\) if there are at least \(r n^l\) \(l\)-tuples \(\bar{b}\) of elements from the given structure such that \(\varphi(\bar{a},\bar{b})\) holds. The vocabulary (signature) is assumed to be relational and finite. For each relation symbol \(R\) a fixed probability \(p_R \in (0,1)\) is associated; so the uniform probability measure corresponds to the special case when \(p_R = 1/2\) for every \(R\). The main result is that every noncritical \(L_{\omega,P}\)-formula is almost everywhere equivalent (in finite structures) to a quantifier-free formula. A corollary of this is that the noncritical fragment of \(L_{\omega,P}\) satisfies a 0-1 law. The main result and its corollary generalize in several ways results of V. V. Knyazev [“Zero-one law for an extension of first-order predicate language”, Cybernetics 26, No. 2, 292–296 (1990); translation from Kibernetika 1990, No. 2, 110–113 (1990; Zbl 0752.03021)]. Very roughly explained, a formula \(\varphi\) is noncritical if every occurrence of \(\exists^{\geq r} \bar{y}\) in \(\varphi\) is subject to the condition that \(r\) must not be the limit (as the size of the universe \(n\to\infty\)) of the proportion of tuples which satisfy \(\psi(\bar{y},\bar{c})\) for some subformula \(\psi\) in the scope of \(\exists^{\geq r} \bar{y}\) and some choice of \(\bar{c}\) in the structure in which truth is evaluated. In the last three sections, the main result and its corollary (the 0-1 law) are generalized in three ways. First, to classes of finite structures which are defined by parametric sentences. Second, to the context of infinitary logic with probability quantifiers and only finitely many variables in each formula. And third, to the situation with probability quantifiers of the form \(\exists^{\geq r(n)}\), where \(r: \mathbb{N} \to (0,1)\) is a function. The definition of a noncritical formula has to be adapted slightly to each of these contexts.


03C13 Model theory of finite structures
03C10 Quantifier elimination, model completeness, and related topics
03C80 Logic with extra quantifiers and operators


Zbl 0752.03021
Full Text: DOI Link


[1] Finite model theory (1999)
[2] Probabilities on finite models 41 pp 17– (1976)
[3] Model theory (1990)
[4] DOI: 10.1090/S0894-0347-1988-0924703-8
[5] Combinatorial theory pp 276– (1982)
[6] Journal of the American Mathematical Society 4 pp 451– (1991)
[7] DOI: 10.1016/0890-5401(92)90021-7 · Zbl 0762.03016
[8] Kibernetika pp 110– (1990)
[9] DOI: 10.1093/logcom/13.2.273 · Zbl 1041.03026
[10] Logic colloquium ’76 (1977)
[11] DOI: 10.1002/rsa.1016 · Zbl 0996.03023
[12] DOI: 10.2307/421173 · Zbl 0869.03019
[13] Cybernetics 5 pp 142– (1969) · Zbl 0978.01027
[14] DOI: 10.1016/0304-3975(93)90218-I · Zbl 0788.03037
[15] Proceedings of the tenth annual IEEE symposium on Logic in Computer Science pp 54– (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.