RANDOMIZATIONS OF MODELS AS METRIC STRUCTURES

ITAÏ BEN YAACOV AND H. JEROME KEISLER

Abstract. The notion of a randomization of a first order structure was introduced by Keisler in the paper Randomizations of Models, Advances in Math. 1999. The idea was to form a new structure whose elements are random elements of the original first order structure. In this paper we treat randomizations as continuous structures in the sense of Ben Yaacov and Usvyatsov. In this setting, the earlier results show that the randomization of a complete first order theory is a complete theory in continuous logic that admits elimination of quantifiers and has a natural set of axioms. We show that the randomization operation preserves the properties of being omega-categorical, omega-stable, and stable.

1. Introduction

In this paper we study randomizations of first order structures in the setting of continuous model theory. Intuitively, a randomization of a first order structure M is a new structure whose elements are random elements of M. In probability theory, one often starts with some structure M and studies the properties of random elements of M. In many cases, the random elements of M have properties analogous to those of the original elements of M. With this idea in mind, the paper Keisler [Kei99] introduced the notion of a randomization of a first order theory T as a new many-sorted first order theory. That approach pre-dated the current development of continuous structures in the paper Ben Yaacov and Usvyatsov [BU].

Here we formally define a randomization of a first order structure M as a continuous structure in the sense of [BU]. This seems to be a more natural setting for the concept. In this setting, the results of [Kei99] show that if T is the complete theory of M, the theory T^{R} of randomizations of M is a complete theory in continuous logic which admits elimination of quantifiers and has a natural set of axioms.

One would expect that the original first order theory T and the randomization theory T^{R} will have similar model-theoretic properties. We show that this is indeed the case for the properties of ω-categoricity, ω-stability, and stability. This provides us with a ready supply of new examples of continuous theories with these properties.

In Section 2 we define the randomization theory T^{R} as a theory in continuous logic, and restate the results we need from [Kei99] in this setting. In Section 3 we begin with a proof that a first order theory T is ω-categorical if and only if T^{R} is ω-categorical, and then we investigate separable structures.

Section 4 concerns ω-stable theories. In Subsection 4.1 we prove that a complete theory T is ω-stable if and only if T^{R} is ω-stable. In Subsection 4.2 we extend this result to the case where T has countably many complete extensions.

Section 5 is about stable theories and independence. Subsection 5.1 contains abstract results on fiber products of measures that will be used later. In Subsection 5.2 we develop some properties of stable formulas in continuous theories. In Subsection 5.3 we prove that a first order theory T is stable if and only if T^{R} is stable. We also give a characterization of independent types in T^{R}.

First author supported by ANR chaire d’excellence junior THEMODMET (ANR-06-CEXC-007) and by the Institut Universitaire de France.

Revision 945 of June 30, 2009.

In the paper [Bena] another result of this type was proved— that T^{R} is dependent (does not have the independence property) as a continuous theory if and only if T is dependent as a first order theory. In this paper we deal only with randomizations of first order structures, but it should be mentioned that randomizations of continuous structures have recently been developed in the papers [Bena] and [Benb].

We thank the participants of the AIM Workshop on the Model Theory of Metric Structures, held at Palo Alto CA in 2006, and Isaac Goldbring, for helpful discussions about this work.

2. Randomizations

In this section we will restate some notions and results from [Kei99] in the context of continuous structures.

We will assume that the reader is familiar with continuous model theory as it is developed in the papers [BU] and [BBHU08], including the notions of a structure, pre-structure, signature, theory, and model of a theory. A pre-model of a theory is a pre-structure which satisfies each statement in the theory. For both first order and continuous logic, we will abuse notation by treating elements of a structure (or pre-structure) M as constant symbols outside the signature of M. These constant symbols will be called parameters from M.

We will assume throughout this paper that T is a consistent first order theory with signature L such that each model of T has at least two elements.

The randomization signature for L is a two-sorted continuous signature L^{R} with a sort K of random elements, and a sort B of events. L^{R} has an n-ary function symbol ⟦φ(·)⟧ of sort K^{n} → B for each first order formula φ of L with n free variables, a [0, 1]-valued unary predicate symbol μ of sort B for probability, the Boolean operations ⊤, ⊥, ⊔, ⊓, ¬ of sort B, and distance predicates d_{K} and d_{B} for sorts K, B. All these symbols are 1-Lipschitz with respect to each argument.

We will use U, V, … to denote continuous variables of sort B. We will use x, y, … to denote either first order variables or continuous variables of sort K, depending on the context. Given a first order formula φ with n free variables, φ(\overline{x}) will denote the first order formula formed by replacing the free variables in φ by first order variables \overline{x}, and ⟦φ(\overline{x})⟧ will denote the atomic term in L^{R} formed by filling the argument places of the function symbol ⟦φ(·)⟧ with continuous variables \overline{x} of sort K.

When working with a structure or pre-structure (K, B) for L^{R}, A, B, C, … will denote elements or parameters from B, and f, g, … will denote elements or parameters from K. Variables can be replaced by parameters of the same sort. For example, if \overline{f} is a tuple of elements of K, ⟦φ(\overline{f})⟧ will be a constant term of L^{R} ∪ \overline{f} whose interpretation is an element of B.

We next define the notion of a randomization (K, B) of M. Informally, the elements B ∈ B are events, that is, measurable subsets of some probability space Ω, and the elements f ∈ K are random elements of M, that is, measurable functions from Ω into M. By “measure” we will always mean “σ-additive measure”, unless we explicitly qualify it as “finitely additive measure”.

Here is the formal definition. Given a model M of T, a randomization of M is a pre-structure (K, B) for L^{R} equipped with a finitely additive measure μ such that:

• (B, μ) comes from an atomless finitely additive probability space (Ω, B, μ).

• K is a set of functions f : Ω → M, i.e. K ⊆ M^{Ω}.

• For each formula ψ(\overline{x}) of L and tuple \overline{f} in K, we have

⟦ψ(\overline{f})⟧ = \{w ∈ Ω : M ⊧ ψ(\overline{f}(w))\}.

(It follows that the right side belongs to the set of events B.)

• For each B ∈ B and real ε > 0 there are f, g ∈ K such that μ(B△⟦f = g⟧) < ε, where △ is the Boolean symmetric difference operation.

• For each formula θ(x, \overline{y}) of L, real ε > 0, and tuple \overline{g} in K, there exists f ∈ K such that

μ(⟦θ(f, \overline{g})⟧△⟦(∃x θ)(\overline{g})⟧) < ε.

• On K, the distance predicate d_{K} defines the pseudo-metric

d_{K}(f, g) = μ⟦f ≠ g⟧.

• On B, the distance predicate d_{B} defines the pseudo-metric

d_{B}(B, C) = μ(B△C).

Note that the finitely additive measure μ is determined by the pre-structure (K, B) via the distance predicates.

A randomization (K, B) of M is full if in addition • B is equal to the set of all events ⟦ψ(\overline{f})⟧ where ψ(\overline{x}) is a formula of L and \overline{f} is a tuple in K.

• K is full in M^{Ω}, that is, for each formula θ(x, \overline{y}) of L and tuple \overline{g} in K, there exists f ∈ K such

that

⟦θ(f, \overline{g})⟧ = ⟦(∃x θ)(\overline{g})⟧.

It is shown in [BU] that each continuous pre-structure induces a unique continuous structure by identifying elements at distance zero from each other and completing the metrics. It will be useful to consider these two steps separately here. By a reduced pre-structure we will mean a pre-structure such that d_{K} and d_{B} are metrics. Then every pre-structure (K, B) induces a unique reduced pre-structure (\overline{K}, \overline{B}) by identifying elements which are at distance zero from each other. The induced continuous structure is then obtained by completing the metrics, and will be denoted by (K̂, B̂). We say that a prestructure (K, B) is pre-complete if the reduced pre-structure (\overline{K}, \overline{B}) is already a continuous structure, that is, (K̂, B̂) = (\overline{K}, \overline{B}). We say that (K, B) is elementarily pre-embeddable in (K′, B′) if (K̂, B̂) is elementarily embeddable in (K̂′, B̂′).

Note that for any pre-structure (K, B), (K̂, B̂) is elementarily equivalent to (K, B), and (K̂, B̂) is separable and only if (K, B) is separable.

In [Kei99], a randomization of M was defined as a three-sorted first order structure instead of a continuous two-sorted structure, with the value space [0, 1] replaced by any first order structure R whose theory is an expansion of the theory of real closed ordered fields which admits quantifier elimination. When R is the ordered field of reals, such a structure can be interpreted as a randomization in the present sense.

The paper [Kei99] gives axioms for a theory T^{R}, called the randomization theory of T, in three-sorted first order logic. We now translate these axioms into a theory in the (two-sorted) continuous logic L^{R} in the sense of [BU], with a connective for each continuous function [0, 1]^{n} ↦ [0, 1] which is definable in R. We use φ for arbitrary formulas of L and Φ for arbitrary formulas of the continuous logic L^{R}. Following [BU], we use the notation ∀x(Φ(x) ≤ r) for (sup_{x} Φ(x)) ≤ r, and ∃x(Φ(x) ≤ r) for (inf_{x} Φ(x)) ≤ r. Thus the existential quantifiers are understood in the approximate sense. We also use the notation U ≐ V for the statement d_{B}(U, V) = 0.

The axioms for the randomization theory T^{R} of a first order theory T are as follows:

Validity Axioms

∀\overline{x}(⟦ψ(\overline{x})⟧ ≐ ⊤)

where ∀\overline{x} ψ(\overline{x}) is logically valid in first order logic.

Boolean Axioms The usual Boolean algebra axioms in sort B, and the statements

∀\overline{x}(⟦(¬φ)(\overline{x})⟧ ≐ ¬⟦φ(\overline{x})⟧)
∀\overline{x}(⟦(φ ∨ ψ)(\overline{x})⟧ ≐ ⟦φ(\overline{x})⟧ ⊔ ⟦ψ(\overline{x})⟧)

∀\overline{x}(⟦(φ ∧ ψ)(\overline{x})⟧ ≐ ⟦φ(\overline{x})⟧ ⊓ ⟦ψ(\overline{x})⟧)

Distance Axioms

∀x∀y d_{K}(x, y) = 1 − μ⟦x = y⟧, ∀U∀V d_{B}(U, V) = μ(U△V)

Fullness Axioms (or Maximal Principle)

∀\overline{y}∃x(⟦φ(x, \overline{y})⟧ ≐ ⟦(∃xφ)(\overline{y})⟧)

As mentioned previously, the quantifiers should be understood in the approximate sense, so this axiom can also be written in the equivalent form

sup_{\overline{y}} inf_{x}(d_{B}(⟦φ(x, \overline{y})⟧, ⟦(∃xφ)(\overline{y})⟧)) = 0

Event Axiom

∀U∃x∃y(U ≐ ⟦x = y⟧)

Measure Axioms

μ[⊤] = 1 ∧ μ[⊥] = 0
∀U∀V(μ[U] + μ[V] = μ[U ⊔ V] + μ[U ⊓ V])

Atomless Axiom

∀U∃V(μ[U ⊓ V] = μ[U]/2)

Transfer Axioms

⟦φ⟧ ≐ ⊤

where φ ∈ T.

Theorem 2.1. ([Kei99], Theorem 3.10, restated). If T is complete, then T^{R} is complete.

Proposition 2.2. ([Kei99], Proposition 4.3, restated) Let T be the complete theory of M. Every randomization (K, B) of M is a pre-model of the randomization theory T^{R}.

Let (K, B) and (K′, B′) be pre-models of T^{R}. We say that (K, B) represents (K′, B′) if their corresponding reduced pre-structures are isomorphic.

Theorem 2.3. (First Representation Theorem) Let T be the complete theory of M. Every pre-model of T^{R} is represented by some randomization of M.

Proof. Let (K, B) be a pre-model of T^{R}. It follows from [Kei99], Corollary 6.6 and Theorem 5.7, that the reduced structure (\overline{K}, \overline{B}) of (K, B) is isomorphically embeddable in the reduced pre-structure of a randomization of M. Since (K, B) satisfies the Fullness and Event Axioms, (\overline{K}, \overline{B}) is isomorphic to the reduced pre-structure of a randomization of M. ■_{2.3}

Definition 2.4. A pre-model (K, B) of T^{R} has perfect witnesses if the existential quantifiers in the Fullness Axioms and the Event Axiom have witnesses in which the axioms hold exactly rather than merely approximately. That is,

Fullness: For each \overline{g} in K^{n} there exists f ∈ K such that

⟦φ(f, \overline{g})⟧ ≐ ⟦(∃xφ)(\overline{g})⟧.

Event: For each B ∈ B there exist f, g ∈ K such that B ≐ ⟦f = g⟧.

The first order models considered in [Kei99] are pre-models with perfect witnesses when viewed as metric structures.

Proposition 2.5. ([Kei99], Proposition 4.3, restated) Let T be the complete theory of M. Every full randomization (K, B) of M has perfect witnesses.

Theorem 2.6. (Second Representation Theorem) ([Kei99], Theorem 4.5, restated) Let T be the complete theory of M. Every pre-model of T^{R} with perfect witnesses is represented by some full randomization of M.

We now show that every model of T^{R} has perfect witnesses.

Theorem 2.7. For any first order theory T, every pre-complete model of T^{R} has perfect witnesses. In particular, every model of T^{R} has perfect witnesses.

Proof. Let (K, B) be a pre-complete model of T^{R}. We first show that (K, B) has perfect witnesses for the Fullness Axioms. Consider a first order formula φ(x, \overline{y}), and let \overline{g} be a tuple in K. Then for each n ∈ ω there exists f_{n} ∈ K such that

d_{B}(⟦φ(f_{n}, \overline{g})⟧, ⟦(∃xφ)(\overline{g})⟧) < 2^{−n}.

Using the Fullness Axioms, we can get a sequence h_{n} in K such that h_{1} = f_{1} and with probability at least 1 − 2^{−2n}, h_{n+1} agrees with h_{n} when φ(h_{n}, \overline{g}) holds, and agrees with f_{n+1} otherwise. Then

d_{B}(⟦φ(h_{n}, \overline{g})⟧, ⟦(∃xφ)(\overline{g})⟧) < 2^{−n} + 2^{−2n}

and

d_{K}(h_{n}, h_{n+1}) < 2^{−n} + 2^{−2n}.

Then the sequence h_{n} is Cauchy convergent with respect to d_{K}. By pre-completeness, h_{n} converges to an element h ∈ K with respect to d_{K}. It follows that

d_{B}(⟦φ(h, \overline{g})⟧, ⟦(∃xφ)(\overline{g})⟧) = 0,

as required.

It remains to show that (K, B) has perfect witnesses for the Event Axiom. Let B ∈ B. By the Event Axiom, for each n ∈ ω there exists f_{n}, g_{n} ∈ K such that μ[B△⟦f_{n} = g_{n}⟧] < 2^{−n}. Since every model of T has at least two elements, there must exist f′, g′ ∈ K such that ⟦f′ = g′⟧ ≐ ⊥. Taking perfect witnesses for the Fullness Axioms, we can obtain elements h_{n} ∈ K such that h_{n} agrees with f′ on ⟦f_{n} = g_{n}⟧, and h_{n} agrees with g′ on ⟦f_{n} ≠ g_{n}⟧. Then the sequence h_{n} is Cauchy convergent with respect to d_{K}, and hence converges to some h in K. It follows that B ≐ ⟦f′ = h⟧. ■_{2.7}

Corollary 2.8. Let T be the complete theory of M. Every pre-complete model of T^{R}, and hence every model of T^{R}, is represented by some full randomization of M.

Theorem 2.9. ([Kei99] Theorems 3.6 and 5.1, restated). For any first order theory T, the randomization theory T^{R} for T admits strong quantifier elimination.

This means that every formula Φ in the continuous language L^{R} is T^{R}-equivalent to a formula with the same free variables and no quantifiers of sort K or B (whereas ordinary quantifier elimination for continuous logic means that every formula can be arbitrarily well approximated by quantifier-free formulas). Note that for each first order formula φ(\overline{x}) of L, μ⟦φ(\overline{x})⟧ is an atomic formula of L^{R} which has no quantifiers. The first order quantifiers within φ(\overline{x}) do not count as quantifiers in L^{R}.

By the Event Axiom and Theorem 2.7, in a model of T^{R}, any element of sort B is equal to a term ⟦g_{1} = g_{2}⟧ with parameters g_{1}, g_{2} of sort K. Therefore, in all discussions of types in the theory T^{R}, we may confine our attention to types of sort K over parameters of sort K.

The space of first order n-types in T will be denoted by S_{n}(T). If T = T h(M) and A is a set of parameters in M, S_{n}(T (A)) is the space of first order n-types in T with parameters in A. The space of continuous n-types in T^{R} with variables of sort K will be denoted by S_{n}(T^{R}). We will use boldface letters p, q, … for types of sort K, and boldface A for a set of parameters of sort K. If (K, B) is a pre-model of T^{R} and A is a set of parameters in K, S_{n}(T^{R}(A)) is the space of continuous n-types in T^{R} with variables of sort K and parameters from A.

Recall from [BU] that for each p ∈ S_{n}(T^{R}) and formula Φ(\overline{x}) of L^{R}, we have (Φ(\overline{x}))^{p} ∈ [0, 1].

Let ℜ(S_{n}(T)) be the space of regular Borel probability measures on S_{n}(T). The next corollary follows from quantifier elimination and the axioms of T^{R}.

Corollary 2.10. For every p ∈ S_{n}(T^{R}) there is a unique measure ν_{p} ∈ ℜ(S_{n}(T)) such that for each formula φ(\overline{x}) of L,

ν_{p}(\{q : φ(\overline{x}) ∈ q\}) = (μ⟦φ(\overline{x})⟧)^{p}.

Moreover, for each measure ν ∈ ℜ(S_{n}(T)) there is a unique p ∈ S_{n}(T^{R}) such that ν = ν_{p}. Similarly for types with infinitely many variables.

We may therefore identify the type space S_{n}(T^{R}) with the space ℜ(S_{n}(T)).

Remark 2.11. In the special case that M is the trivial two-element structure with only the identity relation, the above results show that the continuous theory of atomless measure algebras is complete and admits quantifier elimination. (See [Kei99], Section 7A). This fact was given a direct proof in [BU].

Remark 2.12. Throughout this paper, we could have worked with a one-sorted randomization theory with only the sort K instead of a two-sorted theory with sorts K and B. In this formulation, we would use the results of Section 7C of [Kei99], where the sort B is eliminated. This approach will be taken at the end of Section 5.3. The main advantages of the event sort B are that it allows a nicer set of axioms for T^{R}, and makes it easier to describe the models of T^{R}.

3. Separable Structures

In this section we consider small randomizations of M. In order to cover the case that T has finite models, we adopt the following convention:

“M is countable” means that the cardinality of M is finite or ω.

So a complete first order theory T is ω-categorical if and only if it either has a finite model or has a unique model of cardinality ω up to isomorphism.

We first show that the randomization operation preserves ω-categoricity. We will use the following necessary and sufficient condition for a continuous theory to be ω-categorical.

Fact 3.1. ([BBHU08], Theorem 13.8). Let U be a complete continuous theory with a countable signature. Then U is ω-categorical if and only if for each n ≥ 1, every type in S_{n}(U) is realized in every model of U.

Theorem 3.2. Suppose T has a countable signature. Then T is ω-categorical if and only if T^{R} is ω-categorical.

Proof. Suppose that T is not ω-categorical. Then by the Ryll-Nardzewski Theorem, for some n there is an n-type q ∈ S_{n}(T) which is omitted in some countable model M of T. Then the type p ∈ S_{n}(T^{R}) such that ν_{p}({q}) = 1 is omitted in the separable pre-complete model (M^{[0,1]}, L), of T^{R}, so T^{R} is not ω-categorical.

Now suppose T is ω-categorical. Then T = T h(M) for some M. By Ryll-Nardzewski’s theorem, for each n the type space S_{n}(T) is finite. Let p ∈ S_{n}(T^{R}). By Corollary 2.10, ν_{p} ∈ ℜ(S_{n}(T)), and for each formula φ(\overline{x}) of L,

ν_{p}(\{q : φ(\overline{x}) ∈ q\}) = (μ⟦φ(\overline{x})⟧)^{p}.

Since S_{n}(T) is finite, for each q ∈ S_{n}(T) there is a formula φ_{q}(\overline{x}) of L such that q is the set of T - consequences of φ_{q}. Let (K′, B′) be a model of T^{R}. By Corollary 2.8, (K′, B′) is represented by some full pre-complete randomization (K, B) of M. By Fact 3.1, it suffices to show that p is realized in (K, B). By the axioms and pre-completeness, there are events B_{q}, q ∈ S_{n}(T) in B such that B_{q}, q ∈ S_{n}(T) partitions Ω and μ(B_{q}) = ν_{p}(\{q\}). Since (K, B) has perfect witnesses, for each q there is a tuple \overline{f}_{q} in K such that μ⟦φ_{q}(\overline{f}_{q})⟧ = 1. Using the Fullness and Event Axioms, there is a tuple \overline{f} in K which agrees with \overline{f}_{q} on B_{q} for each q ∈ S_{n}(T). It follows that \overline{f} realizes p in (K, B), as required. ■_{3.2}

We next give a method for constructing small models of T^{R}, and then introduce the notion of a strongly separable model of T^{R}.

Definition 3.3. Let (Ω, B, μ) be an atomless finitely additive probability space and let M be a structure for L.

A B-deterministic element of M is a constant function in M^{Ω} (which may be thought of as an element of M).

A B-simple random element of M is a B-measurable function in M^{Ω} with finite range.

A B-countable random element of M is a B-measurable function in M^{Ω} with countable range .

Example 3.4. ([Kei99], Examples 4.6 and 4.11))

(i) The set K_{S} of B-simple random elements of M is full, and (K_{S}, B) is a full randomization of M. (ii) The set K_{C} of B-countable random elements of M is full. If (Ω, B, μ) is a probability space (i.e.

is σ-additive) then (K_{C}, B) is a full pre-complete randomization of M.

We assume for the rest of this section that the signature L of T is countable

Note that when L is countable, every Borel probability measure on S_{n}(T) is regular. (This follows from [Hal50], page 228, and the fact that every open set in S_{n}(T) is a countable union of compact sets).

Definition 3.5. Let ([0, 1], L, λ) be the natural atomless Borel probability measure on [0, 1]. Given a model M of T, let (M^{[0,1]}, L) be the pre-structure whose universe of sort K is the set of L-countable random elements of M. A pre-model (K, B) of T^{R} is strongly separable if (K, B) is elementarily pre-embeddable in (M^{[0,1]}, L) for some countable model M of T.

Note that (M^{[0,1]}, L) is only a pre-structure, not a reduced pre-structure, because L has nonempty null sets.

Corollary 3.6. If M is a countable model of T, then (M^{[0,1]}, L) is a full randomization of M and is a strongly separable pre-complete model of T^{R}.

Proof. By Example 3.4 (ii). ■_{3.6}

Lemma 3.7. Consider a first order L-structure M. Suppose (Ω, B, μ) is a probability space and A is a subalgebra of B which is dense with respect to the distance predicate d_{B}(U, V) = μ(U△V). Then the set K_{S} of A-simple random elements of M is dense in the set K of B-countable random elements of M with respect to the distance predicate d_{K}. Therefore (K_{S}, A) and (K, B) induce the same continuous structure, and K̂_{S} = K̂.

Proof. By Example 3.4, (K_{S}, A) and (K, B) are full randomizations of M. Let f be an element of K with range {a_{n} : n ∈ ℕ}. Let ε > 0. Take n such that

μ ⟦ ⋁_{m<n}(f = a_{m})⟧ > 1 − ε/2.

For each m < n, let

B_{m} = {w : f(w) = a_{m}} ∈ B.

Then the sets B_{m} are disjoint and

μ [ ⋃_{m<n} B_{m}] > 1 − ε/2.

For each m < n, there is a set A_{m} ∈ A such that d_{B}(A_{m}, B_{m}) < ε/(4n^{2}). Let C_{m} = A_{m} \⋃_{k<m} A_{k}. Then C_{m} ∈ A, the sets C_{m} are disjoint, and one can check that d_{B}(C_{m}, B_{m}) < ε/(2n). There is an A-simple g ∈ K_{S} such that g(w) = a_{m} whenever m < n and w ∈ C_{m}. Then f(w) = g(w) whenever w ∈ B_{m} ∩ C_{m}, so

μ⟦f = g⟧ > 1 − ε,

and hence d_{K}(f, g) < ε. This shows that K_{S} is dense in K. ■_{3.7}

Corollary 3.8. Every strongly separable pre-model of T^{R} is separable.

Proof. Let (K, B) be a strongly separable pre-model of T^{R}, so that (K, B) is elementarily pre-embeddable in (M^{[0,1]}, L) for some countable model M of T. L has a countable dense subalgebra A. By Lemma 3.7, the set of A-simple random elements of M is a countable dense subset of M^{[0,1]} with respect to d_{K}. Therefore (M^{[0,1]}, L) is separable, and hence (K, B) is separable. ■_{3.8}

Lemma 3.9. Let T be complete, p ∈ S_{n}(T^{R}), and ν_{p} be the corresponding measure on S_{n}(T) defined in Corollary 2.10. Then p is realized in some strongly separable model of T^{R} if and only if there is a countable set C ⊆ S_{n}(T) such that ν_{p}(C) = 1.

Proof. Suppose p is realized in some strongly separable model of T^{R}. Then p is realized by an n-tuple \overline{g} in the pre-complete model (M^{[0,1]}, L) of T^{R} for some countable model M of T. Hence ν_{p}(C) = 1 where C is the set of types of elements of the range of \overline{g}.

Suppose ν_{p}(C) = 1 for some countable set C ⊆ S_{n}(T), and let M be a countable model of T which realizes each q ∈ C. Then p is realized in the strongly separable pre-model (M^{[0,1]}, L) of T^{R} by any tuple \overline{g} such that

λ(\{r : tp^{M}(\overline{g}(r)) = q\}) = ν_{p}(\{q\})

for each q ∈ C. ■_{3.9}

Example 3.10. (i) Let T be the first order theory with countably many independent unary relations P_{0}, P_{1}, …, and let p be the type in S_{1}(T^{R}) such that the events ⟦P_{n}(x)⟧, n ∈ ℕ are independent with respect to p. Then p is not realized in a strongly separable model of T^{R}, and hence T^{R} has separable models which are not strongly separable.

(ii) Let ℝ be the ordered field of real numbers, as a first order rather than continuous structure. Let K be the set of all Lebesgue measurable functions from [0, 1] into ℝ. By Proposition 4.12 in [Kei99], (K, L) is a full pre-complete randomization of ℝ. (K, L) is not separable, and the type of the identity function on [0, 1] in (K, L) is not realized in a strongly separable model.

Lemma 3.11. Let M be countable. Then M is ω-saturated if and only if (M^{[0,1]}, L) is ω-saturated as a continuous pre-structure.

Proof. Suppose first that M is not ω-saturated. Then there is a tuple \overline{a} in M, a countable elementary extension N of M, and an element b ∈ N such that the type of b in (N , \overline{a}) is not realized in (M, \overline{a}). By considering the types of the constant functions from [0, 1] to \overline{a} and b, we see that M^{[0,1]} is not ω-saturated.

Now suppose that M is ω-saturated. Let T be the complete theory of M and let K = M^{[0,1]}. It suffices to show that for each finite tuple \overline{g} in K, every type p ∈ S_{1}(T^{R}(\overline{g})) is realized in (K, L). Let \{\overline{b}_{n} : n < ω\} be the range of \overline{g} in M and let

B_{n} = \{r ∈ [0, 1] : \overline{g}(r) = \overline{b}_{n}\} = ⟦\overline{g} = \overline{b}_{n}⟧.

Note that B_{n}, n ∈ ω is a partition of [0, 1] in L, and

∑_{n} μ[B_{n}] = 1.

Since M is countable and ω-saturated, for each n there are countably many types q ∈ S_{1}(T (\overline{b}_{n})), and each of these types is realized by an element a_{q} in M. Let p ∈ S_{1}(T^{R}(\overline{g})). Let A be the set of all deterministic elements of K, and extend p to a type p′ in S_{1}(T^{R}(A ∪ \overline{g})). For each n and first order formula φ(x, \overline{b}_{n}), μ[⟦φ(x, \overline{b}_{n})⟧ ⊓ B_{n}] is a continuous formula with parameters in A ∪ \overline{g}. Let

α(φ, n) = (μ[⟦φ(x, \overline{b}_{n})⟧ ⊓ B_{n}])^{p′}

and for each q ∈ S_{1}(T (\overline{b}_{n})) let

β(q, n) = inf{α(φ, n) : φ ∈ q}.

Since S_{1}(T (\overline{b}_{n})) is countable for each n, we have

∑\{β(q, n) : q ∈ S_{1}(T (\overline{b}_{n}))\} = μ[B_{n}].

There is a function f ∈ K such that for each n and q ∈ S_{1}(T (\overline{b}_{n})),

μ{r ∈ B_{n} : f(r) = a_{q}} = β(q, n).

Then for each n and first order formula φ(x, b_{n}),

μ[⟦φ(f, \overline{g})⟧ ⊓ B_{n}] ≥ α(φ, n).

It follows that f realizes p in (K, L). ■_{3.11}

Theorem 3.12. Let T be complete. The following are equivalent.

(i) T has a countable ω-saturated model.

(ii) T^{R} has a separable ω-saturated model.

(iii) Every separable model of T^{R} is strongly separable.

Proof. (i) implies (ii) and (iii): Let M be a countable ω-saturated model of T and let K = M^{[0,1]}. Then (K, L) is strongly separable, and hence is separable by Corollary 3.8. By Lemma 3.11, (K, L) is ω-saturated, so (ii) holds. It follows that every separable model of T^{R} is elementarily pre-embeddable in the strongly separable pre-model (K, L), and hence is itself strongly separable. This proves (iii).

(ii) implies (i): Assume that (i) fails. Then for some n, S_{n}(T) is uncountable. For each q ∈ S_{n}(T) there is an n-type q′ in S_{n}(T^{R}) such that ν_{q′}({q}) = 1. Let (K, B) be an ω-saturated model of T^{R}. Each n-type q′ is realized by an n-tuple \overline{f}_{q} in (K, B). Suppose p, q ∈ S_{n}(T) and p ≠ q. Then ν_{p′}(\{q\}) = 0 and ν_{q′}({q}) = 1. By the First Representation Theorem 2.3, (K, B) is represented by a randomization of a model of T, so we may assume that (K, B) is already a randomization of a model of T. It follows that \overline{f}_{p} ≠ \overline{f}_{q} almost everywhere, and μ⟦\overline{f}_{p} ≠ \overline{f}_{q}⟧ = 1. Let d_{n} be the metric on K^{n} formed by adding the d_{K} distances at each coordinate. Then

d_{n}(\overline{f}_{p}, \overline{f}_{q}) ≥ μ⟦\overline{f}_{p} ≠ \overline{f}_{q}⟧ = 1.

Since S_{n}(T) is uncountable, we see that the metric space (K^{n}, d_{n}) is not separable. Therefore (K, d_{K}) is not separable, so (K, B) is not separable and (ii) fails.

(iii) implies (i). Again assume (i) fails and S_{n}(T) is uncountable. Then by enumerating the formulas of L one can construct a measure ν ∈ ℜ(S_{n}(T)) such that ν({q}) = 0 for each q ∈ S_{n}(T). By Corollary 2.10 we may take p ∈ S_{n}(T^{R}) such that ν_{p} = ν. By Lemma 3.9, p cannot be realized in a strongly separable model, but p can be realized in a separable model. Therefore (iii) fails. ■_{3.12}

4. ω-Stable Theories

In this section we continue to assume that the signature L of T is countable.

As explained in Section 2, when considering types in T^{R}, we may confine our attention to types of sort K over parameters of sort K. For each model (K, B) of T^{R} and set of parameters A ⊆ K, the d metric on the type space S_{1}(T^{R}(A)) is defined by

d(p, q) = inf{d_{K}(f, g): tp(f/A) = p and tp(g/A) = q in some (K′, B′) ≻ (K, B)}.

We say that the space S_{1}(T^{R}(A)) is separable if it is separable with respect to the d metric. Following [BBHU08], we say that T^{R} is ω-stable if S_{1}(T^{R}(A)) is separable for every model (K, B) of T^{R} and countable set A of parameters in K.

We show that if T has at most countably many complete extensions, then the randomization operation preserves ω-stability. We first take up the case that T is complete.

4.1. Complete Theories.

Theorem 4.1. A complete theory T is ω-stable if and only if T^{R} is ω-stable.

Proof. Assume T^{R} is ω-stable. Let M be an arbitrary countable model of T, let K = M^{[0,1]}, and let A be the set of deterministic elements of K. Then A is countable, so S_{1}(T^{R}(A)) is separable.

For each q ∈ S_{1}(T (M)) let q′ be the type in S_{1}(T^{R}(A)) such that for each first order formula φ(x, \overline{b}) with parameters in M,

(μ⟦φ(x, \overline{b})⟧)^{q′} = \begin{cases}1 & if φ(x, \overline{b}) ∈ q \\ 0 & otherwise \end{cases}

Then q ↦ q′ is a mapping from S_{1}(T (M)) into S_{1}(T^{R}(A)) such that p ≠ q implies d(p′, q′) = 1. Since S_{1}(T^{R}(A)) is separable, it follows that S_{1}(T (M)) is countable, so T is ω-stable.

Now assume that T is ω-stable. Then T has a countable saturated model M_{1}, and M_{1} has a countable elementary extension M_{2} which realizes every type in S_{1}(T (M_{1})). Let ([0, 1] × [0, 1], L ⊗ L, λ ⊗ λ) be the natural Borel measure on the unit square. Let B_{1} be the subalgebra of L ⊗ L generated by {B × [0, 1] : B ∈ L}, and let B_{2} = L ⊗ L. Let K_{1} and K_{2} be the sets of B_{1}-countable random elements of M_{1} and B_{2}-countable random elements of M_{2} respectively. Then (K_{1}, B_{1}) and (K_{2}, B_{2}) are full randomizations of M_{1} and M_{2} respectively. By Theorems 2.9 and 2.1, (K_{1}, B_{1}) is an elementary presubstructure of (K_{2}, B_{2}). By Lemma 3.11, (K_{1}, B_{1}) is ω-saturated. By Lemma 3.7, K_{2} has a countable dense subset. It therefore suffices to show that every type in S_{1}(T^{R}(K_{1})) is realized in (K_{2}, B_{2}).

Let p be a type in S_{1}(T^{R}(K_{1})). Let {q_{0}, q_{1}, …} be an enumeration of the countable set of types S_{1}(T (M_{1})), and let a_{n} realize q_{n} in M_{2}. It follows from the axioms of T^{R} that for each n, there is a unique (σ-additive) measure ν_{n} on L defined by

ν_{n}(B) = inf\{(μ[⟦φ(x, \overline{g})⟧ ⊓ B])^{p} : \overline{g} deterministic, φ(x, \overline{g}) ∈ q_{n}\}.

Then ν_{n} is absolutely continuous with respect to λ, and ν(B) = ∑_{n} ν_{n}(B) is a probability measure on L. By the Radon-Nikodym theorem, there is an L-measurable function f_{n} : [0, 1] → [0, 1] such that ν_{n}(B) = ∫_{B} f_{n}dλ. Define f ∈ K_{2} as follows. For (r, s) ∈ [0, 1] × [0, 1), let f(r, s) = a_{n} if and only if

∑_{k<n} f_{k}(r) ≤ s < ∑_{k≤n} f_{k}(r).

For r ∈ [0, 1] let f(r, 1) be some particular element of M, say f(r, 1) = a_{0}.

Consider a k-tuple \overline{g} in K_{1}. Let M_{1}^{k} = \{\overline{b}_{m} : m ∈ ω\}. For each r ∈ [0, 1] we have \overline{g}(r) ∈ \{\overline{b}_{m} : m < ω\}. Let B_{m} = \{r ∈ [0, 1] : \overline{g}(r) = \overline{b}_{m}\}. Then B_{m} ∈ L. For each m and n we have

ν_{n}(B_{m}) = ∫_{B_{m}} f_{n} dλ = (λ ⊗ λ){(r, s) : f(r, s) = a_{n} ∧ r ∈ B_{m}}.

By the definition of ν_{n}, for each first order formula φ(x, \overline{b}_{m}) ∈ q_{n},

ν_{n}(B_{m}) ≤ (μ[⟦φ(x, \overline{g})⟧ ⊓ B_{m}])^{p}.

It follows that f realizes p in (K_{2}, B_{2}). ■_{4.1}

Isaac Goldbring has noted that in the above proof,

ν_{n}(B) = (λ ⊗ λ){(r, s) : r ∈ B ∧ f(r, s) ⊧ q_{n}},

and hence

ν(B) = ∑_{n} ν_{n}(B) = (λ ⊗ λ)(B × [0, 1]) = λ(B).

Thus ν is the usual measure λ on L and does not depend on p.

Remark 4.2. In [Ben06] it is shown that the theory of atomless measure algebras in continuous logic is ω-stable. In view of Remark 2.11, in the case that M is the trivial two-element structure, Theorem 4.1 gives another proof of that fact. So Theorem 4.1 can be viewed as a generalization of the result that the theory of atomless measures is ω-stable.

4.2. Incomplete Theories. Let S_{0}(T) be the space of complete extensions of T. In this subsection we show that if S_{0}(T) is countable, then T is ω-stable if and only if T^{R} is ω-stable.

We first take a brief detour to state a generalization of the Second Representation Theorem 2.6 which shows that every model of T^{R} can be regarded as a continuous structure whose elements are random variables taking values in random models of T. A full randomization (K, B) of an indexed family ⟨M(w) : w ∈ Ω⟩ of models of T is defined in the same way as a full randomization of M except that K ⊆ Π_{w∈Ω}M(w).

Theorem 4.3. ([Kei99], Proposition 5.6 and Theorem 5.7, restated) A pre-structure (K′, B′) is a premodel of T^{R} with perfect witnesses if and only if it can be represented by some full randomization (K, B) of some indexed family ⟨M(w) : w ∈ Ω⟩ of models of T.

We now introduce countable convex combinations of pre-complete models of T^{R}. This construction will be used in proving that the randomization operation preserves ω-stability. Let S be a countable set, and let (S, B_{0}, μ_{0}) be a probability space where B_{0} is the power set of S. For each w ∈ S let (K(w), B(w)) be a pre-complete model of T^{R}. We then define ∫_{S}(K(w), B(w)) dμ_{0}(w) to be the pre-structure (K, B) such that K = Π_{w}K(w), B is the set of events with parameters in K, and for each tuple \overline{f} in K and first order formula φ(\overline{x}),

μ⟦φ(\overline{f})⟧ = ∫_{S} μ(w)⟦φ(\overline{f}(w))⟧ dμ_{0}(w).

The proof of the following lemma is routine.

Lemma 4.4. Let S, μ_{0}, and (K(w), B(w)) be as above, and let

(K, B) = ∫_{S}(K(w), B(w)) dμ_{0}(w).

(i) (K, B) is a pre-complete model of T^{R}.

(ii) If each (K(w), B(w)) is separable, then (K, B) is separable.

(iii) If each (K(w), B(w)) is ω-saturated, then (K, B) is ω-saturated.

(iv) If S_{1}(T^{R}(K(w))) is separable for each w ∈ S, then S_{1}(T^{R}(K)) is separable.

Theorem 4.5. Suppose that S_{0}(T) is countable. Then T is ω-stable if and only if T^{R} is ω-stable.

Proof. Assume T^{R} is ω-stable. Let M be an arbitrary countable model of T, let K = M^{[0,1]}, and let A be the set of deterministic elements of K. Then A is countable, so S_{1}(T^{R}(A)) is separable. By the argument used in the proof of Theorem 4.1, it follows that S_{1}(T (M)) is countable, so T is ω-stable.

Suppose T is ω-stable. Let S = S_{0}(T). Then each w ∈ S is a complete ω-stable theory which has a countable ω-saturated model M_{1}(w). By Theorem 2.1, each w^{R} is a complete extension of T^{R}. By Lemma 3.11 and Corollaries 3.6 and 3.8, w^{R} has a pre-complete separable ω-saturated model (K_{1}(w), B_{1}(w)). By Theorem 4.1, each w^{R} is an ω-stable theory. Therefore the type space S_{1}(w^{R}(K_{1}(w))) is separable.

Let (K, B) be a separable model of T^{R}. Let μ_{0} be the unique measure in ℜ(S) such that for each sentence φ of L and r ∈ [0, 1], if

(K, B) ⊧ μ⟦φ⟧ ≥ r

then μ_{0}({w ∈ S : w ⊧ φ}) ≥ r. The pre-models (K, B) and (K_{1}, B_{1}) assign the same measure to each sentence φ of L. Therefore by quantifier elimination, (K_{1}, B_{1}) is elementarily equivalent to (K, B).

By Lemma 4.4, (K_{1}, B_{1}) = ∫_{S}(K_{1}(w), B_{1}(w)) dμ_{0}(w) is an ω-saturated separable pre-complete model of T, and the type space S_{1}(T^{R}(K_{1})) is separable. Since (K, B) is separable, (K, B) is elementarily pre-embeddable in (K_{1}, B_{1}). Hence the type space S_{1}(T^{R}(K)) is separable. This shows that T^{R} is ω-stable. ■_{4.5}

5. Independence and Stability

5.1. Conditional expectations and fiber products of measures. We have seen earlier that types in the sense of T^{R} are measures on the type spaces of T. Here we will give a few results in an abstract measure-theoretic setting that will be useful later on.

Fact 5.1. Let (X, Σ_{X}) and (Y, Σ_{Y}) be two measurable spaces, π: X → Y a measurable function and let μ a probability measure on X. Let π̂(μ) = μ ∘ π^{−1} denote the image measure on Y.

Then for every f ∈ L^{p}(X, Σ_{X}, μ) there is a unique (up to equality a.e.) function g ∈ L^{p}(Y, Σ_{Y} , π̂(μ)) such that:

∫_{S} g dπ̂(μ) = ∫_{π^{−1}(S)} f dμ  ∀S ∈ Σ_{Y}

This unique function will be denoted g = 𝔼^{μ}[f|π]. The mapping 𝔼^{μ}[·|π] has all the usual properties of conditional expectation: it is additive, linear in the sense that 𝔼^{μ}[(h ∘ π) · f|π] = h · 𝔼^{μ}[f|π] for h ∈ L^{q}(Y, Σ_{Y} , π̂(μ)), satisfies Jensen’s inequality and so on.

Proof. Identical to the classical proof of the existence of conditional expectation. Indeed, the classical case is merely the one where the underlying sets X and Y are equal and π is the identity. ■_{5.1}

When the mapping π: X → Y is clear from the context we may write 𝔼^{μ}[·|Y] instead of 𝔼^{μ}[·|π]. Let us add assumptions. Now X and Y are compact Hausdorff topological spaces, equipped with their

respective σ-algebras of Borel sets, and π: X → Y is continuous (so in particular Borel measurable). Let ℜ(X) denote the set of regular Borel probability measures on X, and similarly ℜ(Y) and so on. Since π is continuous the image measure of a regular Borel measure is regular as well, so we have π̂: ℜ(X) → ℜ(Y).

Notation 5.2. For a continuous function φ: X → ℝ and μ ∈ ℜ(X) let us define

⟨φ, μ⟩ = ∫ φ dμ.

We equip ℜ(X) with the weak-∗ topology, namely with the minimal topology under which the mapping ⟨φ, ·⟩: μ ↦ ∫ φ dμ is continuous for every continuous φ: X → [0, 1] (equivalently, for every continuous φ: X → ℝ). It is a classical fact that this is a compact Hausdorff topology.

Fact 5.3 (Riesz Representation Theorem). The mapping μ ↦ ⟨·, μ⟩ defines a bijection between ℜ(X) and the positive linear functionals on C(X, ℝ) satisfying λ(1) = 1.

Proof. Rudin, [Rud66, Theorem 2.14]. ■_{5.3}

Equipping the space of positive functionals with the topology of point-wise convergence this bijection is a homeomorphism, whence the compactness of ℜ(X) follows easily.

Let us now consider a “conditional” variant of the functional ⟨φ, ·⟩. For ν ∈ ℜ(Y) let ℜ_{ν}(X) denote the fiber above ν. For a continuous φ: X → [0, 1] and μ ∈ ℜ_{ν}(X) let φ̂_{ν}(μ) = 𝔼^{μ}[φ|Y].

Lemma 5.4. Let φ: X → [0, 1] be a continuous function and ν ∈ ℜ(Y). Then φ̂_{ν}: ℜ_{ν}(X) → L^{1}(Y, ν) is continuous where L^{1}(Y, ν) is equipped with the weak topology. In other words, for every ψ ∈ L^{∞}(Y, ν) the mapping μ ↦ ∫_{Y} 𝔼^{μ}[φ|Y]ψ dν is continuous.

Proof. Let ψ ∈ L^{∞}(Y, [0, 1]), and let ε > 0 be given. Since ν is regular there is a continuous function ψ̃: Y → ℂ which is close in ν to ψ, i.e., such that ν{y: |ψ(y)−ψ̃(y)| > ε} < ε. Then for every measurable χ: Y → [0, 1]:

|∫_{Y} χψ dν − ∫_{Y} χψ̃ dν| < 2ε.

The product φ̃ = φ · ψ̃ ∘ π is continuous on X so μ admits a neighborhood

U = {μ′ ∈ ℜ_{ν}(X): |⟨φ̃, μ⟩ − ⟨φ̃, μ′⟩| < ε}.

We conclude observing that for every μ′ ∈ U

|∫_{Y} 𝔼^{μ}[φ|Y]ψ dν − ∫_{Y} 𝔼^{μ′}[φ|Y]ψ dν| < |∫_{Y} 𝔼^{μ}[φ|Y]ψ̃ dν − ∫_{Y} 𝔼^{μ′}[φ|Y]ψ̃ dν| + 4ε
= |⟨φ̃, μ⟩ − ⟨φ̃, μ′⟩| + 4ε < 5ε.  ■_{5.4}

Sometimes we will find ourselves in a situation where we have some constraints on a measure and we wish to decide whether there is a measure μ ∈ ℜ(X) satisfying these constraints. This will usually take the following form:

Proposition 5.5. Let X be a compact Hausdorff space, A ⊆ C(X, ℝ) any subset and λ_{0} : A → ℝ any mapping. Then the following are equivalent:

(1) There exists a measure μ ∈ ℜ(X) satisfying ⟨φ, μ⟩ ≤ λ_{0}(φ) for every φ ∈ A.

(2) Whenever {φ_{i}}_{i<ℓ} ⊆ A are such that ∑_{i<ℓ} φ_{i} ≥ n we also have ∑_{i<ℓ} λ_{0}(φ_{i}) ≥ n.

Proof. One direction is clear so we prove the other. Let S denote the set of all partial functions λ which satisfy the condition in the second item, noticing that it is equivalent to:

∑_{i<ℓ} α_{i}λ(φ_{i}) ≥ inf_{x∈X} ∑_{i<ℓ} α_{i}φ_{i}(x) for all {(α_{i}, φ_{i})}_{i<ℓ} ⊆ ℝ^{+} × dom(λ).

For λ ∈ S, ψ ∈ C(X, ℝ) and β ∈ ℝ define λ_{ψ,β} be the partial functional which coincides with λ except at ψ and satisfying λ_{ψ,β}(ψ) = β (so dom(λ_{ψ,β}) = dom(λ) ∪ {ψ}).

Given λ ∈ S and ψ ∈ C(X, ℝ) one can always find β such that λ_{ψ,β} ∈ S as well. For example, β = sup ψ will always do. The least such β is always given by:

λ̃(ψ) = sup {inf (ψ + ∑_{i<ℓ} α_{i}φ_{i}) − ∑_{i<ℓ} α_{i}λ(φ_{i}): {(α_{i}, φ_{i})}_{i<ℓ} ⊆ ℝ^{+} × dom(λ)} .

In particular if ψ ∈ dom(λ) then λ̃(ψ) ≤ λ(ψ). It is also immediate to check that:

λ̃(α) = α  α ∈ ℝ
λ̃(αψ) = αλ̃(ψ)  α ∈ ℝ^{+}
λ̃(ψ + ψ′) ≥ λ̃(ψ) + λ̃(ψ′)
λ̃(ψ + ψ′) ≤ λ(ψ) + λ(ψ′)  ψ, ψ′ ∈ dom(λ)

For λ, λ′ ∈ S say that λ ⪯ λ′ if dom(λ) ⊆ dom(λ′) and λ(φ) ≥ λ′(φ) for every φ ∈ dom(λ). By Zorn’s Lemma (S, ⪯) admits a maximal element λ ⪰ λ_{0}. By its maximality λ is total and satisfies λ̃(φ) = λ(φ).

It follows that λ(φ + ψ) = λ(φ) + λ(ψ) and that λ(αφ) = αλ(φ), first for α ≥ 0 and then for every α ∈ ℝ. Therefore λ is a linear functional, and it is positive as it belongs to S. Since in addition λ(1) = 1, it is necessarily of the form λ = ⟨·, μ⟩: φ ↦ ⟨φ, μ⟩ for some measure μ ∈ ℜ(X). Thus ⟨·, μ⟩ ⪰ λ_{0}, so μ is as desired. ■_{5.5}

One can also prove a conditional variant of Proposition 5.5 but such a result will not be required here. Instead, let us re-phrase Proposition 5.5 a little:

Proposition 5.6. Let X be a compact Hausdorff space, A ⊆ C(X, ℝ) any subset and λ_{0} : A → ℝ any mapping sending 1 ↦ 1. Then the following are equivalent:

(1) There exists a measure μ ∈ ℜ(X) satisfying ⟨μ, φ⟩ = λ_{0}(φ) for every φ ∈ A.

(2) Whenever {(φ_{i}, m_{i})}_{i<ℓ} ⊆ A × Z are such that ∑_{i<ℓ} m_{i}φ_{i} ≥ 0 we also have ∑_{i<ℓ} m_{i}λ_{0}(φ_{i}) ≥ 0.

Proof. One direction is clear. For the other observe that if φ, −φ ∈ A then necessarily λ_{0}(−φ)+λ_{0}(φ) = 0. We may therefore define λ_{1} whose domain is A ∪ −A by λ_{1}(φ) = λ_{0}(φ), λ_{1}(−φ) = −λ_{0}(φ). Then λ_{1} satisfies the conditions of the previous Proposition, and the corresponding measure μ is as desired. ■_{5.6}

Let us now consider fiber products of measures. Again we consider general measurable spaces (i.e., not necessarily topological) X = (X, Σ_{X}), Y = (Y, Σ_{Y}), Z = (Z, Σ_{Z}), equipped with measurable mappings π_{X}: X → Z, π_{Y} : Y → Z. Let X ×_{Z} Y denote the set theoretic fiber product:

X ×_{Z} Y = {(x, y) ∈ X × Y : π_{X}(x) = π_{Y} (y)}.

Let Σ_{0} = {A ×_{Z} B: A ∈ Σ_{X}, B ∈ Σ_{Y} } and let Σ_{X} ⊗_{Z} Σ_{Y} denote the generated σ-algebra on X ×_{Z} Y. The set X ×_{Z} Y is thereby rendered a measurable space with the canonical mappings to X and Y measurable (it is the measurable space fiber product).

Let μ and ν be probability measures on X and Y, respectively, with the same image measure on Z: π̂_{X}(μ) = π̂_{Y} (ν). For A ∈ Σ_{X} and B ∈ Σ_{Y} define:

(μ ⊗_{Z} ν)_{0}(A ×_{Z} B) = ∫_{Z} ℙ^{μ}[A|Z]ℙ^{ν}[B|Z] dπ̂_{X}(μ)
= ∫_{A} ℙ^{ν}[B|Z] ∘ π_{X} dμ
= ∫_{B} ℙ^{μ}[A|Z] ∘ π_{Y} dν.

It is not difficult to check that Σ_{0} is a semi-ring and that (μ⊗_{Z} ν)_{0} defined in this manner is a σ-additive probability measure on Σ_{0}. By Carathéodory’s theorem it extends to a σ-additive probability measure on a σ-algebra containing Σ_{0}, and in particular to Σ_{X} ⊗_{Z} Σ_{Y}. We will denote this fiber product measure by μ ⊗_{Z} ν. Its image measures on X and Y are μ and ν, respectively. If we let 𝔐(X) denote the collection of probability measures on X and so on we have obtained a mapping:

\begin{matrix}𝔐(X) ×_{𝔐(Z)} 𝔐(Y) & → & 𝔐 (X ×_{Z} Y) \\ (μ, ν) & ↦ & μ ⊗_{Z} ν \end{matrix}

Let us switch back to the topological setting, where all spaces are compact Hausdorff spaces equipped with the σ-algebras of Borel sets and the mappings are continuous. In particular we have ℜ(X) ×_{ℜ(Z)} ℜ(Y) ⊆ 𝔐(X) ×_{𝔐(Z)} 𝔐(Y). (Going through the construction one should be able to verify that if (μ, ν) ∈ ℜ(X) ×_{ℜ(Z)} ℜ(Y) then μ ⊗_{Z} ν is a regular measure on X ×_{Z} Y as well, but we will not need this observation.) Given a Borel function ρ: X ×_{Z} Y → [0, 1] we may define:

\begin{aligned}ρ̂: & ℜ(X) ×_{ℜ(Z)} ℜ(Y) & → & [0, 1] \\ & (μ, ν) & ↦ & 𝔼^{μ⊗_{Z}ν}[ρ] \end{aligned}

Lemma 5.7. Let X, Y and Z be compact Hausdorff spaces and X ×_{Z} Y defined as above. Let ρ: X ×_{Z} Y → [0, 1] be a Borel function.

Let us fix μ ∈ ℜ(X), letting η = π̂_{X}(μ), and assume we can find a countable family of Borel subsets X_{i} ⊆ X such that

(1) μ (⋃ X_{i}) = 1.

(2) For each i there is a continuous function ρ_{i}(y): Y → [0, 1] such that ρ(x, y) = ρ_{i}(y) for every

(x, y) ∈ X_{i} ×_{Z} Y. Then ρ̂(μ, ·): ℜ_{η}(Y) → [0, 1] is continuous.

Proof. We may assume that all the X_{i} are disjoint. Then:

ρ̂(μ, ν) = ∫ ρ d(μ ⊗_{Z} ν)

= ∑_{i∈I} ∫_{X_{i}×_{Z}Y} ρ d(μ ⊗_{Z} ν)

= ∑_{i∈I} ∫ ρ_{i} · ℙ^{μ⊗_{Z}ν}[X_{i} ×_{Z} Y |Y] dν

= ∑_{i∈I} ∫ 𝔼^{ν}[ρ_{i}|Z] · ℙ^{μ⊗_{Z}ν}[X_{i} ×_{Z} Y |Z] dη

= ∑_{i∈I} ∫ 𝔼^{ν}[ρ_{i}|Z] · ℙ^{μ}[X_{i}|Z] dη

Fixing i ∈ I, the mapping ℜ_{η}(Y) → L^{1}(Z, Σ_{Z}, η) defined by ν ↦ 𝔼^{ν}[ρ_{i}|Z] is continuous in the weak topology by Lemma 5.4. It follows that ν ↦ ∫ 𝔼^{ν}[ρ_{i}|Z] · ℙ^{μ}[X_{i}|Z] dη is continuous. Finally, the series above converges absolutely and uniformly so, whence the continuity of ν ↦ ρ(μ, ν). ■_{5.7}

Proposition 5.8. Let X, Y and Z be compact Hausdorff spaces and X ×_{Z} Y defined as above. Let ρ: X ×_{Z} Y → [0, 1] be any function. Assume that:

(1) The set X is covered by a countable family of Borel sets X = ⋃_{i∈ℕ} X_{i}.

(2) Each X_{i} is covered by a (possibly uncountable) family of relatively open subsets X_{i} = ⋃_{j∈J_{i}} G_{i,j}.

(3) For each pair (i, j) (where i ∈ ℕ and j ∈ J_{i}) there is a continuous function ρ_{i,j}: Y → [0, 1] such

that ρ(x, y) = ρ_{i,j}(y) for every (x, y) ∈ G_{i,j} ×_{Z} Y. Then ρ is Borel and for every η ∈ ℜ(Z) and μ ∈ ℜ_{η}(X), the mapping ρ̂(μ, ·): ℜ_{η}(Y) → [0, 1] is continuous.

Proof. We may assume that the X_{i} are all disjoint.

Restricted to G_{i,j} ×_{Z} Y, ρ is continuous. Since each G_{i,j} is relatively open in X_{i}, the set G_{i,j} ×_{Z} Y is relatively open in X_{i} ×_{Z} Y. Thus ρ restricted to X_{i} ×_{Z} Y is continuous for each i. Moreover, each X_{i} ×_{Z} Y is Borel in X ×_{Z} Y. If follows that ρ is Borel.

Now fix η ∈ ℜ(Z), μ ∈ ℜ_{η}(X). Fix again i ∈ ℕ. Since μ is regular, μ(X_{i}) is the supremum of μ(K) where K ⊆ X_{i} is compact. Each such K can be covered by finitely many of the G_{i,j}. Thus there is a countable family J_{i}^{0} ⊆ J_{i} such that μ(X_{i}) = μ (⋃_{j∈J_{i}^{0}} G_{i,j}). It follows that

μ ( ⋃_{i∈ℕ,j∈J_{i}^{0}} G_{i,j}) = 1.

Moreover each G_{i,j} is relatively open in a Borel set and therefore a Borel set itself. The conditions of the Lemma are therefore fulfilled. ■_{5.8}

5.2. Some reminders regarding stable formulas. Let T denote a first order theory. Let φ(x, y) be a stable formula in T. We may also assume that T eliminates imaginaries.

Since φ is stable, every φ-type over a model p̂ ∈ S_{φ}(M) is definable by a unique formula dp̂φ(y):

p̂(x) = {φ(x, b) ↔ dp̂φ(b)}_{b∈M}.

Let A ⊆ M denote an algebraically closed set, and we may assume that M is sufficiently saturated and homogeneous over A. Then for every complete type p ∈ S_{x}(A) there exists a unique φ-type p̂ ∈ S_{φ}(M) which is definable over A and compatible with p. The (unique) definition of p̂ is also referred to as the φ-definition of p, denoted d_{p}φ(y).

Now let A ⊆ M be any set, not necessarily algebraically closed, and p ∈ S_{x}(A). Let P̂ ⊆ S_{φ}(M) denote the set of global φ-types p̂ which are definable over acl(A) and compatible with p. Then P̂ is non-empty, finite, and Aut(M/A) acts transitively on P̂. We define a [0, 1]-valued continuous predicate ρ(p, y) by:

ρ(p, b) = \frac{|\{p̂ ∈ P̂: p̂ ⊢ φ(x, b)\}|}{|P̂|}.

We consider ρ(p, b) to be the probability that a randomly chosen non-forking φ-extension of p should satisfy φ(x, b).

Shelah’s notions of local rank R(·, φ) and multiplicity M(·, φ), both with values in ℕ∪{∞}, provide a more useful way to calculate ρ(p, b). For our purpose it will be more convenient to define the multiplicity of a partial type π(x) at each rank n, denoted M(·, φ, n).

(1) If π is consistent then R(π, φ) ≥ 0.

(2) Having defined when R(·, φ) ≥ n we define M(·, φ, n). We say that M(·, φ, n) ≥ m if there are types π(x) ⊆ π_{i}(x) for i < m such that for every i < j < m there is a tuple b_{ij} for which π_{i}(x) ∪ π_{j}(x′) ⊢ φ(x, b_{ij}) ↔ ¬φ(x′, b_{ij}), and in addition R(π_{i}, φ) ≥ n for all i < m.

(3) If M(π, φ, n) = ∞ then R(π, φ) ≥ n + 1.

The formula φ is stable if and only if R(π, φ) is always finite. If R(π, φ) = n then M(π, φ) = M(π, φ, n) is the φ-multiplicity of π. Notice that n < R(π, φ) ⟺ M(π, φ, n) = ∞ and n > R(π, φ) ⟺ M(π, φ, n) = 0.

If [π] ⊆ S_{φ}(M) denoted the (closed) set of global φ-types consistent with π then it is not difficult to check that R(π, φ) is precisely the Cantor-Bendixson rank of [π] in S_{φ}(M). Similarly, M(π, φ) is the Cantor-Bendixson multiplicity, namely the number of types in [π] of rank R(π, φ). In case p ∈ S_{x}(A) is a complete type then P̂ is precisely is set of φ-types of maximal Cantor-Bendixson rank n = R(p, φ) in [p], so M(p, φ) = |P̂|. The number of p̂ ∈ P̂ which contain some instance φ(x, b) is then precisely the number of types of rank n in [p(x) ∪ {φ(x, b)}], whereby:

ρ(p, b) = \frac{M(p ∪ \{φ(x, b)\}, φ, n)}{M(p, φ, n)}.

Finally, let ξ(x, ā) ∈ p be such that M(ξ(x, ā), φ, n) = M(p, φ, n), namely, such that [ξ(x, ā)] and [p] contain precisely the same types of rank n. Then we have:

ρ(p, b) = \frac{M(ξ(x, ā) ∧ φ(x, b), φ, n)}{M(ξ(x, ā), φ, n)}.

The value ρ(p, b) only depends on q(y) = tp(b/A), so it is legitimate to write ρ(p, q). We may rewrite p and q as p(x, A) and q(y, A), where W is a tuple of variables corresponding to A, p(x, W) ∈ S_{x,W} (T) and q(y, W) ∈ S_{y,W} (T) are complete types and p↾_{W} = q↾_{W} ∈ S_{W} (T). In other words, (p, q) ∈ S_{x,W} (T) ×_{S_{W} (T)} S_{y,W} (T). To avoid this fairly cumbersome notation let us write Σ_{x,y,W} for the fiber product S_{x,W} (T) ×_{S_{W} (T)} S_{y,W} (T).

Conversely, let (p, q) ∈ Σ_{x,y,W} be any pair in the fiber product and let A realize their common restriction to W. Then ρ(p(x, A), q(y, A)) only depends on (p, q) and not on the choice of A. In other words, ρ(p(x, W), q(y, W)) makes sense for every (p, q) ∈ Σ_{x,y,W}. Henceforth we will therefore consider ρ as a function ρ: Σ_{x,y,W} → [0, 1].

The next step is to show that ρ satisfies the assumptions of Proposition 5.8.

We define Ξ_{n,m} as the set of all formulas ξ(x, w̄) for which M(ξ(x, w̄), φ, n) ≥ m is impossible, namely such that for every choice of parameters ā in a model of T:

M(ξ(x, ā), φ, n) < m.

Clearly, if ξ ∈ Ξ_{n,(m+1)} then M(ξ(x, w̄), φ, n) ≥ m is equivalent to M(ξ(x, w̄), φ, n) = m.

Lemma 5.9. Let χ(x, t) be any formula. Then the property M(χ(x, t), φ, n) ≥ m is type-definable in t. In other words, there is a partial type π(t) such that for every parameter c:

M(χ(x, c), φ, n) ≥ m ⟺ π(c).

Proof. Standard. ■_{5.9}

Lemma 5.10. Assume that ξ(x, w̄) ∈ Ξ_{n,(m+1)}. Then there are formulas ξ̂_{n,m,ℓ}(y, w̄) for 0 ≤ ℓ ≤ m such that:

(1) The formulas {ξ̂_{n,m,ℓ}: 0 ≤ ℓ ≤ m} define a partition: one and only one of them holds for every b, ā in a model of T.

(2) Modulo M(ξ(x, w̄), φ, n) = m, the formula ξ̂_{n,m,ℓ}(y, w̄) defines the property M(ξ(x, w̄)∧φ(x, y), φ, n) = ℓ.

Proof. For 0 ≤ ℓ ≤ m let π_{ℓ}(w̄, y) be the partial type expressing that:

M(ξ(x, w̄) ∧ φ(x, y), φ, n) ≥ ℓ & M(ξ(x, w̄) ∧ ¬φ(x, y), φ, n) ≥ m − ℓ.

If ℓ < ℓ′ then π_{ℓ} ∧ π_{ℓ′} imply that M(ξ(x, w̄), φ, n) ≥ ℓ′ + m − ℓ > m contradicting the assumption on ξ. Thus {π_{ℓ}: 0 ≤ ℓ ≤ m} are mutually contradictory. We can therefore find formulas ξ̂_{n,m,ℓ} ∈ π_{ℓ} which contradict one another as ℓ varies from 0 to m. We may further replace ξ̂_{n,m,m} with ¬ ⋁_{ℓ<m} ξ̂_{n,m,ℓ} to achieve a partition. On the other hand, if M(ξ(x, ā), φ, n) = m and b is arbitrary then π_{ℓ}(ā, b) holds for precisely one 0 ≤ ℓ ≤ m, whence the second item. ■_{5.10} Lemma 5.11. Assume that ξ(x, w̄) ∈ Ξ_{n,(m+1)}. Then is a continuous predicate ξ̂_{n,m}(y, w̄) taking values in \{\frac{ℓ}{m}: 0 ≤ ℓ ≤ m\} such that modulo M(ξ(x, w̄), φ, n) = m:

ξ̂_{n,m}(y, w̄) = \frac{M(ξ(x, w̄) ∧ φ(x, y), φ, n)}{M(ξ(x, w̄), φ, n)}

Proof. This is just a re-statement of the previous Lemma. ■_{5.11}

We define:

P_{n,m}^{0}(x, W) = {¬ξ(x, w̄): w̄ ⊆ W, ξ ∈ Ξ_{n,m}}.

Lemma 5.12. Let p(x, W) = tp(a/A) (in a model of T). Then the following are equivalent: (1) M(p(x, A), φ, n) ≥ m.

(2) p(x, W) contains no member of Ξ_{n,m}.
(3) p(x, W) ⊇ P_{n,m}^{0}(x, W).

In other words, P_{n,m}^{0}(x, W) expresses that M(tp(x/W), φ, n) ≥ m.

Proof. The implications (i) ⟹ (ii) ⟺ (iii) are immediate. If M(p(x, A), φ, n) < m then the existence of a certain tree whose leaves satisfy p(x, A) is contradictory. By compactness this is due to some formula ξ(x, w̄) ∈ p(x, W) in which case ξ ∈ Ξ_{n,m}. ■_{5.12}

For ξ ∈ Ξ_{n,(m+1)} it is convenient to define:

P_{n,m}^{ξ}(x, W) = P_{n,m}^{0}(x, W) ∪ {ξ(x, w̄)}.

Let also:

P_{n,m} = ⋃_{ξ∈Ξ_{n,(m+1)}}[P_{n,m}^{ξ}] = [P_{n,m}^{0}] \ [P_{n,(m+1)}^{0}] ⊆ S_{x,W} (T).

This is the collection of types p(x, W) ∈ S_{x,W} (T) such that M(p(x, W), φ, n) = m. While it is in general neither open nor closed it is locally closed and therefore a Borel set. Thus family {P_{n,m}: n < ω, 1 ≤ m < ω} forms a countable partition of S_{x,W} (T) into Borel sets. On the other hand P_{n,m} is a union of relatively clopen subsets of the closed set [P_{n,m}^{0}]. Moreover, let (p, q) ∈ Σ_{x,y,W} and assume that p(x, W) ⊧ P_{n,m}^{ξ}(x, W), ξ(x, w̄) ∈ Ξ_{n,(m+1)}. Let ξ̂_{n,m}(y, w̄) be as in Lemma 5.11. Then ρ(p, q) = ξ̂_{n,m}(y, w̄)^{q}.

We have thus checked that ρ: Σ_{x,y,W} → [0, 1] satisfies the conditions of Proposition 5.8.

5.3. The main results. We continues with the same assumptions, namely that T is a classical first order theory and φ(x, y) a stable formula. We shall use boldface characters to denote objects of the randomized realm. Thus a model of T^{R} may be denoted M M M, a subset thereof A, a type p, and so on, while objects related to the original theory will be denoted using lightface as usual.

For our purposes here it will be more convenient to consider the theory T^{R} in a single-sorted language in which we have a predicate symbol ℙ[ψ(x̄)] for every formula ψ(x̄) in the original language. Each such predicate is definable in the two-sorted language given earlier by the identity ℙ[ψ] = μ(⟦ψ⟧). Moreover, T^{R} admits quantifier elimination in this language as well (for example, since the atomic formulas separate types).

Let us translate the conclusion of Proposition 5.8 applied to ρ to the situation at hand. First of all we know that ℜ(S_{x,W} (T)) = S_{x,W} (T^{R}) and so on, so:

ℜ(S_{x,W} (T)) ×_{ℜ(S_{W} (T))} ℜ(S_{y,W} (T)) = S_{x,W} (T^{R}) ×_{S_{W} (T^{R})} S_{y,W} (T^{R}).

Let A ⊆ M M M ⊧ T^{R} and let p(x, A) ∈ S_{x}(A). Let r(W) = tp(A), so p(x, W) lies in the fiber above r. Similarly, the fiber of S_{y,W} (T^{R}) lying above r can be identified with S_{y}(A). Then Proposition 5.8 says that the function ρ̂(p(x, A), ·): S_{y}(A) → [0, 1] is continuous. We may therefore identify it with an A-definable predicate:

ρ̂(p(x, A), b) := ρ̂(p, tp(b, A))

Proposition 5.13. Assume that b ∈ A. Then ρ̂(p(x, A), b) = ℙ[φ(x, b)]^{p(x,A)}. In other words, ρ̂(p(x, A), y) is the ℙ[φ]-definition of p(x, A).

Proof. Indeed, let q(x, W) = tp(b, A), and say that w_{0} ∈ W corresponds to b ∈ A. Then the measure q is concentrated on those types q(y, W) which satisfy y = w_{0}, and similarly the measure p⊗_{W} q on Σ_{x,y,W} is concentrated on those pairs (p, q) where q is such. For such pairs we have ρ(p, q) = 1 if p ⊧ φ(x, w_{0}) and zero otherwise, so

ρ̂(p(x, A), b) = 𝔼^{p⊗_{W} q}[ρ] = ℙ[φ(x, w_{0})]^{p} = ℙ[φ(x, b)]^{p(x,A)}.  ■_{5.13}

We now have everything we need in order to prove preservation of stability.

Theorem 5.14. If φ(x, y) is a stable formula of T then ℙ[φ(x, y)] is a stable formula of T^{R}. If T is a stable theory then so is T^{R}.

Proof. We have shown that if φ is stable then every ℙ[φ]-type is definable, so ℙ[φ] is stable as well. Assume now that T is stable. Then every atomic formula of T^{R} is stable, so every quantifier-free formula is stable, and by quantifier elimination every formula is stable. Therefore T^{R} is stable. ■_{5.14}

Given p(x, A) where A ⊆ M M M, define:

p̂(x) = {ℙ[φ(x, b)] = ρ̂(p(x, A), b): b ∈ M M M}.

Lemma 5.15. The set of conditions p̂(x) is a ℙ[φ]-type over M M M, i.e., p̂(x) ∈ S_{ℙ[φ]}(M M M). Moreover, it is consistent with p(x, A).

Proof. It is enough to prove the moreover part. For this matter, it is enough to show that for any finite tuple b̄ = b_{0}, …, b_{n_{1}} the following is consistent:

p(x, A) ∪ {ℙ[φ(x, b_{i})] = ρ̂(p(x, A), b_{i}): i < n_{1}}.

Let q(ȳ, W) = tp(b̄, A), q_{i} = tp(b_{i}, A). Then we need to prove that the following is consistent with T^{R}:

p(x, W) ∪ q(ȳ, W) ∪ {ℙ[φ(x, y_{i})] = ρ̂(p, q_{i}): i < n_{1}}. (1)

Given a sequence of formulas and integer numbers (χ_{k}, m_{k})_{k<ℓ} let [(χ_{k}, m_{k})_{k<ℓ}] denote the formula stating that ∑_{k<ℓ} m_{k}𝟙_{χ_{k}} ≥ 0 (this is indeed expressible by a first order formula). By Proposition 5.6, in order to show that (1) is consistent with T^{R} it is enough to check that:

T ⊧ [(φ(x, y_{i}), f_{i})_{i<n_{1}}, (ψ_{j}(x, w̄), g_{j})_{j<n_{2}}, (χ_{k}(ȳ, w̄), h_{k})_{k<n_{3}}]

⟹

∑_{i<n_{1}} f_{i}ρ̂(p, q_{i}) + ∑_{j<n_{2}} g_{j}ℙ[ψ_{j}(x, w̄)]^{p} + ∑_{k<n_{3}} h_{k}ℙ[χ_{k}(ȳ, w̄)]^{q} ≥ 0.

The sum can be rewritten as:

𝔼^{p⊗_{W} q} [ ∑_{i<n_{1}} f_{i}ρ(p, q↾_{x,y_{i},W}) + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q}] .

It will therefore be enough to show for every (p, q) ∈ Σ_{x,ȳ,W}:

∑_{i<n_{1}} f_{i}ρ(p, q↾_{x,y_{i},W}) + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q} ≥ 0

We may assume that q(ȳ, W) = tp(b̄, A) where b̄, A ⊆ M ⊧ T. Let P̂ ⊆ S_{φ}(M) be the set of φ-types compatible with p(x, A) and definable over acl(A). Then the left hand side becomes:

∑_{i<n_{1}} f_{i}ρ_{φ}(p(x, A), b_{i}) + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q}

= ∑_{i<n_{1}} f_{i} \frac{\{p̂ ∈ P̂: p̂ ⊢ φ(x, b_{i})\}}{|P̂|} + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q}

= \frac{1}{|P̂|} ∑_{p̂∈P̂} ( ∑_{i<n_{1}} f_{i}𝟙_{φ}(x, b_{i})^{p̂(x)} + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p(x,W)} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q(ȳ,W)})

It will therefore be enough to show that the sum inside the parentheses is positive for every p̂ ∈ P̂. Since p̂ is compatible with p(x, A) there is a complete type r̃(x, M) extending both. Let r(x, b̄, A) be its restriction to the parameters which interest us, where as usual r(x, ȳ, W) ∈ S_{x,ȳ,W} (T). Then we have:

∑_{i<n_{1}} f_{i}𝟙_{φ}(x, b_{i})^{p̂(x)} + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{p(x,W)} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{q(ȳ,W)}

= ∑_{i<n_{1}} f_{i}𝟙_{φ}(x, y_{i})^{r} + ∑_{j<n_{2}} g_{j}𝟙_{ψ_{j}}(x, w̄)^{r} + ∑_{k<n_{3}} h_{k}𝟙_{χ_{k}}(ȳ, w̄)^{r}.

Since r is a type of T this is indeed always positive. ■_{5.15}

Theorem 5.16. Assume φ is a stable formula of T, and let A ⊆ M M M ⊧ T^{R}. Then every ℙ[φ]-type over A is stationary. If T is stable then every type over A is stationary.

Proof. We have shown that if p(x) ∈ S_{x}(A) then there exists a ℙ[φ]-type p̂(x) ∈ S_{ℙ[φ]}(M M M) which is definable over A (rather than merely over acl(A)) and compatible with p. ■_{5.16}

Here A consists of random elements in sorts of T. The theory T^{R} necessarily introduces new imaginary sorts (even if T admits elimination of imaginaries) and types over elements from these new sorts need not be stationary.

In the course of the proof we have given an explicit characterization of the unique non forking extension of a type in T^{R}. Let us restate this characterization in a slightly modified fashion. First of all we observe that the entire development above goes through for a formula of the form φ(x, y, w̄) where w̄ ⊆ W is a fixed tuple of parameter variables (alternatively, we could name the tuple w̄ by new constants). Define ρ_{φ}: Σ_{x,y,W} → [0, 1] and ρ̂_{φ} accordingly.

Corollary 5.17. Let c, b, A ⊆ M M M. Then c | ⌣_{A} b if and only if for every ā ⊆ A with corresponding w̄ ⊆ W, and for every formula ℙ[φ(x, y, w̄)]:

ℙ[φ(c, b, ā)] = ρ̂_{φ}(tp(c, A), tp(b, A)).

References

[BBHU08] Itaï Ben Yaacov, Alexander Berenstein, C. Ward Henson, and Alexander Usvyatsov, Model theory for metric structures, Model theory with Applications to Algebra and Analysis, volume 2 (Zoé Chatzidakis, Dugald Macpherson, Anand Pillay, and Alex Wilkie, eds.), London Math Society Lecture Note Series, vol. 350, Cambridge University Press, 2008, pp. 315–427.

[Bena] Itaï Ben Yaacov, Continuous and random Vapnik-Chervonenkis classes, Israel Journal of Mathematics, to appear, arXiv:0802.0068.

[Benb] , On theories of random variables, submitted, arXiv:0901.1584.

[Ben06] , Schrödinger’s cat, Israel Journal of Mathematics 153 (2006), 157–191.

[BU] Itaï Ben Yaacov and Alexander Usvyatsov, Continuous first order logic and local stability, Transactions of the American Mathematical Society, to appear, arXiv:0801.4303.

[Hal50] Paul R. Halmos, Measure Theory, D. Van Nostrand Company, Inc., New York, 1950.

[Kei99] H. Jerome Keisler, Randomizing a model, Advances in Mathematics 143 (1999), no. 1, 124–158.

[Rud66] Walter Rudin, Real and complex analysis, McGraw-Hill, 1966.

Itaï Ben Yaacov, Université Claude Bernard – Lyon 1, Institut Camille Jordan, 43 boulevard du 11 novembre 1918, 69622 Villeurbanne Cedex, France

   URL: http://math.univ-lyon1.fr/~begnac/

H. Jerome Keisler, Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison WI 53706, U.S.A.

   URL: http://math.wisc.edu/~keisler/