The hierarchy of ω_{1}-Borel sets 1

The hierarchy of ω_{1}-Borel sets

Arnold W. Miller^{1}

Abstract

We consider the ω_{1}-Borel subsets of the reals in models of ZFC. This is the smallest family of sets containing the open subsets of the 2^{ω} and closed under ω_{1} intersections and ω_{1} unions. We show that Martin’s Axiom implies that the hierarchy of ω_{1}-Borel sets has length ω_{2}. We prove that in the Cohen real model the length of this hierarchy is at least ω_{1} but no more than ω_{1} + 1.

Some authors have considered ω_{1}-Borel sets in other spaces, ω_{1}^{ω_{1}} Mekler and Vaananen [10] and or completely metrizable spaces of uncountable density, Willmott [21]. But in this paper we only consider the space 2^{ω}.

Define the levels of the ω_{1}-Borel hierarchy of subsets of 2^{ω} as follows:

1. Σ_{0}^{∗} = Π_{0}^{∗} = clopen subsets of 2^{ω}

2. Σ_{α}^{∗} = {⋃_{β<ω_{1}} A_{β} : (A_{β} : β < ω_{1}) ∈ (Π_{<α}^{∗})^{ω_{1}}}

3. Π_{α}^{∗} = {⋃_{β<ω_{1}} A_{β} : (A_{β} : β < ω_{1}) ∈ (Σ_{<α}^{∗})^{ω_{1}}}

4. Π_{<α}^{∗} = ⋂_{β<α} Π_{β}^{∗} Σ_{<α}^{∗} = ⋃_{β<α} Σ_{β}^{∗}

The length of this hierarchy is the smallest α ≥ 1 such that

Π_{α}^{∗} = Σ_{α}^{∗}.

It is easy to show that if α < ω_{2} and every ω_{1}-Borel set is Π_{<α}^{∗}, then Π_{β}^{∗} = Σ_{β}^{∗} for some β < α, i.e., bounded hierarchies must have a top class (see Miller [11] Proposition 4 p.235).

1Thanks to the University of Florida Mathematics Department for their support and especially Jindrich Zapletal, William Mitchell, Jean A. Larson, and Douglas Cenzer for inviting me to the special year in Logic 2006-07 during which most of this work was done.

Mathematics Subject Classification 2000: 03E15; 03E35; 03E50

Keywords: Borel hierarchies, Martin’s Axiom, Q-set, Cohen real model, Steel forcing.

Last revised April 2009.

The classes Π_{1}^{∗} and Σ_{1}^{∗} are the ordinary closed sets and open sets, respectively, so the length of the hierarchy of ω_{1}-Borel sets is at least 2.

Assuming the continuum hypothesis, Π_{2}^{∗} = Σ_{2}^{∗} = P(2^{ω}), so CH implies the order of the hierarchy is 2. It also known to be consistent that

Π_{3}^{∗} = Σ_{3}^{∗} = P(2^{ω}) and Π_{2}^{∗} ≠ Σ_{2}^{∗}

see Steprans [20]. In Stepran’s model, the continuum is ℵ_{ω_{1}}. Carlson [5] showed that if every subset of 2^{ω} is ω_{1}-Borel, then the cofinality of the continuum must be ω_{1}. Stepran’s model was used earlier by Bukovsky [3] and latter by Miller-Prikry [13].

The following is an open question from Brendle, Larson, and Todorcevic [4].

Question 1 Is it consistent with the negation of the continuum hypothesis that Π_{2}^{∗} = Σ_{2}^{∗}?

Steprans noted that it would be too much to ask for

¬CH + Π_{2}^{∗} = Σ_{2}^{∗} = P(2^{ω})

since a Σ_{2}^{∗} set, i.e., an ω_{1} union of closed sets, of size greater than ω_{1} would have to contain a perfect subset, hence ¬CH implies a Bernstein set cannot be Σ_{2}^{∗}. It is also known that Π_{2}^{∗} ≠ Σ_{2}^{∗} in the iterated Sacks model, see Ciesielski and Pawlikowski [6].

Theorem 2 (MA_{ω_{1}}) Π_{α}^{∗} ≠ Σ_{α}^{∗} for every α < ω_{2}.

We prove this using the following two lemmas. A well-known consequence of MA_{ω_{1}} is that every subset Q ⊆ 2^{ω} of size ω_{1} is a Q-set, i.e., for every subset X ⊆ Q there is a G_{δ} set G ⊆ 2^{ω} with G ∩ Q = X (see Fleissner and Miller [7]).

Lemma 3 Suppose there exists a Q-set of size ω_{1}. Then there exists an onto map F : 2^{ω} → 2^{ω_{1}} such for every subbasic clopen set C ⊆ 2^{ω_{1}} the set F^{−1}(C) is either G_{δ} or F_{σ}.

Proof Fix Q = {u_{α} ∈ 2^{ω} : α < ω_{1}} a Q-set. Let G ⊆ 2^{ω} × 2^{ω} be a universal G_{δ} set, i.e., G is G_{δ} and for every G_{δ} set H ⊆ 2^{ω} there exists x ∈ 2^{ω} with G_{x} = H. Define F as follows, given x ∈ 2^{ω} let

F (x)(α) = 1 iff u_{α} ∈ G_{x}

If C is a subbasic clopen set, then for some α and i = 0 or i = 1

C_{α,i} = {p ∈ 2^{ω_{1}} : p(α) = i}.

Then for i = 1

F^{−1}(C_{α,1}) = {x : u_{α} ∈ G_{x}}

which is a G_{δ} set. Since C_{α,0} is the complement of C_{α,1} we have that F^{−1}(C_{α,0}) is an F_{σ}-set

Finally, we note that since Q is a Q-set, i.e., every subset is a relative G_{δ}, it follows that F is onto. QED

The next Lemma is true without any additional assumptions beyond ZFC. Its proof is a generalization of Lebesgue’s 1905 proof (see Kechris [9] p.168) for the standard Borel hierarchy.

Lemma 4 For any α with 0 < α < ω_{2} there exists a Σ_{α}^{∗} set U ⊆ 2^{ω_{1}} × 2^{ω} which is universal for Σ_{α}^{∗} subsets of 2^{ω}, i.e., for any Q ⊆ 2^{ω} which is Σ_{α}^{∗} there exists p ∈ 2^{ω_{1}} with U_{p} = Q. Similarly, there is a universal Π_{α}^{∗} set.

Proof The proof is by induction on α. Note that the complement of a universal Σ_{α}^{∗} set is a universal Π_{α}^{∗}-set.

For α = 1, Σ_{α}^{∗} is just the open sets. There is a universal open set V ⊆ 2^{ω} × 2^{ω}. Put

U = {(p, x) ∈ 2^{ω_{1}} × 2^{ω} : (p ↾ ω, x) ∈ V }

For α such that 2 ≤ α < ω_{2} proceed as follows. Let (δ_{β} < α : β < ω_{1}) have the property that for every γ < α there are ω_{1} many δ_{β} ≥ γ. It follows that for every Σ_{α}^{∗} set Q ⊆ 2^{ω} there is (Q_{β} ∈ Π_{δ_{β}}^{∗} : β < ω_{1}) with

Q = ⋃_{β<ω_{1}} Q_{β}.

By induction, there are U_{β} ⊆ 2^{ω_{1}}×2^{ω} universal Π_{δ_{β}}^{∗} sets. Let a : ω_{1}×ω_{1} → ω_{1} be a bijection. For each β define

π_{β} : 2^{ω_{1}} × 2^{ω} → 2^{ω_{1}} × 2^{ω}, (p, x) ↦ (q, x)

where q(α) = p(a(β, α)). Put

U = ⋃_{β<ω_{1}} π_{β}^{−1}(U_{β})

then U will be a universal Σ_{α}^{∗} set. QED

Now we prove Theorem 2. Suppose for contradiction, that every ω_{1}-Borel set is Σ_{α}^{∗} for some fixed α < ω_{2}. Let U ⊆ 2^{ω_{1}} × 2^{ω} be a universal Σ_{α}^{∗} and define

V = {(x, y) ∈ 2^{ω} × 2^{ω} : (F (x), y) ∈ U}.

Then V is an ω_{1}-Borel set (although not necessarily at the Σ_{α}^{∗}) because the preimage of any clopen box C × D is ω_{1}-Borel by Lemma 3. Define

D = {x : (x, x) ∉ V }.

But then D is ω_{1}-Borel but not Σ_{α}^{∗}. We see this by the usual diagonal argument that if D = U_{p}, then since F is onto there would be x ∈ 2^{ω} such that F (x) = p but then

x ∈ D iff (F (x), x) ∉ U iff x ∉ U_{p} iff x ∉ D.

QED

Remark 5 Note that in the proof V ⊆ 2^{ω} × 2^{ω} is a Σ_{2+α}^{∗}-set, since the preimage of a clopen set under F is Δ_{3}^{0}. Hence for levels α ≥ ω the set V is a Σ_{α}^{∗} set which is universal for Σ_{α}^{∗} sets.

Remark 6 Our result easily generalizes to show that MA implies that for any κ a cardinal with ω ≤ κ < |2^{ω}| the κ-Borel hierarchy has length κ^{+}. This implies that for any κ_{1} < κ_{2} there are κ_{2}-Borel sets which are not κ_{1}-Borel.^{2} It is also true for the Cohen real model that for ω ≤ κ_{1} < κ_{2} < |2^{ω}| that there are κ_{2}-Borel sets which are not κ_{1}-Borel.

2Since κ_{2}-Borel sets at level κ_{1}^{+} or higher cannot be κ_{1}-Borel.

Question 7 Suppose MA and the continuum, 𝔠 = |2^{ω}|, is a weakly inaccessible cardinal. What is the length^{3} of the hierarchy of (< 𝔠)-Borel sets?

Theorem 8 In the Cohen real model every ω_{1}-Borel set is Σ_{ω_{1}+1}^{∗} and there is a Σ_{ω_{1}}^{∗} set which is not in Σ_{<ω_{1}}^{∗}.

Proof We state the lower bound separately as Theorem 9. We will use Steel forcing with tagged trees (Steel [18]) similarly to its use

in Stern [19]. Stern proved that assuming MA_{ω_{1}} an ω_{1} union of Σ_{α}^{0} sets which is Borel, must be Σ_{α}^{0}. Since Steel forcing is countable, he only really needed MA(ctble). Similar results are proved in Solecki [16] Cor 2.3 and Becker and Dougherty [2] Thm 2. These authors do not consider ω_{1}-Borel sets but are interested only in ω_{1}-unions of ordinary Borel sets.

MA_{ω_{1}}(ctble) stands for Martin’s axiom for countable posets. It says that for any countable poset and ω_{1}-family of dense sets there is a filter meeting all the dense sets in the family. It is equivalent to saying that the real line cannot be covered by ω_{1} nowhere dense sets, see for example, Bartoszynski and Judah [1] p. 138. It holds in any generic extension obtained with a finite support ccc iteration of cofinality at least ω_{2}.

Theorem 9 Suppose MA_{ω_{1}}(ctble) holds. Then for any α < ω_{1} there is an ordinary Borel set which is not Σ_{α}^{∗}.

Proof We use Steel forcing with tagged trees^{4} similarly to the way it is described in Harrington [8].

For any countable ordinal α define Q(α) to be the following countable poset. Elements of Q(α) have the form (t, h) where t is a finite subtree of ω^{<ω} and h : t → α ∪ {∞} is called a tagging. The ordering on α ∪ {∞} is ∞ < ∞ and β < ∞ for each ordinal β along with the usual ordering on pairs of ordinals from α. A tagging h is a rank function which means it satisfies: if σ, τ ∈ t and σ is a strict initial segment of τ, then h(σ) > h(τ).^{5}

The ordering on Q(α) is p ≤ q (p extends q) iff

1. t_{q} ⊆ t_{p} and

3The argument of Theorem 9 shows that it is at least ω_{1}.

4Sami [15] gives a proof of Harrington’s Theorem which does not use Steel forcing.

5We differ from [8] by not requiring that h(⟨⟩) = ∞.

2. h_{q} ⊆ h_{p}.

Note that nodes tagged with ∞ can always be extended and tagged with ∞ or any element of α. ^{6}

Now suppose that G is Q(α) generic over M. Define

1. T = T_{G} = {σ : ∃(t, h) ∈ G σ ∈ t}

2. H = H_{G} : T_{G} → α ∪ {∞} by H(σ) = h(σ) for any h such that there exists (t, h) ∈ G with σ ∈ t.

It is easily seen by a density argument that H is a rank function on the tree T where the symbol ∞ gets attached to the nodes of T which can be extended to an infinite branch.

Define p(β) for β ≤ α and p ∈ Q(α) by p(β) = (t, h_{β}) where p = (t, h) and

h_{β}(s) = \{ \begin{matrix}h(s) & if h(s) < ω · β \\ ∞ & otherwise \end{matrix}

Lemma 10 (Retagging Lemma) Suppose p_{1}, p_{2} ∈ Q(α) and β + 1 ≤ α and p_{1}(β + 1) = p_{2}(β + 1). Then for every q_{1} ≤ p_{1} there is q_{2} ≤ p_{2} such that q_{1}(β) = q_{2}(β).

Proof Let p_{i} = (t, h_{i}) for i = 1, 2 and suppose q_{1} = (t′, f_{1}). We define q_{2} = (t′, f_{2}) as follows. Put f_{2} ↾ t = h_{2}. Fix N < ω greater than the height of t′. For each σ ∈ t′\t let τ ⊆ σ be the longest initial segment of σ which is in t.

Case 1. If h_{1}(τ) < ω(β + 1), then by assumption, h_{2}(τ) = h_{1}(τ) and we can define f_{2}(σ) = f_{1}(σ).

Case 2. h_{1}(τ) ≥ ω(β + 1), then by assumption, h_{2}(τ) ≥ ω(β + 1).

(a) If h_{1}(σ) < ωβ, then we put h_{2}(σ) = h_{1}(σ).

(b) Otherwise ωβ ≤ h_{1}(σ) and we put h_{2}(σ) = ωβ + (N − |σ|). Note that in this case when we look at q_{i}(β) these σ will be retagged with ∞. QED

Fix α < ω_{1} and let T be the usual Q(α)-name for the generic tree T_{G}:

T = {(p, š) : s ∈ t_{p} where p = (t_{p}, h_{p}) ∈ Q(α)}.

The following is the main property of Steel forcing. We identify P(ω^{<ω}) with 2^{ω}.

6Harrington [8] makes the additional requirement that the top node, ⟨⟩, be tagged with ∞, but this is unnecessary and makes our proof clumsy, as in Miller [14] Lemma 4.4.

Lemma 11 Suppose p, q ∈ Q(α), 1 + β ≤ α, p(1 + β) = q(1 + β), and B ⊆ P(ω^{<ω}) is Π_{β}^{∗} set coded in the ground model.^{7} Then

p ⊩T ∈ B iff q ⊩T ∈ B.

Proof This is proved by induction on β.

For β = 0 we take for Π_{0}^{∗} basic clopen subsets of P(ω^{<ω}). This means that for some pair F_{0}, F_{1} of disjoint finite subsets of ω^{<ω} that

B = {X ⊆ ω^{<ω} : F_{0} ⊆ X and F_{1} ∩ X = ∅}.

So the statement X ∈ B is a finite conjunction of statements of the form σ ∈ X or σ ∉ X. But note that:

1. p ⊩σ̌ ∈ T iff σ = ⟨⟩, σ ∈ t_{p}, or τ ∈ t_{p} and h_{p}(τ) > 0 where τ is the initial segment of σ of length exactly one less than σ.

2. p ⊩σ̌ ∉ T iff there exists τ ⊆ σ with τ ∈ t_{p} and h_{p}(τ) < |σ| − |τ|.

Both of these are preserved when we look at p(1). Hence if p(1) = q(1) then

p ⊩T ∈ B iff q ⊩T ∈ B.

For β > 0 suppose that B is Π_{β+1}^{∗} and coded in the ground model. Working in the ground model let B = ⋂_{α<ω_{1}} ∼B_{α} where^{8} each B_{α} is Π_{<1+β}^{∗}. And suppose for contradiction that p_{2} ⊩T ∈ B but p_{1} does not force this. Then there exists a q_{1} ≤ p_{1} and α < ω_{1} such that

q_{1} ⊩T ∈ B_{α}.

And suppose that B_{α} is Π_{1+γ}^{∗} where γ < β. Since 1 + γ + 1 ≤ 1 + β, by the retagging lemma we may find q_{2} ≤ p_{2} with q_{1}(1 + γ) = q_{2}(1 + γ). By inductive hypothesis

q_{2} ⊩T ∈ B_{α}

7There are many ways to code Borel (or more generally κ-Borel) sets. Solovay [17] p.25 gives a clear definition of coding and absoluteness which is similar to what we use in the proof of Lemma 4. Harrington [8] Definition 2.5 and Steel [18] code using infinitary propositional logic. We like to use well-founded trees as in Lemma 12.

8We use ∼B to denote the complement of B.

which contradicts that

p_{2} ⊩T ∈ B ⊇ ∼B_{α}.

QED

Suppose for contradiction that in the Cohen real model there is an α_{0} < ω_{1} such that every ω_{1}-Borel set is Π_{α_{0}}^{∗}. It well-known that for every countable ordinal α the set

W F_{α} = {T ⊆ ω^{<ω} : T is a well-founded tree of rank α}

is an (ordinary) Borel set.^{9} Consequently it must be a Π_{α_{0}}^{∗}-set. Fix a countable α > α_{0} · ω. Take a sufficiently large^{10} regular cardinal κ and let H_{κ} be the sets whose transitive closure has cardinality less than κ. Take N to be an elementary substructure of V_{κ} of cardinality ω_{1} which contains α + 1. Then N will contain a code for B the Π_{α_{0}}^{∗} set W F_{α}. Let M be the transitive collapse of N and consider forcing over M with Q(α + 1). Since we are assuming MA(ctbl), for any p ∈ Q(α + 1) there is a G Q(α + 1)-generic over the ground model M with p ∈ G. So take such a G with H_{G}(⟨⟩) = α. Then T_{G} is a well-founded tree of rank α and so T_{G} ∈ W F_{α}. By absoluteness

M[G] ⊧ T_{G} ∈ B

and so there must be a p ∈ G such that

p ⊩T ∈ B.

But consider q = p(α). Note that h_{q}(⟨⟩) = ∞. Consequently, for any G′ which is Q(α + 1)-generic over M with q ∈ G′, the tree T_{G′} is not even well-founded and hence

M[G′] ⊧ T_{G′} ∉ B.

But this means that

q ⊩T ∉ B

which contradicts Lemma 11. QED

Next we prove an upper bound on the ω_{1}-Borel hierarchy in the Cohen real model. Our argument uses some ideas employed by Carlson [5].

9The exact Borel class is computed in Stern [19] and Miller [12].

10For example κ = ℶ_{ω}^{+}.

Lemma 12 In the Cohen real model for any ω_{1}-Borel set B there exists ω_{1} ordinary Borel sets, (B_{β} : β < ω_{1}), such that B is their limit:

B = ⋃_{α<ω_{1}} ⋂_{β>α} B_{β} = ⋂_{α<ω_{1}} ⋃_{β>α} B_{β}

Proof Let B be coded by a well-founded tree T ⊆ ω_{1}^{<ω_{1}} with basic clopen sets (s_{σ} ∈ 2^{<ω} : σ ∈ T^{∗}) where T^{∗} are the terminal nodes (or leaf nodes) of the tree T. Then T, (s_{σ} : σ ∈ T^{∗}) codes B as follows. Define

B(σ) = [s_{σ}] = {x ∈ 2^{ω} : s_{σ} ⊆ x}

for σ ∈ T^{∗}. Then for nonterminal nodes of T define

B(σ) = ⋂{∼B(σˆ ⟨α⟩) : α < ω_{1} and σˆ ⟨α⟩ ∈ T }.

Finally, put B = B(⟨⟩).

Fix such a T for B and for any α < ω_{1} define B_{α} inductively just as above but for the countable tree T ∩ α^{<ω}.

We will show that for some closed unbounded set C ⊆ ω_{1} that B is the ω_{1}-limit of (B_{β} : β ∈ C).

By the Cohen real model we mean an model obtained by forcing with Fn(ω_{2}, 2), the finite partial maps from ω_{2} into 2, over a model of ZFC+GCH. By standard arguments using the countable chain condition and product Lemma, we may without loss of generality assume that our code for B, T, (s_{σ} : σ ∈ T^{∗}), is in the ground model M a model of ZFC+GCH. For any x ∈ M[G] ∩ 2^{ω} (where G is Fn(ω_{2}, 2)-generic over M there is an H ∈ M[G] which is Fn(ω, 2)-generic over M and x ∈ M[H].

Since the ground model M satisfies CH, there is a set of canonical names, CN, for elements of 2^{ω} in the extension M[H] has size ω_{1}.

Working in the ground model M construct an continuous chain (N_{α} : α < ω_{1}) of countable elementary submodels of H_{ω_{2}}, with the code for B, T, (s_{σ} : σ ∈ T^{∗}), in N_{0}, N_{α} ⪯ N_{β} and N_{α} ∈ N_{β} for α < β < ω_{1}. Note that it is automatically the case that every canonical name is in some N_{α}.

Now take for our club C the set

C = {ω_{1} ∩ N_{α} : α < ω_{1}}.

Suppose that x = τ^{H} where τ ∈ N_{α} and H is Fn(ω, 2)-generic over M. Let M_{α} be the transitive collapse of N_{α}. By standard arguments H is Fn(ω, 2)-generic over M_{α}. Note that ordinal δ = N_{∩}ω_{1} is the ω_{1} of M_{α} i.e.,

M_{α} ⊧ δ = ω_{1}.

Let p ∈ Fn(ω, 2) be such that either

M_{α} ⊧ p ⊩τ ∈ B

or

M_{α} ⊧ p ⊩τ ∈ ∼B.

Assume the former. Note that B^{M_{α}[H]}=B_{δ} ∩ M[H]. And since it is forced it must be that x = τ^{H} ∈ B_{δ}.

For every β > α the model N_{β} elementary superstructure of N_{α} and hence that

M_{β} ⊧ p ⊩τ ∈ B

and for the same reason x ∈ B_{δ′} where δ′ is the ω_{1} of M_{β}. QED

Remark 13 Lemma 12 easily generalizes to the ω_{1}-Borel hierarchy giving that every ω_{2}-Borel set is the ω_{2} limit of ω_{1}-Borel sets, and since each of them is at level ω_{1} + 1, we get an upperbound of ω_{1} + 2 for the length of the ω_{2}-Borel hierarchy.

Remark 14 Lemma 12 is also true in the random real model.

Remark 15 In Steprans [20] the hierarchy on the ω_{1}-Borel sets is defined by letting the bottom level, Π_{0}^{ℵ_{1}} = Σ_{0}^{ℵ_{1}}, be the family of all ordinary Borel sets. Lemma 12 shows that every ω_{1}-Borel set in the Cohen real model is Π_{2}^{ℵ_{1}} and hence Σ_{2}^{ℵ_{1}}. It is easy to see that in this model there are Σ_{1}^{ℵ_{1}} sets which are not Π_{1}^{ℵ_{1}}, for example, any nonmeager subset of 2^{ω} of size ω_{1}.

Remark 16 In Miller [11] Theorem 34 and 54, it is shown consistent for any countable ordinal α_{0} ≥ 2 to have separable metric space X such that every subset of X is Borel and the Borel hierarchy on X has length exactly α_{0}. It is easy to show that if the set X ⊆ 2^{ω} has cardinality at least ω_{2} that for each β < α_{0} the generic Π_{β}^{0} sets produced are not Σ_{β}^{∗} relative to X.

Hence these spaces have order α_{0} in the relativized ω_{1}-Borel hierarchy. If we replace the use of almost disjoint forcing in Steprans model [20] Definition 2, by Π_{α_{0}}^{0}-forcing from Miller [11] p. 236, then we get a model of ZFC in which every subset of 2^{ω} is ω_{1}-Borel and the ω_{1}-Borel hierarchy has length at least α_{0} but no more than α_{0} + 1. Similarly if we change the Steprans model by using Π_{α}^{0}-forcing in the α model, then in the resulting model every subset of 2^{ω} is ω_{1}-Borel and the ω_{1}-Borel hierarchy has length at least ω_{1} but no more than ω_{1} + 1.

Question 17 Is possible to have a model of ZFC in which the ω_{1}-Borel hierarchy has length α where ω_{1} + 2 ≤ α < ω_{2}?

References

[1] Bartoszynski, Tomek; Judah, Haim; Set theory. On the structure of the real line. A K Peters, Ltd., Wellesley, MA, 1995. xii+546 pp. ISBN: 1-56881-044-X

[2] Becker, Howard; Dougherty, Randall; On disjoint Borel uniformizations. Adv. Math. 146 (1999), no. 2, 167–174.

[3] Bukovský, Lev; Random forcing. in br Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), pp. 101-117. Lecture Notes in Math., Vol. 619, Springer, Berlin, 1977.

[4] Brendle, Joerg; Larson, Paul; and Todorcevic, Stevo; Rectangular axioms, perfect set properties and decompositions, Bulletin de l’Academie Serbe des Sciences et des Arts, Classe des Sciences Mathematiques et Naturelles, Sciences mathematiques, vol. 33, (2008), 91–130.

[5] Tim Carlson, On ω_{1}-Borel sets, unpublished 1982.

[6] Ciesielski, Krzysztof; Pawlikowski, Janusz; Uncountable intersections of open sets under CPA_{prism}. Proc. Amer. Math. Soc. 132 (2004), no. 11, 3379–3385

[7] Fleissner, William G.; Miller, Arnold W.; On Q sets. Proc. Amer. Math. Soc. 78 (1980), no. 2, 280–284.

[8] Harrington, Leo; Analytic determinacy and 0^{♯}. J. Symbolic Logic 43 (1978), no. 4, 685–693.

[9] Kechris, Alexander S.;Classical descriptive set theory. Graduate Texts in Mathematics, 156. Springer-Verlag, New York, 1995. xviii+402 pp. ISBN: 0-387-94374-9

[10] Mekler, Alan; Vaananen, Jouko; Trees and Π_{1}^{1}-subsets of ^{ω_{1}}ω_{1}. J. Symbolic Logic 58 (1993), no. 3, 1052–1070.

[11] Miller, Arnold W.; On the length of Borel hierarchies. Ann. Math. Logic 16 (1979), no. 3, 233–267.

[12] Miller, Arnold W.; On the Borel classification of the isomorphism class of a countable model. Notre Dame J. Formal Logic 24 (1983), no. 1, 22–34.

[13] Miller, Arnold W.; Prikry, Karel; When the continuum has cofinality ω_{1}. Pacific J. Math. 115 (1984), no. 2, 399-407.

[14] Miller, Arnold W.; Projective subsets of separable metric spaces. Ann. Pure Appl. Logic 50 (1990), no. 1, 53–69.

[15] Sami, Ramez L.; Analytic determinacy and 0^{♯}. A forcing-free proof of Harrington’s theorem. Fund. Math. 160 (1999), no. 2, 153–159.

[16] Solecki, Sławomir; Decomposing Borel sets and functions and the structure of Baire class 1 functions. J. Amer. Math. Soc. 11 (1998), no. 3, 521–550.

[17] Solovay, Robert M.; A model of set-theory in which every set of reals is Lebesgue measurable. Ann. of Math. (2) 92 1970 1–56.

[18] Steel, John R.; Forcing with tagged trees. Ann. Math. Logic 15 (1978), no. 1, 55–74.

[19] Stern, Jacques; valuation du rang de Borel de certains ensembles. C. R. Acad. Sci. Paris Sr. A-B 286 (1978), no. 20, A855–A857.

[20] Steprans, Juris; Cardinal arithmetic and ℵ_{1}-Borel sets. Proc. Amer. Math. Soc. 84 (1982), no. 1, 121–126.

[21] Willmott, R. C.; Some relations between k-analytic sets and generalized Borel sets. Fund. Math. 71 (1971), no. 3, 263–271.

Arnold W. Miller miller@math.wisc.edu http://www.math.wisc.edu/∼miller University of Wisconsin-Madison Department of Mathematics, Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388

Remark (added Jan 2014)

If P(2^{ω}) = ω_{1}-Borel, then for some α < ω_{2} P(2^{ω}) = Σ_{α}^{∗}. Suppose not and let P_{α} for α < ω_{2} be pairwise disjoint homeomorphic copies of 2^{ω}. For each α let A_{α} ⊆ P_{α} be such that A_{α} ∉ Σ_{α}^{∗}. Then A =^{def} ⋃_{α<ω_{2}} A_{α} is not ω_{1}-Borel.