Dominique Lecomte
email: dominique.lecomte@upmc.fr

Miroslav Zelen
email: zeleny@karlin.mff.cuni.cz

Universal and complete sets in martingale theory

Keywords: 2010 Mathematics Subject Classification. 03E15, 60G42 . divergence, Lebesgue measure, martingale, measure zero, G δσ set

The Doob convergence theorem implies that the set of divergence of any martingale has measure zero. We prove that, conversely, any G δσ subset of the Cantor space with Lebesgue-measure zero can be represented as the set of divergence of some martingale. In fact, this is effective and uniform. A consequence of this is that the set of everywhere converging martingales is Π 1 1 -complete, in a uniform way. We derive from this some universal and complete sets for the whole projective hierarchy, via a general method. We provide some other complete sets for the classes Π 1 1 and Σ 1 2 in the theory of martingales.

Introduction

The reader should see [K2] for the notation used in this paper.

Definition 1.1 We say that a map f : 2 <ω → [0, 1] is a martingale if f (s) = f (s0)+f (s1) 2 for each s ∈ 2 <ω . The set of martingales is denoted by M and is a compact subset of [0, 1] 2 <ω (equipped with the usual product topology). This terminology is not the standard one, but the set M can be interpreted as the set of all discrete martingales (in the classical sense) taking values in [0,1], as follows. If s ∈ 2 <ω , then

N s := {β ∈ 2 ω | s ⊆ β}
is the usual basic clopen set. Let f ∈ M. If n ∈ ω, then let S n be the σ-algebra on 2 ω generated by {N s | s ∈ 2 n }, and f n : 2 ω → [0, 1] be defined by f n (β) := f (β|n). Then the sequence (f n ) n∈ω is a discrete martingale taking values in [0,1] with respect to the sequence of σ-algebras (S n ) n∈ω and the usual Lebesgue product measure λ on 2 ω . Conversely, if (f n ) n∈ω is any such martingale, it can be viewed as an element of M by setting f (s) := f |s| (α) if α ∈ N s . This definition is correct because f |s| , as a function measurable with respect to S |s| , has a constant value on N s . Definition 1.2 Let f be a martingale and β ∈ 2 ω . The oscillation of f at β is the number osc(f, β) := inf N ∈ω sup p,q≥N |f (β|p)-f (β|q)|.

The set of divergence of f is D(f ) := {β ∈ 2 ω | osc(f, β) > 0}.
By definition, if f is a martingale, then

β ∈ D(f ) ⇔ ∃r ∈ ω ∀N ∈ ω ∃p, q ≥ N |f (β|p)-f (β|q)| > 2 -r .
This shows that D(f ) ∈ Σ 0 3 . Moreover, D(f ) has λ-measure zero, by Doob's convergence theorem (see Chapter XI, Section 14 in [D]). So it is natural to ask whether any Σ 0 3 subset of 2 ω with λmeasure zero is the set of divergence of some martingale (this question was asked by Louveau). We answer positively:

Theorem 1.3 Let B be a subset of 2 ω . Then the following are equivalent: (a) B is Σ 0 3 and has λ-measure zero, (b) there is a martingale f with B = D(f ).

Definition 1.4 Let Γ be a class of subsets of Polish spaces, X, Y be Polish spaces, and U ⊆ Y ×X. (a) We say that U is Y -universal for the Γ subsets of X if U ∈ Γ(Y ×X) and Γ(X) = {U y | y ∈ Y }. (b) We say that U is uniformly Y -universal for the Γ subsets of X if U is Y -universal for the Γ subsets of X and, for each S ∈ Γ(ω ω ×X), there is a Borel map b :

ω ω → Y such that S α = U b(α) for each α ∈ ω ω . Corollary 1.5 Let G be a G δ subset of 2 ω with λ(G) = 0. Then the set {(f, β) ∈ M×G | β ∈ D(f )} is M-universal for the Σ 0 3 subsets of G.
In fact, we prove an effective and uniform version of the implication (a) ⇒ (b) in Theorem 1.3. In particular, we can associate, via a Borel map F , a martingale to a code α of an arbitrary G δ subset G of G (as in the previous corollary), in such a way that G = D F (α) . A consequence of this is the following:

Theorem 1.6 The set P of everywhere converging martingales is Π 1 1 -complete.

These statements are in the spirit of some results concerning the differentiability of functions due to Zahorski and Mazurkiewicz (see Section 4 for details). In fact, P is Π 1 1 -complete in a uniform way, which allows to derive some universal and complete sets for the whole projective hierarchy, in spaces of continous functions, starting from P. More precisely, let P 1 := [0, 1] 2 <ω and C 1 := P. We define, for each natural number n ≥ 1,

• the space P n+1 := C(2 ω , P n ) of continuous functions from 2 ω into P n , equipped with the topology of uniform convergence (inductively),

• C n+1 := {h ∈ P n+1 | ∀β ∈ 2 ω h(β) / ∈ C n } (inductively), • U n := {(h, β) ∈ P n+1 ×2 ω | h(β) ∈ C n }.
We prove the following:

Theorem 1.7 Let n ≥ 1 be a natural number. Then (a) the set U n is uniformly P n+1 -universal for the Π 1 n subsets of 2 ω , (b) the set C n is Π 1 n -complete.
In fact, our method is more general and works if we start with a Π 1 1 set which is complete in a uniform way.

Let f be a martingale. As D(f ) has λ-measure zero, we can associate to f the partial function ψ(f ) defined λ-almost everywhere by ψ(f )(β) := lim l→∞ f (β|l). The partial function ψ(f ) will be called the associated partial function. The martingale f is in P if and only if ψ(f ) is total, in which case ψ(f ) is called the associated function. Using the work in [B-Ka-L] and [K2] about spaces of continuous functions, we prove the following: Theorem 1.8 (a) The set of sequences of everywhere converging martingales whose associated functions converge pointwise is Π 1 1 -complete. (b) The set of sequences of everywhere converging martingales whose associated functions converge pointwise to zero is Π 1 1 -complete. (c) The set of sequences of everywhere converging martingales having a subsequence whose associated functions converge pointwise to zero is Σ 1 2 -complete.

Theorem 2.1 (Lebesgue) The equality λ(M ) = λ {β ∈ M | d(M, β) = 1} holds for any λ- measurable subset M of 2 ω .
The reader should see [C] for the next lemma. We include a proof to be self-contained and also because we will prove an effective and uniform version of it later.

Lemma 2.2 (Lusin-Menchoff) Let F be a closed subset of 2 ω , and

M ⊇ F be a λ-measurable subset of 2 ω such that d(M, β) = 1 for each β ∈ F . Then there is a closed subset C of 2 ω such that (1) F ⊆ C ⊆ M , (2) d(M, β) = 1 for each β ∈ C, (3) d(C, β) = 1 for each β ∈ F .
Proof. If F is 2 ω , then we can take C := F . So we may assume that F is not 2 ω . We set s -:= s|(|s|-1) if ∅ = s ∈ 2 <ω . Note that ¬F is the disjoint union of the elements of a sequence (N sn ) n∈ω , where

N s - n ∩ F = ∅ for each n ∈ ω. Fix n ∈ ω. By Theorem 2.1, λ(M ∩ N sn ) = λ {β ∈ M ∩ N sn | d(M ∩ N sn , β) = 1} .
The regularity of λ gives a closed subset

F n of 2 ω contained in {β ∈ M ∩ N sn | d(M ∩ N sn , β) = 1} such that λ(F n ) ≥ (1-2 -n )λ(M ∩ N sn ). We set C := F ∪ n∈ω F n , which is closed since |s n | → ∞.
As Conditions (1) and ( 2) are clearly satisfied, pick β ∈ F . Note that

λ(N β|l \C)= Σ sn⊇β|l λ(N sn \C) ≤ Σ sn⊇β|l λ(N sn \F n ) ≤ Σ sn⊇β|l 2 -n λ(M ∩ N sn )+Σ sn⊇β|l λ(N sn \M ) ≤ Σ sn⊇β|l 2 -n λ(N sn )+λ(N β|l \M ).
This implies that the limit of

λ(N β|l \C) λ(N β|l ) is zero since d(M, β) = 1.
The next topology is considered in [Lu-Ma-Z], see Chapter 6.

Definition 2.3 The τ -topology on 2 ω is generated by

F := {M ⊆ 2 ω | M is λ-measurable ∧ ∀β ∈ M d(M, β) = 1}.
The next result is proved in [Lu-Ma-Z], but in a much more abstract way. This is the reason why we include a much more direct proof here, since it is not too long.

Lemma 2.4 The family F is a topology. In particular, any τ -open set is λ-measurable.

Proof. Note first that F is closed under finite intersections, so that it is a basis for the τ -topology. Indeed, let M, M ′ be in F, and β ∈ M ∩ M ′ . Then we use the facts that

λ(M ∩ M ′ ∩ N β|l ) = λ(M ∩ N β|l )-λ (M ∩ N β|l )\M ′ and λ (M ∩ N β|l )\M ′ ≤ λ(N β|l \M ′ ).
Let H be a subfamily of F, and H := ∪H. We claim that there is a countable subfamily C of H such that m := sup{λ(∪D) | D ⊆ H countable} = λ(∪C). Indeed, for each n ∈ ω there is The next lemma is in the style of Urysohn's theorem (see [Lu] for its version on the real line). We include a proof to be self-contained and also because we will prove an effective and uniform version of it later.

D n ⊆ H countable such that λ(∪D n ) > m-2 -n
Lemma 2.5 Let C be a closed subset of 2 ω , and G be a

G δ subset of 2 ω disjoint from C such that λ(G) = 0. Then there is a τ -continuous map h : 2 ω → [0, 1] such that h |C ≡ 0 and h |G ≡ 1.
Proof. Let (F n ) n∈ω be an increasing sequence of closed subsets of 2 ω with union ¬G and

F 0 = C. We first construct a sequence (C 1 2 n ) n∈ω of closed subsets of 2 ω with F n ⊆ C 1 2 n ⊆ ¬G, C 1 2 n ⊆ C 1 2 n+1
, and d(C 1 2 n+1

, β) = 1 for each β ∈ C 1 2 n . We first apply Lemma 2.2 to F := F 0 and M := ¬G, which gives F 0 ⊆ C 1 ⊆ ¬G. Then, inductively, we apply Lemma 2.2 to F := C 1 2 n ∪ F n+1 and M := ¬G, which gives

C 1 2 n ∪ F n+1 ⊆ C 1 2 n+1 ⊆ ¬G such that d(C 1 2 n+1 , β) = 1 for each β ∈ C 1 2 n .
Then we construct C 2k+1 2 n , for 0 < k < 2 n-1 and n ≥ 2. This will give us a family (C k 2 n ) n∈ω,0<k≤2 n of closed subsets of 2 ω . We want to ensure that

C ζ ⊆ C ζ ′ and d(C ζ ′ , β) = 1 for each β ∈ C ζ if ζ ′ < ζ.
We proceed by induction on n. We apply Lemma 2.2 to

F := C k+1 2 n-1 and M := C k 2 n-1 , which gives C 2k+1 2 n such that C k+1 2 n-1 ⊆ C 2k+1 2 n ⊆ C k 2 n-1 , d(C k 2 n-1 , β) = 1 for each β ∈ C 2k+1 2 n , and d(C 2k+1 2 n , β) = 1 for each β ∈ C k+1 2 n-1
. This allows us to define h by

h(β) := 0 if β ∈ G, sup{ζ | β ∈ C ζ } if β / ∈ G.
It remains to see that h is τ -continuous (and then we will set h(β)

:= 1 -h(β)). So let b ∈ (0, 1], and β ∈ 2 ω with h(β) < b. Note that there is ζ < b with h(β) < ζ, so that β / ∈ C ζ . If γ / ∈ C ζ , then h(γ) ≤ ζ < b, so that ¬C ζ
is an open (and thus τ -open since the τ -topology is finer than the usual one) neighborhood of β on which h < b. In particular, h is Borel.

Now let a ∈ [0, 1). It is enough to see that B := {γ ∈ 2 ω | h(γ) > a} is τ -open. So assume that h(γ) > a. Note that there are ζ > ζ ′ > a with h(γ) > ζ, so that γ ∈ C ζ ⊆ C ζ ′ ⊆ B. Thus d(C ζ ′ , γ) = 1,
by construction of the family. As h is Borel, B is Borel, d(B, γ) is defined and equal to 1.

Remark. We in fact proved that h is lower semi-continuous.

Notation. If h : 2 ω → [0, 1] is a λ-measurable map and s ∈ 2 <ω , then we set ffl Ns h dλ := ´Ns h dλ λ(Ns) . Lemma 2.6 Let h : 2 ω → [0, 1] be a τ -continuous map, and β ∈ 2 ω . Then

lim l→∞ N β|l h dλ = h(β).
Proof. Let ε > 0, and

β ∈ M := h -1 B h(β), ε . Note that d(M, γ) = 1 for each γ ∈ M since h is τ -continuous. As h is λ-measurable, we can write ˆNβ|l h dλ = ˆM∩N β|l h dλ+ ˆNβ|l \M h dλ. Note that 0 ≤ ´Nβ|l \M h dλ ≤ λ(N β|l \M ), so that 0 ≤ ffl N β|l \M h dλ ≤ λ(N β|l \M ) λ(N β|l ) → 0. Similarly, M ∩N β|l h dλ ∈ h(β)-ε λ(M ∩ N β|l ) λ(N β|l ) , h(β)+ε λ(M ∩ N β|l ) λ(N β|l ) ,
and we are done since

λ(M ∩N β|l )
λ(N β|l ) tends to 1 as l tends to ∞.

Now we come to our main lemma, inspired by Zahorski (see [Za]).

Lemma 2.7 Let G be a G δ subset of 2 ω with λ-measure zero. Then there is a martingale f with

G = D(f ) and {osc(f, β) | β ∈ 2 ω } ⊆ {0} ∪ [ 1 2 , 1]. Proof. Let (G n ) n∈ω be a decreasing sequence of open subsets of 2 ω with intersection G and G 0 = 2 ω . • We construct g n : 2 ω → [0, 1], open subsets G * n , G * * n of 2 ω
, and a sequence (s n j ) j∈In of pairwise incompatible finite binary sequences, by induction on n ∈ ω, such that, if S n := Σ j≤n (-1) j g j ,

(1) G ⊆ G * n+1 ⊆ G * * n = j∈In N s n j ⊆ G * n ⊆ G n ∧ G * 0 = 2 ω , (2) g n|G ≡ 1 ∧ g n|¬G * n ≡ 0, (3) g n is τ -continuous, (4) g n+1 ≤ g n , (5) λ(G * n+1 ∩ N s n j ) < 2 -n-3 λ(N s n j ), (6) | ffl N s n j S n dλ-S n (β)| < 2 -3 if β ∈ G ∩ N s n j .
We set g 0 :≡ 1, G * 0 , G * * 0 := 2 ω , I 0 := {0} and s 0 0 := ∅. Assume that our objects are constructed up to n.

We first construct an open subset G * n+1 of 2 ω with G ⊆ G * n+1 ⊆ G * * n ∩ G n+1 such that λ(G * n+1 ∩ N s n j ) < 2 -n-3 λ(N s n j ) if j ∈ I n . For each j ∈ I n , there is an open set O j with G ∩ N s n j ⊆ O j ⊆ G n+1 ∩ N s n j such that λ(O j ) < 2 -n-3 λ(N s n j ). We then set G * n+1 := j∈In O j .
We now apply Lemma 2.5 to C := ¬G * n+1 and G, which gives a τ -continuous map h : 2 ω → [0, 1] with h |¬G * n+1 ≡ 0 and h |G ≡ 1. We set g n+1 := min(g n , h), so that g n+1 satisfies (2)-(4).

By Lemma 2.6, lim l→∞ ffl

N β|l S n+1 dλ = S n+1 (β) for each β ∈ G. This gives l(β) ∈ ω minimal with | ffl N β|l(β) S n+1 dλ -S n+1 (β)| < 2 -3 and N β|l(β) ⊆ G * n+1 .
The set G * * n+1 is the union of the N β|l(β) 's, which defines I n+1 and (s n+1 j ) j∈I n+1 (S n+1 (β) is 0 if n is even and 1 otherwise when β ∈ G).

• We then define a partial map f ∞ : 2 ω → [0, 1] by f ∞ := Σ j∈ω (-1) j g j . If β ∈ G, then S n (β) takes alternatively the values 1 and 0, depending on the parity of n, so that f

∞ (β) is not defined. If β / ∈ G, then there is n such that β ∈ ¬G * n+1 ⊆ ¬G * n+2 ⊆ ... This implies that f ∞ (β) is defined and equal to S n (β). As 0 ≤ Σ p≤q (g 2p -g 2p+1 ) = S 2q+1 ≤ S 2q = g 0 +Σ 1≤p≤q (g 2p -g 2p-1 ) ≤ g 0 , f ∞ takes values in [0, 1]. So f ∞ is a partial λ-measurable map defined λ-almost everywhere since λ(G) = 0 (we use Lemma 2.4).
• This allows us to define f :

2 <ω → [0, 1] by f (s) := ffl Ns f ∞ dλ. As λ(N s ) = 2λ(N sε ) for each ε ∈ 2, f (s) = ffl Ns f ∞ dλ = ´Ns0 f∞ dλ+ ´Ns1 f∞ dλ λ(Ns) = f (s0) 2 + f (s1)
2 and f is a martingale.

• If β / ∈ G, then there is n with β ∈ G * n \G * n+1 , so that f ∞ (β) = S n (β). By Lemma 2.6, k ≥ n implies that lim l→∞ ffl N β|l S k+1 dλ = S k+1 (β) = S n (β) since S k+1 is τ -continuous. Note that, for each k ≥ n, ´Nβ|l (f ∞ -S k+1 ) dλ ≤ λ(G * k+2 ∩ N β|l ) ≤ Σ β|l⊆s k+1 j λ(G * k+2 ∩ N s k+1 j ) ≤ Σ β|l⊆s k+1 j 2 -k-4 λ(N s k+1 j ) ≤ λ(N β|l )2 -k-4 . Moreover, |f (β|l)-f ∞ (β)| = | ffl N β|l f ∞ dλ-f ∞ (β)| = | ffl N β|l f ∞ -S k+1 dλ+ ffl N β|l S k+1 dλ-S k+1 (β)| ≤ 2 -k-4 +| ffl N β|l S k+1 dλ-S k+1 (β)|, so that lim l→∞ f (β|l) = f ∞ (β), osc(f, β) = 0 and β / ∈ D(f ). • If β ∈ G and n ∈ ω, then there is j ∈ ω with β ∈ N s n j . Note that f (s n j ) = N s n j f ∞ dλ = N s n j S n dλ+ N s n j (f ∞ -S n ) dλ and | ´Ns n j (f ∞ -S n ) dλ| ≤ λ(G * n+1 ∩ N s n j ) < 1 8 λ(N s n j ), so that | ffl N s n j (f ∞ -S n ) dλ| < 1 8 . By (6), |f (s n j )-S n (β)| < 1 8 + 1 8 = 1 4 . As S n (β) takes infinitely often the values 1 and 0, osc(f, β) ≥ 1 2 and β ∈ D(f ).
The main result will be a consequence of the main lemma and the following.

Lemma 2.8 Let (f n ) n∈ω be a sequence of martingales such that {osc(f n , β) | (n, β) ∈ ω×2 ω } ⊆ {0} ∪ [ 1 2 , 1].
Then there is a martingale f with

D(f ) = n∈ω D(f n ).
Proof. We first observe the following facts. Let g, h : 2 <ω → R be bounded, β ∈ 2 ω and a ∈ R.

(1) osc(g+h, β) ≤ osc(g, β)+osc(h, β).

This comes from the triangle inequality.

(2) osc(ag, β) = |a|•osc(g, β).

(3) osc(g+h,

β) = osc(h, β) if osc(g, β) = 0. By (1), osc(h, β) ≤ osc(g+h, β)+osc(-g, β) = osc(g+h, β) ≤ osc(g, β)+osc(h, β) = osc(h, β), so that osc(h, β) = osc(g+h, β). (4) osc(g, β) ≤ a if g(β|l) ∈ [0, a] for each l ∈ ω.
• We set D n := D(f n ) for each n ∈ ω, and f := Σ n∈ω 4 -n f n . Note that f is defined and a martingale.

• If β / ∈ n∈ω D n , then osc(f n , β) = 0 for each n ∈ ω. In particular, osc(4 -n f n , β) = 0 for each n ∈ ω, by (2). Let ε > 0, and M ∈ ω with Σ n>M 4 -n ≤ ε. By (1), osc(Σ n≤M 4 -n f n , β) = 0. By (3) and (4), osc(f, β) = osc(Σ n>M 4 -n f n , β) ≤ Σ n>M 4 -n ≤ ε. As ε is arbitrary, osc(f, β) = 0, β / ∈ D(f ), which shows that D(f ) ⊆ n∈ω D n . • If β ∈ n∈ω D n , then let m be minimal such that β ∈ D m . Note that f = Σ n<m 4 -n f n +4 -m f m +Σ n>m 4 -n f n .
By (2) and (3), osc(f, β) = osc(4 -m f m +Σ n>m 4 -n f n , β). By (1), ( 2) and (4),

osc(f, β) ≥ osc(4 -m f m , β)-osc(Σ n>m 4 -n f n , β) ≥ 4 -m 1 2 -4 -m 1 3 > 0.
Thus β ∈ D(f ).

Effectivity and uniformity

-We refer to [M] for the basic notions of effective descriptive set theory. We first recall some material present in it.

• Let (p n ) n∈ω be the sequence of prime numbers 2, 3, ...

• If l ∈ ω and s ∈ ω l , then s :=< s(0), ..., s(l -1) >:= p s(0)+1 0 ...p s(l-1)+1 l-1 ∈ ω codes s (if l = 0, then <>:= 1).
• If α ∈ ω ω and l ∈ ω, then α(l) :=< α(0), ..., α(l-1) >∈ ω codes α|l ∈ ω l , and α * is defined by removing the first coordinate: α * := α(1), α(2), ... .

• If κ ∈ {2, ω}, then < ., . >: (κ ω ) 2 → κ ω is a recursive homeomorphism with inverse map α → (α) 0 , (α) 1 defined for example by (α) ε (n) := α(2n+ε) if (n, ε) ∈ ω×2 (we will also consider recursive homeomorphisms < ., ., . >: (κ ω ) 3 → κ ω and < ., ., ... >: (κ ω ) ω → κ ω ).

• If u ∈ ω, then Seq(u) means that there are l ∈ ω and s ∈ ω l (denoted by s(u)) such that u =< s(0), ..., s(l -1) >. The natural number (u) i is s(i) if i < l, and 0 otherwise. The number l is the length of u and is denoted by lh(u). If k ≤ l, then u(k) :=< s(0), ..., s(k -1) >, so that u(l) = u. The standard basic clopen set is

N u := {β ∈ 2 ω | ∀i < lh(u) β(i) = (u) i }. We set u -:=< (u) 0 , ..., (u) lh(u)-2 > (u -:=<> if lh(u) ≤ 1).
• Let X be a recursively presented Polish space. Then we will consider the effective basic open set N (X, u) = B X (r ((u) 1 ) 0 , ((u) 1 ) 1 ((u) 1 ) 2 +1 ).

• Let n ≥ 1 be a natural number. A subset T of ω n is a tree if Seq(u i ) and lh(u i ) = lh(u 0 ) for each (u 0 , ..., u n-1 ) ∈ T and each i < n, and u 0 (k), ..., u n-1 (k) ∈ T if (u 0 , ..., u n-1 ) ∈ T and k ≤ lh(u 0 ).

• The next result is a part of 4A.1 in [M].

Theorem 3.1 Let m ≥ 1 be a natural number, and

B ∈ Σ 0 1 ω ω ×(ω ω ) m . Then there is a recursive subset T of ω ω × ω m such that (α, α 1 , ..., α m ) ∈ B ⇔ ∃l ∈ ω α, α 1 (l), ..., α m (l) /
∈ T , and

T α := {(u 0 , ..., u m-1 ) ∈ ω m | (α, u 0 , ..., u m-1 ) ∈ T } is a tree for each α ∈ ω ω .
• The next result is a part of 4A.7 in [M].

Theorem 3.2 Let X be a recursively presented Polish space and B ∈ ∆ 1 1 (X). Then we can find a recursive function π :

ω ω → X and C ∈ Π 0 1 (ω ω ) such that π is injective on C and π[C] = B.
-We then recall some material from [L].

Notation. Let X be a recursively presented Polish space. Recall that there is a pair (W X , C X ) such that

• W X ⊆ ω is a Π 1 1 set of codes for the ∆ 1 1 subsets of X, • C X ⊆ ω ×X is Π 1 1 and ∆ 1 1 (X) = {C X n | n ∈ W X }, which means that C X is "universal" for the ∆ 1 1 subsets of X, • the relation "n ∈ W X ∧ (n, x) / ∈ C X " is Π 1 1 in (n, x).
If X = ω ω ×2 ω , then we simply write (W, C) := (W X , C X ).

The next result will be extremely useful in the sequel.

The uniformization lemma. Let X, Y be recursively presented Polish spaces, and P ∈ Π 1 1 (X ×Y ). Then the set

P + := {x ∈ X | ∃y ∈ ∆ 1 1 (x) (x, y) ∈ P } is Π 1 1 , and there is a partial Π 1 1 -recursive map f : X → Y such that x, f (x) ∈ P for each x ∈ P + . If moreover S ⊆ P + is a Σ 1 1 subset of X, then there is a total ∆ 1 1 -recursive map g : X → Y such that x, g(x) ∈ P for each x ∈ S.
-The following definition is inspired by 3H.1 in [M].

Definition 3.3 (a) Let Γ be a class of subsets of recursively presented Polish spaces, and Γ be the associated boldface class. A system of sets U X ∈ Γ(ω ω ×X), where is X is a recursively presented Polish space, is a nice parametrization in Γ for Γ if the following hold:

(1)

Γ(X) = {U X α | α ∈ ω ω }, (2) Γ(X) = {U X α | α ∈ ω ω recursive}, (3) if X is a recursively presented Polish space, then there is R : ω ω × ω ω → ω ω recursive such that (α, γ, x) ∈ U ω ω ×X ⇔ R(α, γ), x ∈ U X if (α, γ, x) ∈ ω ω ×ω ω ×X.
(b) If U belongs to a nice parametrization, then we will say that U is a good universal set . (c) If U satisfies all these properties except maybe (3), then we will say that U is a suitable universal set .

By 3E.2, 3F.6 and 3H.1 in [M], there is a nice parametrization in Π 1 n for Π 1 n , for each natural number n ≥ 1.

-We now recall two results that can essentially be found in [K1]. The first one is Theorem 2.2.3.(a) (see also [T1]).

Theorem 3.4 (Tanaka) Let U ∈ Σ 1 1 (ω ω ×ω ω ) be ω ω -universal for the analytic subsets of ω ω . Then L(U ) := (α, p) ∈ ω ω ×ω | λ(U α ∩ 2 ω ) > (p) 0 (p) 1 +1 is Σ 1 1 . Corollary 3.5 Let B ∈ ∆ 1 1 (ω ω ×2 ω ). (a) The map λ B : ω ω → R defined by λ B (α) := λ(B α ) is ∆ 1
1 -recursive, and the partial function

(n, α) → λ(C n,α ) is Π 1 1 -recursive on its domain W ×ω ω . (b) Let D ⊆ ω, O 0 ∈ Σ 1 1 (ω×ω ω ×2 ω ), and O 1 ∈ Π 1 1 (ω×ω ω ×2 ω ) be such that λ (O 0 ) n,α = λ (O 1 ) n,α if n ∈ D. Then the partial map λ O : D×ω ω → R defined by λ O (n, α) := λ (O 0 ) n,α is Σ 1 1 -recursive and Π 1 1 -recursive on its domain. (c) The partial map d B : ω ω ×2 ω → R defined by d B (α, β) := d(B α , β) is ∆ 1 1 -recursive, and the partial map (n, α, β) → d(C n,α , β) is Π 1 1 -recursive on its Π 1 1 domain {(n, α, β) ∈ W ×ω ω ×2 ω | d(C n,α , β) exists}. (d) Let h : ω ω ×2 ω → R be ∆ 1 1 -recursive taking values in [0, 1]. Then the partial map i h : ω ω ×ω → R defined by i h (α, u) := ´Nu h(α, .) dλ is ∆ 1 1 -recursive on its ∆ 0 1 domain ω ω ×{u ∈ ω | Seq(u)}.
Proof. (a) It is enough to see that the relations

P B (α, p) ⇔ λ(B α ) > r p := (-1) (p) 0 • (p) 1 (p) 2 +1 and Q B (α, p) ⇔ λ(B α ) < r p are ∆ 1 1 to see that λ B is ∆ 1 1 -recursive. Note that there is φ : ω 2 → ω recursive with r φ(p,l) = r p -1 l+1 . Thus Q B (α, p) ⇔ ∃l ∈ ω λ(B α ) ≤ r p -1 l+1 ⇔ ∃l ∈ ω ¬ λ(B α ) > r p -1 l+1 ⇔ ∃l ∈ ω ¬P B α, φ(p, l) ,
so that it is enough to see that P B is ∆ 1 1 .

• Now let S ∈ Σ 1 1 ω ω ×(ω ω ) 2 be a good ω ω -universal for the analytic subsets of (ω ω ) 2 . We set

U (α, γ) ⇔ S (α) 0 , (α) 1 , γ , so that U ∈ Σ 1 1 (ω ω × ω ω
) is ω ω -universal for the analytic subsets of ω ω . Let A be a Σ 1 1 subset of ω ω ×2 ω . Then there is α 0 ∈ ω ω recursive with A = S α 0 , so that

γ ∈ A α ⇔ (α 0 , α, γ) ∈ S ⇔ (< α 0 , α >, γ) ∈ U.

This implies that the relation R

A (α, p) ⇔ λ(A α ) > r p , equivalent to (p) 0 is odd ∧ (p) 1 > 0 ∨ (p) 0 is even ∧ (< α 0 , α >, < (p) 1 , (p) 2 >) ∈ L(U ) , is Σ 1 1 , by Theorem 3.4.
• In particular, this applies to A := B, so that P B is Σ 1 1 . Now note that

P B (α, p) ⇔ λ (¬B) α < 1-r p ⇔ Q ¬B α, φ ′ (p) ,
for some φ ′ : ω → ω is recursive, so that P B is Π 1 1 by the previous computation.

• We set C ′ := (γ, β) ∈ ω ω ×2 ω | γ(0) ∈ W ∧ γ(0), γ * , β ∈ C . As C ′ is Π 1 1 , A := (α, p) ∈ ω ω ×ω | λ (¬C ′ ) α > r p is Σ 1 1 , by the previous discussion. So let n ∈ W. Note that λ(C n,α ) > r p ⇔ λ(¬C n,α ) < 1-r p ⇔ λ (¬C ′ ) nα < 1-r p ⇔ ∃l ∈ ω λ (¬C ′ ) nα ≤ 1-r p -1 l+1 ⇔ ∃l ∈ ω nα, φ ′′ (p, l) / ∈ A, for some recursive φ ′′ : ω 2 → ω. Similarly, the relation "λ(C n,α ) < r p " is Π 1 1 in (n, α, p) since the relation "n ∈ W ∧ (n, α, β) / ∈ C" is Π 1 1 , so that (n, α) → λ(C n,α ) is Π 1 1 -recursive on W ×ω ω . (b) Let A := (α, β) ∈ ω ω × 2 ω | α(0), α * , β ∈ O 0 . Note that A is Σ 1 1 . By (a), the relation R A (α, p) ⇔ λ(A α ) > r p is Σ 1 1 . Therefore the relation R O 0 (n, α, p) ⇔ R A (nα, p) is Σ 1 1 too. Moreover, R O 0 (n, α, p) ⇔ λ (O 0 ) n,α > r p ⇔ λ O (n, α) > r p .
• Assume now that n ∈ D. Then as above there is φ ′′ : ω 2 → ω recursive such that

λ O (n, α) > r p ⇔ λ (O 1 ) n,α > r p ⇔ λ (¬O 1 ) n,α < 1-r p ⇔ ∃l ∈ ω λ (¬O 1 ) n,α ≤ 1-r p -1 l+1 ⇔ ∃l ∈ ω ¬ λ (¬O 1 ) n,α > r φ ′′ (p,l) ⇔ ∃l ∈ ω ¬R ¬O 1 n, α, φ ′′ (p, l) , which shows the existence of R ′ O 0 ∈ Π 1 1 such that λ O (n, α) > r p ⇔ R ′ O 0 (n, α, p) if n ∈ D.
• Assume that n ∈ D. Then there is φ ′ : ω → ω recursive such that

λ O (n, α) < r q ⇔ λ (O 1 ) n,α < r q ⇔ λ (¬O 1 ) n,α > 1-r q ⇔ R ¬O 1 n, α, φ ′ (q) , which shows the existence of R ′′ O 0 ∈ Σ 1 1 such that λ O (n, α) < r q ⇔ R ′′ O 0 (n, α, q) if n ∈ D.
• Assume that n ∈ D. Then there is φ ′′ : ω 2 → ω recursive such that

λ O (n, α) < r q ⇔ λ (O 0 ) n,α < r q ⇔ ∃l ∈ ω λ (O 0 ) n,α ≤ 1-r q -1 l+1 ⇔ ∃l ∈ ω ¬ λ (O 0 ) n,α > r φ ′′ (q,l) ⇔ ∃l ∈ ω ¬R O 0 n, α, φ ′′ (q, l) , which shows the existence of R ′′′ O 0 ∈ Π 1 1 such that λ O (n, α) < r q ⇔ R ′′′ O 0 (n, α, q) if n ∈ D. • Finally, r p < λ O (n, α) < r q ⇔ R O 0 (n, α, p) ∧ R ′′ O 0 (n, α, q) and r p < λ O (n, α) < r q ⇔ R ′ O 0 (n, α, p) ∧ R ′′′ O 0 (n, α, q) if n ∈ D, which shows that λ O is Σ 1 1 -recursive and Π 1 1 -recursive on D×ω.
(c) We first prove the following. Let X, Y be a recursively presented Polish spaces and g : X ×ω → Y be a ∆ 1 1 -recursive map. Then the partial map h : X → Y defined by h(x) := lim l→∞ g(x, l)

when this limit exists is ∆ 1 1 -recursive.

Indeed, the domain

D of h is {x ∈ X | ∀r ∈ ω ∃L ∈ ω ∀k, l ≥ L d Y g(x, k), g(x, l) < 2 -r }, so that D is ∆ 1 1 . If x ∈ D, then h(x) ∈ N (Y, u) is equivalent to ∃p, q ∈ ω p q + 1 < (u) 1 1 (u) 1 2 + 1 ∧ ∃L ∈ ω ∀l ≥ L g(x, l) ∈ N Y, 0, < (u) 1 0 , p, q > ,
and we are done.

• We set B ′ := (α, γ) ∈ ω ω ×2 ω | (α) 0 , γ ∈ B ∧ γ ∈ N (α) * 1 |(α) 1 (0) , so that B α ∩ N β|l = B ′ <α,lβ>
and B ′ is ∆ 1 1 . By (a), the map g :

ω ω × 2 ω × ω → [0, 1] defined by g(α, β, l) := 2 -l λ(B α ∩ N β|l ) is ∆ 1 1 -recursive.
By the previous point, the partial map h :

ω ω ×2 ω → [0, 1] defined by h(α, β) := lim l→∞ 2 -l λ(B α ∩ N β|l )
when it exists is also

∆ 1 1 -recursive. But h = d B .
• Fix n ∈ W. Then there is q(n) ∈ W such that

C q(n) = (γ, δ) ∈ ω ω ×2 ω | n, (γ) 0 , δ) ∈ C ∧ (γ) * 1 |(γ) 1 (0) ⊆ δ .
Moreover, we may assume that q is Π 1 1 -recursive on W, by the uniformization lemma. As Π 1 1 has the substitution property, the map g

′ : (n, α, β, l) → 2 -l λ(C q(n),<α,lβ> ) = 2 -l λ(C n,α ∩ N β|l ) is Π 1 1 - recursive on W ×ω ω ×2 ω ×ω. As above, the map h ′ : (n, α, β) → lim l→∞ 2 -l λ(C n,α ∩ N β|l ) = d(C n,α , β) is Π 1 1 -recursive on the Π 1 1 set {(n, α, β) ∈ W ×ω ω ×2 ω | d(C n,α , β) exists}.
(d) The argument here is partly similar to 11.6 and 17.25 in [K2]. We set, for

(k, l) ∈ ω 2 , A k,l := h -1 [ k 2 l , k+1 2 l )
and define h l :

ω ω ×2 ω → [0, 1] by h l = Σ k≤2 l k 2 l χ A k,l . We also define R ⊆ ω ω ×2 ω ×ω 3 by R(α, β, u, k, l) ⇔ k 2 l ≤ h(α, β) < k+1 2 l ∧ Seq(u) ∧ β ∈ N u , so that R is ∆ 1 1 . Then we define O ⊆ ω ω ×2 ω by O(α, β) ⇔ Seq α(0) ∧ lh α(0) = 3 ∧ R α * , β, α(0) 0 , α(0) 1 , α(0) 2 , so that O is ∆ 1 1 .
Note that (h l ) is a sequence of Borel functions pointwise converging to h. By Lebesgue's dominated convergence theorem, ´Nu h(α, .) dλ = lim l→∞ ´Nu h l (α, .) dλ if Seq(u). Note that

´Nu h l (α, .) dλ = ´Nu Σ k≤2 l k 2 l χ A k,l (α, .) dλ = Σ k≤2 l k 2 l λ (A k,l ) α ∩ N u = Σ k≤2 l k 2 l λ(R α,u,k,l ) = Σ k≤2 l k 2 l λ(O <u,k,l>α ).
Using (a), this implies that the map (α, u, l) → ´Nu h l (α, .) dλ is ∆ 1 1 -recursive on its ∆ 0 1 domain ω ω ×{u ∈ ω | Seq(u)}×ω. As in the proof of (c), i h is ∆ 1 1 -recursive on its domain.

We now prove a uniform version of Theorem 4.3.2 in [K1] (due to Tanaka, see [T2]).

Theorem 3.6 Let B ∈ ∆ 1 1 (ω ω ×2 ω ), and ǫ : ω ω → R be ∆ 1 1 -recursive such that ǫ(α) ∈ (0, 1] for each α ∈ ω ω . Then there is T ∈ ∆ 1 1 (ω ω ×ω) such that (a) T α is a tree for each α ∈ ω ω , (b) if K = (α, β) ∈ ω ω ×2 ω | ∀l ∈ ω α, β(l) ∈ T , then K α ⊆ B α and λ(K α ) ≥ λ(B α )-ǫ(α) for each α ∈ ω ω . Proof. Theorem 3.2 gives π : ω ω → ω ω ×2 ω recursive and C ∈ Π 0 1 (ω ω ) such that π is injective on C and π[C] = B. We set Q := {(α, β, γ) ∈ (ω ω ) 3 | γ ∈ C ∧ π(γ) = (α, β)}. As Q ∈ Π 0 1 , Theorem 3.1 gives a recursive subset T of ω ω ×ω 2 such that (α, β, γ) ∈ Q ⇔ ∀l ∈ ω α, β(l), γ(l) ∈ T and T α is a tree for each α ∈ ω ω . • We set, for u, v ∈ ω, u ≤ a v ⇔ Seq(u), Seq(v) ∧ lh(u) = lh(v) ∧ ∀i < lh(u) (u) i ≤ (v) i .
• Then we set, for u ∈ ω with Seq(u) and α ∈ ω ω ,

B u α := β ∈ 2 ω | ∃γ ∈ ω ω γ lh(u) ≤ a u ∧ ∀l ∈ ω α, β(l), γ(l) ∈ T and B ′ := {(α, β) ∈ ω ω ×2 ω | Seq α(0) ∧ β ∈ B α(0) α * }. Note that B ′ is Σ 1 1 . In fact, B ′ is ∆ 1
1 by uniqueness of the witness γ.

• We now define δ α ∈ ω ω as follows. We define δ α (i) by induction on i. We first set

δ α (0) := min{k ∈ ω | λ(B <k> α ) > λ(B α )- ǫ(α) 2 }.
This number exists since B α is the increasing union of the B <k> α 's. Then

δ α (i+1) := min{k ∈ ω | λ(B <δα(0),...,δα(i),k> α ) > λ(B α )- ǫ(α) 2 -...- ǫ(α) 2 i+2 }.
Note that δ α ∈ ∆ 1 1 (α), by Corollary 3.5.(a).

• We set

T := {(α, v) ∈ ω ω ×ω | Seq(v) ∧ ∃u ≤ a δ α (lh(v)) (α, v, u) ∈ T }, so that T ∈ ∆ 1 1 (ω ω ×ω) and T α is a tree for each α ∈ ω ω . • We set K := {(α, β) ∈ ω ω ×2 ω | ∀l ∈ ω β ∈ B δα(l) α }, so that K α ⊆ B α and λ(K α ) = lim l→∞ λ(B δα(l) α ) ≥ λ(B α )-ǫ(α) for each α ∈ ω ω since (B δα(l) α
) l∈ω is decreasing. It remains to apply König's lemma to see that

K = (α, β) ∈ ω ω ×2 ω | ∀l ∈ ω α, β(l) ∈ T since s ∈ ω <ω |< s(0), ..., s(|s|-1) >≤ a δ α |s| ∧ α, β(|s|), < s(0), ..., s(|s|-1) > ∈ T
is a finitely splitting tree.

-We want to prove an effective and uniform version of the Lusin-Menchoff lemma. We first need the following result, which slightly and uniformly refines Theorem A in [L] at the first level of the Borel hierarchy.

Lemma 3.7 Let O be a ∆ 1 1 subset of ω ω ×2 ω with open vertical sections. Then there is a ∆ 1 1 -recursive map f : ω ω → ω ω such that O α is the disjoint union N f (α)(u) | u ∈ ω ∧ Seq f (α)(u) , for each α ∈ ω ω . Proof. Let P := (α, u) ∈ ω ω ×ω | Seq(u) ∧ lh(u) = 0 ∨ (N u ⊆ O α ∧ N u -⊆ O α ) . Note that P is Π 1
1 , since a nonempty ∆ 1 1 (α) closed subset of 2 ω contains a ∆ 1 1 (α) point, by 4F.15 in [M]. We then define a relation R on ω ω ×2 ω ×ω by R(α, β, u) ⇔ P (α, u) ∧ β ∈ N u , so that R is Π 1 1 . Note that, for each (α, β) ∈ O there is u with R(α, β, u). By 4B.5 in [M], there is a ∆ 1 1 -recursive map g : By 4B.11 and 4C in [M], there is

ω ω ×2 ω → ω such that R α, β, g(α, β) for each (α, β) ∈ O. Fix α ∈ ω ω . Note that S α := {g(α, β) | β ∈ O α } is a Σ 1 1 (α) subset of ω contained in the Π 1 1 (α) set P α .
D α ∈ ∆ 1 1 (α) with S α ⊆ D α ⊆ P α . Note that O α ⊆ u∈D α N u ⊆ O α , so that O α is the disjoint union of the sequence (N u ) u∈D α . We define δ α ∈ ω ω by δ α (u) := u if u ∈ D α , 0 otherwise. Note that δ α ∈ ∆ 1 1 (α) and O α is the disjoint union N δα(u) | u ∈ ω ∧ Seq δ α (u) . As the set (α, δ) ∈ ω ω ×ω ω | δ ∈ ∆ 1 1 (α) ∧ O α is the disjoint union N δ(u) | u ∈ ω ∧ Seq δ(u) is Π 1 1
, it remains to apply the uniformization lemma to get the desired map f .

Notation. We set W 1 := {n ∈ W | ∀α ∈ ω ω ∃γ n ∈ ∆ 1 1 (α) C n,α = N γn(u) | u ∈ ω ∧ Seq γ n (u)
, so that, by Lemma 3.7, W 1 is a Π 1 1 set of codes for the ∆ 1 1 subsets of ω ω × 2 ω with open vertical sections.

Lemma 3.8 Let F be a ∆ 1 1 subset of ω ω × 2 ω with closed vertical sections, and B be a

∆ 1 1 subset of ω ω ×2 ω such that B ⊇ F and d(B α , β) = 1 for each (α, β) ∈ F . Then there is a ∆ 1 1 subset C of ω ω ×2 ω with closed vertical sections such that (1) F ⊆ C ⊆ B, (2) d(B α , β) = 1 for each (α, β) ∈ C, (3) d(C α , β) = 1 for each (α, β) ∈ F . Proof. Lemma 3.7 gives a ∆ 1 1 -recursive map f : ω ω → ω ω such that (¬F ) α is the disjoint union N f (α)(u) | u ∈ ω ∧ Seq f (α)(u) , for each α ∈ ω ω . We set B ′ := (α, γ) ∈ ω ω ×2 ω | (α) 0 , γ ∈ B ∧ Seq f (α) 0 (α) 1 (0) ∧ γ ∈ N f ((α) 0 )((α) 1 (0)) , so that B ′ is ∆ 1 1 and B α ∩ N f (α)(u) = B ′ <α,u ∞ > if Seq f (α)(u) . By Corollary 3.5.(c), the partial map (α, β, u) → d(B α ∩ N f (α)(u) , β) is ∆ 1 1 -recursive.
We then set

B ′′ := {(α, γ) ∈ B ′ | d(B (α) 0 ∩ N f ((α) 0 )((α) 1 (0)) , γ) = 1}, so that B ′′ is ∆ 1 1 and {β ∈ B α ∩ N f (α)(u) | d(B α ∩ N f (α)(u) , β) = 1} = B ′′ <α,u ∞ > if Seq f (α)(u) . We define ǫ : ω ω → R by ε(α) := 2 -(α) 1 (0) λ(B ′ α ) if λ(B ′ α ) = 0, 1 otherwise, so that ǫ is ∆ 1
1 -recursive by Corollary 3.5.(a), and ǫ(α) ∈ (0, 1] for each α ∈ ω ω . Theorem 3.6 gives

T ∈ ∆ 1 1 (ω ω ×ω) such that (a) T α is a tree for each α ∈ ω ω , (b) if K = (α, β) ∈ ω ω ×2 ω | ∀l ∈ ω α, β(l) ∈ T , then K α ⊆ B ′′ α and λ(K α ) ≥ λ(B ′′ α )-ǫ(α) for each α ∈ ω ω .
We set, for u ∈ ω,

F u := (α, β) ∈ ω ω ×2 ω | Seq f (α)(u) ∧ (< α, u ∞ >, β) ∈ K ∧ λ(B ′ <α,u ∞ > ) = 0 . As K is ∆ 1 1 with closed vertical sections, so is F u . If Seq f (α)(u) and λ(B ′ <α,u ∞ > ) = 0, then λ(B α ∩ N f (α)(u) ) = 0 and F u α = ∅, so that F u α ⊆ {β ∈ B α ∩ N f (α)(u) | d(B α ∩ N f (α)(u) , β) = 1} and λ(F u α ) ≥ (1-2 -u )λ(B α ∩ N f (α)(u) ). If Seq f (α)(u) and λ(B ′ <α,u ∞ > ) = 0, then F u α = K <α,u ∞ > ⊆ B ′′ <α,u ∞ > = {β ∈ B α ∩ N f (α)(u) | d(B α ∩ N f (α)(u) , β) = 1}.
• Similarly, we construct a ∆ 1 1 -recursive map F : ω → ω satisfying the following properties, if

D := {p ∈ ω | Seq(p) ∧ lh(p) = 2 ∧ 0 < (p) 1 ≤ 2 (p) 0 }. (a) F (p) ∈ W 1 if p ∈ D, in which case we set C p := ¬C F (p) , (b) C p ⊆ C p ′ if p, p ′ ∈ D ∧ (p ′ ) 1 2 (p ′ ) 0 ≤ (p) 1 2 (p) 0 , (c) d (C p ′ ) α , β = 1 if p, p ′ ∈ D ∧ (p ′ ) 1 2 (p ′ ) 0 < (p) 1 2 (p) 0 ∧ (α, β) ∈ C p . • This allows us to define h by 1-h(α, β) := 0 if (α, β) ∈ G, sup{ (p) 1 2 (p) 0 | p ∈ D ∧ (α, β) ∈ C p } if (α, β) / ∈ G. Note that h is ∆ 1 1 -recursive since D ∈ ∆ 0 1 , so that the relation "p ∈ D ∧ (α, β) ∈ C p " is ∆ 1 1 in (p, α, β
). We conclude as in the proof of Lemma 2.5.

-We are now ready to prove the main lemma in this section. We equip the space [0, 1] 2 <ω with the distance defined by d(f, g) := Σ u∈ω,Seq(u)

|f (s(u))-g(s(u))| 2 u+1
. We give a recursive presentation of ([0, 1] 2 <ω , d). We set

f n (s) := ((n) s ) 0 ((n) s ) 0 +((n) s ) 1 +1 if Seq(n) ∧ ∀k < lh(n) Seq (n) k ∧ lh (n) k = 2 ∧ s < lh(n), 0 otherwise, so that (f n ) is dense in [0, 1] 2 <ω . It is now routine to check that the relations "d(f m , f n ) ≤ p q+1 " and "d(f m , f n ) < p
q+1 " are recursive in (m, n, p, q). It is also routine to check that F :

ω ω → [0, 1] 2 <ω is ∆ 1 1 -recursive if the map F ′ : ω ×ω ω → R defined by F ′ (u, α) := F (α) s(u) if Seq(u), 0 otherwise, is ∆ 1
1 -recursive (s(u) was defined at the beginning of Section 3).

Lemma 3.10 Let V := {(f, β) ∈ M× 2 ω | osc(f, β) > 0}, G be a nonempty G δ ∩ ∆ 1 1 subset of 2 ω with λ(G) = 0, and G be a ∆ 1 1 subset of ω ω ×2 ω , contained in ω ω ×G, and with G δ vertical sections. Then there is a ∆ 1 1 -recursive map F : ω ω → [0, 1] 2 <ω , taking values in M, and such that G α = V F (α) for each α ∈ ω ω .

Proof. We will define, by primitive recursion, f : ω → ω 4 coding g n , S n , G * n , and (s n j ) j∈In defining G * * n considered in the proof of the Lemma 2.7. We must find r :

ω 4 ×ω → ω 4 with f (n+1) = r f (n), n . In practice, (1) f 0 (n) ∈ W 1 codes G * n ⊆ ω ω ×2 ω , (2) f 1 (n) ∈ W ω ω ×2 ω ×R codes the graph of g n : ω ω ×2 ω → R, (3) f 2 (n) ∈ W ω ω ×2 ω ×R codes the graph of S n : ω ω ×2 ω → R, (4) f 3 (n) ∈ W ω ω ×ω ω
codes the graph of the function α → (s n,α j ) j∈In,α .

• By Theorem 3.5 in [L], there is a

∆ 1 1 subset O of ω × ω ω × 2 ω such that O n,α is open for each (n, α) ∈ ω × ω ω and G = n∈ω O n . Moreover, we may assume that (O n ) n∈ω is decreasing and O 0 = ω ω ×2 ω . • Let n 0 ∈ W 1 with C n 0 = ω ω ×2 ω , n 1 ∈ W ω ω ×2 ω ×R with C ω ω ×2 ω ×R n 1 = {(α, β, r) ∈ ω ω ×2 ω ×R | r = 1}, and n 3 ∈ W ω ω ×ω ω with C ω ω ×ω ω n 3 = {(α, γ) ∈ ω ω ×ω ω | γ = 10 ∞ }. We set f (0) := (n 0 , n 1 , n 1 , n 3 ), so that C n 0 = G * 0 , C ω ω ×2 ω ×R n 1 = Gr(g 0 ) = Gr(S 0 ), C ω ω ×ω ω n 3 = Gr(α → 10 ∞ ), u ∈ ω | Seq (10 ∞ )(u) = {0} = I 0
and (10 ∞ )(0) = 1 =<>= s 0 0 . So f (0) is as desired.

• We now study the induction step. This means that we must define r(n 0 , n 1 , n 2 , n 3 , n) ∈ ω 4 .

(1) We first define r 0 (n 0 , n 1 , n 2 , n 3 , n) coding G * n+1 . Fix n 3 ∈ W ω ω ×ω ω coding the graph of a ∆ 1 1 -recursive function φ : ω ω → ω ω such that the sequences s φ(α)(u) coded by the u's with Seq φ(α)(u) are pairwise incompatible and

G α ⊆ N φ(α)(u) | u ∈ ω ∧ Seq φ(α)(u) (we call P 3 the Π 1
1 set of such n 3 's). Let α ∈ ω ω . Assume that Seq φ(α)(u) (which intuitively means that u ∈ I n,α and s n,α u is coded by φ(α)(u)). By continuity of λ, u) satisfies the properties of the set O j in the proof of Lemma 2.7. We will have u) . By Corollary 3.5 and the uniformization lemma, we may assume that the map j is ∆ 1 1 -recursive on its ∆ 1 1 domain u) . So we proved that, for each (n 3 , n) ∈ P 3 ×ω, there is m ∈ W 1 such that, for each α ∈ ω ω ,

0 = λ(G α ∩ N φ(α)(u) ) = lim j→∞ λ(O j,α ∩ N φ(α)(u) ). This gives j(n, α, u) > n minimal with λ(O j(n,α,u),α ∩ N φ(α)(u) ) < 2 -n-3-lh(φ(α)(u)) (note that 2 -lh(φ(α)(u)) = λ(N φ(α)(u) )). Moreover, G α ∩N φ(α)(u) ⊆ O j(n,α,u),α ∩N φ(α)(u) ⊆ O n+1,α ∩N φ(α)(u) , so that O j(n,α,u),α ∩ N φ(α)(
G * n+1,α = Seq(φ(α)(u)) O j(n,α,u),α ∩ N φ(α)(
(n, α, u) ∈ ω×ω ω ×ω | Seq φ(α)(u) . Note that G * n+1 is a ∆ 1 1 subset of ω ω ×2 ω with open vertical sections, which gives m ∈ W 1 such that C m = G * n+1 . By incompatibility, G * n+1,α ∩ N φ(α)(u) = O j(n,α,u),α ∩ N φ(α)(
(1) G α ⊆ C m,α ⊆ O n+1,α ∩ N φ(α)(u) | u ∈ ω ∧ Seq φ(α)(u) , (5) λ(C m,α ∩ N φ(α)(u) ) < 2 -n-3-lh(φ(α)(u)) if u ∈ ω ∧ Seq φ(α)(u) .
By Corollary 3.5 and the uniformization lemma, we may assume that the map r0 : (n 3 , n) → m is Π 1 1 -recursive on P 3 × ω. We set r 0 (n 0 , n 1 , n 2 , n 3 , n) := r0 (n 3 , n), which defines a partial map r 0 which is Π 1 1 -recursive on its Π 1 1 domain ω 3 ×P 3 ×ω.

(2) We now define r 1 (n 0 , n 1 , n 2 , n 3 , n) coding g n+1 . We use Lemma 3.9 and its proof. Note that r

0 (n 0 , n 1 , n 2 , n 3 , n) ∈ D 0 := {m ∈ W 1 | G ⊆ C m }.
The proof of Lemma 3.9 shows that for any m ∈ D 0 there is Fm ∈ ω ω ∩ ∆ 1 1 satisfying the conditions (a), (b), (c) and

(d) ∀p ∈ D ¬(0 < (p) 1 = 2 (p) 0 ) ∨ C Fm(p) ⊆ C m .
The uniformization lemma shows that we may assume that the partial map F :

m → Fm is Π 1 1 - recursive on D 0 .
The definition of h in the proof of Lemma 3.9 and the uniformization lemma show the existence of a partial map H : ω → ω, which is Π 1 1 -recursive on D 0 , and such that H(m) is in W ω ω ×2 ω ×R and codes the graph of a ∆ 1 1 -recurive map h :

ω ω ×2 ω → R with 1-h(α, β) := 0 if (α, β) ∈ G sup{ (p) 1 2 (p) 0 | p ∈ D ∧ (α, β) / ∈ C F (m)(p) } if (α, β) / ∈ G if m ∈ D 0 . We set P 1 := {c ∈ W ω ω ×2 ω ×R | C c is the graph of a function ζ c }. It is routine to check that there is a Π 1 1 -recursive partial map I : ω 2 → ω on its domain P 2 1 such that I(c, c ′ ) ∈ W ω ω ×2 ω ×R is the graph of the function min(ζ c , ζ c ′ ) if c, c ′ ∈ P 1 . We set r 1 (n 0 , n 1 , n 2 , n 3 , n) := I n 1 , H r 0 (n 0 , n 1 , n 2 , n 3 , n) , so that r 1 is Π 1 1 -recursive on its Π 1 1 domain ω×P 1 ×ω×P 3 ×ω.
(3) We now define r 2 (n 0 , n 1 , n 2 , n 3 , n) coding

S n+1 = S n +g n+1 if n is odd, S n -g n+1 if n is even.
It is routine to check that there is a Π 1 1 -recursive partial map S : ω 3 → ω on its domain P 2 1 ×ω such that S(c, c ′ , n) ∈ W ω ω ×2 ω ×R codes the graph of the function

(α, β) → ζ c (α, β)+ζ c ′ (α, β) if n is odd ζ c (α, β)-ζ c ′ (α, β) if n is even if (c, c ′ , n) ∈ P 2 1 × ω. We set r 2 (n 0 , n 1 , n 2 , n 3 , n) := S n 2 , r 1 (n 0 , n 1 , n 2 , n 3 , n), n , so that r 2 is Π 1 1 -recursive on its Π 1 1 domain ω×P 2 1 ×P 3 ×ω.
(4) We now define r 3 (n 0 , n 1 , n 2 , n 3 , n) coding the graph of the function α → (s n+1,α j ) j∈I n+1,α . We want to ensure the two following conditions:

(1) G α ⊆ j∈I n+1,α N s n+1,α j ⊆ G * n+1,α (6) | ffl N s n+1,α j S n+1 (α, .) dλ-S n+1 (α, β)| < 2 -3 if j ∈ I n+1,α ∧ β ∈ G α ∩ N s n+1,α j Note first that in practice S n+1 (α, β) = 0 if n is even 1 if n is odd if (α, β) ∈ G since g p (α, β) = 1 for each p in this case. So there is ψ : ω → R 2 recursive with | N s n+1,α j S n+1 (α, .) dλ-S n+1 (α, β)| < 2 -3 ⇔ ψ 0 (n) < N s n+1,α j S n+1 (α, .) dλ < ψ 1 (n)
if (α, β) ∈ G. We use Corollary 3.5 and its proof. Note that r 2 (n 0 , n 1 , n 2 , n 3 , n) ∈ P 1 .

Thus α / ∈ Π ⇔ ∃β ∈ 2 ω (α, β) ∈ H ⇔ ∃β ∈ 2 ω (α, β) ∈ G ⇔ ∃β ∈ 2 ω F (α), β ∈ V ⇔ F (α) / ∈ P.

Thus Π = F -1 (P) and P is Borel Π 1 1 -complete. By 26.C in [K2], P is Π 1 1 -complete.

-We now prove Theorem 1.8. Let X be a metrizable compact space and Y be a Polish space. We equip C(X, Y ) with the topology of uniform convergence, so that it is a Polish space (see 4.19 in [K2]). We use the map ψ defined before Theorem 1.8. Proof. We define ϕ : C(2 ω , [0, 1]) → M by ϕ(h)(s) := ffl Ns h dλ. As in the proof of Lemma 2.7, ϕ is well-defined. It is also continuous, and injective: if h = h ′ , then we can find q ∈ ω and s ∈ 2 <ω such that h(β)-h ′ (β) > 2 -q for each β ∈ N s or h ′ (β)-h(β) > 2 -q for each β ∈ N s , so that

|ϕ(h)(s)-ϕ(h ′ )(s)| = 1 λ(N s ) | ˆNs h dλ- ˆNs h ′ dλ| ≥ 2 -q .
This implies that the range R of ϕ is Borel and ψ := ϕ -1 : R → C(2 ω , [0, 1]) is Borel. As every continuous map h : 2 ω → [0, 1] is τ -continuous,

lim l→∞ ϕ(h)(β|l) = lim l→∞ N β|l h dλ = h(β)
for each β ∈ 2 ω , by Lemma 2.6. This implies that f ∈ P and ψ(f )(β) = lim l→∞ f (β|l) for each β ∈ 2 ω if f ∈ R.

(a) Note that the proof of 33.11 in [K2] shows that the set

P 1 := (h k ) k∈ω ∈ C(2 ω , [0, 1]) ω | (h k ) k∈ω pointwise converges is Π 1 1 -complete.
As E := (f k ) k∈ω ∈ R ω | ψ(f k ) k∈ω pointwise converges = (ψ ω ) -1 (P 1 ), the equalities P 1 = (ϕ ω ) -1 (E) = (ϕ ω ) -1 (P 1 ) hold and P 1 is Π 1 1 -complete.

(b) We argue as in (a).

(c) As in [B-Ka-L], the set

S := (h k ) k∈ω ∈ C(2 ω , [0, 1]) ω | ∃γ ∈ ω ω h γ(i) i∈ω pointwise converges to zero , is Σ 1 2 -complete. Indeed, fix Q ∈ Σ 1 2 (2 ω ).
Let α → (α) k k∈ω be a homeomorphism between ω ω and (ω ω ) ω , with inverse map (α k ) k∈ω →< α 0 , α 1 , ... > .

We set S ′ := {α ∈ ω ω | ∃γ ∈ ω ω ∀i ∈ ω ∀β ∈ 2 ω β / ∈ G (α) γ(i) }. Note that S ′ is Σ 1 2 .

(1) Is S ′ a Borel Σ 1 2 -complete set?

Assume that this is the case. Then the set S 2 := {(f k ) k∈ω ∈ M ω | ∃γ ∈ ω ω ∀i ∈ ω f γ(i) ∈ P} of sequences of martingales having a subsequence made of everywhere converging martingales is Borel Σ 1 2 -complete. Indeed, Lemma 3.10 gives a Borel map F : ω ω → M such that G α = V F (α) for each α ∈ ω ω . The map F : ω ω → M ω defined by F (α)(k) := F (α) k is Borel. Moreover,

F (α) ∈ S 2 ⇔ ∃γ ∈ ω ω ∀i ∈ ω ∀β ∈ 2 ω β / ∈ D F (α) γ(i) ⇔ ∃γ ∈ ω ω ∀i ∈ ω ∀β ∈ 2 ω β / ∈ V F ((α) γ(i) ) ⇔ ∃γ ∈ ω ω ∀i ∈ ω ∀β ∈ 2 ω β / ∈ G (α) γ(i) ⇔ α ∈ S ′ , so that S ′ = F -1 (S 2 ).
(2) Is there a Borel map f : C(2 ω , [0, 1]) → ω ω such that, for each (h k ) k∈ω ∈ C(2 ω , [0, 1])

ω and each β ∈ 2 ω , the following are equivalent:

(a) lim k→∞ h k (β) = 0,

(b) ∀k ∈ ω β / ∈ G f (h k ) ?
Assume that this is the case. Then S ′ (and therefore S 2 ) is Borel Σ 1 2 -complete, and thus Σ 1 2complete (see [P]). We define F : C(2 ω , [0, 1]) ω → ω ω by F (h k ) k∈ω :=< f (h 0 ), f (h 1 ), ... >, so that F is Borel. Note that F (h k ) k∈ω ∈ S ′ ⇔ ∃γ ∈ ω ω ∀i ∈ ω ∀β ∈ 2 ω β / ∈ G f (h γ(i) ) ⇔ ∃γ ∈ ω ω ∀β ∈ 2 ω lim i→∞ h γ(i) (β) = 0 ⇔ (h k ) k∈ω ∈ S, so that S = F -1 (S ′ ).

  , and C := n∈ω D n is suitable. Let C := ∪C. Let β ∈ H, and M in H with β ∈ M . Note that λ(M ∪ C) = λ(C) (consider the family C ∪ {M }). Thus λ(M \C) = 0. As d(M, β) = 1, the equality d(M ∩ C, β) = 1 holds, and d(¬C, β) = 0. This implies that H \C is contained in {β / ∈ C | d(¬C, β) < 1}, which has λ-measure zero by Theorem 2.1. Therefore H \C has λ-measure zero and H = C ∪ (H \C) is λ-measurable. Pick β ∈ H, and M ∈ H with β ∈ M . Then d(M, β) = 1, and thus d(H, β) = 1. Therefore H ∈ F. This finishes the proof.

  Theorem 4.7 (a) The setP 1 := (f k ) k∈ω ∈ P ω | ψ(f k ) k∈ω pointwise converges is Π 1 1 -complete. (b) The set P 2 := (f k ) k∈ω ∈ P ω | ψ(f k ) k∈ω pointwise converges to zero is Π 1 1 -complete. (c) The set S := (f k ) k∈ω ∈ P ω | ∃γ ∈ ω ω ψ(f γ(i) ) i∈ω pointwise converges to zero is Σ 1 2complete.

Moreover, (u) , β) = 1}), by Theorem 2.1. It remains to set C := F ∪ u∈ω F u . We conclude as in the proof of Lemma 2.2.

-We now want to prove an effective and uniform version of Lemma 2.5. Lemma 3.9 Let C be a ∆ 1 1 subset of ω ω ×2 ω with closed vertical sections, G be a Borel subset of 2 ω with λ(G) = 0, and G be a ∆ 1 1 subset of ω ω ×2 ω with G δ vertical sections, contained in ω ω ×G and disjoint from C. Then there is a ∆ 1 1 -recursive map h :

Proof. By Theorem 3.5 in [L], there is a ∆ 1 1 subset F of ω × ω ω × 2 ω such that F n,α is closed for each (n, α) ∈ ω×ω ω and ¬G = n∈ω F n . Moreover, we may assume that (F n ) n∈ω is increasing and F 0 = C.

• We will define, by primitive recursion, a partial map f : ω → ω which is Π 1 1 -recursive on its domain such that f (n) essentially codes the set C 1 2 n constructed in the proof of Lemma 2.5. As this map will in fact be total, it will be ∆ 1 1 -recursive by the uniformization lemma.

We first apply Lemma 3.8 to F := F 0 and B := ¬G. This is possible because G α ⊆ G, so that (¬G) α has λ-measure one and therefore density one at any point of 2 ω , for each α ∈ ω ω . Lemma 3.8 gives

More generally, we will have C f (n) = ¬C 1 2 n . As mentioned above, f will be defined by primitive recursion, which means that there will be a partial map g : ω 2 → ω such that f (n+1) = g f (n), n . This partial map g will be Π 1 1 -recursive on its Π 1 1 domain {m ∈ W 1 | ¬C m ⊆ ¬G}×ω, so that f will be Π 1 1 -recursive on its domain by 7A.5 in [M]. The map g will take values in W 1 , and is constructed in such a way that, if A := ¬C m ⊆ ¬G and A ′ := ¬C g(m,n) , then

Lemma 3.8 ensures that such a g(m, n) ∈ ω exists if (m, n) ∈ {q ∈ W 1 | ¬C q ⊆ ¬G} × ω. As the properties (1)-( 3) are Π 1 1 by Corollary 3.5, the uniformization lemma ensures the existence of g. So we constructed a ∆ 1 1 -recursive map f :

, and

We first consider n ′ 0 ∈ W 1 and n ′ 2 ∈ P 1 (coding G * n+1 and S n+1 respectively) as variables. We define R

.

By Corollary 3.5.(b) applied to D := P 1 , the partial map λ O :

is Σ 1 1 -recursive and Π 1 1 -recursive on its domain. By 3E.2, 3G.1 and 3G.2 in [M], these two classes of functions are closed under composition. In particular, the partial map

is Σ 1 1 -recursive and Π 1 1 -recursive on P 1 ×ω ω ×ω 2 . This shows the existence of

We now consider n ′ 0 ∈ W 1 and n ′ 2 ∈ P 1 as parameters. We set [M]). This shows that

20

The uniformization lemma provides a ∆ 1 1 -recursive map L : ω×ω ω ×2 ω → ω such that

, there is a ∆ 1 1 subset δ of ω ×ω ω ×ω such that σ ⊆ δ ⊆ π. We now also consider n as a parameter and define ϕ :

Note that ϕ is ∆ 1 1 -recursive, and that Seq ϕ(α)(u) is equivalent to (n, α, u) ∈ δ. In particular,

(1)

for each α ∈ ω ω . Let k ∈ W ω ω ×ω ω such that C ω ω ×ω ω k = Gr(ϕ). We now consider n ′ 0 , n ′ 2 and n as variables again. Note that for each

The uniformization lemma provides a partial map K :

Finally, r is Π 1 1 -recursive on W 1 ×P 2 1 ×P 3 ×ω, f is Π 1 1 -recursive on ω, and thus f is ∆ 1 1 -recursive by the uniformization lemma since it is total.

• We are now ready to define the dimension two versions of G * n , g n , S n , and (s n j ) j∈In :

(1)

. By construction of r, these objects satisfy the conditions (1)-( 6) of the proof of Lemma 2.7.

• Consequently, the martingale F (α) will be defined in such a way that if u ∈ ω codes s ∈ 2 <ω , then

Consequently, in order to prove that F is ∆ 1 1 -recursive, it is enough to check that the partial map

This comes from the facts that

• Finally, the map F is ∆ 1 1 -recursive and is as required.

First consequences (A) Universal sets

-We first recall some material from [K2]. The first result can be found in Section 23.F (see also [Za]).

exists} (we consider only one-sided derivatives at the endpoints).

The second result is 23.23.

-We prove results in that spirit here.

Theorem 4.3 Let B be a subset of 2 ω . Then the following are equivalent:

We already noticed in the introduction that B is Σ 0 3 . By Doob's theorem, B has λ-measure zero (see [D]).

, there is a uniform version of Zahorski's theorem, which allows to prove the following result

-Here again, there is a result in that spirit.

Theorem 4.6 The set

Proof. Let U ∈ Π 1 1 (ω ω ×2 ω ) be ω ω -universal for the co-analytic subsets of 2 ω , and

ω such that, for each δ ∈ 2 ω , the following are equivalent:

Then g is continuous and reduces

5 Universal and complete sets in the spaces C(2 ω , X)

-It is known that if Γ is a self-dual Wadge class and X is a Polish space, then there is no set which is X-universal for the subsets of X in Γ (see 22.7 in [K2]). This is no longer the case if the space of codes is different from the space of coded sets.

Proposition 5.1 Let X be a Polish space, Γ be a Wadge class with complete set C ∈ Γ(X), and

We will partially strengthen this result to get our uniform universal sets.

-Recall that it is proved in [K3] that a Borel Π 1 1 -complete set is actually Π 1 1 -complete. In fact, Kechris's proof shows the result for the classes Π 1 n . Our main tool is a uniform version of this. Kechris's result has recently been strengthened in [P] as follows.

Theorem 5.2 (Pawlikowski) Let n ≥ 1 be a natural number, and C ⊆ X ⊆ 2 ω . If Borel functions from 2 ω into X give as preimages of C all Π 1 n subsets of 2 ω , then so do continuous injections.

The main tool mentioned above is the following:

Theorem 5.3 Let n ≥ 1 be a natural number, U Π 1 n ,2 ω be a suitable ω ω -universal set for the Π 1 n subsets of 2 ω , X be a recursively presented Polish space, C ∈ Π 1 n (X), R : ω ω × ω ω → ω ω be a recursive map, and b : ω ω → X be a ∆ 1 1 -recursive map such that

-We first recall some material from [K3].

Definition 5.4 (a) A coding system for nonempty perfect binary trees is a pair (D, O), where D ⊆ 2 ω and O :

Nice coding systems exist. If β ∈ D, then there is a canonical homeomorphism β * from [O(β)] onto 2 ω . We now check that the construction of β * is effective.

Note that

The proof of (b) is similar.

-Let X be a recursively presented Polish space, and d X and (r X n ) n∈ω be respectively a distance function and a recursive presentation of X. We now give a recursive presentation of C(2 ω , X), equipped with the usual distance defined by

since this is not present in [M]. We define, by primitive recursion, a recursive map ν : ω → ω such that ν(i) enumerates {s ∈ 2 <ω | |s| = i}. We first set ν(0) := 1 =<>. Then

If ¬Seq(n) or lh(n) = 2 i for each i, then we define h n : 2 ω → X by h n (β) := r X 0 if β ∈ 2 ω . In any case, h n ∈ C(2 ω , X) and takes finitely many values.

Lemma 5.6 Let X be a recursively presented Polish space. Then the sequence (h n ) n∈ω is a recursive presentation of C(2 ω , X), equipped with d.

Proof. We have to see that

We saw in the proof of Proposition 5.1 that the evaluation map (h, β) → h(β) is continuous from C(2 ω , X)×2 ω into X. We can say more if X is recursively presented.

Lemma 5.7 Let X be a recursively presented Polish space. Then the evaluation map is recursive.

, which gives the result.

-We then strengthen 7A.3 in [M] about primitive recursion as follows. If Z, Y are recursively presented Polish spaces, g :

3 in [M] shows that the map f ′ : ω×Z → Y defined by

As in 7A.5 in [M], this can be extended to partial functions which are Π 1 1recursive on their domain.

-We are ready for the proof of our main tool.

Proof of Theorem 5.3. 3E.6 in [M] provides π :

More generally, let Y be a recursively presented Polish space, and ψ : Y → C(2 ω , X). Note that

and h ((n) 1 ) 0 (β) = r X g(n,β) for some recursive map g : ω×2 ω → ω.

In the present case, Y = C(2 ω , ω ω ) and ψ(y)(β) = π y(β) . Thus

where G π is the Σ 0 1 neighborhood diagram of π. As the evaluation map is recursive, h → π • h is Π 1 1 -recursive and total, and thus ∆ 1 1 -recursive.

• Let us show that there is a ∆ 1 1 -recursive map f :

for each α ∈ ω ω . We adapt the proof of the main result in [K3]. We set

If < β 0 , δ 0 >∈ 2 ω , then we inductively define, for i ∈ ω, m i , β i+1 , δ i+1 as follows. If (β i , δ i ) is given and in Domain(e), then

the location of the first 0 in x i if it exists, 2 otherwise.

We then set

×2 ω (note that B * depends on α, but we denote it like this to keep the notation of [K3]). We define I : ω ω → 2 ω by I(α) := 0 α(0) 10 α(1) 1... Note that I a ∆ 1 1 -recursive injection onto the Π 0 2 set

so that there is a ∆ 1 1 -recursive map φ : 2 ω → ω ω which is the inverse of I on P ∞ . We set

• As in [K3], we can find F : 2 <ω → (2 ω ×ω) <ω satisfying the following properties:

We will need an effective version of this, so that we give the details of the construction of F . In fact, the β i 's involved in the definition of F can be ∆ 1 1 (α). In order to see this, we first define

-recursive, H 0 too, and the niceness of the coding system gives

]. Now suppose that n ∈ ω, (ε 0 , ..., ε n ) and F (ε 0 , ..., ε n-1 ) = (β 0 , k 0 , ..., β n , k n ) are given. We define

, the niceness of the coding system gives

so that F is as desired. So we can assume that the β i 's are ∆ 1 1 (α) in the conditions required for F .

• By [K3] again, the map h α :

As this is not too long to prove, we give the details for completeness. The map h α is in fact more than continuous: it is Lipschitz, by definition. Fix (ε i ). We apply F to the initial segments of (ε i ), which gives (β i ). For each n, we define perfect sets

Note that

(4) δ 0 ∈ C n 0 ⇒ < β i , δ i >∈ Domain(e) for each i ≤ n, where δ 1 , ..., δ n are computed according to the formula in (3).(ii).(b),

(5

It remains to see that the map ψ : α → h α , from ω ω into C(2 ω , ω ω ), can be ∆ 1 1 -recursive (then f will be µ • ψ). By the previous discussion, it is enough to see that the relation "k

• We will define, by primitive recursion, a ∆ 1 1 -recursive map f : ω × ω ω × 2 ω → 2 ω × ω such that f n, α, (ε i ) will be of the form (< β0 , ..., βn , βn , ... >, < k0 , ..., kn >) and can play the role of F (ε 0 , ..., ε n-1 ). We first set

Note that P is Π 1 1 and for any α, (ε i ) ∈ ω ω ×2 ω there is (β, k) ∈ 2 ω ×ω such that α, (ε i ), β, k ∈ P . The uniformization lemma gives a ∆ 1 1 -recursive map g :

for each α, (ε i ) ∈ ω ω ×2 ω . Then we set

Note that D is Π 1 1 , as well as

Moreover, for each β, p, n, α,

The uniformization lemma gives a partial map h : 2 ω ×ω 2 ×ω ω ×2 ω → 2 ω ×ω which is Π 1 1 -recursive on its domain D, and such that β, p, n, α, (ε i ), h β, p, n, α,

This implies that the partial map f defined by

Moreover, an induction shows that f n, α, (ε i ) , n, α, (ε i ) ∈ D for each n, α, (ε i ) , so that f is in fact total, and thus ∆ 1 1 -recursive. More precisely, f n, α, (ε i ) is of the form (< β 0 , ..., β n , β n , ... >, < k 0 , ..., k n >),

where (ε 0 , ..., ε n-1 ) → (β 0 , k 0 , ..., β n , k n ) satisfies the properties (1)-(3) of F . It remains to note that k i = f i, α, (ε i ) (1)(i).

-We now prove the consequences of our main tool.

Definition 5.8 Let Γ be a class of subsets of recursively presented Polish spaces, Γ be the corresponding boldface class, X, Y be recursively presented Polish spaces, and U ∈ Γ(Y ×X). We say that U is effectively uniformly Y -universal for the Γ subsets of X if the following hold:

(

1 be a good ω ω -universal for the Π 1 1 subsets of 2 ω , X 1 be a recursively presented Polish space, and C 1 be a Π 1 1 subset of X 1 for which there is a ∆

Theorem 5.9 Let n ≥ 1 be a natural number. Then (a) the set U n is effectively uniformly X n+1 -universal for the Π 1 n subsets of 2 ω , (b) the set C n is Π 1 n -complete. Proof. We argue by induction on n.

(a) Assume first that n = 1, and fix S ∈ Π 1 1 (ω ω × 2 ω ). Our assumption gives b 1 :

, so that U 1 is X 2 -universal for the Π 1 1 subsets of 2 ω , effectively and uniformly.

We now study U

Theorem 5.3 gives a ∆ 1 1 -recursive map f n+1 such that (α,

such that (α, β) ∈ S ⇔ ∀δ ∈ 2 ω (α, β, δ) / ∈ Q, and

for some α ∈ ω ω . Applying the previous discussion to S := U Π 1 n+1 ,2 ω , we get A = (U n+1 ) f n+1 (R ′ (α Q ,α)) , so that U n+1 is X n+2 -universal for the analytic subsets of 2 ω , effectively and uniformly.

(b) By definition, C 1 ∈ Π 1 1 , and

. Then E = (U n ) h for some h ∈ C(2 ω , X n ), by (a). Thus E = h -1 (C n ). If Z is a zero-dimensional Polish space and D ∈ Π 1 n (Z), then we may assume that Z is a G δ subset of 2 ω by 7.8 in [K2], so that D ∈ Π 1 n (2 ω ). The previous discussion gives g ∈ C(2 ω , X n ) with D = g -1 (C n ). Thus D = (g |Z ) -1 (C n ) and C n is Π 1 n -complete.

Proof of Theorem 1.7. By Theorem 5.9, it is enough to show that if U Π 1 1 ,2 ω ∈ Π 1 1 is a good ω ωuniversal set for the Π 1 1 subsets of 2 ω , then there is a ∆ 1 1 -recursive map b : ω ω → [0, 1] 2 <ω such that (α, β) ∈ U Π 1 1 ,2 ω ⇔ b(< α, β >) ∈ P if (α, β) ∈ ω ω × 2 ω . Let H ∈ Π 0 2 (ω ω × 2 ω × 2 ω ) such that ¬U Π 1 1 ,2 ω = Π ω ω ×2 ω [H]. We set G := (α, β) ∈ ω ω ×2 ω | (α) 0 , (α) 1 , (β) 1 ∈ H ∧ β ∈ K , so that G ∈ ∆ 1 1 (ω ω ×2 ω ), has G δ vertical sections and G ⊆ ω ω ×K. Lemma 3.10 gives a ∆ 1 1 -recursive map F : ω ω → [0, 1] 2 <ω , taking values in M, and such that G α = V b(α) for each α ∈ ω ω . If (α, β) ∈ ω ω ×2 ω , then (α, β) / ∈ U Π 1 1 ,2 ω ⇔ ∃δ ∈ 2 ω (α, β, δ) ∈ H ⇔ ∃δ ∈ 2 ω (< α, β >, δ) ∈ G ⇔ ∃δ ∈ 2 ω b(< α, β >), δ ∈ V ⇔ b(< α, β >) / ∈ P.

This finishes the proof.

Questions. Let U be a Π 0 2 subset of ω ω ×2 ω which is universal for Π 0 2 (2 ω ). We set

Note that G is a Π 0 2 subset of ω ω ×2 ω contained in ω ω ×K which is universal for Π 0 2 (K). Indeed, fix H ∈ Π 0 2 (K). Then H ′ := {γ ∈ 2 ω |< 0 ∞ , γ >∈ H} is Π 0 2 , which gives α 0 ∈ ω ω with H ′ = U α 0 . Then H = G α 0 .