ALMOST EVERYWHERE ELIMINATION OF PROBABILITY QUANTIFIERS

H. JEROME KEISLER AND WAFIK BOULOS LOTFALLAH

Abstract. We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like ∃^{≥3/4}y, which says that “for at least 3/4 of all y”. These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are:

1. We deal with the quantifier ∃^{≥r}y, where y is a tuple of variables.

2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope.

3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities p_{R} for each predicate symbol R.

4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs).

5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers.

6. We allow each p_{R}, as well as each r in the probability quantifier (∃^{≥r}y), to depend on the size of the universe.

§1. Introduction. The 0–1 law is said to hold for a logic if for each sentence φ of the logic, the probability that a model with universe n = {0, …, n − 1} satisfies φ approaches either 0 or 1 as n tends to infinity. One of the nicest theorems in finite model theory is the 0–1 law for first order logic, proved by Glebskii et. al. [6] and independently by Fagin [4].

More recently, 0–1 laws have been obtained for more powerful logics such as the infinitary logic L_{∞ω}^{k} with only k variables. Kolaitis and Vardi [12], [7] proved the following almost everywhere quantifier elimination theorem.

For each k, there is a class of finite models C_{k} of asymptotic measure 1 on which any infinitary formula in L_{∞ω}^{k} is equivalent to a quantifier-free first order formula with the same free variables.

If one allows the quantifier-free always true sentence T, the 0–1 law for infinitary sentences in L_{∞ω}^{k} becomes a special case of the a.e. quantifier elimination theorem. In fact, the latter theorem explains the 0–1 law in a way that answers Fagin’s question “What really causes there to be a 0–1 law?” [5].

The unbiased measure on the set of models with universe n, which is the measure in which each model has the same probability, is obtained by giving each atomic sentence the independent probability 1/2. It is well-known that the proof of the above 0–1 laws, as well as the almost everywhere quantifier elimination theorem, still goes through when the unbiased measure is replaced by the measure μ_{n} on the models with universe n which is obtained by giving each atomic sentence involving a predicate symbol R an independent probability p_{R} ∈ (0, 1).

In this paper we will prove analogous results for an extension of first order logic, introduced by the first author in [10], that allows the use of probability quantifiers like ∃^{≥3/4}y, which means “for at least 3/4 of all y”.

We will use the following convention on tuples of variables. When we write a formula in the form φ(x, y), it will be understood that x and y are tuples of variables with no repeats and no variables in common, and that the set of free variables of φ is equal to the set of variables which occur in either x or y.

In [11], Knyazev proved a 0–1 law for the fragment of this logic over the unbiased measure, but with three restrictions on the probability quantifier (∃^{≥r}y)φ(x, y):

• The probability quantifiers are simple, i.e. |y| = 1.

• The probability quantifiers are closed, i.e. y occurs in all atomic subformulas of the quantifier scope.

• The probability quantifiers are noncritical, i.e. r ≠ lim_{n} μ_{n}(φ). We prove here a 0–1 law and an almost everywhere quantifier elimination theorem for the larger fragment obtained by removing the simplicity and the closedness restrictions. With different probabilities on quantifiers, it is natural to also allow different probabilities on atomic formulas. For this reason we replace the unbiased measure by the more general measure μ_{n} described above. This enables us to exhibit the interplay between the atomic probabilities p_{R} and the probability quantifiers.

Basic concepts and results are introduced in Section 2. In Section 3, we define the noncritical fragment of the finitary logic with probability quantifiers. We prove our main results in Section 4. In Section 5 we extend our main results to parametric classes of finite models, which include the classes of bipartite graphs, undirected graphs, and oriented graphs. In Section 6 our main results are extended to infinitary logics with probability quantifiers. As in the case of ordinary quantifiers, one must restrict attention to formulas with finitely many variables. In the case of probability quantifiers, another restriction is also needed, to formulas in which only finitely many different values occur in the probability quantifiers. Finally, in Section 7 we extend our results to logics in which the atomic probabilities p_{R}(n) and the quantifier probabilities r(n) depend on the universe size n.

§2. Basic Definitions and Background Results. Let ℕ be the set of positive natural numbers. Fix a vocabulary ν which is a nonempty finite set of relation symbols, and consider only ν-formulas and finite ν-models. As usual when considering 0–1 laws, the vocabulary has only predicate symbols, no function symbols. For each predicate symbol R ∈ ν, fix a probability p_{R} ∈ (0, 1). For each n ∈ ℕ, let M_{n} be the (finite) set of models with universe n = {0, …, n − 1}, and let μ_{n} be the probability measure on M_{n} which is generated by independent atomic probabilities p_{R}. That is, if R ∈ ν is a predicate symbol of arity k, then for each k-tuple a of elements of n, the event

{A ∈ M_{n}: A ⊧ R(a)}

has probability p_{R}, and these events are mutually independent. Thus, the unbiased measure is generated by p_{R} = 1/2 for all R ∈ ν. Let M = ⋃_{n} M_{n} be the class of all finite models. For a class

C ⊆ M, μ_{n}(C) will denote the probability μ_{n}(C ∩ M_{n}). We say that the class C has asymptotic measure r if lim_{n} μ_{n}(C) = r. We define the probability of a sentence φ by μ_{n}(φ) = μ_{n}(C) where C is the class of all finite models of φ, and we say that φ has asymptotic measure r if the class of all finite models of φ has asymptotic measure r.

We also define probabilities of formulas. Let φ(x) be a formula and let k = |x|. Given n ∈ ℕ and a tuple of constants a ∈ n^{k}, the sentence φ(a) has the probability

μ_{n}(φ(a)) = μ_{n}{A ∈ M_{n}: A ⊧ φ(a)}.

The probability of the formula φ(x) is obtained by choosing each a with probability 1/n^{k}, so that

μ_{n}(φ(x)) = ∑{μ_{n}(φ(a))/n^{k}: a ∈ {0, …, n − 1}^{k}}.

In the case that the formula φ(x) is a sentence, this definition of μ_{n}(φ) coincides with the definition in the preceding paragraph.

The classical 0–1 law states that every first order sentence φ has asymptotic measure 0 or 1. We will write

φ(x) a.e.

if the sentence ∀x φ(x) has asymptotic measure 1. We say that two formulas φ(x) and ψ(x) are equivalent almost everywhere, written

φ(x) ≡ ψ(x) a.e.

if the sentence (∀x)(φ(x) ↔ ψ(x)) has asymptotic measure 1. If the sentence (∀x)(φ(x) ↔ ψ(x)) holds in all finite models, we write

φ(x) ≡ ψ(x)

(without the a.e.).

Following [7], we say that a logic L reduces to a logic L′ weakly almost everywhere (in symbols L ≤_{w.a.e.} L′) if every formula φ(x) in L is equivalent almost everywhere to a formula φ′(x) in L′. We say that L reduces to L′ almost everywhere (written L ≤_{a.e.} L′) if there is a class of models C ⊆ M of asymptotic measure 1 such that, for every φ(x) ∈ L, there is a φ′(x) ∈ L′, with

C ⊧ ∀x(φ(x) ↔ φ′(x)).

Thus L ≤_{a.e.} L′ implies L ≤_{w.a.e.} L′. We say that L admits (weak) almost everywhere quantifier elimination if L reduces to its quantifierfree fragment (weakly) almost everywhere.

Let L_{ωω} (L_{ω0}) be the set of first order (quantifier-free) formulas, let L_{ωω}^{k} (L_{ω0}^{k}) be the fragment that uses only k variables. We allow L_{ω0}^{0} to include the two quantifier-free sentences T and F, denoting the always true and always false sentences respectively. Let L_{∞ω} be the infinitary logic, where we allow infinite conjunction and disjunction, let L_{∞ω}^{k} be the fragment of L_{∞ω} that uses only k variables, and let L_{∞ω}^{ω} = ⋃_{k} L_{∞ω}^{k}.

It is known that the 0–1 law for first order logic (or even the infinitary logic with finitely many variables) come as an easy corollary from the following theorem [6, 12]^{1}.

Theorem 2.1. For the unbiased measure, first order logic with k variables admits almost everywhere quantifier elimination, that is,

L_{ωω}^{k} ≤_{a.e.} L_{ω0}^{k}.

1Theorem 2.1 was essentially proved in [6], though not explicitly mentioned

In other words, for each k, there is a class C_{k} of asymptotic measure 1, such that for every formula φ(x) in L_{ωω}^{k}, there is a quantifier-free formula θ(x) in L_{ω0}^{k} such that

C_{k} ⊧ (∀x)(φ(x) ⟷ θ(x)).
⊣

An easy induction can lift this result to the infinitary logic with k variables. Also, taking x to be empty, the theorem says that each first order sentence with k variables collapses to T or F almost everywhere, leading to the 0–1 law. Thus we get:

Corollary 2.2. 1. L_{∞ω}^{k} ≤_{a.e.} L_{ω0}^{k}.

2. L_{∞ω}^{ω} ≤_{w.a.e.} L_{ω0}.

3. The 0–1 law holds for the infinitary logic L_{∞ω}^{ω}.

⊣

We point out, however, that it is not true that L_{∞ω}^{ω} ≤_{a.e.} L_{ω0}, or even L_{ωω} ≤_{a.e.} L_{ω0}. To see this, note that there is no class C ⊆ M of asymptotic measure 1 such that, for every first order sentence φ, either C ⊧ φ ↔ T, or C ⊧ φ ↔ F. For example, the first order sentence stating that the model is of size ≥ n is equivalent to T almost everywhere but only on the class of models of size ≥ n.

§3. Logic with Probability Quantifiers. The probability logic L_{ωP}, introduced in [10], is the first order logic augmented with all probability quantifiers of the forms (∃^{≥r}y) where r ∈ (0, 1). To avoid exceptional cases, we do not allow the quantifiers (∃^{≥0}y) and (∃^{≥1}y). We thus have the usual formation rules for first order logic, and the following additional formation rule:

If φ(x, y) is a formula with (x, y) being a list of syntactically distinct variables, then (∃^{≥r}y)φ(x, y) is a formula for each r ∈ (0, 1), with bound variables y. The semantical interpretation of the formula (∃^{≥r}y)φ(x, y) is:

Let k = |x|, ℓ = |y|, A ∈ M_{n} be a finite model with universe A of size n, and a ∈ A^{k} be a k-tuple of elements of A. Then:

A ⊧ (∃^{≥r}y)φ(a, y) iff \frac{|\{b ∈ A^{ℓ} : A ⊧ φ(a, b)\}|}{n^{ℓ}} ≥ r.

Thus, (∃^{≥r}y)φ(x, y) says that the fraction of the tuples y in the model that satisfy the formula φ(x, y) is ≥ r.

If we further allow infinitary conjunctions we get the infinitary counterpart L_{∞P}, which is also introduced in [10].

It is clear that the formula

(∃^{≥r}y)φ(x, y) → (∃^{≥s}y)φ(x, y)

is valid whenever r > s, and that

(∃^{≥r}y)φ(x, y) → ¬(∃^{≥s}y)¬φ(x, y)

is valid whenever r + s > 1.

As usual, the universal and existential quantifiers are formally applied to single variables. ∀y means ∀y_{1}, … ∀y_{k}, and similarly for ∃y. Note that for each formula φ(x, y) and each r ∈ (0, 1), the formulas

∀y φ(x, y) → (∃^{≥r}y)φ(x, y)

and

(∃^{≥r}y)φ(x, y) → ∃y φ(x, y)

are valid.

The goals of this paper are to exhibit the interplay between the predicate probabilities p_{R} and the quantifier probabilities r, and to obtain almost everywhere quantifier elimination as well as 0–1 laws.

The papers [2], [8], and [9] gave some conditions on a set of generalized quantifiers Q that lead to a 0–1 law for the logic L_{ωω}(Q). Those conditions are not fulfilled even for the single quantifier ∃^{≥1/2}. In fact, the 0–1 law fails here even for the unbiased measure (p_{R} = 1/2 for each R ∈ ν). An easy counterexample is the sentence (∃^{≥1/2}x)R(x) (in the simple unary vocabulary {R}), which has an asymptotic probability \frac{1}{2}.

If we further allow binary predicates we lose even the convergence property, as seen in the following:

Proposition 3.1. If the underlying vocabulary contains a binary predicate, then L_{ωP} does not have a convergence law for the unbiased measure.

Proof. Let R be a binary predicate. Consider the sentence

φ = (∃x) [(∃^{≥1/2}y)R(x, y) ∧ (∃^{≥1/2}y)¬R(x, y)] .

Since φ can be read as (∃x)(∃^{=1/2}y)R(x, y), one can see that if n is odd then μ_{n}(φ) = 0. However, to show that lim_{n} μ_{2n}(φ) = 1, we use independence to get

1 − μ_{2n}(φ) = [1 − \binom{2n}{n} (1/2)^{2n}]^{2n}

Then, using Stirling’s Formula, we get an asymptotic upper bound of the right hand side of the form exp(−cn) for some positive constant c. ⊣

To avoid these examples, Knyazev [11] considered a fragment of L_{ωP} with the following restrictions on the measure μ_{n} and the probability quantifier (∃^{≥r}y)φ(x, y): A. μ_{n} is taken to be unbiased. B. The quantifier (∃^{≥r}y) is simple, i.e. |y| = 1. C. The quantifier (∃^{≥r}y) is closed, i.e. y occurs in all atomic sub-

formulas of φ(x, y). D. The quantifier is non-critical, i.e. r ≠ lim_{n} μ_{n}(φ(x, y)). He then proved that the restricted fragment satisfies the 0–1 law for the unbiased measure.

In this section we will remove the first three restrictions A–C, and in the next section we will prove that the resulting fragment admits weak almost everywhere quantifier elimination, as well as a 0–1 law.

For formulas φ(x, y) which satisfy A–C, Knyazev defined the critical value of φ as the limit lim_{n} μ_{n}(φ(x, y)). The critical value of a formula plays a crucial role in the study of probability quantifiers on finite structures. In the absence of restrictions A–C, the notion of a critical value will take a more general form, and will be defined formally in Definitions 3.4 and 3.6. Heuristically, a critical value of a formula φ(x, y) is a value r such that the formula (∃^{≥r}y)φ(x, y) threatens to violate the 0–1 law. To get an idea of where we are headed, we make some preliminary observations.

First, a critical value of a formula may depend on the variable we want to quantify over, so we will need to introduce the notion of a y-critical value of a formula for each tuple y of free variables. For example, for the unbiased measure, the formula

R_{1}(x) ∧ R_{1}(y) ∧ R_{2}(y)

should have the x-critical value 1/2 and the y-critical value 1/4, (i.e. if we quantify over one of these variables using the corresponding critical value for r, we may end up with a sentence that does not have an asymptotic measure 0 or 1).

Moreover, a formula may have more than one y-critical value for some variable y. For example, for the unbiased measure, one can check that the formula

(R_{1}(x) ∧ R_{1}(y)) ∨ (R_{1}(x) ∧ R_{2}(x) ∧ ¬R_{1}(y))

should have both the x-critical values 1/2 and 1/4.

To define the set of y-critical values of a complicated formula φ, we will first need to reduce φ to an almost everywhere equivalent quantifier-free formula φ^{0}, which we will call the quantifier-free content of φ. We can then define the critical values of φ to be those of φ^{0}.

In our formal definition, the y-critical values of a quantifier-free formula α(x, y) will be sensitive to the choice of the variable string y, as well as to the equalities that hold between the variables in the string x. We will simultaneously define, by induction on complexity of formulas, the property of a formula being noncritical and the quantifier-free content of a formula.

To prepare the way, we first compute the asymptotic probabilities of some formulas built from equalities. Given an equivalence relation E on the set {1, .., k} of indices of the (syntactically) distinct variables x = (x_{1}, .., x_{k}), we define the formula D_{E}(x) which says that x_{i} = x_{j} exactly when (i, j) ∈ E, i.e.

D_{E}(x) := ⋀_{(i,j)∈E}(x_{i} = x_{j}) ∧ ⋀_{(i,j)∉E}(x_{i} ≠ x_{j}).

We use D(x) to denote D_{E}(x) when E is the equality, i.e.

D(x) := ⋀_{i≠j}(x_{i} ≠ x_{j}).

Thus D(x) says that the elements of x are pairwise distinct. We define the tuple x_{E} = (x_{E(1)}, …, x_{E(k)}), where E(i) denotes the equivalence class of i.

Thus x_{E} is a renaming of the variables x, where variables are identified iff their indices belong to the same equivalence class. Intuitively we assume an interpretation of x and y that respects the equivalence relation E but otherwise gives distinct values to distinct variables.

We define D_{E}(x_{E}) to be the formula that says that x_{E(i)} ≠ x_{E(j)} whenever (i, j) ∉ E.

For example, if E is the equivalence relation on {1, 2, 3} with equivalence classes {1, 3} and {2}, then

(x_{1}, x_{2}, x_{3})_{E} = (x_{{1,3}}, x_{{2}}, x_{{1,3}}),

D_{E}(x) is equivalent to x_{1} = x_{3} ∧ x_{1} ≠ x_{2}, and D_{E}(x_{E}) is equivalent to x_{{1,3}} ≠ x_{{2}}.

For each equivalence relation E on {1, …, k}, D_{E}(x_{E}) is a conjunction of fewer than k^{2} inequalities, so μ_{n}(¬D_{E}(x_{E})) < k^{2}/n, and therefore

lim_{n→∞} μ_{n}(D_{E}(x_{E})) = 1.

It follows as a special case that lim_{n→∞} μ_{n}(D(x)) = 1. Moreover, if E is an equivalence relation but is not the equality relation, then lim_{n→∞} μ_{n}(D_{E}(x)) = 0.

By a literal we mean an atomic or negated atomic formula.

We now define the notion of a quantifier-free type. Given k ≥ 1 and a k-tuple of variables x, a quantifier-free type β(x) is a maximal consistent conjunction of literals in the variables x. Since the vocabulary ν is finite, each quantifier-free type β(x) is a finite conjunction of literals, and hence is a first order quantifier-free formula. Moreover, the set of all quantifier-free types in x is also finite.

For each quantifier-free type β(x), the relation E on {1, …, k} defined by

E = {(i, j): β(x) ⊧ x_{i} = x_{j}}

is an equivalence relation, which we call the equivalence relation induced by β(x).

Note that if β(x) induces E, then β(x) logically implies D_{E}(x), and β(x_{E}) logically implies D_{E}(x_{E}).

Lemma 3.2. Let β(x) be a quantifier-free type and let E be the equivalence relation induced by β(x). Then lim_{n→∞} μ_{n}(β(x_{E})) exists and is greater than 0.

Proof. β(x_{E}) is equivalent to the conjunction

D_{E}(x_{E}) ∧ ⋀_{i=1}^{m} θ_{i}

where each θ_{i} is either of the form R(z) or of the form ¬R(z). Let p = ∏_{i=1}^{m} p_{i} where

p_{i} = \{ \begin{matrix}p_{R} & if & θ_{i} is of the form R(z) \\ 1 − p_{R} & if & θ_{i} is of the form ¬R(z). \end{matrix}

We have m > 0 and p > 0. By the definition of μ_{n}, for each ktuple a of constants such that D_{E}(a) holds, we have μ_{n}(β(a_{E})) = p. Therefore

p · μ_{n}(D_{E}(x_{E})) ≤ μ_{n}(β(x_{E})) ≤ p + μ_{n}(¬D_{E}(x_{E})).

Since lim_{n→∞} μ_{n}(D_{E}(x_{E})) = 1, it follows that

lim_{n→∞} μ_{n}(β(x_{E})) = p.

⊣

Note that for each quantifier-free type β(x) we have μ_{n}(β(x)) > 0 for all n ≥ |x|, so we can introduce the conditional probability of a formula given β(x) in the natural way.

For a formula φ(x, y) and a quantifier-free type β(x), and for each n ≥ |x|, we define the μ_{n} conditional probability of φ(x, y) given β(x) as

μ_{n}[φ(x, y)|β(x)] = \frac{μ_{n}(φ(x, y) ∧ β(x))}{μ_{n}(β(x))}.

In the next lemma we show that the conditional probability of a quantifier-free formula given a quantifier-free type converges as n → ∞. The proof gives a formula for the limit.

Lemma 3.3. Let α(x, y) be a quantifier-free formula and let β(x) be a quantifier-free type. Then lim_{n→∞} μ_{n}[α(x, y)|β(x)] exists.

Proof. Let E be the equivalence relation induced by β(x). Then β(x_{E}) is a quantifier-free type in x_{E}, and

μ_{n}[α(x_{E}, y)|β(x_{E})] = \frac{μ_{n}(α(x_{E}, y) ∧ β(x_{E}))}{μ_{n}(β(x_{E}))}.

We note that β(x_{E}) implies D_{E}(x_{E}), and for each k-tuple a of constants such that D_{E}(a) holds, we have

α(a, y) ≡ α(a_{E}, y), β(a) ≡ β(a_{E}).

Therefore

μ_{n}[α(x, y)|β(x)] = μ_{n}[α(x_{E}, y)|β(x_{E})].

We may assume that each atomic subformula of α(x_{E}, y) contains a variable in y, since each atomic subformula which contains only variables in x_{E} can be replaced by T if it follows from β(x_{E}), and by F otherwise. Starting from α(x_{E}, y), form the equality-free formula α_{E} by replacing each equality between distinct variables by F, and replacing each equality between the same variable by T.

Now expand α_{E} into the full disjunctive normal form without equality:

α_{E} ≡ ⋁_{i=1}^{m} ⋀_{j=1}^{l} θ_{ij},

where each conjunction corresponds to a row in the truth table representation of α_{E}.

We claim that

lim_{n→∞}(μ_{n}[α(x, y)|β(x)]) = ∑_{i=1}^{m} ∏_{j=1}^{l} p_{ij} = p_{β},

where p_{β} is defined by the above equation, and

p_{ij} = \{ \begin{matrix}p_{R} & if & θ_{ij} is of the form R(z) \\ 1 − p_{R} & if & θ_{ij} is of the form ¬R(z). \end{matrix}

By convention, p_{β} = 0 if α_{E} ≡ F, and p_{β} = 1 if α_{E} ≡ T.

We now prove the claim. For each tuple (a_{E}, b) of distinct elements of n, the sentences α(a_{E}, b) ∧ β(a_{E}) and α_{E}(a_{E}, b) ∧ β(a_{E}) are equivalent in all models A ∈ M_{n}, and the sentence α_{E}(a_{E}, b) has probability

μ_{n}(α_{E}(a_{E}, b)) = p_{β}.

Since distinct atomic sentences have independent probabilities,

μ_{n}(α_{E}(a_{E}, b)) = \frac{μ_{n}(α_{E}(a_{E}, b) ∧ β(a_{E}))}{μ_{n}(β(a_{E}))}.

Therefore the conditional probability μ_{n}[α(x, y)|β(x)] differs from p_{β} by at most the probability q(n) that the elements of (x_{E}, y) are not all distinct. But q(n) ≤ (|x| + |y|)^{2}/n, so lim_{n→∞} q(n) = 0 and the claim follows. ⊣

The above lemma lets us make the following definition.

Definition 3.4. Let α(x, y) be a quantifier-free formula. For each quantifier-free type β(x), we define

μ[α(x, y)|β(x)] = lim_{n→∞} μ_{n}[α(x, y)|β(x)].

The y-critical values of α(x, y) are the values μ[α(x, y)|β(x)] where β(x) is a quantifier-free type.

Proposition 3.5. Every quantifier-free formula has finitely many y-critical values for each tuple of variables y. Moreover, each ycritical value is equal to a polynomial in p_{R}, R ∈ ν, with integer coefficients. In particular, if each probability p_{R} is a rational number, then each y-critical value of a quantifier-free formula is a rational number.

Proof. This follows easily from the proof of Lemma 3.3. ⊣

We now give our main definition, which simultaneously defines the set of noncritical formulas of L_{∞P} and the quantifier-free content φ^{0} of a formula φ. The limits mentioned in this definition exist by Lemma 3.3.

Definition 3.6. Let φ be a formula in the infinitary logic L_{∞P} with only finitely many free variables.

1. If φ is quantifier-free, we stipulate that φ is noncritical and that φ^{0} is φ itself.

2. If φ = ¬ψ, then φ is noncritical if and only if ψ is noncritical, and we define φ^{0} = ¬(ψ^{0}).

3. If φ = ⋀_{i} ψ_{i}, then φ is noncritical if and only if ψ_{i} is noncritical for each i, and we define φ^{0} = ⋀_{i}((ψ_{i})^{0}).

4. If φ(x) = ∃y ψ(x, y), then φ is noncritical if and only if ψ is noncritical, and we define

φ^{0}(x) = ⋁{β(x): μ[ψ^{0}(x, y)|β(x)] > 0} ∨ ⋁_{i<|x|} ψ^{0}(x, x_{i}).

5. If φ(x) = (∃^{≥r}y)ψ(x, y), then φ is noncritical if and only if ψ is noncritical and r is not a y-critical value for ψ^{0}, and we define

φ^{0}(x) = ⋁{β(x): μ[ψ^{0}(x, y)|β(x)] > r}.

The noncritical fragment L_{ωP}^{−} is defined as the set of all noncritical formulas of L_{ωP}. The noncritical fragment L_{∞P}^{−} is defined as the set of all noncritical formulas of L_{∞P} with only finitely many free variables.

Warning: The noncritical fragment L_{ωP}^{−} and the quantifier-free content function φ ↦ φ^{0} depend on the given atomic formula probabilities p_{R}, R ∈ ν.

Note that in the special case when ψ(x, y) is noncritical and

μ[ψ^{0}(x, y)|β(x)] = 0 for all β(x),

the formula (∃^{≥r}y)ψ(x, y) is also noncritical and has quantifier-free content F.

On the other hand, if ψ(x, y) is noncritical and

μ[ψ^{0}(x, y)|β(x)] = 1 for all β(x),

the formula (∃^{≥r}y)ψ(x, y) is also noncritical and has quantifier-free content T.

The language L_{ωP} has uncountably many formulas because there are uncountably many probability quantifiers. But if we restrict the language to formulas with rational probability quantifiers, then the set of formulas is countable. We now observe that if each atomic probability p_{R}, R ∈ ν is also rational, the set of critical formulas and the quantifier-free content are computable.

Proposition 3.7. Suppose that p_{R} is a rational number for each R ∈ ν. Call a formula φ ∈ L_{ωP} rational if for every probability quantifier (∃^{≥r}y) in φ, r is a rational number, and let L_{ωℚ} be the set of rational formulas of L_{ωP}. Then each of the following is primitive recursive:

1. The relation “α is quantifier-free and r is a y-critical value of α”.

2. The set L_{ωℚ} ∩ L_{ωP}^{−} of rational noncritical formulas.

3. The quantifier-free content function φ ↦ φ^{0} restricted to L_{ωℚ} ∩ L_{ωP}^{−}.

Proof. The proof of Lemma 3.3 gives a primitive recursive algorithm for computing the y-critical values of a quantifier-free formula, establishing (1 ). Parts (2 ) and (3 ) follow easily from Part (1 ) and Definition 3.6. ⊣

§4. Elimination of Probability Quantifiers. In this section we prove our main result, which shows that each noncritical formula φ is almost everywhere equivalent to its quantifier-free content φ^{0}. As we mentioned in the introduction, it is well-known that the proof of Theorem 2.1 goes through for the measure μ_{n} instead of the unbiased measure, so that every first order formula is almost everywhere equivalent to a quantifier-free formula. In fact, from that proof one can easily see that every first order formula is almost everywhere equivalent to its quantifier-free content as defined in Definition 3.6. We will not repeat that proof here, but we will need the following special case of the result.

Lemma 4.1. For each quantifier-free first order formula ψ(x, y), ∃y ψ(x, y) is almost everywhere equivalent to its quantifier-free content (∃y ψ(x, y))^{0}. ⊣

The formula below for the conditional probability of the negation is easily checked.

Lemma 4.2. For any quantifier-free formula φ(x, y) and quantifierfree type β(x), we have

μ[¬φ(x, y)|β(x)] = 1 − μ[φ(x, y)|β(x)].
⊣

We next observe that every quantifier-free first order formula can be represented in the following normal form. We omit the proof, which is routine.

Lemma 4.3. Each quantifier-free first order formula φ(x, y) can be represented in the normal form

φ(x, y) ≡ ⋁_{i=1}^{h}(α_{i}(x, y) ∧ β_{i}(x)),

where the β_{i}(x) are quantifier-free types in x, and each atomic subformula of each α_{i}(x, y) contains a variable from y. This representation is unique up to renumbering and logical equivalence. ⊣

The next lemma gives the asymptotic probabilities of the formulas α_{i}(x, y).

Lemma 4.4. Let α(x, y) be a first order quantifier-free formula in which every atomic subformula contains a variable from y. Let β(x) be a quantifier-free type and let E be the equivalence relation induced by β(x). Then

lim_{n→∞} μ_{n}(α(x_{E}, y)) = μ[α(x, y)|β(x)].

Proof. Since

μ[α(x, y)|β(x)] = μ[α(x_{E}, y)|β(x_{E})],

and β(x_{E}) is a quantifier-free type which implies u ≠ v for every pair of syntactically distinct variables u, v in the tuple x_{E}, we may assume that E is the equality relation. By hypothesis, α(x, y) and β(x) have no atomic subformulas in common. Therefore for any constants a and b which have no elements in common, we have

μ_{n}(α(a, b) ∧ β(a)) = μ_{n}(α(a, b)) · μ_{n}(β(a)).

Let q(n) be the probability that some element of y equals some element of x. Then

|μ_{n}(α(x, y) ∧ β(x)) − μ_{n}(α(x, y)) · μ_{n}(β(x))| ≤ q(n),
|μ_{n}[α(x, y)|β(x)] − μ_{n}(α(x, y))| ≤ q(n)/μ_{n}(β(x)).

We have q(n) ≤ |x| · |y|/n, so lim_{n→∞} q(n) = 0. The result now follows form Lemmas 3.2 and 3.3 by taking the limit as n → ∞. ⊣

The next lemma is implicit in the paper [11]. For completeness we give a proof here.

Lemma 4.5. Let ψ(x, y) be a first order quantifier-free formula such that y appears in every atomic subformula. Let

L = lim_{n→∞} μ_{n}(ψ(x, y))

(which exists by Lemma 4.4). Then 1. If r < L, then D(x) → (∃^{≥r}y)ψ(x, y) a.e.

2. If r > L, then D(x) → ¬(∃^{≥r}y)ψ(x, y) a.e.

Proof. Let β(x) be a quantifier-free type which induces the equality relation. By Lemma 4.4, L = μ[ψ(x, y)|β(x)]. As in the proof of Lemma 3.3, we can compute L by starting from ψ(x, y), forming the equality-free formula α(x, y) by replacing each equality between distinct variables by F, and replacing each equality between the same variable by T, and putting α into the full disjunctive normal form without equality:

α ≡ ⋁_{i=1}^{m} ⋀_{j=1}^{l} θ_{ij}.

We have

L = ∑_{i=1}^{m} ∏_{j=1}^{l} p_{ij},

where

p_{ij} = \{ \begin{matrix}p_{R} & if & θ_{ij} is of the form R(z) \\ 1 − p_{R} & if & θ_{ij} is of the form ¬R(z). \end{matrix}

It follows from the theory of independent Bernoulli trials that for each real ε > 0 there exist c > 0 and N ∈ ℕ such that for each n ≥ N and each tuple of distinct constants a ∈ n^{|x|},

μ_{n} (|\frac{|\{y ∈ n: ψ(a, y)\}|}{n} − L| > ε) ≤ e^{−cn}.

But lim_{n→∞} n^{|x|}e^{−cn} = 0. Thus for each ε > 0 we have

lim_{n→∞} μ_{n} (∀x (D(x) → (∃^{≥L−ε}y)ψ(x, y))) = 1,

so (1 ) holds. Similarly,

lim_{n→∞} μ_{n} (∀x (D(x) → ¬(∃^{≥L+ε}y)ψ(x, y))) = 1,

and (2 ) follows. ⊣

Lemma 4.5 deals with the simple case, where the probability quantifier is on a single variable y. To handle the general case, we prove a stronger lemma, which almost everywhere eliminates the quantifiers (∃^{≥r}y).

Lemma 4.6. Let ψ(x, y) be a first order quantifier-free formula, in which each atomic subformula contains at least one of the variables in y. Let L = lim_{n→∞} μ_{n}(ψ(x, y)). Then

1. If r < L, then D(x) → (∃^{≥r}y)ψ(x, y) a.e.

2. If r > L, then D(x) → ¬(∃^{≥r}y)ψ(x, y) a.e.

Proof. By induction on |y|. Basis: (|y| = 1) This is Lemma 4.5.

Induction Step: (Assume the result for |y| and quantify over y, z) For (1 ), we assume that r < L, and put ψ(x, y, z) in the full disjunctive normal form, so that the disjuncts are exclusive. We’ll show by an example that if (1 ) is proved for the exclusive disjuncts, it will then follow that it holds for the full disjunction.

Say ψ(x, y, z) = ψ_{1}(x, y, z) ∨ ψ_{2}(x, y, z), where ψ_{1}(x, y, z) and ψ_{2}(x, y, z) are exclusive and may or may not contain z. Thus we have that L = L_{1} + L_{2} where L_{1} = lim_{n→∞} μ_{n}(ψ_{1}(x, y, z)), and L_{2} = lim_{n→∞} μ_{n}(ψ_{2}(x, y, z)).

Since L−r = L_{1}+L_{2}−r > 0, we can find r_{1}, r_{2} such that r = r_{1}+r_{2}, 0 < r_{1} < L_{1}, and 0 < r_{2} < L_{2}.

Now it is readily seen that the implication

(∃^{≥r_{1}}yz)ψ_{1}(x, y, z) ∧ (∃^{≥r_{2}}yz)ψ_{2}(x, y, z) → (∃^{≥r}yz)ψ(x, y, z)

is logically valid.

Thus, if both

D(x) → (∃^{≥r_{1}}yz)ψ_{1}(x, y, z) a.e.

and

D(x) → (∃^{≥r_{2}}yz)ψ_{2}(x, y, z) a.e. ,

then

D(x) → (∃^{≥r}yz)ψ(x, y, z) a.e.

So it is enough to prove (1 ) for the disjuncts, i.e. without loss of generality we assume that ψ(x, y, z) is a conjunction of literals.

Let’s write it as:

ψ(x, y, z) = ⋀_{i=1}^{m} α_{i}(x, y, z) ∧ ⋀_{i=1}^{k} β_{i}(x, y),

where z appears in each α_{i}(x, y, z).

From the form of ψ(x, y, z) we can see that L = ∏_{j=1}^{m+k} p_{j} for suitable values of p_{j}, j = 1, …, m + k. Since r < L, we can again find r_{1} and r_{2} such that r = r_{1}r_{2}, ∏_{j=1}^{m} p_{j} > r_{1} > 0 and ∏_{j=m+1}^{m+k} p_{j} > r_{2} > 0.

Now one can check that the implication

(∃^{≥r_{2}}y) (D(y) → (∃^{≥r_{1}}z)ψ(x, y, z)) ⟶ (∃^{≥r}yz)ψ(x, y, z)

is valid almost everywhere. Thus, we just need to prove that

D(x) → (∃^{≥r_{2}}y) (D(y) → (∃^{≥r_{1}}z)ψ(x, y, z)) a.e.

But we have that:

D(y) → (∃^{≥r_{1}}z)ψ(x, y, z)
= D(y) → (∃^{≥r_{1}}z) (⋀_{i=1}^{m} α_{i}(x, y, z) ∧ ⋀_{i=1}^{k} β_{i}(x, y))

≡ D(y) → (((∃^{≥r_{1}}z) ⋀_{i=1}^{m} α_{i}(x, y, z)) ∧ ⋀_{i=1}^{k} β_{i}(x, y))

≡  D(y) → ⋀_{i=1}^{k} β_{i}(x, y) a.e. ,

where in the last a.e. equivalence we used Lemma 4.5, which states that

D(y) → (∃^{≥r_{1}}z) ⋀_{i=1}^{m} α_{i}(x, y, z) a.e. ,

since

lim_{n→∞} μ_{n} (⋀_{i=1}^{m} α_{i}(x, y, z)) = ∏_{j=1}^{m} p_{j} > r_{1}.

Now, since

lim_{n→∞} μ_{n} (⋀_{i=1}^{m} β_{i}(x, y)) = ∏_{j=m+1}^{m+k} p_{j} > r_{2},

we can use the induction hypothesis to get:

D(x) → (∃^{≥r_{2}}y) ⋀_{i=1}^{k} β_{i}(x, y) a.e.

Thus, we get

D(x) → (∃^{≥r_{2}}y) (D(y) → (∃^{≥r_{1}}z)ψ(x, y, z)) a.e. ,

which completes the proof of (1 ).

For (2 ), we assume that r > L, or equivalently, 1 − r < 1 − L. By Lemma 4.2, 1−L is the y-critical value of ¬ψ(x, y, z). Choose s such that 1 − r < s < 1 − L. Applying (1 ) to the formula ¬ψ(x, y, z), we see that

D(x) → (∃^{≥s}yz)¬ψ(x, y, z) a.e.

We have r + s > 1, and it follows that

D(x) → ¬(∃^{≥r}yz)ψ(x, y, z) a.e. ,

and we conclude that (2 ) holds. ⊣

This removes Restriction B (quantifier simplicity). As an easy corollary we have:

Lemma 4.7. Let ψ(x, y) be a first order quantifier-free formula, in which each atomic subformula contains at least one of the variables in y. Let E be an equivalence relation on the indices of x, and let L = lim_{n→∞} μ_{n}(ψ(x_{E}, y)). Then

1. If r < L, then D_{E}(x) → (∃^{≥r}y)ψ(x, y) a.e.

2. If r > L, then D_{E}(x) → ¬(∃^{≥r}y)ψ(x, y) a.e.

⊣

We now deal with general quantifier-free formulas. The following lemma allows us to remove Restriction C (quantifier closedness).

Lemma 4.8. Let ψ(x, y) be a first order quantifier-free formula. and assume that r ∈ (0, 1) is not a y-critical value for ψ. Then

(∃^{≥r}y)ψ(x, y) ≡ ((∃^{≥r}y)ψ(x, y))^{0} a.e.

That is, (∃^{≥r}y)ψ(x, y) is almost everywhere equivalent to its quantifierfree content.

Proof. We first write ψ in the normal form of Lemma 4.3:

ψ(x, y) ≡ ⋁_{i=1}^{m}(α_{i}(x, y) ∧ β_{i}(x)).

For each i, we have β_{i}(x) → D_{E}(x) where E is the equivalence relation induced by β_{i}(x). Therefore by Lemma 4.7, whenever r < μ[α_{i}(x, y)|β_{i}(x)], we have

β_{i}(x) → (∃^{≥r}y)α_{i}(x, y) a.e. ,

and hence

β_{i}(x) ≡ (∃^{≥r}y)α_{i}(x, y) ∧ β_{i}(x) a.e.

On the other hand, when r > μ[α_{i}(x, y)|β_{i}(x)], we have

β_{i}(x) → ¬(∃^{≥r}y)α_{i}(x, y) a.e. ,

and hence

F ≡ (∃^{≥r}y)α_{i}(x, y) ∧ β_{i}(x) a.e.

Since each β_{i}(x) is a quantifier-free type, for each i we have

ψ(x, y) ∧ β_{i}(x) ≡ α_{i}(x, y) ∧ β_{i}(x),

so

μ[ψ(x, y)|β_{i}(x)] = μ[α_{i}(x, y)|β_{i}(x)].

It follows that

(∃^{≥r}y)ψ(x, y) ≡ (∃^{≥r}y) ⋁_{i=1}^{m} (α_{i}(x, y) ∧ β_{i}(x))

≡ ⋁_{i=1}^{m} ((∃^{≥r}y)α_{i}(x, y) ∧ β_{i}(x))
≡ ⋁{β_{i}(x): r < μ[α_{i}(x, y))|β_{i}(x)]} a.e.
= ⋁{β_{i}(x): r < μ[ψ(x, y))|β_{i}(x)]}
= ((∃^{≥r}y)ψ(x, y))^{0} .
⊣

Using this lemma, we obtain our main result, which extends Theorem 2.1 to the probability logic L_{ωP}^{−}.

Theorem 4.9. Every formula φ in L_{ωP}^{−} is a.e. equivalent to its quantifier-free content.

Proof. By induction on the complexity of φ. The basis step is trivial, and the induction steps for connectives are easy.

For the induction step for existential quantifiers, we let φ(x) = ∃y ψ(x, y) where ψ(x, y) is noncritical, and assume the inductive hypothesis that ψ(x, y) is a.e. equivalent to ψ^{0}(x, y). Then φ(x) is a.e. equivalent to ∃y ψ^{0}(x, y). By definition, φ(x) has the same quantifier-free content as ∃y ψ^{0}(x, y), and by Lemma 4.1, ∃y ψ^{0}(x, y) is a.e. equivalent to its quantifier-free content, so φ(x) is a.e. equivalent to its quantifier-free content.

It remains to give the induction step for probability quantifiers. For this step, we let φ(x) be a noncritical formula of the form (∃^{≥r}y)ψ(x, y), assume the induction hypothesis that ψ(x, y) is a.e. equivalent to ψ^{0}(x, y), and use Lemma 4.8 to get:

φ(x) = (∃^{≥r}y)ψ(x, y) ≡ (∃^{≥r}y)ψ^{0}(x, y) ≡ ((∃^{≥r}y)ψ^{0}(x, y))^{0} a.e.

⊣

Corollary 4.10. 1. L_{ωP}^{−} ≤_{w.a.e.} L_{ω0}.

2. The 0–1 law holds for the logic L_{ωP}^{−}.

Proof. Part 1 is a corollary of Theorem 4.9, and part 2 follows because the quantifier-free content of a sentence must be T or F. ⊣

We conclude this section with a discussion of almost everywhere reducibility for fragments of L_{ωP}^{−}. For k ∈ ℕ, let L_{ωP}^{k−} be the set of formulas of L_{ωP}^{−} with at most k variables. For each finite subset P_{0} ⊆ (0, 1), let L_{ωP_{0}}^{k−} be the set of formulas of L_{ωP}^{k−} with probability quantifiers only from P_{0}. Thus L_{ωP} is the union of the fragments L_{ωP_{0}}^{k−} over all k ∈ ℕ and all finite P_{0} ⊆ (0, 1).

We observe that L_{ωP}^{1−} ≤_{a.e.} L_{ω0} does not hold. To see this, suppose that L_{ωP}^{1−} ≤_{a.e.} L_{ω0} holds for the unbiased measure, and R ∈ ν is a unary relation. Then there is a set C of finite models of asymptotic measure 1 such that for each A ∈ C and n ∈ ℕ we have A ⊧ (∃^{≥(1/2−1/n)}y)R(y). But then each A ∈ C satisfies A ⊧ (∃^{≥1/2}y)R(y), which contradicts the fact that (∃^{≥1/2}y)R(y) has asymptotic probability 1/2.

Theorem 4.11. For each k ∈ ℕ and finite set P_{0} ⊆ (0, 1) we have L_{ωP_{0}}^{k−} ≤_{a.e.} L_{ω0}.

Proof. Let F be the set of all formulas φ(x) in L_{ωP_{0}}^{k−} such that for some quantifier-free formula α, either

φ(x) = ∃yα(x, y)

or

φ(x) = (∃^{≥r}y)α(x, y)

for some r ∈ P_{0}. Since k and P_{0} are finite, the set F is finite. By Theorem 4.9 and the fact that finite intersections of sets of asymptotic measure 1 have asymptotic measure 1, there is a set of finite structures C of asymptotic measure 1 such that for each formula φ(x) ∈ F and each A ∈ C,

A ⊧ ∀x (φ(x) ↔ φ^{0}(x)) .

Now let S be the set of all formulas ψ(x) ∈ L_{ωP_{0}}^{k−} such that

A ⊧ ∀x (ψ(x) ↔ ψ^{0}(x))

for all A ∈ C. Then every quantifier-free formula belongs to S, and also F ⊆ S. An easy induction on the complexity of formulas will show that every formula of ψ(x) ∈ L_{ωP_{0}}^{k−} belongs to S.

The probability quantifier step of this induction is as follows. Suppose that ψ(x, y) ∈ S and φ(x) = (∃^{≥r}y)ψ(x, y) is noncritical. Then φ^{0}(x) = ((∃^{≥r}y)ψ^{0}(x, y))^{0}. Let A ∈ C. Since ψ(x, y) ∈ S we have

A ⊧ ∀x∀y (ψ(x, y) ↔ ψ^{0}(x, y)) ,

and hence

A ⊧ ∀x ((∃^{≥r}y)ψ(x, y) ↔ (∃^{≥r}y)ψ^{0}(x, y)) .

Since (∃^{≥r}y)ψ^{0}(x, y) ∈ F ⊆ S, we have

A ⊧ ∀x ((∃^{≥r}y)ψ^{0}(x, y) ↔ φ^{0}(x)) .

Therefore

A ⊧ ∀x (φ(x) ↔ φ^{0}(x)) ,

that is, φ(x) ∈ S. The other steps of the induction are similar. ⊣

§5. Parametric Classes. In [14], W. Oberschelp showed that the first order 0–1 law holds for the class of all finite models of certain universal first order sentences, called parametric sentences (see also [3], Section 4.2). In this section we get similar generalizations of the almost everywhere quantifier elimination theorem and the 0–1 law for the probability logic L_{ωP}^{−}.

Definition 5.1. A first order sentence π is said to be parametric if it is a finite conjunction of sentences of the form ∀x[D(x) → τ(x)] where τ(x) is a Boolean combination of literals τ_{1}, …, τ_{k} such that each element of x occurs at least once in each τ_{i}. The class of finite models of a parametric sentence is called a parametric class.

For example, the class of all bipartite graphs, and the class of all oriented graphs, are parametric. The class of all models in which certain relations are symmetric and irreflexive is also parametric. In particular, the class of all undirected graphs is parametric.

If k is the maximum arity of the relations in ν, then any parametric sentence which has a model of cardinality ≥ k has models of all cardinalities.

We assume throughout this section that π is a parametric formula

⋀_{i=1}^{k} ∀z_{i}[D(z_{i}) → τ_{i}(z_{i})]

which has models in all finite cardinalities. For any n and formula φ(x), we define

(μ_{n}|π)(φ(x)) = \frac{μ_{n}(φ(x) ∧ π)}{μ_{n}(π)}.

Since π has models of all finite cardinalities, (μ_{n}|π) is a probability measure on the class of all models with universe n.

All of the notions and results in Sections 3 and 4 will carry over to the class of finite models of π with the measure (μ_{n}|π) in place of μ_{n}. Instead of considering all quantifier-free types β(x), we consider only the quantifier-free types which are consistent with π. We will define the π-noncritical fragments of L_{ωP} and L_{∞P}, denoted by L_{ωP}^{−} (π) and L_{∞P}^{−} (π). The following lemma lets us compute (μ_{n}|π)(φ(x)) from μ_{n}(φ(x)), and to pass to the limit as n → ∞

Lemma 5.2. For each k and each n ≥ k, there is a constant c_{n,k} ≥ 1 such that for each k-tuple of distinct variables x:

(i) For every quantifier-free type β(x) which is consistent with π and induces the identity relation on x,

(μ_{n}|π)(β(x)) = μ_{n}(β(x)) · c_{n,k}.

(ii) lim_{n→∞} c_{n,k} exists.

Proof. Let y be a tuple of distinct variables such that x ∩ y = ∅ and |x ∪ y| = n. Let θ(x, y) be the conjunction of D(x, y) and all instances τ_{i}(z_{i}) of parts of π where z_{i} is a subsequence of x, y that contains at least one variable from y. Let a, b be sequences of distinct elements of n of length |a| = |x| and |b| = |y| such that a ∪ b = n. Using the hypothesis that π is a parametric sentence, we note that in any model A ∈ M_{n}, for each quantifier-free type β(x), β(a)∧π is equivalent to β(a)∧θ(a, b). Since each atomic subformula of θ is either an inequality in D(x, y) or contains a variable in y, β(x) is independent of θ(x, y). Let c_{n,k} = μ_{n}(θ(x, y))/μ_{n}(π). It is clear that c_{n,k} depends only on n and k (and π), and not on the k-tuple of variables x.

(i) We have c_{n,k} ≥ 1, and for any quantifier-free type β(x) consistent with π we have

μ_{n}(β(a) ∧ π) = μ_{n}(β(a)) · μ_{n}(θ(a, b)) = μ_{n}(β(a)) · μ_{n}(π) · c_{n,k}.

Therefore

μ_{n}(β(x) ∧ π) = μ_{n}(β(x)) · μ_{n}(π) · c_{n,k},

and (i) follows.

(ii) Let B be the set of all quantifier-free types β(x) such that β(x) induces the identity relation on x and is consistent with π. Let ψ(x) be the conjunction of D(x) and all instances τ_{i}(x_{i}) of parts of π where x_{i} is a subsequence of x. Then

\frac{1}{c_{n,k}} = \frac{μ_{n}(π)}{μ_{n}(θ(x, y))} = \frac{μ_{n}(θ(x, y) ∧ ψ(x))}{μ_{n}(θ(x, y))} = μ_{n}(ψ(x)|θ(x, y))

= μ_{n}(ψ(x)) = ∑{μ_{n}(β(x)) : β ∈ B}.

By Lemma 3.2, the limit of the right side exists and is > 0, so (ii) holds. ⊣

The analogue of Lemma 3.2 is:

Lemma 5.3. Let β(x) be a quantifier-free type which is consistent with π and let E be the equivalence relation induced by β(x). Then

lim_{n→∞}(μ_{n}|π)(β(x_{E}))

exists and is greater than 0.

Proof. By Lemmas 3.2 and 5.2. ⊣

The conditional probability (μ_{n}|π)[α(x, y)|β(x)] is then defined in the obvious way when β(x) is consistent with π. We have the following analogue of Lemma 3.3:

Lemma 5.4. Let α(x, y) be a quantifier-free formula and let β(x) be a quantifier-free type consistent with π. Then

lim_{n→∞}(μ_{n}|π)[α(x, y)|β(x)]

exists.

Proof. By Lemmas 3.2, 3.3, and 5.2. ⊣ This lemma lets us make the following definition.

Definition 5.5. Let α(x, y) be a quantifier-free formula. For each quantifier-free type β(x) which is consistent with π, we define

(μ|π)[α(x, y)|β(x)] = lim_{n→∞}(μ_{n}|π)[α(x, y)|β(x)].

The π, y-critical values of α(x, y) are the values (μ|π)[α(x, y)|β(x)] where β(x) is a quantifier-free type consistent with π.

We can now define the π-quantifier-free content φ^{π} of φ and the π-noncritical fragments of L_{ωP} and L_{∞P} by a small modification of Definition 3.6.

Definition 5.6. Let φ be a formula in the infinitary logic L_{∞P} with only finitely many free variables.

1. If φ is quantifier-free, we stipulate that φ is π-noncritical and that φ^{π} is φ itself.

2. If φ = ¬ψ, then φ is π-noncritical if and only if ψ is π-noncritical, and we define φ^{π} = ¬(ψ^{π}).

3. If φ = ⋀_{i} ψ_{i}, then φ is π-noncritical if and only if ψ_{i} is πnoncritical for each i, and we define φ^{π} = ⋀_{i}((ψ_{i})^{π}).

4. If φ(x) = ∃y ψ(x, y), then φ is π-noncritical if and only if ψ is π-noncritical, and we define

φ^{π}(x) = ⋁{β(x): (μ|π)[ψ^{π}(x, y)|β(x)] > 0} ∨ ⋁_{i<|x|} ψ^{π}(x, x_{i}).

5. If φ(x) = (∃^{≥r}y)ψ(x, y), then φ is π-noncritical if and only if ψ is π-noncritical and r is not a π, y-critical value for ψ^{π}, and we define

φ^{π}(x) = ⋁{β(x): (μ|π)[ψ^{π}(x, y)|β(x)] > r}.

The π-noncritical fragment L_{ωP}^{−} (π) is defined as the set of all πnoncritical formulas of L_{ωP}. The π-noncritical fragment L_{∞P}^{−} (π) is defined as the set of all π-noncritical formulas of L_{∞P} with only finitely many free variables. Two formulas φ(x), ψ(x) of L_{ωP}^{−} (π) are said to be a.e.(π)-equivalent if

lim_{n→∞}(μ_{n}|π)(∀x[φ(x) ↔ ψ(x)]) = 1.

The following analogue of Theorem 4.9 is obtained by a routine modification of its proof, using Lemma 5.2.

Theorem 5.7. Every formula φ in L_{ωP}^{−} (π) is a.e.(π)-equivalent to its π-quantifier-free content.

Corollary 5.8. The 0–1 law holds for the logic L_{ωP}^{−} (π) with respect to the measures (μ_{n}|π).

§6. Infinitary Logic. We continue to work with a finite vocabulary ν, and an underlying atomic probability p_{R} for each predicate symbol R ∈ ν.

We first note that the 0–1 law fails for the infinitary probability logic L_{∞P}, even if we limit the number of variables used and allow only noncritical formulas. For example, let R be a unary predicate symbol in ν, and for each natural n define the sentence

φ_{n} = (∃^{≥(1/2−1/n)}x)R(x).

Then φ_{n} is a noncritical sentence in L_{ωP}^{−}, which has asymptotic measure 0, but one can easily check that

⋁_{n} φ_{n} ≡ (∃^{≥1/2}x)R(x)

which has asymptotic measure 1/2.

If we allow binary predicates then we can imitate the example given in Proposition 3.1 to get a nonconvergent sentence. However, if we allow only finitely many values of r to occur in quantifiers ∃^{≥r} within a single infinitary formula, then we get both an almost everywhere quantifier elimination as well as a 0–1 law.

Thus, for each k ∈ ℕ and each finite P_{0} ⊆ (0, 1) let’s define L_{∞P_{0}}^{k−} to be the set of formulas of L_{∞P}^{−} (where we allow infinitary conjunctions and disjunctions) with at most k variables and with probability quantifiers only from P_{0}.

Then we have

Theorem 6.1. Let k ∈ ℕ and let P_{0} ⊆ (0, 1) be finite.

1. L_{∞P_{0}}^{k−} ≤_{a.e.} L_{ω0}^{k},

2. Every formula of L_{∞P_{0}}^{k−} is a.e. equivalent to its quantifier-free content.

Proof. The proof is the same as the proof of Theorem 4.11, but with infinitely many formulas at the conjunction step of the induction. ⊣

Define L_{∞P}^{ω−} to be the union of L_{∞P_{0}}^{k−} for all k ∈ ℕ and all finite P_{0} ⊆ (0, 1). Thus each particular formula of L_{∞P}^{ω−} has only finitely many variables and finitely many distinct probabilities occurring in quantifiers.

Corollary 6.2. 1. L_{∞P}^{ω−} ≤_{w.a.e.} L_{ω0}.

2. The 0–1 law holds for the logic L_{∞P}^{ω−}.

⊣

We note that the probability logics L_{∞P_{0}}^{k−} and L_{∞P}^{ω−} correspond to the logics L_{∞ω}^{k} and L_{∞ω}^{ω} respectively. For each noncritical formula φ of L_{∞P}^{ω−}, the quantifier-free content φ^{0} is a first order quantifier-free formula, so by Proposition 3.5 it has finitely many y-critical values, each of which is equal to a polynomial in p_{R}, R ∈ ν with integer coefficients.

§7. Logic with Probability Functions. In this section we treat the case where the atomic probabilities p_{R}(n) and quantifier probabilities (∃^{≥r(n)}y) are allowed to depend on the universe size n. L_{ωP (n)} will be first order logic augmented by the probability quantifiers (∃^{≥r(n)}y) where r(n) ∈ (0, 1) for each n ∈ ℕ, and L_{∞P (n)} will be the corresponding extension of the infinitary logic L_{∞ω}.

The dependency of the ratio r(n) on n puts the quantifiers (∃^{≥r(n)}y) in correspondence with the general monotone numerical quantifier (Q^{f}y), which says that the number of tuples y in a model of size n is ≥ f(n). Here, r(n) = f(n)/n^{ℓ}, when ℓ = |y|.

The ordinary existential quantifier ∃y has the same semantic interpretation as the probability quantifier (∃^{≥1/n}y), but our definitions of a noncritical formula and quantifier-free content will differ for these two quantifiers. (It will be easier for ∃yφ(x, y) to be noncritical than for (∃^{≥1/n}y)φ(x, y) to be noncritical).

For the usual infinitary logic L_{∞ω}^{k} with k variables and ordinary existential quantifiers, the proofs of the 0–1 law as well as the almost everywhere quantifier elimination theorem go through when the independent atomic probabilities p_{R}(n) vary with n, as long as they are bounded away from 0 and 1.

If p_{R}(n) → 0 or 1 as n → ∞, the 0–1 law may not hold, as shown in [15] and [13], where one can find a nearly complete characterization of those p_{R}(n) for which the 0–1 law holds.

As the atomic probabilities change with n, y-critical values also change with n, and will now be called y-critical sequences. One difficulty we face is that the analogue of Lemma 3.3 will fail, that is, the conditional probability μ_{n}[α(x, y)|β(x)] of a quantifier-free formula given a quantifier-free type need not converge.

In the present setting, we define a y-critical sequence as follows.

Definition 7.1. Let α(x, y) be a quantifier-free first order formula. A sequence r(n) is y-critical for α(x, y) if for some quantifierfree type β(x) we have

1. lim inf(μ_{n}[α(x, y)|β(x)] − r(n)) ≤ 0 and

2. lim inf(r(n) − μ_{n}[α(x, y)|β(x)]) ≤ 0.

The simultaneous definition of the noncritical fragment and the quantifier-free content now takes the following form.

Definition 7.2. Let φ be a formula in the infinitary logic L_{∞P (n)} with only finitely many free variables.

1. If φ is quantifier-free, we stipulate that φ is noncritical and that φ^{0} is φ itself.

2. If φ = ¬ψ, then φ is noncritical if and only if ψ is noncritical, and we define φ^{0} = ¬(ψ^{0}).

3. If φ = ⋀_{i} ψ_{i}, then φ is noncritical if and only if ψ_{i} is noncritical for each i, and we define φ^{0} = ⋀_{i}((ψ_{i})^{0}).

4. If φ(x) = ∃y ψ(x, y), then φ is noncritical if and only if ψ is noncritical and for each quantifier-free type β(x), either

lim inf μ_{n}[ψ^{0}(x, y)|β(x)] > 0

or

⊧ ∀x (β(x) → ⋁_{i<|x|} ψ^{0}(x, x_{i})) ,

and we define

φ^{0}(x) = ⋁{β(x): lim inf μ_{n}[ψ^{0}(x, y)|β(x)] > 0} ∨ ⋁_{i<|x|} ψ^{0}(x, x_{i}).

5. If φ(x) = (∃^{≥r(n)}y)ψ(x, y), then φ is noncritical if and only if ψ is noncritical and r(n) is not a y-critical sequence for ψ^{0}, and we define

φ^{0}(x) = ⋁{β(x): lim inf(μ_{n}[ψ^{0}(x, y)|β(x)] − r(n)) > 0}.

The noncritical fragment L_{ωP (n)}^{−} is defined as the set of all noncritical formulas of L_{ωP (n)}. The noncritical fragment L_{∞P (n)}^{−} is defined as the set of all noncritical formulas of L_{∞P (n)} with only finitely many free variables.

For each k ∈ ℕ and finite set P_{0} of sequences r(n) ∈ (0, 1) we define L_{∞P_{0}(n)}^{k−} to be the set of formulas in L_{∞P (n)}^{−} with at most k free variables and with probability quantifiers only from P_{0}. We let L_{∞P (n)}^{ω−} be the union of L_{∞P_{0}(n)}^{k−} over all k ∈ ℕ and all finite P_{0}.

With this definition, our earlier proofs go through, and we have the following theorem.

Theorem 7.3. Let k ∈ ℕ and let P_{0} be a finite set of sequences of elements of (0, 1).

1. L_{∞P_{0}(n)}^{k−} ≤_{a.e.} L_{ω0}^{k}.

2. Every formula φ ∈ L_{∞P_{0}(n)}^{k−} is a.e. equivalent to its quantifierfree content.

⊣

Corollary 7.4. 1. L_{∞P (n)}^{ω−} ≤_{w.a.e.} L_{ω0}.

2. The 0–1 law holds for the logic L_{∞P (n)}^{ω−}.

⊣

REFERENCES

[1] C.C. Chang and H.J. Keisler, Model Theory, North Holland Elsevier 1990.

[2] A. Dawar and E. Grädel, Generalized quantifiers and 0–1 laws, in Proceedings of the Tenth Annual IEEE Symposium on Logic in Computer Science, 1995, pp. 54-64.

[3] H-D. Ebbinghaus and J. Flum, Finite Model Theory, Second Edition, Springer-Verlag 1999.

[4] R. Fagin, Probabilities on finite models, The Journal of Symbolic Logic, 1976, vol. 41, pp. 17-21.

[5] R. Fagin, Finite model theory - a personal perspective, Theoretical Computer Science, 1993, vol. 116, pp. 3-31.

[6] Y.V. Glebskii, D.I. Kogan, M.I. Liogonki and V.A. Talanov, Range and degree of realizability of formulas in the restricted predicate calculus, Cybernetics, 1969, vol. 5, pp. 142-154.

[7] L. Hella, P.G. Kolaitis and K. Luosto, Almost everywhere equivalence of logics in finite model theory, The Bulletin of Symbolic Logic, 1996, vol. 2, no. 4, pp. 422-443.

[8] R. Kaila, On probabilistic elimination of generalized quantifiers, Random Structures and Algorithms, 2001, vol. 19, no. 1, pp. 1-36.

[9] R. Kaila, On Almost Sure Elimination of Numerical Quantifiers, Journal of Logic and Computation, 2003, vol. 13, no. 2, pp. 273-285.

[10] H.J. Keisler, Hyperfinite model theory, in Gandy and Hyland, eds., Logic Symposium ’76, North Holland, 1977.

[11] V.V. Knyazev, Zero-One law for an extension of first-order predicate language, Kibernetika, March-April 1990, No. 2, pp. 110–113.

[12] P.G. Kolaitis and M.Y. Vardi, Infinitary logics and 0–1 laws, Information and Computation, 1992, vol. 98, pp. 258-294, special issue: selections from the fifth annual IEEE symposium on logic in computer science.

[13] T. Luczak and J. Spencer, When does the zero-one law hold, Journal of the American Mathematical Society, 1991, vol. 4, no. 3, pp. 451-468.

[14] W. Oberschelp. Asymptotic 0–1 laws in combinatorics. In D. Jungnickel (ed.), Combinatorial Theory, Lecture Notes in Mathematics 969, pp. 276-292. Springer, 1982.

[15] S. Shelah and J. Spencer, Zero-one laws for sparse random graphs, Journal of the American Mathematical Society, 1988, vol. 1, pp. 97-115.

DEPARTMENT OF MATHEMATICS, UNIVERSITY OF WISCONSIN

480 LINCOLN DRIVE, MADISON WI 53706

E-mail: keisler@math.wisc.edu

DEPARTMENT OF MATHEMATICS, THE GERMAN UNIVERSITY IN CAIRO,

ON LEAVE FROM

THE DEPARTMENT OF ENGINEERING MATHEMATICS, FACULTY OF ENGINEERING, CAIRO UNIVERSITY.

E-mail: wafik.lotfallah@guc.edu.eg