Randomizing a Model

H. Jerome Keisler University of Wisconsin, Madison WI keisler@math.wisc.edu

Abstract A randomization of a first order structure M is a new structure with certain closure properties whose universe is a set K of “random elements” of M. Randomizations assign probabilities to sentences of the language of M with new constants from K. Our main theorem shows that all randomizations of M are models of the same first order theory T, which has a nice set of axioms and admits elimination of quantifiers. Moreover, the class of substructures of models of T is characterized by a natural set V of universal axioms of T, so that T is the model completion of V.

1 Introduction

A common theme in mathematics is to start with a first order structure M, and introduce a new structure K which has a set K of “random elements” of M as a universe and which assigns probabilities to sentences of the language of M with new constants from K. There are several ways to do this; three well-known examples will be given in this introduction, and many others will be given in Section 4. The aim of this paper is to show that all such structures K are very much alike in the same way that all real closed ordered fields are very much alike. We will see that they are all models of the same complete first order theory T, and this theory admits elimination of quantifiers. But before giving the axioms, or even the vocabulary, of T, we will motivate the theory by presenting the examples.

Each of the three examples will depend on a first order structure M with vocabulary L(M) whose universe M has more than one element, a complete atomless countably additive probability space (Ω, B, P), and a set K of functions from Ω into M. Moreover, in each example, B will be the set of all sets (called events) of the form

{w ∈ Ω : M ⊧ ψ(X⃗(w))}

where ψ(x⃗) is a formula of L(M) and X⃗ is in K. The three examples will have different universe sets K.

Example 1 (Boolean power). Let K_{1} be the the set of all functions X : Ω → M such that the range of X is countable and X^{−1}{m} ∈ B for each m ∈ M.

The Boolean power construction is a generalization of the ultrapower construction (see [DM]).

Example 2 (Bounded Boolean power). Let K_{2} be the set of all X ∈ K_{1} such that X has finite range.

See [BN] for a discussion of bounded versus ordinary Boolean powers.

Example 3 (All measurable functions). Suppose that M has a Polish topology T , and that each formula of L(M) defines a Borel relation in M with respect to T . Now let K_{3} be the set of all (B, T )-measurable functions from Ω into M.

Example 3 appears implicitly in the literature on probability theory (e.g. see [EK]), except that the assumption that every formula defines a Borel relation is rather strong. An important case where that assumption holds in when M is the ordered field of real numbers, or more generally an o-minimal structure on the real line.

Each of these examples gives rise to a structure K_{i} for a first order language L with variables of three sorts K, B, and R, called the sorts of random elements, events, and scalars. L has a function symbol P (for probability) of sort B → R, and a function symbol [[φ(⋯)]] (the event mapping) of sort K^{n} → B for each formula φ(x⃗) of L(M) with n free variables. The structure of sort R is the ordered field R of real numbers. Interpret the equality relation on K_{i} by almost sure equality with respect to P. Similarly, interpret the equality relation on B by almost sure equality. The event mapping [[⋯]] is interpreted by the rule

[[ψ(X⃗)]] = {w ∈ Ω : M ⊧ ψ(X⃗(w))}

for each formula ψ(x⃗) of L(M) and tuple X⃗ in K_{i}.

(In Section 4 we will adopt the usual trick to get structures with ordinary equality. The universe of sort K will be the set K̄_{i} of equivalence classes of elements of K_{i} under the almost sure equality relation P [X(w) = Y (w)] = 1, and similarly the universe of sort B will be the measure algebra B̄ whose elements are equivalence classes of sets in B under almost sure equality.)

We can now describe the randomization theory T (for M with scalar part R). The language L is the vocabulary of T. The axioms of T say that B is a Boolean algebra, R is a real closed ordered field, [[⋯]] preserves Boolean operations, P is a finitely additive probability measure, and:

Transfer for M: [[ψ]] = ⊤ for each ψ ∈ T h(M) Maximal Principle: ∀X⃗∃Y ([[φ(X⃗, Y)]] = [[∃yφ(X⃗, y)]]) [[⋯]] is onto B: ∀A∃X∃Y ([[X = Y]] = A) P is Atomless: {P [B] : B ⊆ A} = {r : 0 ≤ r ≤ P [A]}

Main Theorem For each M, the randomization theory T is complete and admits elimination of quantifiers.

The structures K_{1} and K_{2} of Examples 1 and 2 are clearly models of T. We will see in Section 4 that the structure K_{3} of Example 3 is also a model of T. It follows from the Main Theorem that K_{2} is an elementary submodel of K_{1}, and K_{3} is an elementary extension of K_{1}.

The models of T will be called randomizations of M. Let L(K, M) be the vocabulary formed by adding a new constant symbol to L(M) for each element of K. Any randomization of M will determine a probability measure P on the set of sentences L(K, M); the sentence ψ(X⃗) gets probability P ([[ψ(X⃗)]]). Probability measures on sets of sentences were studied in a model-theoretic setting by Gaifman in [G] and Scott and Krauss in [SK].

In the paper [SK] the idea of developing probability theory by assigning probabilities to sentences is suggested as an alternative to the classical Kolmogorov approach using a probability space (Ω, B, P). In the present work, we maintain a flexible position and take advantage of both approaches. The notion of a randomization follows the formula approach, but the examples of randomizations are built using the Kolmogorov approach. Moreover, as we will see in Section 4, the Kolmogorov approach can readily be modified to construct models of the first order theory T which are only finitely additive.

Examples 1 and 2 above can be simplified by using the measure algebras directly, without a sample set Ω (e.g. see [BN], [S], [DM]). The paper [DM] gives an alternative approach to Example 3 as a completion of the Boolean power.

In Section 2 we will formally list the axioms of the randomization theory T. In Section 3 we will prove our main quantifier elimination and completeness result. In Section 4 we will expand our list of examples to include a variety of constructions which only require finitely additive probability measures. In Section 5 we look at the subtheory S of T which has all the axioms of T except the Transfer Axioms for M.

Quantifier elimination still holds for S. Example 3 gives a model of S even without the assumption that every definable subset of M is Borel. We will show that S is the theory of all “simple randomizations” which are obtained by a construction like Example 2 above but with finitely many different M’s.

In Section 6 we prove that a natural subset U of the set of axioms for S characterizes the universal consequences of S. This shows that S is the model completion of U. In the last section we obtain parallel results for the three simpler languages obtained by removing one of the three sorts from L.

For background material in model theory, see [CK], and for background material in measure theory see [H].

This work was supported in part by the National Science Foundation and the Vilas Trust Fund.

2 The Randomization Theory for M

In this section we will formally introduce the first order theory of randomizations which will be our main object of study. As a starting point we fix a complete theory T h(M) in a vocabulary L(M) such that

T h(M) ⊢ ∃x∃y(x ≠ y),

and a complete theory T h(R) (for the “scalars”) in a vocabulary L(R). The reader can, if (s)he wishes, take T h(R) to be the theory of the ordered field of real numbers, that is, the theory of real closed ordered fields. We will work in a slightly more general setting. Throughout this paper we assume that T h(R) is a complete theory which has the following two properties:

(1) T h(R) contains the theory of the reals with order, addition, and the constants 0, 1 (possibly with additional symbols in its vocabulary), and

(2) T h(R) admits elimination of quantifiers.

For example, T h(R) can be the the theory of the reals with only the symbols ≤ , +, −, 0, 1, the theory of real closed ordered fields (where quantifiers were eliminated by Tarski [Ta]), or the complete theory of the ordered field of reals with symbols for the exponential, logarithm, and restricted analytic functions (see [D], [DMM]).

The randomization language L = L(K, B, R) is the three-sorted first order language described in the introduction. Sort K has “random variables” X, Y, …, sort B has “event variables” A, B, …, and sort R has “scalar variables” r, s, . . ..

The vocabulary of L is as follows:

In each sort: An equality symbol =.

In sort B: Constant symbols ⊥, ⊤ for the Boolean zero and unit, and function symbols ⊔, ⊓, − for the Boolean operations.

In sort R: All symbols of the vocabulary L(R).

In sort K^{n} → B: For each formula φ(x⃗) of L(M) with an n-tuple x⃗ of free variables, a function symbol [[φ(⋯)]].

In sort B → R: A function symbol P.

Terms and formulas are built in the usual way, with quantifiers over variables of all three sorts. L does not have a sort for the elements of the underlying model M. However, bound individual variables of the original language L(M) appear within formulas φ in terms [[φ(⋯)]] of sort B, and will be denoted by x, y, . . .. We shall sometimes use the expression A ⊑ B as an abbreviation for the Boolean inclusion relation A = A ⊓ B.

A structure for the language L will be denoted by a triple (K, B, R), where K is the universe of sort K, and B and R are the reducts of the structure to the other two sorts.

Definition 2.1 The following set T of sentences of L is called the randomization theory (for M with scalar part R). It will depend only on the complete theories T h(M) and T h(R). φ(x⃗), ψ(x⃗), θ(x⃗) denote arbitrary formulas of L(M).

Validity Axioms:

∀X⃗([[ψ(X⃗)]] = ⊤)

where ∀x⃗ψ(x⃗) is logically valid, and

∀X∀Y (X = Y ⇔ [[X = Y]] = ⊤)

Boolean Axioms: The usual Boolean algebra axioms in the language L(B) (including the axiom ⊥ ≠ ⊤), and the sentences

∀X⃗([[¬φ(X⃗)]] = −[[φ(X⃗)]])
∀X⃗([[(φ ∨ ψ)(X⃗)]] = [[φ(X⃗)]] ⊔ [[ψ(X⃗)]])
∀X⃗([[(φ ∧ ψ)(X⃗)]] = [[φ(X⃗)]] ⊓ [[ψ(X⃗)]])

Fullness Axiom (or Maximal Principle):

∀X⃗∃Y ([[φ(X⃗, Y)]] = [[(∃y φ)(X⃗, y)]])

Event Axiom:

∀A∃X∃Y (A = [[X = Y]])

Scalar Axioms: Each sentence of T h(R).

Measure Axioms:

∀A (0 ≤ P [A] ≤ 1)
P [⊤] = 1
∀A∀B (A ⊓ B = ⊥ ⇒ P [A ⊔ B] = P [A] + P [B])
∀A(P [A] = 0 ⇔ A = ⊥)

Atomless Axiom:

∀A∀r[(0 ≤ r ≤ P [A]) ⇒ ∃B(B ⊑ A ∧ P [B] = r)]

Transfer Axioms:

[[φ]] = ⊤, where φ ∈ T h(M).

Notice that variables of sort K occur only in the Validity, Boolean, Fullness, and Event Axioms. Terms of scalar sort R occur only in the Scalar, Measure, and Atomless Axioms.

The Fullness Axiom says that every sentence starting with an existential quantifier has a witness. The Event Axiom says that every element of B occurs as an event. The first three Measure Axioms say that P is a finitely additive probability measure on B, and the fourth Measure Axiom says that P is strictly positive. The Atomless Axiom says that P maps each principal ideal in B onto a closed interval in R. In the case that P is countably additive and R is the field of reals, this axiom is equivalent to the usual notion of an atomless measure.

Because of the Transfer Axiom, each sentence of L(M) has probability 0 or 1. The Fullness, Event, and Atomless Axioms are closure principles saying that certain objects exist in K.

Here are some consequences of T. They are natural alternatives to the Fullness, Event, and Atomless Axioms.

Proposition 2.2 (Witness Principles) For each formula φ(x⃗, y) of L(M), the following two sentences are consequences of T:

(i)

∀X⃗ ∀A (([[∀y⃗ φ(X⃗, y⃗)]] ⊑ A ⊑ [[∃y⃗ φ(X⃗, y⃗)]]) ⇒ ∃Y⃗ [[φ(X⃗, Y⃗)]] = A) .

(ii)

∀X⃗ ∀r ([P ([[∀y⃗ φ(X⃗, y⃗)]]) ≤ r ≤ P ([[∃y⃗ φ(X⃗, y⃗)]])] ⇒ ∃Y⃗ P ([[φ(X⃗, Y⃗)]]) = r) .

Proof: Let K = (K, B, R) be a model of T.

(i) For simplicity we give the proof for a single y rather than a tuple y⃗. Take X⃗ in K and A ∈ B. Suppose X⃗ and A satisfy the hypothesis of (i). By the Event Axiom there are Z, Z′ ∈ K be such that [[Z = Z′]] = A. Then

[[Z ≠ Z′]] ⊑ [[∃y¬φ(X⃗, y)]]

and

[[Z = Z′]] ⊑ [[∃yφ(X⃗, y)]].

Therefore

[[Z ≠ Z′ ⇒ ∃y(Z ≠ Z′ ∧ ¬φ(X⃗, y))]] = ⊤

and

[[Z = Z′ ⇒ ∃y(Z = Z′ ∧ φ(X⃗, y))]] = ⊤.

It follows that

[[∃y(Z = Z′ ⇔ φ(X⃗, y))]] = ⊤.

Let Y ∈ K be a witness for this existential quantifier. Then [[φ(X⃗, Y)]] = A, so (i) holds in K.

(ii) Take X⃗ in K and r ∈ R satisfying the hypothesis of (ii). Let

B = [[∀y⃗ φ(X⃗, y⃗)]], C = [[∃y⃗ φ(X⃗, y⃗)]].

Then B ⊑ C and P [B] ≤ r ≤ P [C], so

0 ≤ r − P [B] ≤ P [C] − P [B] = P [C − B].

By the Atomless Axiom there exists D ∈ B such that

(D ⊑ C − B) ∧ (P [D] = r − P [B]).

Then A = D ⊔ B satisfies the hypothesis of (i) and P [A] = r. By (i) there exists Y ∈ K which satisfies the conclusion of (i) and therefore satisfies the conclusion of (ii). □

Remark. Witness Principle (i) easily implies the Fullness and Event Axioms, and thus is equivalent to the conjunction of these two axioms with respect to the other axioms of T. Witness Principle (ii) is equivalent to the conjunction of the Fullness Axiom and the Atomless Axiom with respect to the other axioms of T. Thus one or both of these principles could have been used in place of other axioms.

The following consequence of the axioms allows one to transfer a statement about deterministic structures to a statement about random structures. Using this result, one can obtain the Boolean value of an arbitrary prenex sentence ψ(X⃗) ∈ L(K, M) in terms of the Boolean values of quantifier-free sentences φ(X⃗, Y⃗).

Proposition 2.3 For each formula φ(x⃗, y⃗) of L(M) and sequence of quantifiers Q⃗y⃗, the following sentences are consequences of T:

(i)

∀X⃗ ([[Q⃗y⃗ φ(X⃗, y⃗)]] = ⊤ ⇔ Q⃗Y⃗ ([[φ(X⃗, Y⃗)]] = ⊤)) .

(ii)

∀X⃗ (P ([[Q⃗y⃗ φ(X⃗, y⃗)]]) = 1 ⇔ Q⃗Y⃗ P ([[φ(X⃗, Y⃗)]]) = 1) .

(i′)

∀X⃗∀A (A ⊑ [[Q⃗y⃗ φ(X⃗, y⃗)]] ⇔ Q⃗Y⃗ (A ⊑ [[φ(X⃗, Y⃗)]])) .

(ii′)

∀X⃗∀r (r ≤ P ([[Q⃗y⃗ φ(X⃗, y⃗)]]) ⇔ Q⃗Y⃗ (r ≤ P ([[φ(X⃗, Y⃗)]]))) .

Proof: Argue by induction on the length of the quantifier string Q⃗y⃗, taking witnesses for ∃y_{i}φ when Q_{i} = ∃ and taking witnesses for ∃y_{i}¬φ when Q_{i} = ∀. □

3 Quantifier Elimination

Throughout this section we will work within an arbitrary model (K, B, R) of T. We shall first prove a series of lemmas and then prove that T admits quantifier elimination. Using quantifier elimination, we will prove that T is complete.

Lemma 3.1 Let A_{1}, …, A_{n} ∈ B be pairwise disjoint, and let X_{1}, …, X_{n} ∈ K. There exists Y ∈ K such that

⋀_{i=1}^{n}(A_{i} ⊑ [[Y = X_{i}]]).

Proof: For each i, let Z_{i}, Z′_{i} be such that [[Z_{i} = Z′_{i}]] = A_{i}. Then

[[∃y( ⋀_{i=1}^{n}(Z_{i} = Z′_{i} ⇒ y = X_{i}))]] = ⊤.

Let Y ∈ K be a witness for the quantifier in the above sentence. Then Y has the required property. □

Lemma 3.2 Let θ_{i}(x, y⃗), i = 1, …, n be a sequence of formulas in L(M) such that

⊢ (θ_{1} ∨ ⋯ ∨ θ_{n})(x, y⃗) and ⊢ ¬(θ_{i} ∧ θ_{j})(x, y⃗) for 1 ≤ i < j ≤ n.

Let A_{1}, …, A_{n} ∈ B and let Y⃗ be a tuple in K. Then the following are equivalent: (i) There exists X ∈ K such that for each i ≤ n,

A_{i} = [[θ_{i}(X, Y⃗)]].

(ii) The events A_{i}, i = 1, …, n form a partition of ⊤ and for each i ≤ n,

[[∀x θ_{i}(x, Y⃗)]] ⊑ A_{i} ⊑ [[∃x θ_{i}(x, Y⃗)]].

Proof: It is clear that (i) implies (ii). This direction requires only the Validity and Boolean Axioms.

Now assume (ii). For each i ≤ n, let X_{i} ∈ K be a witness for ∃x θ_{i}(x, Y⃗). By Lemma 3.1 there exists X ∈ K such that

A_{i} ⊑ [[X = X_{i}]]

for each i ≤ n. We have

A_{i} ⊑ ([[∃x θ_{i}(x, Y⃗)]] ⊓ [[X = X_{i}]]) = ([[θ_{i}(X, Y⃗)]] ⊓ [[X = X_{i}]]) ⊑ [[θ_{i}(X, Y⃗)]].

Since both A_{i}, i ≤ n and [[θ_{i}(X, Y⃗)]], i ≤ n are partitions of ⊤, (i) must hold. □

Definition 3.3 A formula ψ of L is existential if all its quantifiers are existential and occur at the beginning.

Lemma 3.4 For every existential formula ψ in L there is an existential formula θ in L with the same free variables such that T ⊢ ψ ⇔ θ and θ has no quantifiers of sort K.

Proof: It suffices to prove the result in the case that ψ has only one quantifier, which is an existential quantifier of sort K, for one can then prove the lemma by moving an existential quantifier of sort K to the inside and arguing by induction on the number of quantifiers of sort K. Thus ψ has the form

∃X ψ_{1}(X, Y⃗ , A⃗, r⃗)

where ψ_{1} is quantifier-free. The variable X occurs in ψ_{1} in finitely many terms [[φ_{i}(X, Y⃗)]], i ≤ m of sort B. Each φ_{i}(x, y⃗) is a formula of L(M). Let θ_{j}(x, y⃗), j ≤ n, be a list of the conjunctions

(φ′_{1} ∧ ⋯ ∧ φ′_{m})(x, y⃗)

where n = 2^{m} and each φ′_{i} is either φ_{i} or its negation. The formulas θ_{j}(x, y⃗) satisfy the hypotheses of Lemma 3.2. Using the Boolean Axioms, the formula ψ_{1} is equivalent to a quantifier-free formula ψ_{2} in which the variable X occurs only in the terms [[θ_{j}(X, Y⃗)]]. Let ψ_{3} be the quantifier-free formula obtained from ψ_{2} by replacing each term [[θ_{j}(X, Y⃗)]] by a new variable B_{j} of sort B. Then X does not occur in ψ_{3}, and ψ is equivalent to the formula

∃B⃗[∃X( ⋀_{j=1}^{n}(B_{j} = [[θ_{j}(X, Y⃗)]])) ∧ ψ_{3}(Y⃗ , A⃗, B⃗, r⃗)].

By Lemma 3.2, the formula

∃X( ⋀_{j=1}^{n}(B_{j} = [[θ_{j}(X, Y⃗)]]))

is equivalent in T to a quantifier-free formula γ with the same free variables. It follows that ψ is equivalent in T to the existential formula

∃B⃗(γ ∧ ψ_{3})(Y⃗ , A⃗, B⃗, r⃗).

This is the required formula θ.

For future reference, we observe that the direction ψ ⇒ θ required only the Validity and Boolean Axioms. □

Lemma 3.5 For every existential formula ψ in L there is an existential formula θ in L with the same free variables such that T ⊢ ψ ⇔ θ and θ has no quantifiers of sorts K or B.

Proof: we may assume without loss of generality that ψ has the form

∃B ψ_{1}(Y⃗ , A⃗, B, r⃗),

because the proof can then be completed by first applying Lemma 3.4 to eliminate quantifiers of sort K, and then arguing by induction on the number of resulting quantifiers of sort B. The terms of sort B which occur in ψ_{1} belong to a finite Boolean algebra generated by B and finitely many terms α_{1}, …, α_{m} such that T proves that α_{1}, …, α_{m} partition ⊤. Using the Boolean and Measure Axioms, the probability of any term of sort B in ψ_{1} can be expressed as a linear combination of probabilities of terms which do not involve B and the probabilities

P [B ⊓ α_{i}], i ≤ m.

It follows that ψ is equivalent in T to a formula of the form

∃s_{1} ⋯ ∃s_{m}[∃B( ⋀_{i=1}^{m}(s_{i} = P [B ⊓ α_{i}])) ∧ ψ_{2}(Y⃗ , A⃗, r⃗, s⃗)]

where ψ_{2} is quantifier-free. By the Atomless and Boolean Axioms, the formula

θ_{0} = ∃B( ⋀_{i=1}^{m}(s_{i} = P [B ⊓ α_{i}]))

is equivalent in T to the quantifier-free formula

θ_{1} = ⋀_{i=1}^{m}(0 ≤ s_{i} ≤ P [α_{i}])

with the same free variables. It follows that ψ is equivalent in T to the formula

θ(Y⃗ , A⃗, r⃗) = ∃s_{1} ⋯ ∃s_{m}[(θ_{1} ∧ ψ_{2})(Y⃗ , A⃗, r⃗, s⃗)],

which has the required properties. For future reference, note that the direction ψ ⇒ θ required only the Validity, Boolean, and Measure Axioms. □

Theorem 3.6 (Quantifier Elimination) The randomization theory T admits quantifier elimination.

Proof: It suffices to prove that every existential formula ψ in L is equivalent in T to a quantifier-free formula φ with the same free variables. By Lemma 3.5, ψ is equivalent in T to an existential formula

θ = ∃s_{1} ⋯ ∃s_{m}θ_{1}(Y⃗ , A⃗, r⃗, s⃗)

with the same free variables, where θ_{1} is quantifier-free. An equation of the form X = Y between random variables is equivalent in T to the equation P ([[X = Y]]) = 1 between terms of sort R. Similarly, an equation α = β between two terms of sort B is equivalent in T to the equation P [α ↔ β] = 1 between terms of sort R. Therefore θ_{1} is equivalent in T to a formula θ_{2} with the same free variables which is obtained from a quantifier-free formula in L(R) by replacing some variables of sort R by terms of L of sort R. Since T h(R) is contained in the set of axioms of T and admits elimination of quantifiers, it follows that θ is equivalent in T to a quantifier-free formula ϕ with the same free variables.

For future reference, we observe that the direction ϕ ⇒ φ used only the Validity, Boolean, and Measure Axioms and universal consequences of T h(R). □

Corollary 3.7 Suppose T h(M) admits quantifier elimination. Then every formula ψ of L is equivalent in T to a quantifier-free formula θ with the same free variables such that in every term of the form [[φ(X⃗)]] which occurs in θ, φ(x⃗) is an atomic formula of L(M).

Proof: By the Quantifier Elimination Theorem and the hypothesis on T h(M) we may assume that ψ is quantifier-free and in every term [[γ(X⃗)]] occurring in ψ, γ(x⃗) is quantifier-free. By the Boolean axioms, each [[γ(X⃗)]] can be replaced by a finite Boolean combination of terms of the form [[φ(X⃗)]] where φ(x⃗) is atomic. □

Scott and Krauss [SK] used the following notion of a probability assertion in their investigation of probability models. We shall slightly broaden the definition here by allowing a probability assertion to have free variables of sort R as well as sort K, where the definition in [SK] only allowed free variables of sort K.

Definition 3.8 A probability assertion is a formula Φ(X⃗, s⃗) of L obtained from a quantifier-free formula θ(r⃗, s⃗) of L(R) by replacing r⃗ by a tuple of terms of L of the form P ([[φ(X⃗)]]). That is, Φ(X⃗, s⃗) is a quantifier-free formula of L with no variables of sort B, no equality symbols of sort B or K, and no Boolean operation symbols of sort B.

The next corollary shows that for formulas with no free variables of sort B, one can eliminate the Boolean operation symbols and equality as well as the quantifiers.

Corollary 3.9 Let ψ be a formula of L with no free variables of sort B. (i) ψ is equivalent in T to a probability assertion Φ with the same free variables. (ii) If T h(M) admits quantifier elimination, then Φ may be taken so that in every

term P ([[φ(X⃗)]]) occurring in Φ, φ(x⃗) is a finite conjunction of atomic formulas of L(M).

Proof: (i) By the Quantifier Elimination Theorem, ψ is equivalent in T to a quantifier-free formula θ with the same free variables. One can get a probability assertion equivalent in T to θ as follows. First eliminate the Boolean constants ⊤, ⊥ using the Validity Axioms

[[∃x x = x]] = ⊤, [[∃x x ≠ x]] = ⊥.

Then eliminate the Boolean operation symbols using the Boolean Axioms of T. Then eliminate the equality symbols of sorts K and B with the rules

X = Y ⇔ P ([[X = Y]]) = 1,
[[φ]] = [[δ]] ⇔ P ([[φ ⇔ δ]]) = 1.

(ii) By quantifier elimination for T h(M), we may get Φ so that in every P ([[γ(X⃗)]]) occurring in Φ, γ(x⃗) is quantifier-free. Using the Boolean and Measure Axioms, each P ([[γ(X⃗)]]) can be expressed as a linear combination of finitely many expressions of the form P ([[φ(X⃗)]]) where φ(x⃗) is a finite conjunction of atomic formulas of L(M). □

Theorem 3.10 For each structure M for L(M) with at least two elements, the randomization theory T is complete.

Proof: The examples in the next section will show that T is consistent. (This is the place where we need the hypothesis that M has at least two elements.) Let ψ be a sentence in L. By Quantifier Elimination there is a sentence θ in L such that T ⊢ ψ ⇔ θ and θ has no quantifiers. Then no variables of sorts K or B can occur in θ. The language L has no constant symbols of sort K. Every constant term of sort B must be built up, using the Boolean operations ⊔, ⊓, −, from terms of the form [[φ]] where φ is a sentence of L(M) and the constant symbols ⊥, ⊤. It follows that in T, every constant term of sort B is provably equal to ⊥ or ⊤. Since P [⊥] = 0 and P [⊤] = 1, any term of the form P [⋯] within θ can be replaced by 0 or 1, and we obtain a sentence δ of L(R) which is equivalent to ψ in T. Since T contains the complete theory T h(R) in L(R), δ is either provable or refutable in T. □

Remark 3.11 Theorem 3.10 holds even without the assumption that T h(R) admits quantifier elimination.

To see this, just apply Theorem 3.10 to the Morleyization R′ of R, which is the expansion of R formed by adding a new predicate symbol for each formula of L(R). This works because T h(R′) admits quantifier elimination and all the new predicate symbols are definable in R.

4 Examples

In this section we expand the list of three examples of randomizations of M given in the introduction. This will add some bite to the study of the Randomization Theory T. We will give several constructions of randomizations where the universe K is a set of equivalence classes of functions from a set Ω into M.

We first note that in each of the examples from the Introduction, the measure P was σ-additive. We can cast a wider net in a search for models of T by dropping the σ-additivity requirement. Instead, we strengthen the notion of an atomless measure in a manner which is suggested by the Atomless Axiom.

Definition 4.1 By an R-atomless measure on a Boolean algebra B we mean a function P : B → R which satisfies the first three Measure Axioms and the Atomless Axiom. P is strictly positive if it also satisfies the fourth Measure Axiom.

If P is an R-atomless measure on an algebra of subsets B of Ω, and (B̄, P) is the corresponding measure algebra, it is easily seen that P is a strictly positive R-atomless measure on B̄.

Definition 4.1 generalizes the usual notion of an atomless σ-additive probability measure. A still more general notion in the literature is the notion of a measure with values in a pointed monoid given by Myers in [M].

Another way we cast a wider net is to drop the requirement that the Boolean algebra B be σ-additive. Instead we will rely on the Fullness Axiom to make events behave well with respect to quantifiers.

The next definition introduces a notion which is the key to building randomizations of M. We assume throughout this section that Ω is a nonempty set and K is a set of functions from Ω into M.

Definition 4.2 We shall say that K is full in M^{Ω} if for each formula θ(x⃗, y) of L(M) and tuple X⃗ in K, there exists Y ∈ K such that

{w : M ⊧ θ(X⃗(w), Y (w))} = {w : M ⊧ ∃yθ(X⃗(w), y)}.

Proposition 4.3 Suppose K is full in M^{Ω}, B is the set of all events

[[ψ(X⃗)]]_{Ω} = {w ∈ Ω : M ⊧ ψ(X⃗(w))}

where ψ(X⃗) ∈ L(K, M), and P is an R-atomless measure on B. The structure K = (K̄, B̄, R) built by identifying elements of K or B which agree on a set of measure one is a model of the randomization theory for M.

Discussion: We will call K the randomization of M induced by (K, P). Let us sketch the construction of K. Later on we will follow the same notation in several examples.

Let F be the filter

F = {A ∈ B : P [A] = 1}

in B. K̄ is the set of equivalence classes

K̄ = {X/F : X ∈ K}, where X/F = {Y ∈ K : {w : X(w) = Y (w)} ∈ F}.

(B̄, P) is the corresponding measure algebra where B̄ = B/F. Finally, the event mapping from L(K̄, M) onto B̄ is defined by

[[φ(X⃗/F)]] = [[φ(X⃗)]]_{Ω}/F.

It is easily seen that K is a model of T. □

We will take up the question of the existence of an R-atomless measure P on B in Section 7.

Another property of full sets in M^{Ω} is the following analog of Łoś’ theorem on ultrapowers. It can be proved by an easy induction.

Corollary 4.4 Let K be full in M^{Ω}. Define the mapping

[⋯] : L(K, M) → B

inductively with the rule

[ψ(X⃗)] = [[ψ(X⃗)]]_{Ω}  (1)

for atomic ψ, the obvious rules for logical connectives, and the quantifier rule

[∃yθ(X⃗, y)] = max{[θ(X⃗, Y)] : Y ∈ K}.  (2)

Then the maximum in Equation (2) is always attained in B, and Equation (1) holds for all sentences ψ(X⃗) ∈ L(K, M). □

Here is a converse of Proposition 4.3.

Theorem 4.5 (Representation Theorem) Let K′ = (K′, B′, R) be a model of the randomization theory for M with scalar part R. Then K′ is isomorphic to a structure K = (K̄, B̄, R) which is induced by a pair (K, P) where K is full in M^{Ω} and P is an R-atomless measure on the corresponding algebra of events B.

Proof: Let Ω be the set of all functions from K′ into M with finite range. For each k ∈ K′ let X_{k} be the function from Ω into M defined by X_{k}(w) = w(k), and let K′′ = {X_{k} : k ∈ K′}. Then the function f(X_{k}) = k is a bijection from K′′ to K′. Let B′′ be the set of events [[ψ(X_{k}, ⋯)]]_{Ω}.

We claim that if [[ψ(k, …)]] ≠ ⊥′ in B′ then [[ψ(X_{k}, …)]]_{Ω} ≠ ∅. To simplify notation we prove the claim for the case where ψ has just one free variable. Suppose [[ψ(k)]] ≠ ⊥′. Then [[∃xψ(x)]] ≠ ⊥′. By the Transfer Axiom, M ⊧ ∃xψ(x). Choose m ∈ M such that M ⊧ ψ(m), and choose w ∈ Ω so that w(k) = m. Then X_{k}(w) = m, so M ⊧ ψ(X_{k}(w)) and hence w ∈ [[ψ(X_{k})]]_{Ω}. This proves the claim.

By the above claim, we may define functions g : B′′ → B′ and P′′ : B′′ → R by putting

g([[ψ(X_{k}, …]]_{Ω}) = [[ψ(k, …)]], P′′(A) = P′(g(A)).

It is easy to check that B′′ is an algebra of subsets of Ω, and that P′′ is an R-atomless measure on B′′.

Since (K′, B′, R) satisfies the Fullness Axiom, for each θ(x⃗, y) and X⃗ in K′′ there exists Y ∈ K′′ such that

P′′([[∃y θ(X⃗, y) ⇔ θ(X⃗, Y)]]) = 1.

To get a full set in M^{Ω} we need this to work everywhere instead of almost everywhere. We do this by letting K be the set of all X : Ω → M such that X agrees with some X′′ ∈ K′′ on a set of P′′-measure one. K is full in M^{Ω}. Let (Ω, B, P) be the completion of (Ω, B′′, P′′), that is, B is the set of all A ⊆ Ω such that A agrees with some A′′ ∈ B′′ on a set of P′′-measure one, and P is the obvious extension of P′′ to B. Then B is the set of all events [[ψ(X⃗)]]_{Ω} with ψ(X⃗) ∈ L(K, M).

Finally, using the functions (f, g) we get an isomorphism from the randomization K of M induced by (K, P) to the original structure K′ = (K′, B′, R). □

Note that the randomization theory T depends only on the complete theories T h(M) and T h(R), but the Representation Theorem can be applied to each particular pair of models M, R of these complete theories.

We shall now give several ways of constructing full sets in M^{Ω}. By Proposition 4.3, each example will induce a whole class of randomizations of M, one for each R-atomless measure on B.

It will be instructive to compare some of these examples with the corresponding construction where the measure P is two valued, so that F is an ultrafilter in B and B̄ = {⊥, ⊤}. In this case the event algebra B̄ and the scalar part R can be ignored, and we get a structure K for the original language L(M) with universe K̄ such that φ(X⃗/F) holds in K if and only if [[φ(X⃗)]]_{Ω} ∈ F. This structure turns out to be exactly the same thing as Engeler’s generalization of an ultrapower in [En], called an elementary filter image of M. Theorem 2.1 of [En] shows that the class of elementary filter images of M is equal, up to isomorphism, to the class of all models which are elementarily equivalent to M.

Our first example extends the bounded Boolean power construction (Example 2 in the Introduction) to atomless measures which are not necessarily σ-additive.

Example 4.6 (Simple functions) Let B be an algebra of subsets of Ω. We call a function X : Ω → M simple if X has finite range and X^{−1}{a} ∈ B for each a ∈ M. The set K of all simple functions from Ω into M is full in M^{Ω}.

The two-valued case of this example is trivial, producing a model isomorphic to M (since every simple function is constant over some set in the ultrafilter).

Example 4.7 (Ultrapowers) The set of all functions from Ω into M is full in M^{Ω}. The corresponding algebra B of events is the power set of Ω.

The two-valued case of this example is the usual ultrapower M^{Ω}/F (e.g. see Chapter 4 of [CK]).

In the following, definable means definable in M by a formula of L(M) with parameters from M. A structure M is said to have definable Skolem functions if for each definable relation R(x⃗, y) there is a definable function f(x⃗) such that

M ⊧ ∀x⃗[∃yR(x⃗, y) ⇒ R(x⃗, f(x⃗))].

Example 4.8 (Definable ultrapowers) Suppose M has definable Skolem functions, and Ω is definable in M. The set K of all definable functions f : Ω → M is full in M^{Ω}. The corresponding algebra of events is the set B of all subsets of Ω which are definable in M.

The two-valued analogue of this example is the original definable ultrapower construction introduced by Skolem [Sko] to extend the standard model M of arithmetic to a nonstandard model.

Example 4.9 (Internal functions) Suppose that in an ω_{1}-saturated nonstandard universe, Ω is an internal set and M is an internally presented structure (that is, every finite reduct of M is internal). Then the set K of all internal functions X : Ω → M is full in M^{Ω}. (E.g. see [CK, Section 4.4])

Example 4.10 (Limit ultrapowers) Let G be a filter over Ω × Ω. The set K of all X : Ω → M such that {(v, w) : X(v) = X(w)} ∈ G is full in M^{Ω}. The corresponding algebra of events is the power set of Ω.

The two-valued case of this example is the limit ultrapower Π_{F|G}M of M introduced in [K] (see also [CK], Section 6.4).

For the remainder of this section, assume that B is a σ-complete field of subsets of Ω.

Our next example extends the Boolean power construction given in Example 1 in the Introduction.

Example 4.11 (Boolean powers). The set K of all functions X : Ω → M with countable range such that X^{−1}{m} ∈ B for each m ∈ M is full in M^{Ω}.

By Lemma 4.3, in the above example we get a model of T for every R-atomless measure P on B. This is a bit more general than Example 1, where P was σadditive. In the two-valued case the corresponding notion is the Boolean ultrapower construction (see [Ma]).

Proposition 4.12 (o-minimal structures) Suppose M = ⟨M, ≤, …⟩ is an o-minimal structure such that ⟨M, ≤⟩ has a countable dense subset. Let K be the set of all functions X : Ω → M such that X^{−1}(I) ∈ B for each interval I in M. Then K is full in M^{Ω}.

Proof: Let D_{n} be the σ-algebra of subsets of M^{n} generated by the set of definable n-ary rectangles. We claim that every definable n-ary relation in M belongs to D_{n}. Our proof relies on the notion of a cell in the paper [KPS]. By [KPS], each definable relation in M is a finite pairwise disjoint union of cells. We show by double induction on n and k that each cell C ⊆ M^{n} of dimension k belongs to D_{n}. For n = 1 this follows by the definition of o-minimal, and for k = 0 the claim is trivial. Now let n > 1 and 0 < k ≤ n. Assume the claim for all cells in M^{m} for m < n and for all cells in M^{n} of dimension less than k. Let D ⊆ M^{n} be a cell of dimension k. By definition of cells, there are two cases to consider.

In the first case, there is a cell B ⊆ M^{n−1} of dimension k and a definable continuous function f : B → M such that D is the graph of f. B ∈ D_{n−1} by induction hypothesis, and since M has a countable dense subset, it follows that D ∈ D_{n}.

In the second case, there is a cell C ⊆ M^{n−1} of dimension k − 1 and a pair of definable continuous functions f, g : C → M such that

D = {(x, y) : x ∈ C ∧ f(x) < y < g(x)}

(perhaps with −∞ in place of f or +∞ in place of g). It again follows that D ∈ D_{n}. This completes the proof of the claim.

It follows that for each definable set C ⊆ M^{n} and X⃗ ∈ K^{n}, we have X⃗^{−1}(C) ∈ B. Now consider a formula θ(x⃗, y) of L(M) and a tuple X⃗ in K. Let D = {d_{k} : k ∈

ω} be a countable dense set in ⟨M, ≤⟩. For each w ∈ Ω, let

A(w) = {y : M ⊧ θ(X⃗(w), y)}.

By o-minimality, each set A(w) is a finite union of intervals. Since D is dense, either A(w) has a least element, A(w) meets D, or A(w) is empty. Define the function Y : Ω → M as follows.

Y (w) is the least element of A(w) if there is one.

Y (w) = d_{1} if A(w) is empty.

Otherwise, Y (w) = a_{k} where k is the least j ∈ ω such that a_{j} ∈ A(w).

Consider an interval I in M. The reader can check that there is a countable sequence of definable relations E_{k}, k ∈ ω such that

Y^{−1}(I) = ⋃_{k}(X⃗^{−1}(E_{k})).

It follows that Y^{−1}(I) ∈ B. Since this holds for every interval I we have Y ∈ K. From the definition of Y we see that

[[θ(X⃗, Y)]]_{Ω} = [[∃yθ(X⃗, y)]]_{Ω}.

This shows that K is full in M^{Ω}. □

We conclude this section by showing that the structure built in Example 3 of the Introduction is a model of T.

Proposition 4.13 (Measurable functions) Let (Ω, B, P) be a complete σ-additive probability space. Let M be a structure with a Polish topology T , and assume that each definable relation on M is Borel with respect to T . Then the set K of all (B, T )-measurable functions from Ω into M is full in M^{Ω}.

Proof: Consider a formula ψ(x⃗, y) of L(M). By hypothesis, the relation defined by ψ is Borel with respect to T . Let

S = {m⃗ in M : M ⊧ ∃yψ(m⃗, y)}.

Let A be the σ-algebra of subsets of M^{|x⃗|} generated by the analytic sets with respect to T . By the Jankov-Von Neumann selection theorem (see [Kc], p. 120), there is a function U : S → M such that U is (A, T )-measurable and M ⊧ ψ(m⃗, U(m⃗)) for all m⃗ ∈ S. Now let X⃗ be a tuple in K, and define Y : Ω → M by Y (w) = U(X⃗(w)). Then

[[ψ(X⃗, Y)]]_{Ω} = [[∃yψ(X⃗, y)]]_{Ω}.

It remains to show that Y ∈ K, that is, Y is (B, T )-measurable. Let V be open in T . Then U^{−1}(V) ∈ A. By Proposition 11.2 in [EK], X⃗^{−1}(A) ⊆ B, and hence Y^{−1}(V) = X⃗^{−1}(U^{−1}(V)) ∈ B. □

In the next section we will see what happens in the preceding proposition if we drop the assumption that each definable relation on M is Borel with respect to T .

5 The Pure Randomization Theory

In this section we consider the subtheory S of T which has all the axioms of T except the Transfer Axioms. The theory S depends only on the vocabulary L(M) and the complete theory T h(R). We will call S the pure randomization theory (with scalar part R). The models of can be thought of as structures whose elements are random variables which take values in random models with the vocabulary L(M).

Throughout this section the scalar structure R will remain fixed, and all models mentioned for L(M) are assumed to have at least two elements.

Each model K = (K, B, R) of S still determines a probability measure on the set of sentences L(K, M). But now the sentences of L(M) can have probabilities between 0 and 1.

The subtheory S is of interest because of the following result.

Theorem 5.1 The pure randomization theory S admits quantifier elimination.

Proof: The Transfer Axioms were never used in the proof of the Quantifier Elimination Theorem for T, so the original proof also applies to the theory S. □

We can easily improve Theorem 3.10 to characterize the complete theory of an arbitrary model of S.

Theorem 5.2 Let K be a model of S and let Φ be the set of all sentences of L(M). Assume (for simplicity) that for each φ ∈ Φ there is a constant symbol c_{φ} in L(R) such that

K ⊧ P ([[φ]]) = c_{φ}.

Then the theory

S ∪ {P ([[φ]]) = c_{φ} : φ ∈ Φ}

is complete.

Proof: Argue as in the proof of Theorem 3.10, using the Quantifier Elimination Theorem. □

The next lemma gives a consequence of S which we will need later.

Lemma 5.3 S ⊢ [[∃x∃y(x ≠ y)]] = ⊤.

Proof: By the Event Axiom,

S ⊢ ∃X∃Y ([[X = Y]] = ⊥),

so

S ⊢ ∃X∃Y ([[X ≠ Y]] = ⊤).

By the Validity Axioms,

S ⊢ ∀X∀Y ([[X ≠ Y ⇒ ∃x∃y(x ≠ y)]] = ⊤).

Then by the Boolean Axioms,

S ⊢ [[∃x∃y(x ≠ y)]] = ⊤. □

The next proposition gives a natural class of models of the theory S which is related to the Boolean valued model approach to independence proofs in set theory.

Proposition 5.4 Let R be the reals, and let (Ω, B, P) be a complete atomless σadditive probability space. Let K be a set of functions from Ω into M such that:

(i) There exist X, Y ∈ K such that {w : X(w) = Y (w)} = ∅.

(ii) For each atomic sentence ψ(X⃗) in L(K, M), the set {w : M ⊧ ψ(X⃗(w))} belongs to B.

(iii) For each partition A_{n}, n ∈ ω of Ω in B and sequence X_{n}, n ∈ ω in K, there exists Y ∈ K such that for each n, Y (w) = X_{n}(w) for almost all w ∈ A_{n}.

Form K̄ and B̄ by identifying elements of K or B which are almost surely equal. Define the event mapping [[ψ(X⃗)]] by induction on the complexity of ψ, with the rule

[[ψ(X⃗)]] = {w : M ⊧ ψ(X⃗(w))}/F

for atomic formulas ψ, the obvious rules for connectives, and the quantifier rule

[[∃yθ(X⃗, y)]] = max{[[θ(X⃗, Y)]] : Y ∈ K̄}.  (3)

Then [[⋯]] is well defined and the structure K = (K̄, B̄, R) is a model of the pure randomization theory S.

Proof: All the axioms of S except the Fullness Axiom are clear. It is well known that the measure algebra B̄ is a complete Boolean algebra. In this circumstance, the Fullness Axiom is proved in [J, page 202]. □

As a special case, the structure K_{3} in Example 3 in the introduction is a model of S when the event mapping [[⋯]] is defined as in the above proposition. In fact, this works even when the assumption that each definable relation in M is Borel is weakened to the assumption that each symbol of L(M) has a Borel interpretation in M. However, one can no longer conclude that K_{3} satisfies the Transfer Axioms of T.

The Representation Theorem in the preceding section has an analog for the Pure Randomization Theory S. The models of S will be related to the models of T in roughly the same way that ultraproducts are related to ultrapowers. Instead of a single structure M, there will be a “random structure” M(w) which varies with w ∈ Ω.

Definition 5.5 Let Ω be an infinite set, let

⟨M(w) : w ∈ Ω⟩

be an indexed family of structures for L(M) such that each M(w) has at least two elements, and let K be a nonempty subset of the Cartesian product ∏_{w∈Ω} M(w). The notion of K being full in ∏_{w∈Ω} M(w) is defined as in Proposition 4.3 but with M(w) in place of M. Similarly for the randomization induced by (K, P).

Proposition 5.6 Suppose K is full in ∏_{w∈Ω} M(w), and P is an R-atomless measure on the corresponding algebra of events B. Then the randomization induced by (K, P) is a model of the pure randomization theory S. □

The following representation theorem is weaker than Theorem 4.5 because the family of structures ⟨M(w)⟩_{w∈Ω} is allowed to depend on the given structure K′.

Theorem 5.7 (Representation Theorem) Let K′ = (K′, B′, R) be a model of the pure randomization theory S. Then there is a full set K in a product ∏_{w∈Ω} M(w) and an R-atomless measure P on the corresponding algebra of events B such that the randomization K induced by (K, P) is isomorphic to K′.

Proof: Our sample space Ω will be the set of all ultrafilters on B′. By the Stone representation theorem, the Boolean algebra B′ is isomorphic to an algebra B of subsets of Ω. Let P be the R-atomless measure on B obtained from this isomorphism. For each ultrafilter w ∈ Ω, let Γ(w) be the set of all sentences θ(X⃗) ∈ L(K, M) such that [[θ(X⃗)]]′ ∈ w. Each Γ(w) is a complete theory, and has a model (M(w), X̂(w))_{X∈K′}. Then the set K = {X̂ : X ∈ K′} is a subset of the Cartesian product ∏_{w∈Ω} M(w). By Lemma 5.3, each M(w) has at least two elements. One can now check that K is full in ∏_{w∈Ω} M(w), and the randomization K induced by (K, P) is isomorphic to the given structure K′. □

The simple function construction given in Example 4.6 can be generalized to build models of the theory S, which we will call simple randomizations. We will apply the Quantifier Elimination Theorem to show that S is exactly the set of sentences which hold in all simple randomizations.

For the rest of this section, let us fix a Boolean algebra B of subsets of a set Ω, and an R-atomless measure P on B.

By a simple function on (Ω, B, P) we mean a function X with domain Ω and finite range such that X^{−1}{m} ∈ B for each point m in the range of X.

Definition 5.8 Let w ↦ M(w) be a simple function on (Ω, B, P) such that each M(w) is a structure for L(M) (so there are only finitely many different models M(w)). Let K be the set of all simple functions X ∈ ∏_{w∈Ω} M(w) on (Ω, B, P). The randomization induced by (K, P) is called the simple randomization from (Ω, B, P) to ⟨M(w) : w ∈ Ω⟩.

Proposition 5.9 Every simple randomization from (Ω, B, P) is a model of the pure randomization theory S.

Proof: The set K of all simple functions is clearly full in ∏_{w∈Ω} M(w). □

Theorem 5.10 The pure randomization theory S is equivalent to the set of sentences which hold in every simple randomization from (Ω, B, P).

Proof: Let ψ be a sentence which is consistent with S. We must find a simple randomization K from (Ω, B, P) in which ψ holds. By Quantifier Elimination, there is a quantifier-free sentence θ such that S ⊢ ψ ⇔ θ. Since θ is a quantifier-free sentence, it has no variables. Using the Boolean Axioms, one can also eliminate all Boolean operation symbols from θ. Thus each term in θ is built from constants of sort R, and expressions of the form P ([[φ]]) where φ is a sentence of L(M). By further use of the Boolean Axioms, the expressions of the form P ([[φ]]) occurring in θ can be split into sums of probabilities of pairwise inconsistent sentences. Thus one can get a formula δ(r_{1}, …, r_{n}) of L(R) and a finite set Γ = {γ_{1}, …, γ_{n}} of sentences of L(M) such that:

(1)

S ⊢ θ ⇔ δ([[γ_{1}]], …, [[γ_{n}]]),

(2) Every structure for L(M) satisfies exactly one sentence in Γ.

(3)

S ⊢ δ(r_{1}, …, r_{n}) ⇒ ( ⋀_{i=1}^{n} 0 ≤ r_{i} ∧ r_{1} + ⋯ + r_{n} = 1) .

We may assume without loss of generality that for each i ≤ n, the sentence [[γ_{i}]] ≠ ⊥ is consistent with S. Therefore by the Validity Axioms and Lemma 5.3, the sentence

∃x∃y(x ≠ y) ⇒ ¬γ_{i}

of L(M) is not valid, and hence there exists a model M_{i} of γ_{i} with at least two elements.

Since ψ is consistent with S, θ is consistent with S. Therefore the sentence

∃r_{1} ⋯ ∃r_{n}δ(r_{1}, …, r_{n})

of L(R) is consistent with S and thus holds in R. Choose an n-tuple a_{1}, …, a_{n} which satisfies δ(r⃗) in R. By (3), the elements a_{i} are non-negative and add up to 1 in R. We may list the elements a_{i} in decreasing order, and let m be the largest i ≤ n such that a_{i} > 0. By the Atomless Axiom, we can partition Ω into pairwise disjoint sets Ω_{1}, …, Ω_{m} in B such that P [Ω_{i}] = a_{i}.

Now let M(w) = M_{i} for each w ∈ Ω_{i}, and let K be the simple randomization from (Ω, B, P) to ⟨M(w) : w ∈ Ω⟩. K is a model of S by the preceding proposition. K satisfies

δ(a_{1}, …, a_{n}) ∧ P ([[γ_{1}]]) = a_{1} ∧ ⋯ ∧ P ([[γ_{n}]]) = a_{n},

and hence K ⊧ θ. Finally, since S ⊢ ψ ⇔ θ, K is a model of ψ as required. □

6 Substructures of Randomizations

In this section we will study substructures of models of the pure randomization theory S in the following sense.

Definition 6.1 Let K = (K, B, R) and K_{1} = (K_{1}, B_{1}, R_{1}) be structures for the language L. K is an extension of K_{1}, and K_{1} is a substructure of K, if K_{1} ⊆ K, B_{1} ⊆ B, R_{1} ⊆ R, and the functions [[⋯]] and P for K are extensions of the corresponding functions for K_{1}.

We shall prove that a natural subset U of the set of axioms of the pure randomization theory S is logically equivalent to the set of all universal consequences of S.

We will use the Łoś-Tarski theorem (see [CK], Theorem 3.2.2 and Remark 3.5.6), which shows that a structure K satisfies all universal consequences of a theory S if and only if K is a substructure of a model of S.

Definition 6.2 Let T h_{∀}(R) be the set of all universal consequences of T h(R) in the language L(R). The subrandomization theory U for L(M) (with scalar part R) is the following subset of S:

• The Validity Axioms.

• The Boolean Axioms.

• The Measure Axioms.

• The set T h_{∀}(R).

Every axiom of U is a universal axiom of S, so every substructure of a model of S is a model of U. The axioms of S which are missing from U are the Fullness, Event, and Atomless Axioms, and the complete theory T h(R). These axioms contain existential quantifiers.

In algebraic terms, a structure K′ = (K′, B′, R′) is a model of U if and only if:

• B′ is a nontrivial Boolean algebra,

• [[⋯]]′ is a mapping from sentences into B′ which preserves Boolean operations,

• P′ is a strictly positive probability measure from B′ into R′,

• R′ is a substructure of a model of T h(R).

Each model K of S induces a probability measure P ([[φ(X⃗)]]) on the set of sentences L(K, M).

The next result is a one-sided version of the Quantifier Elimination Theorem, and will be a key to proving that the theory U is actually equivalent to the set of universal consequences of S.

Theorem 6.3 For every existential formula ψ in L there is a quantifier-free formula φ in L with the same free variables such that U ⊢ ψ ⇒ φ and S ⊢ φ ⇒ ψ.

Proof: The observations we made for future reference during the proof of the Quantifier Elimination Theorem show that the implication ψ ⇒ φ from T only used axioms of U. □

Theorem 6.4 The subrandomization theory U is logically equivalent to the set of all universal consequences of the pure randomization theory S.

Proof: Let ψ be an existential sentence which holds in some model K_{0} = (K_{0}, B_{0}, R_{0}) of U. It suffices to show that ψ holds in some model of S. The argument is similar to the proof of Theorem 5.10.

By Theorem 6.3 there is a quantifier-free sentence θ such that U ⊢ ψ ⇒ θ and S ⊢ θ ⇒ ψ. Using the Boolean axioms, we can get a quantifier-free formula δ(r_{1}, …, r_{n}) of L(R) and a finite set Γ = {γ_{1}, …, γ_{n}} of sentences of L(M) such that conditions (1)–(3) in the proof of Theorem 5.10 hold with U instead of S.

Since ψ holds in K_{0} and U ⊢ ψ ⇒ θ, we see from (1) that δ(P ([[γ_{1}]]), …, P ([[γ_{n}]])) holds in K_{0}. The scalar part R_{0} of K_{0} is a model of T h_{∀}(R), so by the Łoś-Tarski theorem, R_{0} can be extended to a model R of T h(R). For each i ≤ n, let a_{i} = P_{0}([[γ_{i}]]). Then δ(a_{1}, …, a_{n}) holds in R_{0}. Since δ is quantifier-free, δ(a_{1}, …, a_{n}) holds in R. As in the proof of Theorem 5.10, one can now construct a simple randomization K with scalar part R which satisfies

δ(a_{1}, …, a_{n}) ∧ P ([[γ_{1}]]) = a_{1} ∧ ⋯ ∧ P ([[γ_{n}]]) = a_{n},

and hence is a model of S which satisfies θ. Since S ⊢ θ ⇒ ψ, ψ holds in K. □

Corollary 6.5 S is the model completion of U.

Proof: By the Quantifier Elimination Theorem, Theorem 6.4, and Proposition 3.5.19 in [CK]. □

Corollary 6.6 A structure (K′, B′, R′) for L is a model of the subrandomization theory U if and only if it can be extended to a model of the pure randomization theory S. □

We can now easily solve the equation

\frac{U}{S} = \frac{?}{T} .

Corollary 6.7 Let V be the union of the subrandomization theory U and the Transfer Axioms for T h(M). Then V is logically equivalent to the set of all universal consequences of T, and hence T is the model completion of V. □

Proof: It suffices to observe that the Transfer Axioms for T h(M) have no quantifiers, and T is the union of S and the Transfer Axioms for T h(M). □

Here is an open question concerning the extension of a model of U to a model of S:

Question 6.8 Given a submodel R_{1} ⊆ R, when can a model (K_{1}, B_{1}, R_{1}) of U with scalar part R_{1} be extended to a model (K, B, R) of S with scalar part R?

Let us call the structure R real if it is an expansion of the ordered group of real numbers with addition and the constants 0, 1. The next result gives an affirmative answer to the above question in the case that R is real.

Theorem 6.9 Let R be real. Every model (K_{1}, B_{1}, R_{1}) of the subrandomization theory U such that R_{1} ⊆ R can be extended to a model (K, B, R) of the pure randomization theory S.

Proof: By Corollary 6.6, we can extend (K_{1}, B_{1}, R_{1}) to a model (K_{2}, B_{2}, R_{2}) of S. By compactness we may take (K_{2}, B_{2}, R_{2}) to be ω_{1}-universal. For each r ∈ R_{2} such that R_{2} ⊧ 0 ≤ r ≤ 1, let st(r) be the “standard part” of r in R, that is, the least upper bound of the set of rational q such that R_{2} ⊧ q < r. The standard part function may behave badly for the extra relations of the vocabulary of R, but for all r, s, t between 0 and 1 in R_{2} we have

r ∈ R_{1} ⇒ st(r) = r, r ≤ s ⇒ st(r) ≤ st(s), r + s = t ⇒ st(r) + st(s) = st(t).

It follows that the function A ↦ st(P_{2}[A]) is a probability measure on B_{2} with values in R which is an extension of P_{1}. This probability measure on B_{2} is not necessarily strictly positive. Let F be the filter F = {A ∈ B_{2} : st(P_{2}[A]) = 1} in B_{2}, let B be the quotient of B_{2} modulo F, and define P on B by P [A/F] = st(P_{2}[A]). Then P is a strictly positive probability measure on B with values in R. Since (K_{2}, B_{2}, R_{2}) is ω_{1}-universal, the standard part mapping sends the interval [0, 1] of R_{2} onto the interval [0, 1] of R. Using the Atomless Axiom of S, it follows that P is R-atomless.

Define f : B_{1} ⇒ B by f(A) = A/F. Since P_{1} is strictly positive and R_{1} ⊆ R, f embeds the Boolean algebra B_{1} isomorphically into B and P is an extension of P_{1}∘f. Let K = K_{2} and for each sentence φ(X⃗) ∈ L(K, M) let [[φ(X⃗)]] = [[φ(X⃗)]]_{2}/F. Then (K, B, R) is a structure with scalar part R which extends (K_{1}, B_{1}, R_{1}). The Scalar Axioms hold in (K, B, R) because R ⊧ T h(R). The construction of (K, B, R) from (K_{2}, B_{2}, R_{2}) preserves the other axioms, and therefore (K, B, R) is a model of S. □

Theorem 6.9 is closely related to Gaifman’s completeness theorem for measure models in [G]. Gaifman proved that for every set K_{1} of new constant symbols and every real-valued probability measure P_{1} on the set of sentences L(K_{1}, M), there is a set K ⊃ K_{1} and a real-valued probability measure P ⊇ P_{1} on the set of sentences L(K, M) which satisfies the Fullness Axiom. This can be easily modified to show that every model (K_{1}, B_{1}, R_{1}) of the theory U where R_{1} ⊆ R and R is real can be extended to a model (K, B, R) which satisfies all the axioms of S except for the Atomless Axiom. Theorem 6.9 improves this by getting an extension which also satisfies the Atomless Axiom.

Here is another open question about extending models.

Question 6.10 Suppose (K′, B′, R′) is a model of the subrandomization theory U and satisfies the Atomless Axiom. Suppose B ⊇ B′, R ⊇ R′, P ⊇ P′, and P is a strictly positive R-atomless measure. When can (K′, B′, R′) be extended to a model (K, B, R) of S with the given measure P?

7 Removing a Sort

Most of the results in this paper have similar but simpler counterparts where one of the three sorts K, B, R is omitted. In this section we will look at what happens when each sort is removed.

7A Probability Algebras

We consider the language L(B, R) obtained by removing the random element sort K but keeping the other two sorts. This greatly simplifies our theory—the structure M no longer plays a role, and all that remains is the theory of R-atomless measure algebras. See Fremlin [F] or Kappos [Ka] for expositions of the classical theory of (σ-additive) probability measure algebras.

The language L(B, R) has the sorts B of events and R of scalars, and the probability function symbol P of sort B → R.

Definition 7.1 The theory T (B, R) of R-atomless measure algebras has the usual Boolean algebra axioms in the language L(B), and the Scalar, Measure, and Atomless Axioms from Section 2.

The subtheory U(B, R) has the usual Boolean algebra axioms, the Measure Axioms from Section 2, and the set of universal sentences T h_{∀}(R).

Every axiom of T (B, R) is an axiom of the pure randomization theory S. Moreover, every model of T (B, R) can easily be expanded to a model of the randomization theory T where M is a model with two elements and no relations except equality. Our results for the randomization theory T have the following analogues for T (B, R), whose proofs are left to the reader.

Theorem 7.2 (i) The theory T (B, R) of R-atomless measure algebras is complete and admits quantifier elimination.

(ii) The theory U(B, R) is logically equivalent to the set of all universal consequences of T (B, R). □

The next corollary, which concerns real valued probability measure algebras, is the analogue of Theorem 6.9 for the language L(B, R).

Corollary 7.3 Let R be real. Every model (B′, R′) of U(B, R) with scalar part R′ ⊆ R can be extended to a model (B, R) of T (B, R) with scalar part R. Thus every strictly positive finitely additive probability measure on a Boolean algebra B′ can be extended to a strictly positive R-atomless measure on some B ⊇ B′.

Proof: Expand (B′, R′) to a model (K′, B′, R′) of the subrandomization theory U, apply Theorem 6.9 to extend this to a model (K, B, R) of the pure randomization theory S, and then take the reduct (B, R). □

A natural question arises at this point.

Question 7.4 Given B and R, when does there exist a function P : B → R which makes (B, R) a model of T (B, R)? That is, when does there exist a strictly positive R-atomless measure on B?

The following example shows that every R can be expanded to a model of T (B, R).

Example 7.5 Given R, let B be the collection of all finite unions of half-open intervals [r, s) with 0 ≤ r < s ≤ 1 in R, and P be the unique finitely additive measure on B such that P [r, s) = s − r for each r, s. Then P makes (B, R) a model of T (B, R).

There are pairs (B, R) such that B has no strictly positive R-atomless measure. In fact, if B has a strictly positive R-atomless measure then all maximal chains in B have the same order type (which must be the order type of [0, 1] in the sense of R).

The next result answers Question 7.4 for the case that B and R are countable, and will be useful when we remove the sort R and look at L(K, B).

Proposition 7.6 Suppose B is a countable atomless Boolean algebra and R is countable. Then there exists a strictly positive R-atomless measure P on B.

Proof: We build P by a back and forth construction using the fact that every finite subset of B generates a finite subalgebra of B. (Similar constructions can be found, e.g. in [HT]). Let F be the set of all pairs (B_{0}, P_{0}) in R such that B_{0} is a finite subalgebra of B and P_{0} : B_{0} → R is a strictly positive probability measure. Note that F is nonempty, because it has the minimal element consisting of the unique probability measure on the two-element Boolean algebra.

Consider a (B_{0}, P_{0}) ∈ F. Let B_{1}, …, B_{k} be the atoms of B_{0} and for each i let s_{i} = P_{0}[B_{i}]. Thus s_{i} > 0. The measure P_{0} on B_{0} is determined by the values s_{1}, …, s_{k} since any element of B_{0} is a disjoint union of atoms. It suffices to prove that:

(a) For each A ∈ B there is a (B_{1}, P_{1}) ⊇ (B_{0}, P_{0}) such that A ∈ B_{1} and (B_{1}, P_{1}) ∈ F.

(b) For each B ∈ B_{0} and r ∈ R with 0 < r < P_{0}[B] there is a (B_{1}, P_{1}) ⊇ (B_{0}, P_{0}) in F and a C ∈ B_{1} such that C ⊑ B and P_{1}[C] = r.

Proof of (a): Let B_{1} be the Boolean subalgebra of B generated by B_{0} ∪ {A}. Then the atoms of B_{1} are those elements B_{i} ⊓ A, B_{i} − A, i = 1, …, k which are unequal to ⊥. For each i ≤ k choose s_{i} ∈ R with 0 < s_{i} < r_{i}. We obtain a P_{1} on B_{1}with (B_{0}, P_{0}) ⊆ (B_{1}, P_{1}) ∈ F by putting P [B_{i} ⊓ A] = s_{i} whenever B_{i} ⊓ A ≠ ⊥ and B_{i} ⊓ A ≠ B_{i}.

Proof of (b): B is a union of finitely many atoms of B_{0}. Thus there are D, E ∈ B_{0} and an atom B_{i} of B_{0} such that D ⊔ B_{i} = E ⊑ B and P_{0}[D] ≤ r < P_{0}[E]. If P_{0}[D] = r we may simply take B_{1} = B_{0} and C = D. Suppose P [D] < r. Then 0 < r − P [D] < r_{i}. Since B is atomless we may choose C ∈ B such that D ⊑ C ⊑ E and C ≠ D, C ≠ E. Then C ⊑ B. Let B_{1} be the subalgebra of B generated by B_{0} ∪ {C}. B_{1} has the same atoms as B_{0} except that B_{i} is split into C − D = B_{i} ⊓ C and E − C = B_{i} − C. By putting P_{1}[B_{i} ⊓ C] = r − P_{0}[D] we determine a P_{1} such that (B_{0}, P_{0}) ⊆ (B_{1}, P_{1}) ∈ F and P_{1}[C] = r as required. □

Corollary 7.7 For every atomless Boolean algebra B and every R, there are elementary extensions B′ ≻ B and R′ ≻ R with a strictly positive R′-atomless measure P′ on B′.

Proof: Let W be the theory containing the elementary diagram of B in sort B, the elementary diagram of R in sort R, and Measure and Atomless Axioms. It suffices to prove that W has a model. Proposition 7.6 shows that every finite subset of W is consistent, so W has a model by the compactness theorem. □

7B Boolean Valued Models

We consider the language L(K, B) obtained by removing the scalar sort R but keeping the other two sorts. This gives us a language for Boolean valued models for L(M). We no longer have the probability function symbol P, but we still have the event function symbol [[φ(⋯)]] of sort K^{n} → B for each formula φ(x⃗) of L(M) with n free variables.

Definition 7.8 The theory T (K, B) of full atomless Boolean valued models of T h(M) has the Validity, Boolean, Fullness, Event, and Transfer Axioms from Section 2, and the following Boolean Atomless Axiom:

(∀A)[A = ⊥ ∨ (∃B)(B ⊑ A ∧ (B ≠ ⊥ ∧ B ≠ A))]

The subtheory S(K, B) has all the axioms of T (K, B) except the Transfer Axioms.

The subtheory U(K, B) has just the Validity and Boolean Axioms and the Axiom

[[∃x∃y(x ≠ y)]] = ⊤.

It is clear that the reduct of every model of T to L(K, B) is a model of T (K, B). The next proposition concerns expansions from models of S(K, B) to models of S.

Proposition 7.9 (i) For every countable R, every countable model of S(K, B) can be expanded to a model of the pure randomization theory S with scalar part R.

(ii) For every R and model (K, B) of S(K, B), there is a model (K′, B′, R′) of S such that (K′, B′) ≻ (K, B) and R′ ≻ R.

Proof: Part (i) follows directly from Proposition 7.6. Part (ii) can be proved by a compactness argument like the proof of Corollary 7.7. □

The quantifier elimination result and its consequences are summarized in the next theorem.

Theorem 7.10 (i) S(K, B) admits quantifier elimination.

(ii) For each M with at least two elements, the theory T (K, B) of full atomless Boolean valued models of T h(M) is complete.

(iii) The theory U(K, B) is equivalent to the set of all universal consequences of S(K, B).

Proof: (i) This follows from Lemma 3.4 and the fact that the usual theory of atomless Boolean algebras admits quantifier elimination.

(ii) Let ψ be a sentence of L(K, B). By (i), ψ is equivalent in T (K, B) to a quantifier-free sentence θ. Each constant term of sort B must be built up from the constants ⊥, ⊤ and terms of the form [[φ]] where φ is a sentence of L(M), using the Boolean operations ⊔, ⊓, −. In T (K, B), each such term can either be proved to be equal to ⊥ or be proved to be equal to ⊤. The sentence θ is a propositional combination of equations between such terms, so either θ or its negation can be proved from T (K, B).

(iii) This follows from Corollary 7.7, Theorem 6.4, and the fact that any Boolean algebra can be extended to an atomless Boolean algebra. □

7C Eventless Randomizations

Finally, we remove the event sort B, leaving us with the language L(K, R) of eventless randomizations. In this language, the probability function is applied directly to formulas. Formally, for each formula φ(x⃗) of L(M) with an n-tuple x⃗ of free variables, there is a function symbol P [φ(⋯)] of sort K^{n} → R.

By the reduct to L(K, R) of a structure (K, B, R) for L we mean the structure (K, R) obtained by deleting the sort B and interpreting terms of the form P [φ(X⃗)] by the value of P ([[φ(X⃗)]]) in (K, B, R).

Definition 7.11 The eventless randomization theory T (K, R) (for M with scalar part R) in the language L(K, R) has the following axioms.

Validity Axioms:

∀X⃗(P [ψ(X⃗)] = 1)

where ∀x⃗ψ(x⃗) is logically valid,

P [∃x∃y x ≠ y] = 1,

and

∀X∀Y (X = Y ⇔ P [X = Y] = 1).

Witness Axioms:

∀X⃗ ∀r[(P [∀y⃗ φ(X⃗, y⃗)] ≤ r ≤ P [∃y⃗ φ(X⃗, y⃗)]) ⇒ ∃Y⃗ P [φ(X⃗, Y⃗)] = r].

Scalar Axioms: Each sentence of T h(R).

Measure Axioms:

∀X⃗ (0 ≤ P [φ(X⃗)] ≤ 1)
∀X⃗(P [(φ ∧ ψ)(X⃗)] = 0 ⇒ P [φ(X⃗)] + P [ψ(X⃗)] = P [(φ ∨ ψ)(X⃗)])

Transfer Axioms: P [φ] = 1 where φ ∈ T h(M).

The subtheory S(M, R) has the same axioms except for the Transfer Axioms. The subtheory U(M, R) has just the above Validity and Measure Axioms and the

set of universal sentences T h_{∀}(R).

One can readily check that every axiom of S(K, R) is a consequence of the pure randomization theory S, with the term P [φ(X⃗)] in place of P ([[φ(X⃗)]]). Therefore, for every model (K, B, R) of S, the reduct (K, R) to L(K, R) is a model of S(K, R). Atomlessness cannot be expressed directly because we no longer have variables for events. Instead, we combined the old Fullness and Atomless Axioms into a single scheme, the Witness Axioms. We proved this axiom scheme as a consequence of the theory S in Proposition 2.2. The next result shows that the three sorted theory S is a conservative extension of the eventless theory S(K, R) in a very strong sense.

Proposition 7.12 Every model (K, R) of S(K, R) has an expansion to a model (K, B, R) of S, and this expansion is unique up to isomorphism.

Proof: Consider a model (K, R) of S(K, R). Let ≡ be the equivalence relation on the set of sentences L(K, M) defined by

φ(X⃗) ≡ ψ(Y⃗) iff P [φ(X⃗) ⇔ ψ(Y⃗)] = 1.

The set of all ≡-equivalence classes forms a Boolean algebra B in the obvious way. Define the event mapping [[φ(⋯)]] by [[φ(X⃗)]] = φ(X⃗)/ ≡. The Boolean operations and constants of sort B are defined in the natural way so that the Boolean Axioms will hold. The probability function P : B → R is defined by the rule

P ([[φ(X⃗)]]) = P [φ(X⃗)].

It is routine to check that the three sorted structure (K, B, R) obtained in this way is a model of S, and that any other expansion of (K, R) to a model of S is isomorphic to (K, B, R). □

Theorem 7.13 (i) The theory S(K, R) admits quantifier elimination. (ii) For each M, the eventless randomization theory T (K, R) for M is complete. (iii) The theory U(K, R) is equivalent to the set of all universal consequences of

S(K, R).

Proof: We prove (i). Let φ(X⃗, r⃗) be a formula of L(K, R). By the Quantifier Elimination Theorem for S, there is a quantifier-free formula ψ(X⃗, r⃗) of L which is equivalent to φ(X⃗, r⃗) under S. The remaining difficulty is that the formula ψ may contain terms of sort B and thus not be a formula of L(K, R). Using the Boolean Axioms of S, the Boolean operations may be moved inside the [[⋯]] brackets and replaced by logical connectives. Similarly, the Boolean constants ⊤ and ⊥ may be replaced by terms [[θ]] where θ is a logically true or false sentence of L(M). Thus we may assume that every term of sort B which occurs in ψ has the form [[α(Y⃗)]] where α(y⃗) is a formula of L(M). An equation [[α(Y⃗)]] = [[β(Y⃗)]] between two such terms may be replaced by P ([[α(Y⃗) ⇔ β(Y⃗)]]) = 1. Then all occurrences of terms of sort B within ψ will be in terms of the form P ([[α(Y⃗)]]), which are in the language L(K, R). This transforms ψ into an equivalent quantifier-free formula θ of L(K, R), as required. □

References

[BN] B. Banaschewski and Evelyn Nelson. Boolean Powers as Algebras of Continuous Functions. Dissertationes Math. 179 (1980).

[CK] C.C.Chang and H. Jerome Keisler. Model Theory. North-Holland 1990.

[D] L. van den Dries. O-minimal Structures. Pp. 143-185 in Logic: From Foundations to Applications, ed. by W. Hodges et al, 1996, Oxford Press.

[DMM] L. van den Dries, A. Macintyre, and D. Marker. The Elementary Theory of Restricted Analytic Fields with Exponentiation. Ann. Math. 140 (1994), 183-205.

[DM] C.A.Drossos and G. Markakis. Boolean Powers and Stochastic Spaces. Math Slovaca vol. 44 no.1 (1994), pp. 1-19.

[En] E. Engeler. On Structures Defined by Mapping Filters. Math. Ann. 167 (1966), pp. 105-112.

[EK] S. Ethier and T. Kurtz. Markov Processes. Wiley (1986).

[F] D. Fremlin. Measure algebra, in Handbook of Boolean Algebras, Vol. 3, Ch. 22, pp. 877-980. Ed. by J. D. Monk, North-Holland 1989.

[G] H. Gaifman. Concerning Measures on First Order Calculi. Israel J. Math. 2 (1964), pp. 1-18.

[H] P. Halmos. Measure Theory. Van Nostrand 1950.

[HT] A. Horn and A. Tarski. Measures in Boolean Algebras. Trans. Amer. Math. Soc. 64 (1948), pp. 467-497.

[J] T. Jech. Boolean Valued Models. In Handbook of Boolean Algebras, Vol. 3, Ch. 27, pp. 1197-1211. Ed. by J. D. Monk, North-Holland 1989.

[Ka] Kappos, D. Probability Algebras and Stochastic Spaces. Academic Press 1969.

[Kc] A. S. Kechris. Classical Descriptive Set Theory. Springer-Verlag 1995.

[K] H. J. Keisler. Limit Ultrapowers. Trans. Amer. Math. Soc. 107 (1963), pp. 382-408.

[KPS] J. Knight, A. Pillay and C. Steinhorn. Definable Sets in Ordered Structures II. Trans. Amer. Math. Soc. 295 (1980), pp.593-605.

[Ma] R. Mansfield. The Theory of Boolean Ultrapowers. Ann. Math. Logic 2 (1971), pp. 297-323.

[My] D. Myers. Lindenbaum-Tarski Algebras, in Handbook of Boolean Algebras, Vol. 3, Ch. 26, pp. 1167-1195. Ed. by J. D. Monk, North-Holland 1989.

[S] D. Scott. Boolean Models and Non-standard Analysis. In Applications of Model Theory to Algebra, Analysis, and Probability. Ed. by W.A.J. Luxemburg, Holt, Rinehart and Winston, 1969.

[SK] D. Scott and P. Krauss. Assigning Probabilities to Logical Formulas. In Aspects of Inductive Logic, ed. by J. Hintikka and P. Suppes. North-Holland 1966, pp. 219-264.

[Sko] T. Skolem. Über die Nicht-Charakterisierbarkeit der Zahlenreihe mittels endlich order abzählbar unendlicht vieler Aussagen mit ausschliesslich Zahlenvariablen. Fund. Math. 23 (1934), pp. 150-161.

[Ta] A. Tarski. A Decision Method for Elementary Algebra and Geometry. Univ. of Calif. Press 1951, Second ed.

Mathematical Subject Classification, 1991:

Primary: 03C10, 03C65

Secondary: 03C20, 28A60, 60A05

Keywords: elimination, quantifier, random, probability