This paper is a continuation of the study of topological properties of omega context free languages (!-CFL). We proved in (Topological properties of omega context free languages, Theoretical Computer Science, 262 (1-2) (2001) 669-697) that the class of !-CFL exhausts the ΓΏnite ranks of the Borel hie
The normal form of Borel sets. Part II: Borel sets of infinite rank
β Scribed by Jacques Duparc
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 459 KB
- Volume
- 328
- Category
- Article
- ISSN
- 0764-4442
No coin nor oath required. For personal study only.
β¦ Synopsis
RBsumC.
For each Bore1 set of reals of infinite rank A we obtain u "normal form" of A by finding a Bore1 set 62 such that A and 6! continuously reduce to each other. We do so by defining simple Bore1 operations which are homomorphic to the w, first Veblen ordinal operations of base (J, required to compute the Wadge degree of a Borei set. 0 Acad6mie des Sciences/Elsevier, Paris La Jot-me norm& des bor6lien.s de rang infini Version frangaise abrdge'e Cette Note est la suite de la Note 111 concernant la forme normale des Borkliens. Nous rappelons yue nous considkons les ensembles .4 C A:, qui sont bort5liens pour la topologie produit de la topologie discrke sur un ensemble denombrable A . Pour deux tels ensembles A 5 A'$ et U g AL;; la relation A <,,, 13 signifie qu'il existe une fonction continue de 114 dans A';;: tel que A soit l-image inverse de B par cette fonction. La relation d'bquvalence A E-,! L3 dCsigne le fait qu'8 la fois A <,(, 13 et EI <,,: A sont vCrifiCes. La relation stricte 4 <,(, I3 dit que A <,, B est vCrifiCe saris que II <,, A le soit. Martin et Wadge ont montr6 que cette dernikre relation restreinte aux ensembles borkliens constituait un pr&-bon ordre. Plus exactement. la relation <,,:, quotientke par la relation d'equivalence M definie par A M 13 si et seulement si (iI +,: [I V ,,I zu; -n), est un bon ordre sur les ensembles boreliens. Note prhent6e par Gustave CHOQIIIX.
π SIMILAR VOLUMES
It is shown that for every primitive recursive sequence [m i ] i=0 of positive integers, there is an ackermannic sequence [n i ] i=0 of positive integers such that for every partition of the product > i=0 n i into two Borel pieces, there are sets H i n i with |H i |=m i such that the subproduct > i=