PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 90(104) (2011), 1–11 DOI: 10.2298/PIM1104001M

BOREL SETS AND COUNTABLE MODELS

Žarko Mijajlović, Dragan Doder, and Angelina Ilić-Stepić

Communicated by Stevan Pilipović

Abstract. We show that certain families of sets and functions related to a countable structure 𝔸 are analytic subsets of a Polish space. Examples include sets of automorphisms, endomorphisms and congruences of 𝔸 and sets of the combinatorial nature such as coloring of countable plain graphs and domino tiling of the plane. This implies, without any additional set-theoretical assumptions, i.e., in ZFC alone, that cardinality of every such uncountable set is 2^{ℵ_{0}} .

1. Introduction

Works of Kueker [6], Reyes [10], Barwise [1], Makkai [8] and others, show that certain sets S of model-theoretic objects related to a countable structure 𝔸, as Aut𝔸 for example, behave as analytic subsets of the Cantor discontinuum. Here we present a method for coding some notions related to countable first-order structures by theories of propositional calculus L_{ω_{1}} . After that, we consider countable models and we discus the topological and cardinal properties of the set of valuations satisfying a formula of the infinitary logic L_{ω_{1} ω} . Finally, we transfer those considerations to the models that are not necessarily countable. Then, we use the Suslin theorem on the cardinality of analytic subsets in a Polish space, to derive various known theorems in a uniform way.

Let X be a Polish space. The family of the Borel subsets of X is the smallest σ algebra on P (X) which contains closed subsets of X. Analytic sets are continuous images of Borel sets. The following theorem, see [9], will have the important role in the following considerations.

Theorem 1.1 (Suslin). Let X be an infinite analytic subset of a Polish space. Then either |X| = ℵ_{0} or |X| = 2^{ℵ_{0}} .

2010 Mathematics Subject Classification: Primary: 03C07.

Partially supported by Ministarstvo prosvete i nauke Republike Srbije, projects ON174026 and III44006.

We will say that a collection X satisfies CH (Continuum hypothesis) if every uncountable member S of X has the cardinality of continuum, 2^{ℵ_{0}} . In proofs that X satisfies CH, the idea of our approach is to interpret the members S of X by analytic subsets of Cantor space, or more generally of a Polish space.

2. Coding into L_{ω_{1}}^{P}

In this section we present a method for coding the first order properties of countable structures by valuations of the sentences of the infinitary propositional logic L_{ω_{1}} . Let us first review some definitions and notions of this logic.

The logic L_{ω_{1} ω} is an extension of the classical first order predicate logic L_{ωω} . Besides the usual logical symbols it admits also countable conjunctions (⋀ ) and disjunctions (⋁ ), see [4]. For instance, if the language contains countably many constant symbols c_{n}, n ∈ ω, then the formula of this logic ∀x ⋁ _{n∈ω} x = c_{n} asserts that the domain of the structure is at most countable. On the other hand, the logic L_{ω_{1}}^{P} is an extension of the classical propositional calculus with particular set of propositional letters P which allows countable conjunctions and disjunctions. The set of formulas F_{cP} of L_{ω_{1}}^{P} is defined by recursion as follows:

F_{0} = P,
F_{n+1} = F_{n} ∪ {¬φ | φ ∈ F_{n}} ∪ { ⋀ S | S ∈ [F_{n}]^{⩽ω} } ∪ { ⋁ S | S ∈ [F_{n}]^{⩽ω} },
F_{cP} = ⋃_{n∈ω} F_{n}.

Here, the symbol [X]^{⩽ω} denotes the set of at most countable subsets of X. If S = {φ_{n} | n ∈ ω}, then ⋀ S and ⋁ S are denoted also by ⋀ _{n∈ω} φ_{n} and ⋁ _{n∈ω} φ_{n} respectively. A map μ : P ↦ 2 is called a valuation and the value of the formula in the valuation μ is defined by induction on complexity of formulas as follows:

p[μ] = μ(p), p ∈ P,

(⋀ _{n∈ω} φ_{n})[μ] = ∏ _{n∈ω} φ_{n}[μ], where ∏ _{n∈ω} φ_{n}[μ] is an infimum of the set

{φ_{n}[μ] | n ∈ ω} in the boolean algebra 2 = (2, ·, +,′, 0, 1),

(⋁ _{n∈ω} φ_{n})[μ] = ∑ _{n∈ω} φ_{n}[μ], where ∑ _{n∈ω} φ_{n}[μ] is a supremum of the set

{φ_{n}[μ] | n ∈ ω} in 2,
(¬φ)[μ] = φ[μ]′.

Therefore we have defined for each formula φ a function φ̂ : 2^{c}P → 2 such that φ̂(μ) = φ[μ] for all μ : cP → 2. If φ is finite, observe that φ̂ is a continuous function. We say that a valuation μ is a model of the formula φ if φ̂(μ) = 1. Let us assume discrete topology on the set 2. Then 2^{P} is the Cantor space and its domain is the set of all valuations of the propositional variables, i.e., models of the propositional calculus. Since φ̂ is a Borel function, the set 𝔐(φ) of all models of φ is a Borel subset of the Cantor space 2^{P}. Thus we proved

Theorem 2.1. Assume T is a theory in L_{ω_{1}}^{P} over a countable set cP of propositional letters. Then 𝔐(T) is a Borel subset of the Cantor space 2^{P}.

By Theorem 1.1 we have immediately

Corollary 2.1. CH holds for 𝔐(φ).

The essence of the method we are proposing now is based on the Corollary and is stated as follows: Let X be a class of certain sets. If every X ∈ X is coded by a set of all models of a theory of L_{ω_{1}}^{P} , then CH is true for a class X.

2.1. Map ∗. Let 𝔸 = (A, …) be a countable first-order structure of a countable language L, L_{A} = L ∪ \{\underline{a} | a ∈ A\}, and (𝔸, a)_{a∈A} the simple expansion of 𝔸 to L_{A}. We define the set cP of propositional letters as

cP = {p_{F,a_{1} ,...,a_{n} ,b} | a_{i}, b ∈ A, F is a function symbol of L}
∪ {q_{R,a_{1} ,...,a_{n}} | a_{i} ∈ A, R is a relation symbol of L}.

The map ∗ from the set Sent_{L_{A}} of all L_{ω_{1} ω} -sentences of L_{A} into the set of infinitary propositional formulas of L_{ω_{1}}^{P} over the set P is defined recursively as follows:

(F (\underline{a}_{1}, …, \underline{a}_{n}) = \underline{b})^{∗} = p_{F,a_{1} ,...,a_{n} ,b} ,

(R(\underline{a}_{1}, …, \underline{a}_{n}))^{∗} = q_{R,a_{1} ,...,a_{n}} ,
(¬θ)^{∗} = ¬θ^{∗}, (⋀ _{n∈ω} θ_{n})^{∗} = ⋀ _{n∈ω} θ_{n}^{∗}, (⋁ _{n∈ω} θ_{n})^{∗} = ⋁ _{n∈ω} θ_{n}^{∗},
(∀xθ)^{∗} = ⋀ _{a∈A} θ(\underline{a})^{∗}, (∃xθ)^{∗} = ⋁ _{a∈A} θ(\underline{a})^{∗},
(F (t_{1}(\underline{a}_{i1}, …, \underline{a}_{im} ), …, t_{n}(\underline{a}_{i1}, …, \underline{a}_{im} )) = \underline{b})^{∗} =
⋀ _{(b_{1} ,...,b_{n} )∈A^{n}} (⋀ _{i=1}^{n} (\underline{b}_{i} = t_{i}(\underline{a}_{i1}, …, \underline{a}_{im} ))^{∗} → p_{F,b_{1} ,...,b_{n} ,b}),
(R(t_{1}(\underline{a}_{i1}, …, \underline{a}_{im} ), …, t_{n}(\underline{a}_{i1}, …, \underline{a}_{im} )))^{∗} =
⋀ _{(b_{1} ,...,b_{n} )∈A^{n}} ((⋀ _{i=1}^{n} t_{i}(\underline{a}_{i1}, …, \underline{a}_{im} ) = \underline{b}_{i})^{∗} ∧ q_{R,b_{1} ,...,b_{n}} ).

Theorem 2.2. Let 𝔸 = (A, …) be a countable model of a countable language L, L′ is a countable expansion of L and T be a theory of L′ in L_{ω_{1} ω} . Then the set of all L′-expansions 𝔸′ of 𝔸 that are models of T is coded by a Borel subset of the Cantor space.

Proof. With the notation as above, let T^{∗} = {φ^{∗} | φ ∈ T }. Then 𝔐(T^{∗}) = ⋂ _{φ∈T} 𝔐(φ^{∗}) is a Borel set as a countable intersection of Borel sets. It remains to see that there is a one-to-one and onto correspondence between valuations that are the models of T^{∗} and expansions 𝔸′ of 𝔸 in L′ that are models of T. The function h which assigns to each μ ∈ 𝔐(T^{∗}) an expansion h(μ) = 𝔸_{μ} of 𝔸 is defined as follows:

If F ∈ L′ is a function symbol, then

F^{𝔸_{μ}} (a_{1}, …, a_{n}) = b iff (F (\underline{a}_{1}, …, \underline{a}_{n}) = \underline{b})[μ] = 1,
i.e., F^{𝔸_{μ}} (a_{1}, …, a_{n}) = b iff μ(p_{F,a_{1} ,...,a_{n} ,b} ) = 1.

If R ∈ L′ is a predicate symbol, then

R^{𝔸_{μ}} (t_{1}, …, t_{n}) iff (R(\underline{t}_{1}, …, \underline{t}_{n}))[μ] = 1,
i.e., R^{𝔸_{μ}} (t_{1}, …, t_{n}) iff μ(q_{R,t_{1} ,...,t_{n}} ) = 1.

By induction on the complexity of the formula φ, it is easy to prove that 𝔸_{μ} is a model of T and if μ ≠ ν, then 𝔸_{μ} ≠ 𝔸_{ν}. Hence the mapping h is one-to-one. Conversely, let 𝔸′ be an L′-expansion of 𝔸 that is a model of T. Then we define a valuation μ_{𝔸′} of as follows:

μ_{𝔸′}(p_{F,a_{1} ,...,a_{n} ,b} ) = 1 iff 𝔸′ ⊧ F (\underline{a}_{1}, …, \underline{a}_{n}) = \underline{b}.
μ_{𝔸′}(q_{R,t_{1} ,...,t_{n}} ) = 1 iff 𝔸′ ⊧ R(t_{1}, …, t_{n}).

Since 𝔸′ is a model of T, μ_{𝔸′} is a model of T^{∗}, i.e., h(μ_{𝔸′}) = 𝔸′. Thus h is onto. The mapping c = h^{−1} codes expansions 𝔸′ and this proves the theorem. □

Under the assumptions of the previous theorem by Suslin’s theorem we have immediately the following

Corollary 2.2. If the set of all L′-expansions 𝔸′ of 𝔸 that are models of T is uncountable, then it has the cardinality 2^{ℵ_{0}} .

From Theorem 2.2 we can easily deduce a variant of Makkai’s theorem [8, Theorem 9.1.]. Let ψ be a Σ_{1}^{1} sentence of the logic L_{ω_{1} ω} , i.e., ψ is a second order formula of the form ∃R̄φ(R̄), where φ(R̄) is of L_{ω_{1} ω} in a language L ∪ {R̄}, R̄ is a finite or infinite set of predicate (and/or function) symbols not belonging to L.

Theorem 2.3. Let 𝔸 = (A, …) be a countable model of a countable language L, L′ is a countable expansion of L and ψ = ∃R̄φ(R̄) be a Σ_{1}^{1} sentence of L′ in L_{ω_{1} ω} (the sequence R̄ does not belong to L′). Then the set of all L′-expansions 𝔸′ of 𝔸 that are models of ψ is coded by an analytic subset of the Cantor space.

Proof. Let S be the set of all expansions 𝔸′′= (𝔸′, R̄) that satisfy the sentence φ(R̄), where 𝔸′ is an expansion of 𝔸 to the language L′. By Theorem 2.2, S is coded by a Borel subset B of 2^{cP}, where cP is the set of propositional letters introduced by the inductive definition of the map ∗. Let cP_{1} be the set of propositional letters in cP which do not contain in their indices the symbols which occur in the block ∃R̄ and cP_{2} be the set of propositional letters in cP which do contain in their indices the symbols which occur in the block ∃R̄. Hence cP = cP_{1} ∪ cP_{2} and cP_{1} ∩ cP_{2} = ∅. So, B is a Borel subset of 2^{cP ^{1}} × 2^{cP ^{2}} and its projection B′ to 2_{1}^{cP} is the code set of S′, the set of all expansions 𝔸′ satisfying ψ. Hence B′ is the analytic subset of B. □

2.2. Examples. Though some of the following examples can be seen as special cases of Theorem 2.2, for the sake of simplicity we will give a direct application of ∗. Also, we believe that in this way certain combinatorial problems are easier to be coded directly.

Example 2.1 (Kueker’s theorem, revisited). Let 𝔸 = (A, …) be a countable algebra of a countable language L. We shall show that CH is true for the number of automorphisms of 𝔸, see [6]. First, we describe the suitable propositional theory that codes the notion of an automorphism of the model 𝔸.

Let f ∈ Aut𝔸 and P = {p_{ab} | a, b ∈ A} be a set of propositional letters. Here, p_{ab} intuitively means that f(a) = b, or, more formally, according to definition of the map ∗, (f(a) = b)^{∗} = p_{ab}. The theory T that we shall define now will exactly describe this situation. The theory T is defined as follows:

– T_{1} = {¬(p_{ab_{1}} ∧ p_{ab_{2}} ) | b_{1} ≠ b_{2}, a, b_{1}, b_{2} ∈ A}.

Observe that 𝔐(T_{1}) = ⋂ _{φ∈T_{1}} φ̂^{−1} [1], so 𝔐(T_{1}) is a closed subset of the Cantor space 2^{P}. Also observe that T_{1} codes the notion of the function.

– T_{2} = {⋁ _{b}φ_{ab} | a ∈ A}, where φ_{ab} = p_{ab}.

Note that 𝔐(T_{2}) = ⋂ _{a} ⋃ _{b} φ̂_{ab}^{−1} [1], thus 𝔐(T_{2}) is G_{δ} in 2^{P}. Also note that T_{2} says that A is the domain of a function.

– T_{3} = {¬(p_{a_{1} b} ∧ p_{a_{2} b}) | a_{1} ≠ a_{2}, a_{1}, a_{2}, b ∈ A}.

It is easy to see that 𝔐(T_{3}) is closed in 2^{P}. Observe that T_{3} codes the notion of injection.

– T_{4} = {⋁ _{a} p_{ab} | b ∈ A}.

Similarly as in the case of the set of all models of T_{2}, 𝔐(T_{4}) is G_{δ} subset of 2^{P}. Note that T_{4} codes the notion of surjection.

– Let F be an n-ary function symbol of L. Define the theory T_{F} by

T_{F} = {¬(p_{a_{1} b_{1}} ∧ ⋯∧ p_{a_{n} b_{n}} ) ∨ p_{F^{𝔸}(a_{1} ,...,a_{n} )F^{𝔸}(b_{1} ,...,b_{n} )} | a_{i}, b_{j} ∈ A}

and define T_{5} by T_{5} = ⋃ _{F} T_{F}. Clearly, 𝔐(T_{5}) is F_{σ} in 2^{P}. Finally, let us remark that T_{5} provides the compatibility of the function f with the operation F. Then the theory T_{5} says that f is an endomorphism of the algebra 𝔸.

Let T = T_{1}∪⋯ ∪ T_{5}. We see that the theory T says that f is an automorphism of the algebra 𝔸. Hence, 𝔐(T) = ⋂ _{i=1}^{5} 𝔐(T_{i}) is a Borel subset of 2^{P} since it is a finite intersection of Borel sets. Therefore CH holds for 𝔐(T).

Finally, the map H : 𝔐(T) → Aut𝔸 defined by H(μ)(a) = b iff μ(p_{ab}) = 1 is a bijection, thus the number of automorphisms of an countable algebra satisfies CH. If 𝔸 is an countable algebra with relations, i.e., a model of the first order predicate calculus, a similar proposition holds for Aut𝔸. It is obtained by adding to the theory T the set of appropriate axioms for relation symbols of the language of the model 𝔸.

Example 2.2 (Graph coloring). A graph is a pair (Γ, R), where Γ is a nonempty set and R is a binary relation on Γ. We say that the elements of the set Γ are nodes of the graph. If a and b are nodes and if a R b is true, then we say that nodes a and b are connected.

It is well known that there is a coloring of nodes of a countable planar graph in four colors such that connected nodes are colored in different colors. We will show that the number of such colorings satisfies CH.

Let P = {p_{ab} | a, b ∈ Γ} ∪ {q_{a}^{n} | a ∈ Γ, n ∈ 4}, where p_{ab} means that nodes a and b are connected ((aRb)^{∗} = p_{ab}), and q_{a}^{n} means that the node a is colored in n-th color((R_{i}(a))^{∗} = q_{a}^{i}, where R_{i} is the relation “i-th color"). We define the theory T as follows:

T_{1} = {⋁ _{n∈4} q_{a}^{n} | a ∈ Γ}, T_{2} = {¬q_{a}^{m} ∨ ¬q_{a}^{n} | a ∈ Γ, m, n ∈ 4, m ≠ n}, T_{3} = {¬p_{ab} ∨ ¬q_{a}^{n} ∨ ¬q_{b}^{n} | a, b ∈ Γ, n ∈ 4}, T = T_{1} ∪ T_{2} ∪ T_{3}.

Notice that each model of the theory T defines a unique coloring of the graph (Γ, R) in four colors, and vice versa, each coloring defines a unique model of the theory T. Thus the number of such colorings is equal to the number of models of the theory T, so it satisfies CH.

Example 2.3 (Wang dominoes). This example is connected with the problem of domino tiling of a plane [11], see also [5, Vol. , pp. 381–384]. Suppose we have countably many dominoes, where each domino is a unit square divided into four triangles by its diagonals and each triangle is enumerated by some natural number.

The type of the domino is a quadruple of natural numbers (a, b, c, d), where a is a label of the lower triangle, b is a label of the left triangle, c is a label of the upper triangle and d is a label of the right triangle. Let S be a finite set of domino types.

We cover the plane by dominoes as follows: The vertices of dominoes should have integers as coordinates. The position of a domino are coordinates of the upper right vertex. We combine dominoes in the usual way. Using the Transfer Principle from the nonstandard analysis we can show that the existence of a covering of the first quadrant implies existence of a covering of the entire plane. Namely, suppose that there is a covering of the first quadrant. Then, by the Transfer Principle, there is a covering of the nonstandard first quadrant. If H is an infinite nonstandard positive integer, then any covering of the galaxy of (H, H) is also a covering of the standard plane. Now we shell discuss the number of these coverings.

Let P = {p_{abcd}^{m,n} | (a, b, c, d) ∈ S, m, n ∈ ω} be the set of propositional letters, where p_{abcd}^{m,n} means “the domino of the type (a, b, c, d) is on the position (m, n)". The suitable propositional theory T which will describe the covering of the plane is defined as follows:

T_{1} = {_{⋁S} p_{abcd}^{m,n} | m, n ∈ ℤ},
T_{2} = {¬p_{abcd}^{m,n} ∨ ¬p_{pqrs}^{m,n−1} | a ≠ r, p_{abcd}^{m,n}, p_{pqrs}^{m,n−1} ∈ S},
T_{3} = {¬p_{abcd}^{m,n} ∨ ¬p_{pqrs}^{m+1,n} | b ≠ s, p_{abcd}^{m,n}, p_{pqrs}^{m+1,n} ∈ S},
T_{4} = {¬p_{abcd}^{m,n} ∨ ¬p_{pqrs}^{m,n+1} | c ≠ p, p_{abcd}^{m,n}, p_{pqrs}^{m,n+1} ∈ S},
T_{5} = {¬p_{abcd}^{m,n} ∨ ¬p_{pqrs}^{m−1,n} | q ≠ d, p_{abcd}^{m,n}, p_{pqrs}^{m−1,n} ∈ S},
T = T_{1} ∪ ⋯∪ T_{5}.

Observe that T_{1} codes the notion of the covering of the plain, while T_{2}, T_{3}, T_{4}, T_{5} code other properties of the domino tiling. Further, it is easy to see that 𝔐(T) = ⋂ _{φ∈T} φ̂^{−1} [1], thus 𝔐(T) is a Borel subset of the Cantor space 2^{P}, so CH holds for 𝔐(T). In addition, we have a one-to-one and onto correspondence between the set of all coverings of the plane and the set of all models of the theory T. Thus, the number of coverings satisfies CH.

Of course, many other examples fall in this category. For example, CH is true for:

(1) The number of countable linear extensions of a countable partially ordered set.

(2) The number of congruences of a countable algebra (Burris and Kwaitinetz).

(3) The number of maximal (prime) ideals of countable ring, i.e., Zariski space of a countable ring. In particular, CH holds for the Stone space of a countable Boolean algebra 𝔹.

(4) The numbers of maximal chains and antichains in a countable partially ordered set. In particular, CH holds for the number of branches of a countable tree.

(5) The number of ordered fields (𝔽, ⩽), for every countable real closed field 𝔽.

3. On the number of valuations

In this section we discus the topological and cardinal properties of the set of valuations satisfying a formula of the infinitary logic L_{ω_{1} ω} . The basic assumption is that the domain of the considered model is equipped with a certain topology. We note that our consideration in this section is not limited only to the countable models.

3.1. Valuations in countable models. Let L be a language with a countable set of variables V and let 𝔸 = (A, …) be a countable model of language L. If we consider A as a discrete topological space, then the set of all valuations A^{V} is homeomorphic to the Baire space.

Let φ(x_{1}, …, x_{n}) be an arbitrary first-order formula of the language L. We define the map φ̂ : A^{V} → 2 by

φ̂(μ) = \{ \begin{matrix}1, & 𝔸 ⊧ φ[μ] \\ 0, & 𝔸 ⊧ ¬φ[μ]. \end{matrix}

Lemma 3.1. The function φ̂ is continuous.

Proof. The set

φ̂^{−1} [{1}]= {μ ∈ A^{V} | 𝔸 ⊧ φ[μ]}
= ⋃ {π_{1}^{−1} [{a_{1}}] ∩ ⋯∩ π_{n}^{−1} [{a_{n}}] | a_{i} ∈ A ∧ 𝔸 ⊧ φ[a_{1}, …, a_{n}]},

is open as the union of open sets. Similarly, φ̂^{−1} [{0}] is open, so φ̂ is a continuous map. □

Let t(x_{1}, …, x_{n}) = {φ_{m}(x_{1}, …, x_{n}) | m ∈ ω} be a countable type in variables x_{1}, …, x_{n} of the language L. We define the function t̂: A^{V} → 2^{ω} by

t̂(μ) = ⟨φ̂_{n} [μ] | n ∈ ω⟩.

Since for each m we have π_{m} ∘ t̂ = φ̂_{m} , and each function φ̂_{m} is continuous, we obtain the following

Corollary 3.1. The function t̂ is continuous.

The set of all valuations that satisfy the type t(x_{1}, …, x_{n}) is equal to the set t̂^{−1} [{⟨1 | n ∈ ω⟩}], so we have the following fact.

Corollary 3.2. The set of all valuations that satisfy the type t(x_{1}, …, x_{n}) is a closed subset of the Baire space A^{V}.

Next we shall consider formulas φ(x_{1}, x_{2}, …) and types t(x_{1}, x_{2}, …) of L_{ω_{1} ω} with countably many free variables, together with corresponding functions φ̂ and t̂.

Theorem 3.1. For arbitrary formula φ(x_{1}, x_{2}, …) of L_{ω_{1} ω} the function φ̂ is Borel.

Proof. We use the induction on the complexity of φ. If φ is an atomic formula, then by the argument stated above the function φ̂ is continuous and hence it is Borel.

Suppose that φ is the formula ⋁ _{n∈ω} φ_{n}. Then φ̂^{−1} [{1}] = ⋃ _{n∈ω} φ̂_{n}^{−1} [{1}], so it is a Borel set as a countable union of Borel sets.

Suppose that φ is the formula ¬ψ. Then φ̂^{−1} [{1}] = ψ̂^{−1} [{0}], so it is a Borel set by the induction hypothesis.

Suppose that φ is the formula ∃x ψ(x, x_{1}, x_{2}, …). Then

φ̂^{−1} [{1}]= {μ ∈ A^{V} | 𝔸 ⊧ ∃xψ(x, x_{1}, x_{2}, …)[μ]}

= ⋃_{b∈A} {μ ∈ A^{V} | 𝔸 ⊧ ψ(b, x_{1}, x_{2}, …)[μ]},

so it is a Borel set as a countable union of Borel sets. □

Corollary 3.3. The set of all valuations which satisfy the type t(x_{1}, x_{2}, …) is a Borel subset of the Baire space, thus CH is true for this set as well.

Let 𝔸 and 𝔹 be countable models of the language L and let 𝔸 be a submodel of 𝔹. Then 𝔸 is an elementary submodel of 𝔹 if for each first-order formula φ the function φ̂_{𝔸} : A^{V} → 2 has a continuous extension φ̂_{𝔹} : B^{V} → 2.

Example 3.1. The number of cuts of a countable linear ordering satisfies CH. Really, the notion of the cut can be coded by the conjunction of the following formulas:

∀x ⋁_{i∈ω} x = x_{i}, ⋀_{i∈ω} x_{2i} < x_{2i+2} , ⋀_{i∈ω} x_{2i+3} < x_{2i+1} ,

⋀_{i,j∈ω} x_{2i} < x_{2j+1} , ⋀_{i∈ω} ⋁_{j∈ω} x_{2i} < x_{2j} , ⋀_{i∈ω} ⋁_{j∈ω} x_{2j+1} < x_{2i+1} .

3.2. Valuations in uncountable models. In this subsection we shall transfer some results from the previous subsection to the models that are not necessarily countable. Let 𝔸 = (A, …) be a model of the language L, where A is a Polish space and suppose that all of functions and relations of the model 𝔸 are Borel. For simplicity such models we shall call Borel models. Note that if A is countable, then all these relations and functions are anyway Borel. In a Borel model 𝔸 we can identify valuations from A^{V} with elements of the Polish space A^{ω}. In what follows, we shall use the following two basic facts:

Lemma 3.2. Let A be a Polish space and let B be a Borel subset of A^{n}. If π is a permutation of the set {0, …, n−1}, then {(a_{π(0)} , …, a_{π(n−1)} ) | (a_{0}, …, a_{n−1} ) ∈ B} is a Borel set.

Lemma 3.3. Let A be a Polish space and let B be a Borel subset of A^{n}. Then the sets B × A^{k} and B × A^{ω} are Borel subsets of A^{n+k} and A^{ω}, respectively.

Let 𝔸 be a Borel model of a language L and t = t(x_{1}, x_{2}, …, x_{m}) be a term of L, where x_{1}, x_{2}, …, x_{m} is the list of all variables occurring in t. The term mapping f_{t}: A^{m} → A associated to t is naturally defined by f_{t}(a_{1}, a_{2}, …, a_{m}) = t^{𝔸}[a_{1}, a_{2}, …, a_{m}]. The following lemma shows that in Borel models term mappings are Borel functions.

Lemma 3.4. Let 𝔸 = (A, …) be a Borel model of the language L and t be a term of L. Then f_{t} is the Borel function.

Proof. We prove the statement by induction on the complexity of terms. Obviously, terms of the complexity 0 define unary functions that are identities or constant functions.

Let t = g(t_{1}, …, t_{n}), where g is a function symbol and t_{1}, …, t_{n} are terms of the lower complexity. Further, let x_{1}, x_{2}, …, x_{m} be the list of all variables occurring in t. The terms t_{1}, …, t_{n} define Borel term functions h_{1}, …, h_{n} by the induction hypothesis. To prove that the function f = g^{𝔸} ∘ (h_{1}, …, h_{n}) is Borel, it suffices to show that the function (h_{1}, …, h_{n}): A^{m} → A^{n} is Borel. The graph of the function (h_{1}, …, h_{n}) is the set

{(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | h_{i}(a_{0}, …, a_{m}) = b_{i}, i ∈ {1, …, n}}
= ⋂_{1⩽i⩽n} {(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | h_{i}(a_{0}, …, a_{m}) = b_{i}} .

Further, the set

{(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | h_{1}(a_{0}, …, a_{m}) = b_{1}}
= {(a_{0}, …, a_{m}, b_{1}) ∈ A^{m+2} | h_{1}(a_{0}, …, a_{m}) = b_{1}} × A^{n−1}

is Borel, according to the previous lemma. Similarly, the other terms of the intersection are Borel sets, therefore the function (h_{1}, …, h_{n}) is Borel. □

Theorem 3.2. Let 𝔸 = (A, …) be a Borel model. If φ is a quantifier-free formula of the language L_{ω_{1} ω} , then the set of valuations which satisfy formula φ is a Borel subset of A^{V}.

Proof. Since

{μ ∈ A^{V} | 𝔸 ⊧ _{⋀ n∈ω} φ_{n}} = ⋂_{n∈ω} {μ ∈ A^{V} | 𝔸 ⊧ φ_{n}},
{μ ∈ A^{V} | 𝔸 ⊧ ¬φ} = {μ ∈ A^{V} | 𝔸 ⊧ φ}^{c},

it suffices to prove the statement for the atomic formulas.

Let R(t_{1}(x_{0}, …, x_{m}), …, t_{n}(x_{0}, …, x_{m})) be an atomic formula. We show that the set

S = {(a_{0}, …, a_{m}) ∈ A^{m+1} | R^{𝔸}(t_{1}^{𝔸}[a_{0}, …, a_{m}], …, t_{n}^{𝔸}[a_{0}, …, a_{m}])}

is Borel. Notice that S = π(S_{1}), where

S_{1} = {(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | R^{𝔸}(b_{1}, …, b_{n}), b_{i} = t_{n}^{𝔸}[a_{0}, …, a_{m}]}

and π : A^{m+n+1} −→ A^{m+1} is the projection

π((a_{0}, …, a_{m}, b_{1}, …, b_{n})) = (a_{0}, …, a_{m}).

Then,

S_{1} = {(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | R^{𝔸}(b_{1}, …, b_{n})}

∩ ⋂_{1⩽i⩽n} {(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | b_{i} = t_{i}^{𝔸}[a_{0}, …, a_{m}]}.

By our assumption and Lemma 3.3, the set

{(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | R^{𝔸}(b_{1}, …, b_{n})}
= A^{m+1} × {(b_{1}, …, b_{n}) ∈ A^{n} | R^{𝔸}(b_{1}, …, b_{n})}

is Borel. Using lemmas 3.2, 3.3 and 3.4 we conclude that the set

{(a_{0}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{m+n+1} | b_{1} = t_{1}^{𝔸}[a_{0}, …, a_{m}]}
= {(a_{0}, …, a_{m}, b_{1}) ∈ A^{m+2} | b_{1} = t_{1}^{𝔸}[a_{0}, …, a_{m}]} × A^{n−1}

is Borel, as well as the other members of the intersection. Hence, S_{1} is a Borel set.

The projection π is continuous; notice that its restriction π|_{S_{1}} is injective. Thus, S is a Borel set as an injective image of the Borel set S_{1} (see [3, Theorem 15.1]). □

Since the continuous image of a Borel set is analytic, we have

Corollary 3.4. Assume that the model 𝔸 = (A, …) of the language L satisfies the conditions of the previous theorem. If φ is an L_{ω_{1} ω} formula of the form ∃x_{1} …∃x_{n} ψ, where ψ is quantifier free, CH holds for the number of valuations which satisfy φ.

In the same manner as in the proof of Theorem 3.2, we can prove the following theorem:

Theorem 3.3. Let 𝔸 = (A, …) be a model of the language L, where the set A is a Polish space and all of the functions and relations of 𝔸 are projective. If φ is an arbitrary formula of L_{ω_{1} ω} , then the set of valuations satisfying φ is the projective subset of A^{V}.

We have immediately from [3, Theorem 38.17] the following result.

Corollary 3.5. Let 𝔸 = (A, …) be a model of the language L, where the set A is a Polish space and all of the functions and relations of 𝔸 are projective and assume PD (the axiom of projective determinacy). If φ is an arbitrary formula of L_{ω_{1} ω} , then CH holds for the number of valuations satisfying φ.

References

1. J. Barwise, Admissible Sets And Structures, Springer, Berlin, 1977.

2. C. C. Chang, H. J. Keisler, Model Theory, 3rd ed. North-Holland, Amsterdam, 1990.

3. A. S. Kechris, Classical Descriptive Set Theory, Springer-Verlag, New York, 1995.

4. H. J. Keisler, Model Theory For Infinitary Logic, North-Holland, Amsterdam, 1971.

5. D. E. Knuth, The Art of Computer Programming, Addison-Wesley, Reading, Mass., 1973.

6. D. Kueker, Definability, automorphisms and infinitary languages, in: J. Barwise (ed.),The Syntax and Semantics of Infinitary Logic, Lect. Notes Math. 72, Springer, Berlin, 1968, pp. 152–165.

7. K. Kuratowski and A. Mostowski, Set Theory, PWN–Polish Scientific Publishers, Warszawa, 1967.

8. M. Makkai, Admissible sets and infinitary logic, in: in: J. Barwise (ed.),Handbook of Mathematical Logic, North-Holland, Amsterdam, 1977, pp. 233–282.

9. Y. N. Moschovakis, Descriptive Set Theory, North-Holland, Amsterdam, 1980.

10. G. Reyes, Local definability theory, Ann. Math. Logic 1 (1970), 95–137.

11. H. Wang, Games, logic and computers, Scientific American 213(5) (1965), 98–106.

University of Belgrade (Received 02 10 2011) Faculty of Mathematics Studentski trg 16 11000 Belgrade Serbia

zarkom@matf.bg.ac.rs, angelina@matf.bg.ac.rs

University of Belgrade Faculty of Mechanical Engineering Kraljice Marije 16 11120 Belgrade Serbia

ddoder@mas.bg.ac.rs