Computer Science and the fine structure of Borel sets

J.Duparc O. Finkel and J-P. Ressayre

Equipe de Logique Mathémathique, CNRS URA 753 et Université Paris VII

U.F.R. de Mathématiques, 2 place Jussieu, 75251 Paris Cedex 05, France. duparc@logique.jussieu.fr & finkel@logique.jussieu.fr & ressayre@logique.jussieu.fr

Abstract

I) Wadge defined a natural refinement of the Borel hierarchy, now called the Wadge hierarchy WH. The fundamental properties of WH follow from results of Kuratowski, Martin, Wadge and Louveau. We give a transparent restatement and proof of Wadge’s main theorem. Our method is new for it yields a wide and unexpected extension: from Borel sets of reals to a class of natural but non Borel sets of infinite sequences. Wadge’s theorem is quite uneffective and our generalization clearly worse in this respect. Yet paradoxically our method is appropriate to effectivize this whole theory in the context discussed below. II) Wagner defined on Büchi automata (accepting words of length ω) a hierarchy and proved for it an effective analog of Wadge’s results. We extend Wagner’s results to more general kinds of Automata: Counters, Push Down Automata and Büchi Automata reading transfinite words. The notions and methods developed in (I) are quite useful for this extension. And we start to use them in order to look for extensions of the fundamental effective determinacy results of Büchi-Landweber, Rabin; and of Courcelle-Walukiewicz.

Aknowledgements

The new results announced in the set theoretic part of this note are due to the first author. Part of them belongs to his thesis made under the supervision of the third author. The first author owes a debt of gratitude to J.P. Ressayre for suggesting the problem, pointing out some of the fundamental ideas of that work, and supporting its achievement by many stimulating remarks and advices. He also wants to thank A. Louveau for careful checking of part of the proofs and helping to correct some imperfections. Thanks also to P. Simonnet who introduced the third author to the Wagner and Wadge hierarchies and persuaded him that the two hierarchies should be studied together.

This is a survey trying to avoid technicalities; its main theme is the interplay between the study of the Wadge Hierarchy –a set theoretic, non effective subject - and some questions in Computer Science (abbreviated CS) - also of theoretical nature but intimately related to practical aspects. The set theoretic work we have to report on is in a rather definitive state while on the side of CS our work is at its very beginning. For that reason §1 is devoted to the set theory, which in particular involves ordinals. But the reader unfamiliar with such a topic should not worry: §2 belongs to Theoretical Computer Science (abbreviated TCS) and relates the ordinals with concrete objects such as Büchi and push down automata.

1 The Wadge hierarchy WH

We work on product spaces Λ^{ω} = infinite words of alphabet Λ, equipped with the product topology: basic open sets are conditions on a word x in Λ^{ω} that depend only on a finite number of coordinates x_{i}

V_{s} = {x ∈ Λ^{ω} : x ↾ n = s}, n < ω, s ∈ Λ^{n}.

Open sets are unions of such elementary open sets V_{s}; in other words U is open if whenever x belongs to U there is n < ω such that U contains all words of Λ^{ω} extending x ↾ n The Borel sets of Λ^{ω} are all sets which result from the open and the closed sets by countable unions and intersections. And the Borel rank of such a set is the ordinal which counts the number of nested unions and intersections needed to obtain the set in this way. More precisely, open sets and closed sets have rank 1; “G_{δ}” sets (countable unions of closed sets) have rank at most 2 as well as their complements the F_{σ} sets. Etc up to the first uncountable ordinal ω_{1}. This is the Borel hierarchy, of fundamental role in Analysis, Statistical physics etc.

Definition 1 For A, B ⊆ ω^{ω}, A ≤_{W} B iff A has a continuous reduction to A: there is a continuous map f : ω^{ω} ⟼ ω^{ω} such that “x ∈ A” reduces to “f(x) ∈ B”. A <_{W} B iff A ≤_{W} B but not B ≤_{W} A; A ≡_{W} B iff A ≤_{W} B ≤_{W} A.

WH is the class of Borel subsets of ω^{ω}, equipped with ≤_{W} and ≡_{W}. WH is a natural refinement of the Borel hierarchy. In fact the relation A ≤_{W} B is not only finer, but also more natural that the relation r(A) ≤ r(B); so WH is more natural than BH ! However the Wadge hierarchy is terribly refined compared to BH : see thm. 2 and rem.1(a) below. This has put severe limitations on the use of WH in mathematical practice; which are also limitations to the audience of the beautiful work on WH done by Martin, Wadge, Louveau and others (see the bibliography). We tried to add to their work a postscriptum - barely sketched below, but fully exposed in [D 94], [D 96], [D 97]. Let us hope that it will help in making the subject more accessible. We end §1 by recalling the fundamental results about WH. The complement ω^{ω} ∖ A of a set A ∈ WH is demoted ^{−}A.

Theorem 1 (Martin) Up to the complement and ≡_{W}, WH is a well ordered hierarchy: there is an ordinal |WH| (called the length of the hierarchy) and a map d_{W}^{∘} from WH onto |WH|, such that for all A, B ∈ WH

d_{W}^{∘} A < d_{W}^{∘} B ⟷ A <_{W} B
d_{W}^{∘} A = d_{W}^{∘} B ⟷ A ≡_{W} B or A ≡_{W} ^{−}B

After thm. 1, a natural question is: determine the ordinal |WH|. The answer to this question is Wadge’s main theorem:

Theorem 2 |WH| is the Veblen ordinal.

Remarks 1 (a) The Veblen ordinal is large beyond measure (fortunately no other knowledge of this ordinal is needed by the reader here)... Thus |W H| is so large that it was a “gageure” to conjecture Th.4, let alone to prove it. Hence the 300 pages thesis of Wadge became famous among Set theorists –even though the thesis was never published, and no proof existed from any other source before [D 94][D 96][D 97] (which also expose new results; one is presented in §5 ). We shall give the main ideas of our proof: they make the structure of WH become more transparent.

(b) The size beyond measure of |W H| also means that it is extremely refined with respect to the Borel hierarchy. In Analysis and Set theory this finesse has been so far more cumbersome than useful; but it is exactly the finesse one needs for the effective study of Borel sets – which plays an important role in Computer Science. This appears in §2 which investigates a small effective portion of WH.

We end §1 with other results of Wadge.

Definition 2

(a) Given sets A ⊆ Λ_{A}^{ω} and B ⊆ Λ_{B}^{ω}, the Wadge game W (A, B) denotes the following infinite game between two players, I and II.

(i) I chooses x ∈ Λ_{A}^{ω} and II chooses y ∈ Λ_{B}^{ω}: at move p < ω, I chooses x_{p} ∈ Λ1_{A}. And II replies with y_{p} ∈ Λ1_{B}, or chooses to skip, in which case y_{p} is the empty sequence <>; after ω moves, the play is (x, y), where x = x_{0}⌢x_{1}⌢ … and y = y_{0}⌢y_{1}⌢ . . ..

(ii) II wins play (x, y) iff his play y is infinite and (x ∈ A ⟷ y ∈ B).

Lemma 1 (The Wadge Lemma)

A ≤_{W} B iff II has a w.s. inW (A, B) .

Definition 3 We say that A is selfdual iff A ≤_{W} ^{−}A. For every set A of words, let ^{±}A denote the set 0.A ∪ 1.^{−}A.

Examples 1 {x : x(0) = 0} is selfdual, while {x : x(n) = 0 for some n} is not. Clearly ^{±}A is selfdual for every A: it is reduced to its complement by an application f such that f(0.x) = 1.x, f(1.x) = 0.x and f(y) = some fixed suitable element y_{0} if y is not of the form 0.x or 1.x . Also it is clear that if A already was selfdual then A ≡_{W} ^{±}A.

The next proposition is just as easy but its sequel is a deeper result due to Wadge.

Proposition 1 For every A in WH, if A is non selfdual then A <_{W} ^{±}A. In fact ^{±}A is the upper bound for the relation <_{W} of A and ^{−}A.

Theorem 3 For every set B in WH with a finite alphabet, B is self dual iff B ≡_{W} ^{±}A for some non selfdual A in WH.

(The general form of Wadge’s result includes the case of a countable alphabet, see §3) Put together, the above two results make it simple to deduce the full structure of WH from its restriction to non selfdual sets. So henceforth by abuse we let WH denote the Wadge hierarchy restricted to non selfdual sets.

2 Effective Borel sets and CS

Let us first recall the fundamental work on automata reading infinite words, and its significance for CS (this work is due to Büchi-Landweber, Rabin, Harrington-Gurevich and still others. For a good introduction see [T 90]).

• A Büchi automaton A is an automaton reading infinite words x ∈ Λ_{A}^{ω}, and having an acceptance condition which tells whether or not A accepts x –in a way that only depends on the set of states which are visited infinitely often by A while reading x. We denote BA the class of these automata. For A in BA we denote also A the set of infinite words accepted by the automaton A. And we play on both terminologies, speaking of the set A and of the automaton A. The set A is Borel; in fact it is a boolean combination of G_{δ} sets.

Moreover every A in BA is effective, in the sense that one can decide whether A accepts at least one infinite word: one uses

Büchi’s lemma A Büchi automaton A is non empty iff it accepts an ultimately periodic word.

• A transducer is an automaton σ which while it reads x ∈ Λ_{A}^{≤ω} writes a word σ∗x ∈ Λ_{B}^{≤ω} on an input tape (henceforth all alphabets are finite).

• Given any set Z ⊆ Λ_{Z}^{ω} the infinite game G (Z) lets two players choose z ∈ Λ_{Z}^{ω} (at move p < ω, I chooses z(2p) and II replies with z(2p + 1)). The winner of this play z is II iff z ∈ Z. A strategy for a player is a function which applied to the sequence of previous moves of his enemy produces the next move of the player. It is a winning strategy (written w.s.) if the player always wins when applying it.

Theorem 4 (effective determinacy)

For every A in BA, the winner of G (A) has a w.s. which is a transducer

(in other words: every infinite game refereed by an automaton is won by some automaton...)

This last result is of great practical and effective content. For present days industry raises a large number of problems of the form: design a processor working in real time interaction with its environment, which satisfies for a certain specification. The above theorem is the theoretical background of a successful modelization of this problem.

(a) One imagines an infinite game in which player I is the environment: its possible moves are all stimuli which the environment might send at once to the processor. Player II is the processor: its possible moves are all the reactions which the processor might have to make at once. The plays are all infinite sequences of alternate moves of I and II - each move coded by a letter of a suitable alphabet Λ .

(b) The specification is then represented by the set A of all plays z ∈ Λ^{ω} such that the moves of II are a satisfactory response to the moves of I, according to the specification; thus our problem becomes: find a transducer σ which is a w.s. for II in the game G (A).

(c) If A happens to be accepted by a Büchi automaton, then by the effective determinacy theorem one of the players has a w.s. σ for G (A) which is a transducer. If this player is II, then σ is the desired processor; and if it is I, then no processor of any kind can satisfy the specification. Moreover by Büchi’s lemma we can effectively determine which player has the w.s. – and find out the transducer which realizes it.

The infinite length of G (A) is an imaginary feature; but when a real world real time processor has a short looping time (which is usually the case), if a w.s. for G (A) is performed by such a processor then it is quickly effective. So that the above model of processor design is accurate in a very large class of applications - for instance, in the design of processors used in modern planes. Which is an extraordinary fate for theoretical results about infinite games...

Remark - a) For the development of computers and data bases, the problem of designing a processor meeting a given specification must be extended to the case of processors working in polynomial time, satisfying specifications which are Borel but not just boolean combinations of G_{δ} sets. So one would like to extend the above work in the way appropriate to this extended problem. b) This gives one motivation for extending effective determinacy beyond the above case. But there is another motivation provided by Rabin’s work: in addition to proving effective determinacy, he obtains it under the form of a quantifier elimination result in Monadic Second Order Arithmetic with two successors. Once second order quantifiers have been (partially) eliminated this way from a sentence, he is able to decide its truth by use of an extension of Büchi’s lemma. He thus obtains the decidability of MSA with 2 successors, a result widely applied in CS. So if one succeeds to extend effective determinacy one may also extend such results. To the two perspectives of the above remark belongs the work of Courcelles [C 95][C 96], Walukiewicz [W 96]: every game refereed by a DPDA (= deterministic pushdown automaton) has a w.s. which is also a DPDA; and one can decide which player is the winner. Clearly this is a significant progress; yet in terms of the Borel hierarchy the progress is invisible. For DPDA’s have same Borel rank as BA’s. In contrast we are going to see that the Wadge Hierarchy precisely captures the difference in power between BA’s and stronger “automata”. To that end we study below the restriction of WH successively: to the “Wadge closure” [BA] of BA (that is to the class of all sets which are ≤_{W} to some element of BA); to BA; to DPDA; and to “blind” counters (denoted BC, and BC(k) when restricted to k counters).

Remarks 2 Together with the Wadge lemma, the effective determinacy theorem implies that if A and B are BA’s then A ≤_{W} B iff A can be reduced to B by a transducer τ : a word x is in A iff τ∗x (the word written by τ once he read x) belongs to B. In other words, B simulates A via composition with the transducer τ. So WH↾BA is an effective, decidable hierarchy. ( We conjecture that the the same applies with DPDA acceptors and transducers, although a Wadge game between two DPDA’s does not always have his winning set accepted by a single DPDA). WH↾BA is called the Wagner hierarchy because Wagner [W 79] provided a particularly effective and thorough description of its structure.

Theorem 5

(a) There are natural Borel operations on sets A, B (of infinite words): A ˆ+B, Aˆ.∞, Aˆ.α (where α is any countable ordinal) such that:

d_{W}^{∘} (A ˆ+B) = d_{W}^{∘} (A)+d_{W}^{∘} (B); d_{W}^{∘} (Aˆ.∞) = d_{W}^{∘} (A).ω_{1}; d_{W}^{∘} (Aˆ.α) = d_{W}^{∘} (A).α.

(b) Up to complement and ≡_{W}, WH↾[BA] is the closure of { } under ˆ+, ˆ.∞, ˆ.α (α < ω_{1}).

(c) Up to complement and ≡_{W}, WH↾BA is the closure of { } under just ˆ+ and ˆ.∞. And WH↾DPDA is the closure of { } under the same operations plus ˆ.ω.

Put simply, the theorem says that the difference between BA and DPDA lies in the operation ˆ.ω, which is defined on DPDA but not on BA. Similarly, the difference between DPDA and [BA] lies in ˆ.α for ω^{ω} ≤ α < ω_{1}. Let us first define A ˆ+B and Bˆ.∞.

Definition 4

(a) Assume Λ_{A} = Λ_{B}∪{e_{+}, e_{−}} (disjoint union); then Bˆ.∞ = (Λ_{A}^{∗}.e_{+})^{∗}.B∪ (Λ_{A}^{∗}.e_{−})^{+}.^{−}B. And A ˆ+B = B ∪ Λ_{B}^{∗}.e_{+}.A ∪ Λ_{B}^{∗}.e_{−}.^{−}A.

Nota Bene 1

(i) This defines Bˆ.∞ in all cases and A ˆ+B in a special case. But we can always assume this special case to hold, by renaming the variables of Λ_{A} ∪ Λ_{B} and adding dummy variables.

(ii) It is rather clear that BA, BC(k) and DPDA are closed under these two operations; to illustrate this let us give examples, when the graph of an automaton is represented with the following conventions:

• a state which has a trivial loop in the graph is represented by if the loop is rejecting and by otherwise. Thus is the graph of the automaton which accepts the empty set of words (it is also our notation for this empty set)

• an arrow is labeled with − if every loop of the graph including it is rejecting.

With these conventions consider A = B = ; then A ˆ+B and Bˆ.∞ have the pictures:

[figure: e_{+}; e_{−}]

[figure: e_{+}; e_{+}; e_{−}; e_{−}]

And this is extended to all DPDA’s A and B by substituting to and the whole machines B, A and ^{−}A in the above pictures.

Next we define Aˆ.α for finite α: Aˆ.1 = A, and by induction on n: Aˆ.(n + 1) = Aˆ.n ˆ+A.

Since BA’s are closed under ˆ+ as we just saw, they are closed under Aˆ.n. And DPDA’s are closed as well. In addition the definition of Aˆ.n can be simplified for certain A’s: for instance ˆ.n can be simplified to the automaton with picture

\underbrace{⟶ ⟶ . . . . . . ⟶ ⟶ ⟶ lra . . . . . .}_{n}

(alternating n times and ).

Next we give an abstract, non effective definition of Aˆ.α in case α is infinite: the successor case is as in the finite case

(b) Aˆ.(β + 1) = (Aˆ.β) ˆ+A

(c) and for α limit ordinal, Aˆ.α = ŝup_{β<α}Aˆ.β. Where sup is the following operation.

(d) For all sets A_{i}, i ∈ I, set ŝup_{i∈I}A_{i} = ⋃_{i∈I}i.A_{i}.

Nota Bene 2 (a) In defining ŝupA_{i} we assume that this family is infinite and has no maximal element for <_{W}; for the other case is pointless. But this infinite case makes sup A_{i} be a selfdual set whereas we took the convention that WH is restricted to non selfdual sets. So by convention ŝupA_{i} denotes a non selfdual set which in the order ≤_{W} comes immediately after: ⋃_{i∈I}d^{∗}.i.A_{i} where d is any additional letter.

(b) In case selfdual sets with countable alphabets are included in WH, theorem 3 has the following extension:

A is selfdual iff \{ \begin{matrix}A ≡_{W} ^{±}B for some non sefdual set B \\ or \\ A ≡_{W} ⋃_{i∈I}d^{∗}.i.A_{i} for some family of non selfdual sets A_{i}. \end{matrix}

We next discuss all the above set theoretic operations from the Wadge game point of view: this will help to understand the last ones. We start with Aˆ.∞ ; consider a player in charge of this set (player I in W (Aˆ.∞, B) or II in W (B, Aˆ.∞)). Then it looks as if

(a) the player starts to play in charge of A

(b) but at any time before the end of the play he may erase his former moves and decide to be in charge of A or of ^{−}A for the rest of the play

(c) he may repeat (b) even an infinite number of times: in such a case his play is considered to be in the complement of the set he is in charge of.

For in practice (a) holds as long as the player plays only letters from Λ_{A};

(b) becomes true if he plays the letter e_{+} or e_{−}, and only letters from Λ_{A} afterwards; and (c) is true since every word in Aˆ.∞ has a finite number of occurrences of the letters “e”. Properties ((a)+(b)+(c)) are what we call the playful characterization of Aˆ.∞: they define this set only up to Wadge equivalence but in this way they tell the essence of this operation. It is easy to convince oneself that the other above operations have the following playful characterization:

• the player in charge of A ˆ+B starts every play in charge of B; but at any time during each play he may decide to be in charge of A for the rest of the play, or in charge of ^{−}A. Then his former moves are erased (but not those of his enemy).

• The player in charge of ŝup_{i∈I}A_{i} chooses at the start of each play which one of the sets A_{i} he will be in charge of (for the whole play). Indeed, in the selfdual version his very first move chooses A_{i}; and in the non selfdual version, by playing the letter d (for “delay”) he may wait before choosing A_{i}. He may wait for ever by playing d^{ω} then his play is not in his set.

• The player in charge of Aˆ.α is a player in charge of Aˆ.∞ (as redefined by ((a)+(b)+(c))) but subject in addition to the following requirement: at the beginning of the play he is given the ordinal α, and he must decrease this ordinal at each move where he applies (b). (Thus during any play he can apply (b) only a finite number of times: as long as he did not reach 0 this way).

When A is any DPDA, let us turn Aˆ.ω to a DPDA, using this playful characterization (and forgetting about the former set theoretic definition). This DPDA involves the DPDA A, and works like it at the start (so the player starts in charge of A). But in addition it involves a one turn counter C : the content of C is an integer which can increase to any value n < ω but can only stay or decrease once it started to decrease. And the player can choose letters that increase C to n; then whenever he decreases n to a value n − i, the DPDA starts functioning anew, like ^{−}A if i is odd and like A if i is even.

Remarks 3 • We did not specify the way by which the counter C may be increased or decreased. But clearly there are many precise ways which allow for the playful characterization of the DPDA Aˆ.ω to be satisfied. Any such DPDA version of Aˆ.ω satisfies theorem 2 as required. And DPDA becomes closed under the operation Aˆ.ω.

• The closure of DPDA under Aˆ.ω and A ˆ+B easily implies its closure under Aˆ.α for every α < ω^{ω}.

Now we see concretely the content of theorem 5(b); but we can be much more precise than this theorem, by completely telling the structure of WH restricted to : [BA], BA, BC(k) and DPDA. To that end we restate Th.5(a); let < ω_{1}^{ω} > denote the structure of the ordinals < ω_{1}^{ω}, equipped with its “arithmetical” notions: <, +, 1, and all multiplications .α where α ≤ ω_{1}. And let <WH> denote the structure

⟨W H, <_{W} , ˆ+, , (ˆ.α)_{α<ω_{1} or α=∞}⟩

then the theorem says that the two structures < ω_{1}^{ω} > and <WH>↾ bc(G_{δ}) are isomorphic via the map d_{W}^{∘} . Now any ordinal α < ω_{1}^{ω} has a Cantor Normal Form which is a canonical term

CNF (α) = ω_{1}^{n_{0}}.ν_{0} + ... + ω_{1}^{n_{k}}.ν_{k}

(with 0 ≤ n_{i} ∈ IN and 1 ≤ ν_{i} < ω_{1}), denoting α inside the structure < ω_{1}^{ω} >. Let us evaluate this term CNF (α) in the isomorphic structure < W H > :

ω_{1}^{0} = 1 gets evaluated to ;

ω_{1}^{2}.ν to (( ˆ.∞)ˆ.∞) ˆ.ν, etc.

Thus the evaluation of CNF (α) in < W H > produces a set of [BA] which we denote Ω(α). To say that d_{W}^{∘} is an isomorphism of the structures is to say that d_{W}^{∘} Ω(α) is just α; and by definition of d_{W}^{∘}, whenever d_{W}^{∘} (A) = α then A or its complement is ≡_{W} to Ω(α). In this way theorem 5(a) gets refined to theorem 6(a) below.

Theorem 6 (theorem 5 refined)

(a) Up to complement and ≡_{W}, [BA] consists of the sets Ω(α), α < ω_{1}^{ω}

(b) Up to complement and ≡_{W}, BA consists of Ω(α) where the parameters ν_{i} of CNF (α) = ω_{1}^{n_{i}}.ν_{i} are finite. BC(k) is the case ν_{i} < ω^{k+1}; and DPDA the case ν_{i} < ω^{ω}.

In case of BA, 6(b) follows from Wagner’s theorem [Wa]; but the cases concerning BC(k) and DPDA are new: see [D 98] and [F 99(a)][F 99(b)]. Note the analogy between this theorem and Cantor’s Normal Form theorem: Cantor’s theorem provides a canonical and unique way to obtain each α < ω^{ω} as a term CNF (α); this theorem provides Ω(α) as the normal form of BA’s, BC’s and DPDA’s...

Nota Bene: BC(k) is not closed under ˆ.ω, for otherwise it would also be closed under ˆ.ω^{k+1} contradicting the theorem.

2.1 Conclusions

• While the Borel Hierarchy does not see any difference between BA, BC(k), DPDA and [BA], the canonical operations of WH pinpoint the differences between these classes...

• This is nice but not too important, because we already know the effective determinacy of BA and DPDA. But the phenomenon that canonical operations of WH are precisely relevant for capturing main classes of Borel sets occuring in TCS, continues beyond DPDA. This may help to extend effective determinacy : add one more canonical operation of WH, ∞^{A} to the ones which generate WH↾DPDA; and take the closure of DPDA under these operations. The resulting class is a part of NPDA (non deterministic PDA) which may lead to new effective determinacy results. (This cannot happen with NPDA as a whole: see theorem 7 below). Thus in §3 we study WH in order to introduce ∞^{A}.

Theorem 7

(a) NPDA contains Borel sets of every finite rank [F 98 ].

(b) Alas, one cannot decide which player is the winner of a game G (A), when A is NPDA [F 98 ]. Also one cannot decide the Wadge class of an NPDA [F 98 ][F 99(a)].

• So much for the interest of WH in CS; what about the converse ? The above description of W H ↾ [A] (by canonical generators Ω(α) resulting from the normal form of ordinals) and its proof (seen in §3), were first developed just for the Wagner hierarchy W H ↾ BA and were suggested by this initial case. And this first success of the method provided the crucial idea to understand the structure of WH and prove Wadge’s theorem: consider the canonical operations on ordinals which generate Veblen’s ordinal =|W H|, providing a Veblen Normal Form for each ordinal < |W H|. And find isomorphic operations on WH.

3 The conciliatory hierarchy

Definition 5

(a) We call Sets (with capital S) all sets A of finite or infinite strings: A ⊆ Λ_{A}^{≤ω}, where Λ_{A} is any set - called the alphabet of A.

(b) Given Sets A and B, C (A, B) denotes the following infinite game between two players, I and II.

(i) I chooses x ∈ Λ_{A}^{≤ω} and II chooses y ∈ Λ_{B}^{≤ω}: at move p < ω, I chooses x_{p} ∈ Λ1_{A}, or chooses to skip, in which case x_{p} is the empty sequence <>. And II replies with y_{p} ∈ Λ1_{B} ∪ {<>}; after ω moves, the play is (x, y), where x = x_{0}⌢x_{1}⌢ … and y = y_{0}⌢y_{1}⌢ . . ..

(ii) II wins play (x, y) iff (x ∈ A ⟷ y ∈ B). (This is the Wadge game except that both players may skip as much as they want to, so that the plays x, y may be finite).

(c) We set:

A ≤_{c} B ⟺ II has a winning strategy (w.s.) in C (A, B)
A <_{c} B ⟺ A ≤_{c} B but not conversely
A ≡_{c} B ⟺ A ≤_{c} B ≤_{c} A.

The conciliatory hierarchy CH is the class of all Sets A ⊆ Λ_{A}^{≤ω} with countable alphabet and such that A ∩ Λ_{A}^{ω} is Borel. CH is equipped with ≤_{c} and ≡_{c}.

(a) Our definition of C (A, B) of course derives from W (A, B): it is W (A, B) made symmetric w.r. to the players, so that it has no importance which player starts the first move.

(b) The complement of a Set A, denoted ^{−}A, is Λ_{A}^{≤ω} ∖ A. Using (a) it is immediate that A ≡_{c} ^{−}A, never holds; so the hierarchy CH has no “self dual” Sets.

Suppose we modify the outlook of C(A,B) by deciding that whenever a player wants to skip, he chooses a special letter b (for “blank”) not in the alphabets of Sets - instead of choosing <>. Thus every play in the game becomes an infinite sequence, and C(A,B) is turned to a Wadge game W (A^{b}, B^{b}) with A^{b} = {x ∈ (Λ_{A} ∪ b)^{ω} : x′ ∈ A} where x′ denotes the sequence x in which every occurrence of “b” has been removed. Clearly this change is purely formal: a player wins C (A, B) iff he wins W (A^{b}, B^{b}). Thus A <_{c} B iff A^{b} <_{W} B^{b} : we constructed a trivial and canonical embedding of CH into WH. In the opposite sense there is an embedding which is almost the identity, too: it chooses for every set B a set s(B) of finite sequences from Λ_{B} (hence B ∪ s(B) becomes a Set) so that the map : B ⟼ B ∪ s(B) is an embedding of WH into CH, in fact it is equivalent for a player:

• to be in charge of B and be applied the rules of the Wadge game, and

• to be in charge of B ∪s(B) and be applied the rules of the conciliatory game.

[The choice of s(B) is not obvious : for B in BA or B in bc(G_{δ}) it is easy to define, but we don’t know how to prove the general case without proving along that |CH|=Veblen’s ordinal=|W H|...] We summarize the above two ways-correspondence between CH and WH by

Theorem 8 CH and WH are isomorphic.

Thus we prove Wadge’s theorem by

• proving its analog for CH (theorem 9 below): |CH| = Veblen’s ordinal

• and then proving theorem 8.

[This detour through CH allows an essential simplification of the proof. For it is CH and not WH which has really simple operations generating it from .]

Theorem 9 There is a map d_{c}^{∘} from Borel Sets onto the Veblen ordinal such that:

A ≡_{c} B iff d_{c}(A) < d_{c}(B)

As a warmup to the proof of theorem 9, we prove its restriction to [BA] (which here denotes all Sets which are ≤_{c}A for some A in BA):

Theorem 10

|CH ↾ [BA]| = ω_{1}^{ω}

□ thm. 10 - - Step 1 - We define a Set Ω(α) for each α < ω_{1}^{ω} and prove: α < β iff Ω(α) ≤_{c} Ω(β). To that end we extend to CH the operations of ˆ+,ˆ.α,ˆ.∞: the definition is unchanged, only it is applied to Sets, which involve finite words as well. 10□

Lemma 2

(a) A ≤_{c} A′ implies A + B ≤_{c} A′ + B; B <_{c} B′ implies A + B <_{c} A + B′

(b) A.α ≤_{c} A.∞, for any ordinal α

□ lem. 2(a) - : by assumption II has a w.s. against I in C (A, A′) and C (B, B′), but not in C (B′, B). Using these strategies and the playful characterization of A ˆ+B it is easy to devise a w.s. for player II in C (A ˆ+B, A ˆ+B′): namely II applies his w.s. in B′ as long as I is remaining in charge of B. And if I decides to become in charge say of A, II decides the same thing and wins by playing the same letters as I later on. And a similar playful argument applied to I’s play shows that II cannot have a w.s. in C (A′ + B, A + B) or in C (A ˆ+B′, A ˆ+B): it would induce a w.s. for him in C (B′, B). 2□ □ lem. 2(b) - : obvious from the playful characterizations. We define the Set Ω(α) from CNF(α) just as in §2, but using the conciliatory extension of the operations. Then Step 1 follows easily from the Lemma by induction on α. 2□ Step 2: “separation lemma”:

Lemma 3 for every Set A, if

A ≤_{c} Ω(α) and A ≤_{c} ^{−}Ω(α) ⟹ A ≤_{c} Ω(β) or A ≤_{c} ^{−}Ω(β), for some β < α □ lem. 3 - By induction on α: α = 1 is trivial, so we assume α > 1 and that the lemma holds for every β < α.

Case 1: Ω(α) is of the form B ˆ+C. The complement of B ˆ+C is B ˆ+^{−}C (because of the symmetry between B and ^{−}B in the definition); thus the assumption on A is that II is given w.s. σ_{+} and s (i) gma_{−} in the games C (A, B ˆ+C) and C (A, B ˆ+^{−}C). Recall that by the playful definition of B ˆ+C, strategies σ_{+} and s (i) gma_{−} may ask to become in charge of B or ^{−}B during any play; but let F denote the set of all infinite words x in Λ_{A} such that if I in charge of A plays x, then neither σ_{+} nor s (i) gma_{−} make use of this right. Thus σ_{+} shows that A ∩ F ≤_{c} C and σ_{−} shows that A ≤_{c} ^{−}C. By definition of Ω(α) = B +C, there is γ < α such that C is Ω(γ). So by the induction hypothesis, A ∩ F ≤_{c} ^{ϵ}Ω(γ) where ϵ = + or −. Let β = α + γ, so Ω(β) = B + Ω(γ). Then II has a w.s. τ in charge of Ω(β), against I in charge of A: as long as I’s play did not go out of F, τ plays so as to remain in ^{ϵ}Ω(γ) and win against A ∩ F. And if I chooses to go in ^{ϵ}B, τ does the same and starts repeating every move of I. Thus τ wins in any case, and the induction is done.

Case 2: Ω(α) is of the form Bˆ.∞. Similar to case 1: the assumption provides II with two strategies σ_{+} and s (i) gma_{−} against I in charge of A. Since σ_{+} is in charge of Bˆ.∞ and s (i) gma_{−} in charge of its complement, it never happens that both strategies will play an infinite number of letters “e_{+}” or “e_{−}”. For they both would have their play rejected so one of them would win and the other lose. Then from σ_{+} and s (i) gma_{−} one can manufacture a w.s. τ for II in charge of Bˆ.∞ which never plays an infinite number of “e’s”: roughly speaking at each move τ chooses between mimicking σ_{+} and dually mimicking s (i) gma_{−}İn addition τ makes this choice so as to avoid playing “e” except when both options require it. Thus τ is a w.s. not only when II is in charge of Bˆ.∞, but also when it is in charge of B.∞ restricted so as to never play an infinite number of “e”. One can show for every strategy τ with this property that there is an ordinal γ (depending on τ) such that τ actually wins against Bˆ.γ. Thus A ≤_{c} Bˆ.γ, and this completes the induction in Case 2.

Case 3: Ω(α) is of the form ŝup_{c}(B_{i})_{i<α}. This case is simple.

Step 3 :

Lemma 4

a Set A is in [BA] iff A ≤_{c} Ω(α) for some α.

□ lem. 4 - : [BA] is closed under the operations building Ω(α); this proves the “if” direction. Opposite direction: A ≤_{c} Ω(ω^{n}) for some n; this can be proved first when A is an automaton. Then it applies to all A’s just by transitivity of ≤_{c}. 4□

Step 4 : final step.

Lemma 5 Let A be any Set in [BA],

A or its complement is ≡_{c} to Ω(α) for some α.

□ lem. 5 - Let α be the smallest ordinal such that A or its complement is ≤_{c} Ω(α). Only one of the two inequalities holds; for the above separation lemma says that otherwise α would not be smallest possible. So for instance II wins C (A, Ω(α)) but not C (^{−}A, Ω(α)). But the latter game is determined: if II has no w.s. then it is I who has a w.s., say σ˙(This holds because ^{−}A and Ω(α) are boolean combinations of G_{δ} sets; and for such games determinacy is a consequence -for instance- of the Gurevich-Harrington proof of effective determinacy. But more generally Martin has proved the determinacy of all Borel games) Now the perfect symmetry between the two players in a conciliatory game implies that if σ is a w.s. for I in C (^{−}A, Ω(α)) then it is also a w.s. for II in C (Ω(α), A). Thus we showed A ≡_{c} Ω(α) and the proof is done. 5□

We remark it is now easy to prove theorem 8 for [BA]; then as corollaries of the theorem just proved we obtain theorem 5, and the restriction to [BA] of theorem 5(a).

4 WH and CH on sets of finite Borel rank

In order to go beyond [BA] a new operation on Sets ∞^{A} is needed; we introduce it in the playful way.

Lemma 6

(a) ∞ ≡_{c} (b) ∞^{A ˆ+} ≡_{c} (∞^{A})ˆ.∞

(c) ∞^{sup_{n<ω}A_{n}} ≡_{c} sup_{n}(∞^{A_{n}})ˆ.∞

This lemma is a corollary of theorem 11 to come. However its proof is left to the reader because it is an instructive exercise. It starts making the new operation ∞^{A} resemble ordinal exponentiation, which we now recall. For all ordinals γ and α, γ^{α} is defined by induction on α : γ^{1} = γ; γ^{α+1} = γ^{α}.γ and γ^{sup_{i}α_{i}} = sup_{i}γ^{α_{i}}. The resemblance between ∞^{A} and exponentiation of base ω_{1} is an isomorphism except for a (small) imperfection ε :

Theorem 11

d_{c}(∞^{A}) = ω_{1}^{d_{c}(A)+ε} where ε is − 1, 0 or + 1

(depending on the value of d_{c}(A)).

The preceding lemma (a) shows the result in the initial case where d_{c}(A) = 1. So inductively assume it true for d_{c}(A) < some ordinal γ. Then the lemma proves it when γ is α + 1 and when γ is sup_{n}α_{n}. The remaining case is more delicate: full proof of theorem 9 is needed to obtain it in general. The case where A is of finite rank is a corollary to the next theorem.

Let ε_{0}(γ) denote sup_{n} γ_{n}, where γ_{1} = γ, γ_{n+1} = γ^{γ_{n}}. Thus ε_{0}(ω) is Cantor’s ordinal ε_{0}, and ε_{0}(ω_{1}) is the first ordinal closed under exponentiation of base ω_{1}. Remark - Suppose α < ε(ω_{1}); α has a Cantor Normal Form just as in the former case α < ω_{1}^{ω}, except that the additional operation ω_{1}^{x} is used at some stages. This allows to extend the definition of Ω(α), simply by additional clauses

Ω(α) = ∞^{Ω(β)}

or (depending on the value of ε, in theorem11 applied to A = Ω(β))

Ω(sup_{n<ω}α_{n}) = ˆ sup_{n<ω} Ω(α_{n}).

Theorem 12

Set A is of finite Borel rank iff A or ^{−}A ≡_{c} Ω(α) for some α < ε(ω_{1}).

Then d_{c}(A) = α iff A or ^{−}A ≡_{c} Ω(α).

□ thm. 12 - We make the same proof in 4 steps as for [BA], except that we take care in addition of the operation ∞^{A}.

Step 1:

α < β iff Ω(α) <_{c} Ω(β). This step was an easy consequence of lemma2. Here we only need to extend this lemma to the new operation: A <_{c} B implies ∞^{A} <_{c} ∞^{B}. This is easy.

Step 2 - Separation Lemma:

if A and ^{−}A ≤_{c} Ω(α), then there is β < α such that A or ^{−}A ≤_{c} Ω(β).

Proof - We only have to consider the case where Ω(α) is of the new form ∞^{B}, because the other cases are handled by the former proof.

Case 1: B is not itself of the form ∞^{B′}. Thus B is for instance of the form C ˆ+D; and a player in charge of ∞^{B} is in charge of C ˆ+D (...with an additional right to erase). If we forget the remark in parenthesis, we are thus proving the separation lemma in one of the cases handled by the former proof. Then it is possible to imitate that proof so as to transfer it from C ˆ+D to ∞^{C ˆ+D} = B...

Not case 1 : even in that case, there is B′ not of the form ∞^{B′′}, such that B results from B′ by the operation ∞^{A} iterated a finite number of times. Then the idea of case 1 can be applied, using B′ in place of B...

Step 3: Set A is of finite rank iff A or ^{−}A ≤_{c} Ω(α) for some α < ε(ω_{1}). Proof - The operations used to build Ω(α) all are Borel, and they increase the Borel rank at most by 1. So Ω(α) is Borel; and its rank is finite by easy induction on α. Let Ω_{n} denote the result of ∞^{A} applied n times to .2; one can show that A is of rank≤ n exactly when A or ^{−}A ≤_{c} Ω_{n}. Hence the result, since Ω_{n} is of the form Ω(α) for some α.

Step 4: one takes the smallest α such that A or ^{−}A ≤_{c} Ω(α) and shows that A or ^{−}A ≡_{c} Ω(α). Proof of step 4 is exactly the former one.

12□

Remark - As corollaries one can obtain the case of finite rank of theorems 12, 8, 9 and of Wadge’s main theorem.

5 The Set theoretic logarithm

The operation ∞^{A} acts like exponentiation on Sets; it can be inverted: for every Set A we define a Set A^{F} such that roughly (∞^{A})^{F} ≡_{c} A. Remembering that a player in charge of ∞^{A} is in charge of A but has an extra right to change the past of his play, we see that a player in charge of A^{F} should be in charge of A but have an extra duty: the duty to inform in advance about his future moves. To that end one carefully chooses a countable family F of closed subsets of the space Λ_{A}^{ω}; the player in charge of A^{F} is the usual player in charge of A with the additional duty to inform already at move n whether or not his final play will eventually belong to the n^{th} set of the family F.

A case where A^{F} is easy to understand is when A = ∞^{B}; then we take for F all sets of the form {x ∈ Λ_{A}^{ω} : x(i) = a} (i < ω and a ∈ Λ_{B}). A player in charge of (∞^{B})^{F} is forced during the play to decide all these sets; eventually he is thus forced to eventually decide the value of each of his moves. But after he has done it for a move, he can no longer erase it. So taking ∞^{B} gave him the right to erase, but then applying “F ” gradually suppresses this right! It is then easy to see that (∞^{B})^{F} ≡_{c} B: the operation acted as a kind of logarithm...This is a powerful tool reducing questions about a Set of the form ∞^{B} to questions about B. Remember that the idea to prove the Separation lemma is to deduce it from his former version by such a reduction. The new “logarithm” A^{F} offers the best way to realize this idea precisely.

6 Effective Borel Sets

In §3 we saw that ˆ.ω is a basic notion for WH; and in §2 we had seen that it also is the right notion in some effective studies. What about other basic notions about WH: ∞^{A}, A^{F}, CH; are they useful in the same effective way? This question is recent so we only have preliminary remarks and results about it.

a) In §3 we used CH to prove results about WH because CH is much simpler. This is good news here, for the conciliatory framework seems more natural in connection to TCS: it certainly is more realistic to allow words and plays to be finite!

b) Remember that infinite games modelize interacting processors. And that the operation ∞^{A} not only allows but even forces players to erase. For if a player in charge of ∞^{A} does not erase then he is only in charge of A which is much weaker. May be this could be used to modelize processors interacting in a memory saving way: if their specification can be expressed in a way that involves Sets of the form ∞^{A} in a suitable way, then a processor satisfying the specification will be a fanatical eraser!

c) Alas, in CS if Set B arises in a model for a specification, in practice it will not present itself under the form ∞^{A} for some A. But it may be possible to use the “logarithm”, putting B in the form ∞^{(B^{F})}. For it seems that if B is effective in some sense, then in a similar sense B^{F} is effective too.

Thus the notions we have come to in the non effective theory may have applications in the effective domain. But there are several ways for a Borel set to be effective, and to pursue the discussion we need to specify the one we consider.

6.1 (non deterministic) PDA’s

Proposition 2

(a) PDA ∩ co-PDA is closed under the operations ˆ+, ˆ.ω, ˆ.∞, ∞^{A}; and the same holds for NAPDA (that is non ambiguous PDA’s) ∩ co-NAPDA.

(b) Let DA^{−} denote the closure of DPDA under the above operations; the ordinal length of CH ↾ DA^{−} is Cantor’s ε_{0}. And provided CH ↾ DP DA is decidable with w.s. performed by DPDA transducers (something we expect to be proved soon) then the same holds for CH ↾ DA^{−}.

(c) In addition for every game G (A) with A in DA^{−} one can decide which player has a w.s.; and DPDA transducers suffice to win.

This sounds very nice, since DA^{−} contains Sets of every finite Borel rank: it looks as if DA^{−} is the extension of DPDA one is looking for, beyond the results of Courcelles-Walukiewicz! The trouble is that the proof of the proposition is too easy, reflecting the fact that DA^{−} is not rich enough: its Sets modelize rather limited kinds of specifications. Thus in reality one needs to extend the proposition to some richer class DA. But it is plausible that this can be done relying on existing ideas: the case of DA^{−} is so unchallenging that there is room for strengthenings...So let DA denote the set of all PDA’s that are ≤_{c} to some element of DA^{−} via a rational transducer; does every game G(A) with A in DA have an effective w.s. ?

The undecidability results of theorem 7 suggest that one has to restrict NAPDA in some explicit way if one is to obtain effective determinacy results. It is not easy and clear how to make this restriction; and the method based on ∞^{A} we used to define DA^{−}, is the only way which we see...Thus the operation ∞^{A} seems particularly useful to study NAPDA. On the other hands its inverse A^{F} quickly leads outside of PDA. This is one of the many reasons to consider the notion of effective Set we will introduce in §4.C.

6.2 Transfinite BA’s

By slightly generalizing the acceptance condition of BA’s one enables them to read transfinite words x in Λ^{α} for α > ω; the case α = ω^{n} is the main one: we then speak of an ω^{n} −BA. At first this seems too far from the real world to ever have applications. But this impression is due to a misunderstanding: when A in ω^{n} − BA is considered, people think that the associated game G (A) takes place in ω^{n} moves –a pure fantasy. But actually the associated game takes ω steps as before, producing a word x′ of length ω. It is the referee of the game which in order to determine the winner decodes x′ into a word x of length ω^{n}, and takes this number of steps to read x –just as for accepting words of length l many processors make computations of a longer length l^{n}. Put this way, ω^{n} − BA’s are natural. And in fact they define some of the most basic and natural effective Borel sets of rank up to 2n + 1. Prop - The hierarchy CH ↾ ω^{ω} − BA is of length at least ε_{0}(ω^{ω}) = ε_{0}. We expect that this bound will turn out to be the exact length, that the hierarchy is decidable and that every reduction between two ω^{ω} − BA’s can be done by an effective transducer (some partial results in this direction are obtained). This is not using ∞^{A} which leads to an undecidable extension of CH ↾ ω^{ω} − BA. But ω^{ω} − BA is closed under a variant of ∞^{A} denoted (Π, A), which has a quite similar theory.

6.3 Local Sets

A local sentence is a universal first order sentence ϕ such that in all models of ϕ , the set of all terms reduces to a fixed finite set T of terms. This is possible in the following way: for each term t(x_{1}...x_{k}) having all its proper subterms in T, we can write a finite disjunction D_{t} of equations which asserts that the value of t(x_{1}...x_{k}) equals the value of some term s of T applied to some of the variables x_{1} … x_{l}. Let ϕ include the universal closure of the disjunctions D_{t} : then clearly, in any model of ϕ, every term s in which parameters from the model are substituted to all variables reduces to a term s′ of T (s’ depends on the model and on the parameters, not only on s itself). In other words, as soon as the rest of the sentence ϕ is universal, ϕ will be local. Clearly every model M of a local sentence ϕ is locally finite in the sense that any finite part X of M generates a finite substructure A (in fact the cardinal of A is bounded by a polynomial of card X). This is the origin of the terminology “local”. A class C of words is local if for some local sentence ϕ it is of the form :

{x ∈ Λ^{ω} : the structure x can be extended to a model of ϕ}

(when the word x is considered as a structure in the usual way). One can show the existence of local Sets in this sense which are Borel of infinite rank or even analytic. Still all local Sets are effective in the sense that there is an algorithm to decide whether they contain at least one infinite word. This analog of Büchi’s lemma is proved in [R 88] and [R F 96] also shows that any weaker combinatorial principle than the infinite Ramsey theorem does not suffice to justify the algorithm. This is in sharp contrast with Büchi’s lemma, which rests on a particularly weak combinatorial principle -namely: the form of the pigeon hole principle asserting that there is no injection from an infinite set into a finite one! The contrast suggests that local Sets form a particularly rich class of effective Sets. It is an open question whether they include all PDA’s; but any concrete and usable example of PDA which we know of is easily seen to be local. In addition every ω^{n} − BA is local [F 99(d)]. Local Sets are closed under union but not under complement [F 94]; but Sets local and co-local are closed under the operations ˆ+, Aˆ.ω, Aˆ.∞, ∞^{A}. Work has started to show that the class of local Sets of finite Borel rank is in addition closed under the operation A^{F}, and that it is close to the class of ω^{ω} − BA. This would be nice because local sentences are a much more flexible way to define Sets than ω^{n} − BA’s. On the other hand, ω^{n} − BA’s have good decidability properties, so one would have both advantages. Finkel has started to show that the ordinal length of CH ↾(local and co-local Sets) is much larger than ε_{0} ; so that this notion of effective Set is a story at its very beginning.

6.4 CONCLUSION

So much about using the non effective theory of WH to help the investigation of effective determinacy (both of G(A) and W(A,B) games). What about the converse -using CS to help the Set Theory of WH ? Our initial goal was to study the effective part W H ↾ ω^{ω}-BA rather than WH itself. This study lead to the operation (Π, A) (used in the study of transfinite BA’s) and to the “conciliatory” framework, which lead to ∞^{A}, which lead to A^{F}. The latter concepts were up to the challenge of giving full proof and extension of Wadge’s main theorem. This lead the first author to concentrate on the non effective aspects of WH until the challenge was won. Consequently the effective investigations we have told in this section only started recently: there still is a wealth of ideas to be developed.

7 Climbing to the top of WH

One reaches the Veblen ordinal by a clever iteration of ordinal exponentiation of base ω_{1}. The cleverness is used to monstrously prolongate this iteration without loosing control of the process. So that the Veblen ordinal thus reached and defined is very large, yet has a “Veblen Normal form” for all its predecessors, as ε(ω_{1}) has a Cantor Normal form. The isomorphism between CH and the Veblen ordinal is then constructed by using the Veblen Normal form and converting it to a normal form Ω(α) of every Borel Set, in 4 steps as before. The additional work needed w.r. to §3 consists:

i) in iterating the operation ∞^{A} in a way clever enough to make these iterations correspond to Veblen’s iterations of ordinal exponentiation ii) and in iterating the operation A^{F} so that it provides the inverse of the iterated ∞^{A}. This is hard work but in some sense all the ideas are to be found in §3 except for the Veblen construction, to be found in [V 08]. Thus |CH| = Veblen ordinal gets proved (theorem 9). There remains to prove WH isomorphic to CH (theorem 8). This is done by induction on all ordinals < |CH|, using the knowledge of CH provided by the proof of theorem 9.

8 WH extended to uncountable alphabets

So far the alphabet Λ of any set of words was of cardinal ≤ ω; and the Veblen ordinal was the one we now denote V (ω), which uses exponentiation of base ω_{1}. But the proof of |W H| = V (ω) can be extended to the case where Λ has cardinal < κ (κ any infinite cardinal); and where V (ω) is replaced by V (κ) (defined as V (ω), but when exponentiation of base κ is used). And the extended proof determines |W H| when κ replaces ω. There is however a significant difference in the result one obtains, whenever κ is uncountable : namely |W H| is much smaller than V (κ). Since not many people are aware of WH even in the countable case, one may wonder if it makes sense to consider this uncountable case, still less effective. Here are two reasons to do so.

Reason 1: a missing part of WH The fact that |W H| becomes strictly less than the Veblen ordinal V (κ) raises the question: is there a hierarchy WH(κ) which coincide with WH in the countable case but is larger in the uncountable case, so that |W H(κ)| = V (κ) becomes true for all values of κ ? This problem of the “missing part” W H(κ) ∖ W H has been solved by J. Duparc (feb. 1998): the length of WH and CH does jump precisely to V (κ) if the hierarchy is extended to all analytic∩co-analytic– sets; where a set A included in Λ^{ω} is analytic if it is the projection of some closed subset of Λ^{ω} × ω^{ω}. (If Λ is countable, by Suslin’s celebrated theorem these analytic∩co-analytic sets reduce to the Borel ones. It is only if Λ is uncountable that they contain substantially more than the Borel sets –providing for the “missing part” of WH).

Reason 2: the extension of WH goes in the direction of more effectivity ! For Girard-Vauzeille [G V 84] extended the Veblen hierarchy to a Veblen functor V of ordinals, which is effective in the following sense: the restriction of this functor to finite objects (integers and morphisms between them) is primitive recursive and this restriction uniquely determines all of Veblen’ functor, in an utterly direct way. Now once WH is extended to W H(κ) we have turned WH to a function of the cardinals κ which is partially isomorphic to this Veblen functor. It is then easy to define more generally W H(α) for every ordinal α so that the function: α ⟼ |W H(α)| coincides with the function: α ⟼ V(α). We intent to enrich the function: α ⟼ W H(α) to a functor, so that the above isomorphism of functions becomes an isomorphism of functors: one that preserves their categorical structure and not only the order. Our proof of Wadge‘s main result proceeded by turning the equality |CH| = V(ω) to be proved, into a isomorphism between < CH > (Sets with their natural structure), and < V (ω) > (= ordinals with their natural structure); this projected extension is the analog when functors over the ordinals (called dilators) replace ordinals. Its goal is to apply to effective determinacy the beautiful ideas of Girard - see [G V 84] - connecting dilators with large cardinals and determinacy. This is a long term program; there is a plenty to do in the meantime...

References

[C 95] Courcelles B. [1995] The monadic second-order logic of graphs IX: Machines and their behaviours Theoretical Computer Science, 151 (1995) 125-162.

[C 96] Courcelles B. [1996] The monadic second-order logic of graphs X: Linear orders Theoretical Computer Science, 160 (1996) 87-143.

[D 95] Duparc J. [1995] La forme normale des Boréliens de rangs finis Thèse de Doctorat, Université Denis Diderot Paris VII. Juillet 95.

[D 94] Duparc J. [1994] The normal form of Borel sets of finite rank Accepted by A.P.A.L.

[D 96] Duparc J. [1996] Wadge hierarchy and Veblen hierarchy: part I Borel sets of finite rank To appear in The Journal of Symbolic Logic.

[D 97] Duparc J. [1997] A normal form for Borel sets of any rank. Submitted to The Journal of Symbolic Logic.

[D 98] Duparc J. [1998] Hierarchy of push down automata. Unpublished.

[D 95] Duparc J. [1995] Wadge degrees of Louveau’s (Wadge) classes. Unpublished.

[F 98 ] Finkel O. [1998] Topological properties of context free ω - languages. submitted to TCS.

[F 99(a)] Finkel O. [1999] Wadge Hierarchy and context free ω-languages. In preparation

[F 99(b)] Finkel O. [1999] Wadge hierarchy and counter ω-languages. In preparation.

[F 99(c)] Finkel O. [1999] Locally finite ω -languages. In preparation.

[F 99(d)] Finkel O. [1999] Locally finite languages. To appear in T.C.S..

[F 94] Finkel O. [1994] Closure Properties of Locally Finite ω-languages . Preprint.

[F 89] Finkel O. [1989] Langages de Büchi et ω-langages Locaux. C.R.A.S. Paris, t.309, Série 1, p. 991-99

[G V 84] Girard J.-Y., Vauzeilles J. [1984] Functors and ordinal notations I: A functorial construction of the Veblen hierarchy The Journal of Symbolic Logic, vol 49 (1984) 713-729.

[L 83] Louveau A. [1983] Some Results in the Wadge Hierarchy of Borel Sets. Cabal Sem 79-81, Lecture Notes in Mathematics (1019) 28-55.

[L-SR 85] Louveau A.,St.Raymond J. [1985] The strength of Borel Wadge determinacy. Cabal Sem 81-85, Lecture Notes in Mathematics (1333) 1-30.

[L-SR 88] Louveau A.,St.Raymond J. [1988] Les propriétés de réduction et de norme pour les classes de Boréliens. Fund. Maths. vol. 131 (1988) 223-243.

[M 75] Martin D.A. [1975] Borel Determinacy. Ann. Math. vol.102 (1975) 363-371.

[M 85] Martin D.A. [1985] A purely inductive proof of Borel Determinacy. Rec. Theory, Proc. Symp. Pure Math. 42. (1985) 303-308.

[R 88] Ressayre J-P. [1988] Formal languages defined by the underlying structure of their words. J. Symbolic Logic 53 (1988), no. 4, 1009– 1026.

[R F 96] Ressayre J-P. and Finkel O. [1996] Stretchings. Journal of Symbolic Logic, Volume 61, number 2, June 1996, p. 563-585.

[T 90] Thomas W. [1990] Automata on Infinite Objects. Handbook of Theoretical Computer Science, ch. 4; edited by J. van Leeuwen Elsevier Science Publishers B. V., 1990.

[V 08] Veblen O. [1908] Continuous increasing fonctions of finite and transfinite ordinals. Transactions of the American Mathematical Society vol 9 (1908) 280-292.

[W 72] Wadge W.W. [1972] Degrees of complexity of subsets of the Baire space. Notice A.M.S. (1972), A-714.

[W 84] Wadge W.W. [1984] Ph.D. Thesis, Berkeley

[W 79] Wagner Klaus W. [1979] On ω-regular sets. Inform. and Control 43 (1979), no. 2, 123–177.

[W 96] Waluliewicz I. [1996] Pushdown processes: games and model checking. CAV’96, to appear in Information and Computation (32 pages)