• 晋中市通报五起违反中央八项规定精神问题 2019-10-08
  • 人民日报金台锐评:让工作日志减负增效 2019-10-08
  • 帮助孩子成为优秀的人:如何通过编故事来发展孩子的创造力 2019-10-02
  • 人民日报评论员:民生改善是梦想的最好诠释 2019-10-02
  • 辽宁大连:玩具卡住男童手  消防耐心帮解困 2019-09-30
  • 可再生能源电价附加资金补助目录公布 2019-09-13
  • 慈善实践与新时代道德建设 2019-09-08
  • 王子文再登封面 黑白光影间酷女孩玩转高级时尚 2019-09-06
  • 【大家谈】激励实干担当,谱写奋斗“进行曲” 2019-09-06
  • 她主动借腹给我生儿子,中途又移情别恋 有故事的人 2019-09-03
  • 90后创业者成电商谷第100家园企 ——凤凰网房产北京 2019-09-03
  • 拥有大智慧的中国古人就把“子”和“女”结合在一体,造出一个会意字“好”字。一直就用这个“好”的感觉结果去衡量其它任何生存环境中的万物万事所给人的感觉。 2019-08-14
  • 中共中央组织部“12380”举报网站 2019-08-08
  • 省委扫黑除恶专项斗争督导组反馈吉安督导情况 胡世忠作表态发言 2019-07-28
  • 实现中华民族伟大复兴是近代以来中华民族最伟大的梦想(认真学习宣传贯彻党的十九大精神) 2019-07-28
  • 江苏七位体彩开奖结果
    学霸学习网 这下你爽了
    当前位置:江苏七位体彩开奖结果 >> >>

    体育彩票竞猜:Russian Math. Surveys 585 839–927 c○2003 RAS(DoM) and LMS Uspekhi Mat. Nauk 585 3–88 DOI

    江苏七位体彩开奖结果 www.jwbw.net Russian Math. Surveys 58:5 839–927 Uspekhi Mat. Nauk 58:5 3–88

    c 2003 RAS(DoM) and LMS DOI 10.1070/RM2003v058n05ABEH000666

    Dedicated to the centenary of P. S. Novikov’s birth

    On some classical problems of descriptive set theory

    V. G. Kanovei and V. A. Lyubetskii [Lyubetsky]
    Abstract. The centenary of P. S. Novikov’s birth provides an inspiring motivation to present, with full proofs and from a modern standpoint, the presumably de?nitive solutions of some classical problems in descriptive set theory which were formulated by Luzin [Lusin] and, to some extent, even earlier by Hadamard, Borel, and Lebesgue and relate to regularity properties of point sets. The solutions of these problems began in the pioneering works of Aleksandrov [Alexandro?], Suslin [Souslin], and Luzin (1916–17) and evolved in the fundamental studies of G¨ odel, Novikov, Cohen, and their successors. Main features of this branch of mathematics are that, on the one hand, it is an ordinary mathematical theory studying natural properties of point sets and functions and rather distant from general set theory or intrinsic problems of mathematical logic like consistency or G¨ odel’s theorems, and on the other hand, it has become a subject of applications of the most subtle tools of modern mathematical logic.

    Contents Introduction §1. Borel sets and projective sets 1A. Real line, Polish spaces, and the Baire space 1B. Principal regularity properties in Polish spaces 1C. Projective hierarchy and the language of analytic formulae 1D. Elements of the theory of Π1 1 sets 1E. Digression: encoding by points of the Baire space §2. G¨ odel’s constructibility 2A. Set-theoretic universe 2B. General notion of G¨ odel’s constructibility 2C. Constructibility in the domain of the Baire space 2D. Absoluteness §3. Resolvents of classical problems: Part 1 3A. Cohen points and random points 3B. Main results on resolvents of the regularity properties 3C. Uncountable Π1 1 sets without a perfect kernel 3D. Non-measurable sets of second projective level 840 846 847 848 851 852 855 859 859 860 862 864 866 866 867 868 869

    The ?rst author was supported by the Russian Foundation for Basic Research under grant no. 03-01-00757. The second author was supported by Minpromnauka under grant no. RF 37053-11-0061. AMS 2000 Mathematics Subject Classi?cation. Primary 03E15, 03E30, 03E45; Secondary 03E40, 28A05, 54H05, 03C25, 54E52.

    840

    V. G. Kanovei and V. A. Lyubetskii

    3E. Generalization: measurability with respect to an ideal 3F. Sets that are non-measurable with respect to an ideal 3G. Consistency of the existence of counterexamples §4. Resolvents of classical problems: Part 2 4A. Basics of forcing and comments 4B. If there are few constructible points, then the Π1 1 sets have the perfect kernel property 4C. Forcing induced by an ideal of Borel sets 4D. Two examples 4E. If there are few non-random points, then all sets of the second projective level are measurable §5. Combinatorics of eventual domination 5A. Eventual domination and measurability 5B. Eventual domination and the Baire property 5C. In the class Σ1 2 measurability implies the Baire property §6. ‘Elementary’ proof of one of the theorems 6A. Analysis of the proof 6B. Descriptive continua 6C. Generic extensions of descriptive continua 6D. Completion of the ‘elementary’ proof of Theorem 6.1 §7. Undecidability of the problems 7A. De?nitions and comments on the theorems 7B. First model; one collapse function 7C. The proof of the key lemma 7D. Second model; ?L 2 collapse functions 7E. Perfect kernel property in the second model 7F. Solovay model §8. Irreversibility of the implications 8A. Four key forcings 8B. LM(Σ1 ? PK(Π1 2) = 1) 1 8C. BP(Σ2 ) =? LM(?1 2) 1 8D. BP(?1 ? BP(Σ1 2 ) ∧ LM(?2 ) = 2) 1 1 8E. BP(Σ2 ) ∧ LM(?2 ) =? LM(Σ1 2) 8F. LM(?1 ? BP(?1 2) = 2) §9. Further results 9A. Do we need an inaccessible cardinal? 9B. Problems of third and fourth projective levels 9C. Some new σ-CAC ideals and other regularity properties Bibliography

    870 872 874 875 876 878 879 882 882 885 885 887 889 890 891 891 892 895 896 897 898 899 901 903 905 907 908 909 910 912 914 917 920 920 921 921 923

    Introduction An international mathematical conference dedicated to the 100th anniversary of the birth of P. S. Novikov was held in Moscow in August 2001. The authors of this paper were among the participants and speakers at the conference.

    On some classical problems of descriptive set theory

    841

    The beginning of the 21st century also marks the centennial of the descriptive theory of sets and functions,1 an area in which many fundamental achievements are due to P. S. Novikov. The regularity properties, that is, the perfect kernel property, Lebesgue measurability, and the Baire property, were among Novikov’s favourite topics in descriptive set theory. In what follows, let K denote any class of point sets. (For the moment, we mean by a point set a subset of the real line R or of a space of the form Rn , as was customary in the early ‘Luzin’ era of development of descriptive set theory. A somewhat wider modern understanding of the notion of point set is given below in 1A.) The expression K-set means a set belonging to the class K. The principal question here is formulated as follows: For a given class K of point sets and for each of the three regularity properties mentioned above, is it true that every K-set has this property ? To facilitate the discussion to follow, let us explicitly formulate three possible answers, or three hypotheses concerning the principal regularity properties:2 PK(K): every K-set X has the perfect kernel property, that is, X is either ?nite or countable or contains a perfect subset (a non-empty closed set having no isolated points); LM(K): every K-set X is Lebesgue measurable; BP(K): every K-set X has the Baire property, that is, X coincides with a Borel set modulo a meagre set.3 More general formulations applicable to sets in any uncountable Polish spaces4 and not just sets in R will be given in 1B below. The perfect kernel property arose as a possible approach to the problem of cardinality of point sets; indeed, any perfect subset of the real line is in fact of cardinality the continuum c = 2?0 . Measurability and the Baire property are basic mathematical notions. Examples of non-regular sets, for instance, non-measurable point sets, have been known since the beginning of the 20th century (Vitali, Bernstein, and others), but all of them are obtained by using the axiom of choice, and hence they are not individual unambiguously de?ned sets. The desire to obtain more explicit, ‘e?ective’ counterexamples led to heightened interest in explicitly de?nable point sets studied in descriptive set theory. In the mid-1920s the family of such sets included the Borel sets (they form the smallest σ-algebra containing all open sets in the given space), the A sets (the closure of the Borel σ-algebra under the operation A), and the projective sets (the closure of the Borel σ-algebra under
    1 The origins of descriptive theory can be traced back either to the introduction of Borel sets and Baire functions in the works of Borel [13] (1898) and Baire [6] (1899) or to Lebesgue’s memoir [47] (1905), which systematized the very ?rst results on such sets and functions. 2 The abbreviations mean: perfect kernel, Lebesgue measurability, Baire property. Those three properties are known as the principal regularity properties. Other properties of this kind are also considered; some of them are discussed in 9C. 3 The meagre sets, or ?rst-category sets, are the countable unions of nowhere dense sets. The sets complementary to meagre sets are said to be co-meagre. 4 Separable complete metric spaces are called Polish spaces.

    842

    V. G. Kanovei and V. A. Lyubetskii

    the operations of taking continuous images and complements). The sets of the last 1 1 kind are arranged in a hierarchy of classes of sets Σ1 n , Πn , ?n (or An , CAn , Bn in the classical system of notation) which increase as the index n increases; the class 1 1 Π1 n consists of the complements of the Σn sets, and the class ?n coincides with the 1 1 intersection of Σn and Πn . (For the exact de?nitions, see 1A below.) Since measure and category are σ-additive notions, all Borel subsets of the real line are Lebesgue measurable and have the Baire property, of course. The perfect kernel property of Borel sets is not so simple, because one cannot use direct induction when constructing sets by using Borel operations. The solution was found by P. S. Aleksandrov [3] and F. Hausdor? [23] independently and by di?erent methods. The proof given by Aleksandrov led Suslin [91] to the discovery of the A operation and A sets (now known as Σ1 1 sets). Luzin [51] and Suslin established the three reg1 ularity properties for all A-sets, that is, in our notation, one has PK(Σ1 1 ), LM(Σ1 ), 1 1 and BP(Σ1 ). Measurability and the Baire property carry over to the class Π1 of complementary sets (classically known as CA-sets), of course. All attempts made in classical descriptive set theory to extend these results to higher projective classes, in other words, to prove or disprove at least the asser1 1 tions PK(Π1 1 ), LM(Σ2 ), BP(Σ2 ), were fruitless. The problems were very quickly recognized to be di?cult and probably central problems of descriptive set theory. Moreover, Luzin expressed in [53] (1925) the opinion that those problems were undecidable in general, that is, admitted no de?nite answer, and he discussed in [52] the undecidability of several more general problems related to the perfect kernel property, measurability, and the Baire property for all projective sets.5 The 1 perfect kernel problem for Π1 1 sets and the measurability problem for Σ2 sets were later characterized by Novikov in [78] (1951) as two of the three main problems of the descriptive theory of functions.6 Thus, the development of classical descriptive set theory led to problems concerning the regularity properties of point sets, both in their ‘minimal’ form (from the point of view of the projective class involved)7 and in the most direct form, that is, for the special classes, PK(Π1 1 ), LM(?1 2 ), BP(?1 2 ), LM(Σ1 2 ), BP(Σ1 2 ), (?)

    5 “It is not known and will never be known whether or not every set in this family [that is, the family of projective sets] is of cardinality the continuum, is a set of third category [that is, a set that does not have the Baire property], is measurable.” This was written in [52], dozens of years before the discovery of methods which enabled one to actually establish the undecidability of the problems. Moreover, at that time, the prevailing opinion was that every mathematical problem is soluble. 6 The third problem in Novikov’s list is the separation property in higher projective classes, which became especially interesting after his own paper [76], where it was shown that the laws of separation at the second projective level are opposite to the laws of separation at the ?rst projective level. (See Luzin’s comments in [58], § 23.) The uniformization problem, which was ?rst considered in the context of descriptive set theory in [56], and several problems on uncountable sequences of Borel sets (see, for example, [58], § 23, or [59]) can be added to the list. For these problems, which we do not discuss here, see the surveys and papers [36], [38], [40], [93], [97]. 7 Except, of course, for the provable claims for the class Σ1 . 1

    On some classical problems of descriptive set theory

    843

    and for the class of all projective sets as a whole.8 The absence of any reasonable approach to those problems, in any direction, rapidly led researchers to the idea of undecidability of the problems. Let us say a few words on the very notion of undecidability. Undecidability problems, that is, problems on the impossibility of constructing a certain mathematical object (including the construction of a proof or a refutation of some hypothesis) by using certain tools, had been known in mathematics long before the appearance of descriptive set theory; we can point to Abel’s theorem on the impossibility of solving higher-degree algebraic equations in radicals or the three famous age-old geometric problems on trisecting an angle, squaring the circle, and doubling the cube. However, a rigorous statement of the undecidability problem for set-theoretic problems arose after the creation of the Zermelo–Fraenkel axiomatic set theory ZFC. This axiomatic system was developed (1908–1925), in particular, in connection with the aim of making mathematical proofs more precise and codifying the axioms involved in the proofs. It is of interest that there were in general no axioms subject to controversy as to whether or not they should be included in this axiomatic set theory.9 After long study of the foundations of all branches of mathematics, it is regarded as an established fact that any mathematical argument can be converted into a proof based on the ZFC axioms, or, brie?y, a derivation in ZFC, and, in this sense, the fact that a statement P cannot be proved in ZFC means that P cannot be proved in mathematics. Thus, the undecidability of a mathematical problem, that is, the impossibility of giving a positive or negative answer to the corresponding question, is equated to its undecidability in ZFC. The latter means that neither the formula P expressing the problem nor its negation ?P have a proof in ZFC. By the G¨ odel completeness theorem, the deducibility of some formula P in ZFC is equivalent to the condition that P holds in every model of ZFC theory. Therefore, a typical proof of the undecidability of some problem P is the construction of a model M of (all) axioms of ZFC in which P is true (that is, P has an a?rmative solution in M ) and of another model N of the ZFC axioms in which P is false (that is, P is solved in N in the negative). The ?rst part of such an argument shows the consistency of adjoining the formula P to the axioms of ZFC and the second

    speaking, the Σ1 2 case of the problems of measurability and the Baire property is 1 1 not minimal, because the class ?1 2 is a proper subclass of Σ2 , and the problems for ?2 are also undecidable. However, this class deserves to be included in the list for at least two reasons. First, the class Σ1 2 = A2 generally attracted more attention in classical descriptive set theory than the 1 1 class ?1 2 = B2 . Second, the methods of solving the problems for Σ2 and ?2 are the same in essence. 9 If one does not consider the discussion relating to the axiom of choice, which was rather in the framework of a controversy about the admissibility of certain mathematical tools like the law of the excluded middle, non-e?ective constructions, ‘really’ in?nite sets, and so on, where the negation of the axiom of choice meant rather the negation of any axiomatics at all. The famous ‘Cinq lettres’ [8], the letters among Hadamard, Baire, Borel, and Lebesgue, were largely devoted to this topic. Luzin dwells on it in [58], Part III, [55], pp. 31, 60, 64, and [57], Chapter 1 and the Conclusion.

    8 Strictly

    844

    V. G. Kanovei and V. A. Lyubetskii

    the consistency of adjoining the formula ?P to the axioms of ZFC.10 Of course, there are proofs in which one or both parts (relating to P or to ?P) are obtained by reduction to known consistency results. The ?rst results concerning proofs of consistency and undecidability for settheoretic statements were obtained by G¨ odel [20] (1938–1940). He de?ned the class L of all constructible sets and proved that L, when regarded as a set-theoretic structure with the ordinary membership relation ∈ for two sets, is the smallest model of the axioms of ZFC that contains all ordinals (ordinal numbers). G¨ odel also proved that the generalized continuum hypothesis GCH holds in L, and thus established the consistency of GCH. The study of the class L was continued in 1 Novikov’s paper [78] (1951), where he solved the problems PK(Π1 1 ) and LM(?2 ) 1 1 1 (and hence the problem LM(Σ2 ) as well, because ?2 is a subclass of Σ2 , and the 1 problems BP(?1 2 ) and BP(Σ2 ) for similar reasons) in the class L in the negative, that is, appropriate counterexamples can be explicitly de?ned in L. Thus, the consistency of negative solutions of the regularity problems was established for those projective classes. Another method, opposite in a sense to the method of constructing models of ZFC, is the method of forcing discovered by P. Cohen (1963). This is a general tool for extending any given model M of ZFC theory (for instance, the class L) by adjoining some set a ∈ / M (and of course all ‘derived’ sets, that is, sets whose existence in the model M [a] follows from the existence in it of a) in such a way that the extended structure M [a] also satis?es all the axioms of ZFC. Cohen himself used this method to de?ne a model in which GCH (and even CH) fails (1962– 1963; see the book [15]). Somewhat later, Solovay [89] (1970) presented a model of ZFC in which every projective set satis?es the three regularity properties. Together with the above results of Novikov, this result proved that the regularity problems of 1 1 point sets are undecidable, both in their ‘minimal’ forms PK(Π1 1 ), LM(?2 ), BP(?2 ), 1 1 LM(Σ2 ), BP(Σ2 ), and for the class of all projective sets as a whole, that is, Luzin’s undecidability conjecture was con?rmed for the ?ve problems. We note that, in contrast to G¨ odel’s incompleteness theorems or, say, to the continuum hypothesis, we speak here of the undecidability of speci?c mathematically meaningful properties of quite individually de?ned and rather simple point sets. For example, there is an explicitly de?ned Π1 1 set X ? R such that the assertion PK(X ) that X has the perfect kernel property is undecidable. Along with undecidability theorems, the investigations of many authors in the late 1960s and early 1970s established striking connections between the problems 1 1 under consideration. It turned out that PK(Π1 1 ) implies both LM(Σ2 ) and BP(Σ2 ), 1 and somewhat later it became clear that LM(Σ1 ) implies BP(Σ ). These results 2 2 are shown in the diagram. At the end of the 1980s, the forcing method was used to
    10 All arguments on undecidability in ZFC and consistency with respect to ZFC certainly assume that ZFC theory itself is consistent, that is, one cannot derive in this system both some formula Φ and its negation ?Φ (or, equivalently, some formula cannot be derived in ZFC.) It is impossible to prove the consistency of ZFC by the tools of contemporary mathematics, because such a proof would mean a proof of consistency of ZFC by using its own axioms, which is excluded by G¨ odel’s second incompleteness theorem. Nevertheless, the long development of a mathematics free of contradictions, explicitly or implicitly on the basis of precisely the axioms of ZFC, has made the consistency hypothesis for ZFC generally accepted.

    On some classical problems of descriptive set theory

    845

    construct models which established the completeness of the diagram, in the sense that no other implication between its elements is derivable in ZFC. These results all together completed the cycle of the most principal studies of the regularity 1 1 problems for the projective classes Π1 1 (the perfect kernel property), Σ2 , and ?2 (measurability and the Baire property), and for the class of projective sets as a whole.11

    Diagram. All ?ve hypotheses of the above list (?) are undecidable in ZFC; the arrows show provable implications between the hypotheses; 1 the dashed arrows show trivial implications (because ?1 2 ? Σ2 ); 1 ) = ? BP(Σ ) is distinguished because it was the ‘derived’ implication PK(Π1 1 2 1 obtained together with PK(Π1 ) = ? LM(Σ ) and much earlier than the implica1 2 1 tion LM(Σ1 ) = ? BP(Σ ). 2 2

    The aim of this paper is to present all the principal results obtained in these studies with su?ciently complete proofs (and at the same time substantially simpli?ed and modernized as compared with those in the original works) and also to systematically present the corresponding methods. The paper is intended for the reader who is interested in set-theoretic problems, has some experience in this area and in the area of mathematical logic, and, at least for some parts of the paper, is acquainted (at least minimally) with the method of forcing. As far as the technique (the proofs) is concerned, we tried to make the exposition self-contained, although the paper certainly cannot be regarded as a textbook on G¨ odel constructibility and forcing theory. The structure of the paper is as follows. Section 1 is a general introduction. Section 2 is an introduction to the theory of G¨ odel constructible sets (in the framework needed for this paper). In particular, we consider the de?nability of the structure of constructible sets within the continuum. The non-trivial implications in the diagram are derived in Sections 3–5. To this end, corresponding to each of the ?ve propositions in the diagram, that is, to 1 1 1 1 PK(Π1 1 ), LM(Σ2 ), BP(Σ2 ), LM(?2 ), and BP(?2 ), is a resolvent (Luzin’s term), which for a given proposition means an (equivalent) reformulation of signi?cantly simpler nature. Corollary 3.4 presents all ?ve reformulations, that is, resolvents, and each is in a natural way an equivalence. More ‘e?ective’ versions of these equivalences are given in Theorem 3.3. The proofs of the equivalences in one direction are given in § 3 by using constructibility theory, and in the other direction in § 4 by
    we do not touch upon studies in the framework of the theory of set operations founded by Kolmogorov and Hausdor? in which large classes of point sets were discovered within the class ?1 2 that still preserve measurability and the Baire property. For this topic, see [39].
    11 Here

    846

    V. G. Kanovei and V. A. Lyubetskii

    using the method of forcing. Finally, in § 5, the problems of measurability and the Baire property are related to the properties of eventual domination (for a natural partial order relation on the set Nω of all self-maps of the natural numbers), which enables us to derive the implication LM(Σ1 ? BP(Σ1 2) = 2 ). This completes the proof of all the implications of the diagram. It is a special feature of the standard proofs of the non-trivial implications in the diagram that, to derive statements with su?ciently elementary formulations on the nature of point sets in low projective classes, one uses methods (like constructibility and forcing) which explicitly involve the class of all sets. In Section 6 we consider a problem which is of importance in our opinion, namely, whether or not one can prove the same results without using arbitrary (Cantorian, so to speak) sets while remaining within the framework of notions used in the setting of problems in descriptive set theory, that is, using only objects of the type of point sets. By the example of the implication PK(Π1 ? LM(Σ1 1) = 2 ), we answer this question in the positive and call these proofs ‘elementary’, in contrast to proofs involving arbitrary ‘Cantorian’ sets. In the next section, § 7, we present a remarkable result: even if non-regular projective sets exist, for instance, if there is an uncountable projective set without perfect subsets (or a non-measurable set, or a set for which the Baire property fails), this does not imply the existence of an explicitly de?nable non-regular projective set, that is, the existence of a speci?c, unambiguously de?ned counterexample! The di?erence between de?nable and ‘arbitrary’ sets (for example, those given by the axiom of choice) was given great signi?cance at earlier stages of the development of descriptive set theory (see the footnote 9). In § 7 we also prove Solovay’s theorem claiming that positive solutions of the three regularity problems for all projective sets (in fact, for a somewhat wider class of point sets) are consistent with the axioms of ZFC. The completeness of the above diagram is established in § 8. In particular, we prove by constructing appropriate models that none of the implications in the diagram can be reversed. The ?nal section, § 9, contains a short survey of results on regularity properties that could not be presented with their proofs in a single paper for lack of space. We consider there the role of inaccessible cardinals in some consistency proofs, regularity properties for the third projective level, and some other related issues. § 1. Borel sets and projective sets This is an introductory section. We give de?nitions of the projective hierarchy of point sets in Baire spaces and of a ?ner e?ective hierarchy using the de?nability of point sets by analytic formulae, consider the sieve operation, and prove that problems on the regularity properties are independent of the choice of base space in the category of perfect Polish spaces, and that the measurability problem is independent of the choice of a measure in the category of Borel measures vanishing at points. The section ends with an exposition of encoding for Borel sets and countable ordinals which plays an important role in the proofs and in the understanding of the meaning of theorems.

    On some classical problems of descriptive set theory

    847

    1A. Real line, Polish spaces, and the Baire space. Descriptive set theory, which originated from the theory of functions at the beginning of the 20th century, developed for a long time mainly as a theory of point sets on the real line R and in the spaces Rn . However, it had already become clear by the mid-1920s that the principal results in this area could be generalized to any uncountable Polish space. (By a Polish space one means a complete separable metric space.) Hausdor?’s book [25] contained the ?rst systematic exposition of descriptive set theory for general Polish spaces. Somewhat later, Kuratowski [45] (see also his monograph [46], § 37.II) proved the following theorem, which showed that descriptive set theory has little dependence on the choice of an uncountable Polish space. Theorem 1.1 (Kuratowski). Any two uncountable Polish spaces X and Y are Borel onto isomorphic, that is, there exists a bijection F : X ?→ Y (a so-called Borel isomorphism) such that the F -images and the F -pre-images of Borel sets are again Borel sets. Thus, at least in the study of problems of descriptive set theory which are invariant (directly or modulo appropriate corrections) under Borel isomorphisms, one can restrict attention to point sets in a ?xed uncountable Polish space. For this space, descriptive set theory tends now to use the Baire space Nω .12 Our paper follows this practice. Concerning the forms taken by the problems of regularity properties in the case of Nω and arbitrary uncountable Polish spaces, see the next subsection. Let us now proceed to the technical details. Let 2<ω N<ω be the set of all ?nite sequences of the numbers 0, 1 and the set of all ?nite sequences of natural numbers, respectively. Let lh s be the length of s ∈ N<ω . If s ∈ N<ω and n ∈ N, then s ∧ n ∈ N<ω is the sequence obtained by adjoining n to s as the rightmost term. The notation s ? t means that the sequence t is a proper extension of s. The Baire space Nω (also denoted by N) is formed by all in?nite sequences of natural numbers. Its topology is generated by the Baire intervals, that is, the sets of the form Ns = {x ∈ Nω : s ? x}, s ∈ N<ω . We note that the spaces Nω and N(k, ) = Nk × N (k 1) are homeomorphic to Nω ; for example, the map onto Nω ?→ Nω , x → {(x)n }n∈N, where a point (x)n ∈ Nω is de?ned for x ∈ Nω and n ∈ N by the equality (x)n (k ) = x(2n (2k + 1) ? 1) for any k , is a homeomorphism. The closed subsets of Nω admit the following useful representation. A non-empty set T ? N<ω is called a tree if t ∈ T when s ∈ T , t ∈ N<ω , and t ? s. (It follows that the empty sequence Λ belongs to T .) The sets of the form [T ] = {x ∈ Nω : ? m (x m ∈ T )}, where T ? N<ω is a tree, are exactly the non-empty closed
    12 The reasons for preferring the space Nω (for example, to the real line R) are certain topological properties of Nω , in particular, its 0-dimensionality (see Comment 2 in [60], p. 725), but mainly the fact that the structure of Nω enables us to describe point sets and their properties by means of a simple language of analytic formulae (see subsection 1C). This enables one to greatly simplify the technical aspects of the exposition. At the same time, the space Nω is not much inferior to the real line in geometric clearness, because it is isomorphic to the Baire line, that is, to the set 1| 1| of all irrational numbers of R, by means of the known correspondence x → | x(0)+1 + | x(1)+1 +

    + · · · , x ∈ Nω , in terms of continued fractions, or using the more direct construction given in [4], Russian p. 155. The Baire line is considered in Luzin’s Le? cons [57], for instance.

    1| | x(2)+1

    848

    V. G. Kanovei and V. A. Lyubetskii

    subsets of Nω ; moreover, it su?ces to consider only trees T without ?-maximal elements. By a branching node of a tree T we mean any element s ∈ T such that s ∧ j ∈ T for at least two di?erent numbers j ∈ N. A tree T is said to be perfect if for every t ∈ T there exists a branching node s ∈ T with t ? s. The sets of the form [T ], where T ? N<ω is a perfect tree, are precisely the perfect subsets of Nω . One can view the Cantor discontinuum 2ω either as a closed compact subset of Nω or as an independent space equipped with topology generated by the Cantor intervals Cs = {x ∈ 2ω : s ? x}, s ∈ 2<ω . 1 1 The projective classes Σ1 n , Πn , and ?n (An , CAn , and Bn in the earlier system (k, ) of notation) for spaces of the form N are de?ned by induction on n as follows: consists of all open sets in spaces of the form N(k, ); Σ1 0 1 Πn consists of all complements of sets in Σ1 n; consists of all projections of sets in Π1 Σ1 n+1 n , where the projection of a set (k +1, ) ω ∧ P ?N is the set { x, k : ? y ∈ N ( x y, k ∈ P )}; 1 ?1 consists of all sets that belong to both Σ1 n n and Πn ; 1 1 1 Σ∞ denotes the class n Σn = n Πn of all projective sets.
    1 One can equivalently de?ne Σ1 n+1 as the class of all continuous images of the Πn sets belonging to the same space N(k, ). In such a form the de?nition of projective classes can be extended to every Polish space X with the following speci?cation of the initial inductive step: by de?nition, the class Σ1 1 consists of all continuous images of the Gδ sets in this space. (The class Π1 0 of all closed sets, which is used in the de?nition of N(k, ), is insu?cient in general because, for example, for σ-compact spaces (in particular, for R) all projections (and even the continuous images of closed sets) belong to the class of Fσ sets, which is a proper subclass of Σ1 1 .)

    1B. Principal regularity properties in Polish spaces. It is quite clear that the problems of a perfect kernel and the Baire property (see the Introduction) have an obvious and precise meaning for any topological space, whereas the measurability problem depends on the choice of a measure. To consider this issue in detail, we specify some notions relating to measures. By a Borel measure on a space X we mean any measure ? de?ned on the σalgebra of all Borel subsets of X such that ? is σ-additive and σ-?nite (that is, X is a countable union of Borel sets of ?nite measure) and satis?es the conditions ?(X) > 0 and ?({x}) = 0 for any point x ∈ X.13 A measure ? is said to be ?nite if the value ?(X) is ?nite and σ-?nite if X is a countable union of sets of ?nite measure. The Lebesgue extension of a measure ? on X, which will be denoted by the same symbol ?, is de?ned on the σ-algebra of all sets X ? X such that there exist Borel sets U , V with U ? X ? V and ?(V U ) = 0; the sets X of this kind are said to be ?-measurable , and we let ?(X ) = ?(U ) = ?(V ).
    last condition means that ? is continuous, a condition tacitly assumed throughout the paper for all Borel measures. It can readily be seen that this condition leads to no loss of generality in the treatment of problems considered here, at least in the class of σ-?nite measures.
    13 The

    On some classical problems of descriptive set theory

    849

    Since the projective classes are closed with respect to the operation of intersection with Borel sets, it follows that the measurability of all projective sets with respect to σ-?nite Borel measures is a consequence of their measurability with respect to ?nite Borel measures. Using this fact, we can reformulate the hypotheses PK, LM, and BP (see the Introduction) for any given Polish space X and any given projective class K as follows: PKX (K): every K-set X ? X has the perfect kernel property; LM? X (K): every K-set X ? X is measurable with respect to a given ?nite Borel measure ? on X; BPX (K): every K-set X ? X has the Baire property. Remark 1.2. For any ?xed projective class K each of these three statements does not depend on the choice of the uncountable Polish space X, nor, as far as LM is concerned, on the choice of the measure ? in the family of ?nite Borel measures. For measurability this fact follows immediately from Theorem 1.1 and Lemma 1.3 below, because every projective class is invariant under Borel isomorphisms. In the case of PK we can apply the fact that any uncountable Borel set in a Polish space contains a perfect subset. As for the Baire property, the desired result follows from another theorem claiming that if X is a perfect Polish space, then there exists a set Y ? X homeomorphic to Nω and such that X Y is a meagre set in X.14 Lemma 1.3. Suppose that ? and ν are ?nite Borel measures on Polish spaces X and Y, respectively, and K is a projective class. Then there are Borel sets X ? X onto of full ?-measure and Y ? Y of full ν -measure and a Borel bijection h : X ?→ Y ν taking ? to ν . Therefore, LM? X (K) ?? LMY (K). Proof. We can assume that ?(X) = ν (Y) = 1, and, by Remark 1.2, that X = Y = [0, 1] (a closed interval of the real line). Let us remove all intervals (a, b) of ?-measure zero from [0, 1]; we obtain a perfect set X ? [0, 1] satisfying ?(X ) = 1, and ?(I ∩ X ) > 0 whenever the interval I = (a, b) intersects X . Similarly, there is a perfect set Y ? [0, 1] such that ν (Y ) = 1 and ν (I ∩ Y ) > 0 whenever the open interval I intersects Y . Let f (x) = ?(X ∩ [0, x)) for any x ∈ X . One can readily see that f is an orderpreserving continuous map from X onto [0, 1]. Moreover, f takes the measure ? on X to the ordinary Lebesgue measure on [0, 1]. Finally, f is ‘almost’ one-to-one, in the sense that the equality f (x) = f (y) holds for x = y if and only if x and y are the endpoints of some maximal open interval disjoint from X . In other words, if one removes from X , say, all left endpoints of those intervals, then f becomes a bijection on the set X thus obtained, and we still have ?(X ) = 1. onto In the same way, beginning with ν , we construct a function g : Y ?→ [0, 1] onto and a set Y ? Y with ν (Y ) = 1. Then h(x) = g?1 (f (x)) : X ?→ Y is a
    prove this claim, we note that if ? = U ? X is an open set, then for any ε > 0 there exist countably many pairwise disjoint non-empty neighbourhoods U ? U of diameter < ε with union dense in U such that the closure of each U is contained in U . This enables us to de?ne a system {Us }s∈N<ω of neighbourhoods such that UΛ = X, the diameter of Us does not exceed (lh s)?1 for lh s 1, the closure of Us ∧ n is included in Us , and n Us ∧ n is a dense subset of Us for any s. The set Y = n n=lh s Us = a∈Nω n Ua n is homeomorphic to Nω under the map sending each point a ∈ Nω to a unique point of the intersection n Ua n .
    14 To

    850

    V. G. Kanovei and V. A. Lyubetskii

    Borel isomorphism taking ? to ν . This proves the lemma, because Borel bijections preserve the projective class. It follows that, without any loss of generality, our hypotheses can be considered just for point sets in a ?xed uncountable Polish space X and, concerning measurability, just for a single ?nite Borel measure on X. It is convenient to take for X the Baire space Nω for PK and BP, and the Cantor space 2ω equipped with the probability measure λ assigning the value λ(Cs ) = 2? lh s to any Cantor interval Cs , s ∈ 2<ω , for the problem LM.15 However, the measure λ can be formally extended to the entire space Nω by the condition λ(Nω 2ω ) = 0, that is, λ(X ) = λ(X ∩ 2ω ) λ for any X ? Nω . Then the assertion LMλ Nω (K) is equivalent to LM2ω (K) for any projective class K. These arguments reduce the hypotheses of a perfect kernel, measurability, and the Baire property to the following ?nal forms, which are equivalent to the original formulations (for the real line) given in the Introduction: PK(K): every K-set X ? Nω has the perfect kernel property; LM(K): every K-set X ? 2ω (equivalently, every K-set X ? Nω ) is λ-measurable; BP(K): every K-set X ? Nω has the Baire property. The next theorem sums up several classical results.
    1 1 1 Theorem 1.4. The assertions PK(Σ1 1 ), LM(Σ1 ), BP(Σ1 ) hold, that is, every Σ1 ω set X ? N has the perfect kernel property, is λ measurable, and has the Baire property. The results for LM and BP are equally true for the class Π1 1.

    Proof. The claims relating to measurability and the Baire property are established in a more general form below (Theorem 3.7). Thus, we dwell on PK. It is known ω ω that all Σ1 1 sets in N are continuous images of closed subsets of N . Suppose that ω ω X = F ”P , where P ? N is closed and F : P → N is a continuous function. We say that a Baire interval U ? Nω is ‘good’ if the F -image F ”(U ∩ P ) is uncountable. For example, the interval Nω itself is ‘good’ because X is uncountable. Moreover, if U is a ‘good’ set, then there exist ‘good’ sets U1 , U2 ? U of diameter not exceeding half the diameter of U and such that F ”(U1 ∩ P ) is disjoint from F ”(U2 ∩ P ); in particular, the sets U1 and U2 themselves are disjoint. This enables us to de?ne a split system {Us }s∈2<ω of ‘good’ sets Us ? U such that (1) Us ∧ i ? Us and the diameter of Us ∧ i is at most half the diameter of Us ; (2) F ”(Us ∧ 0 ∩ P ) is disjoint from F ”(Us ∧ 1 ∩ P ). The set C = m m=lh s Us ? P is perfect and compact and F is a bijection on C , and hence Y = F ”C is a perfect subset of X . 1C. Projective hierarchy and the language of analytic formulae. The structure of the Baire space N = Nω enables one to use a simple language to describe sets in spaces of the form N(k, ). This language has two types of variables,
    preference given to 2ω (rather than Nω ) is primarily explained by the compactness of which is useful in some arguments, and by the non-existence of a Borel measure on Nω taking equal values at all Baire intervals of equal rank. We note in addition that the map sending each ∞ ?n?1 takes the measure λ to the ordinary point a ∈ 2ω to the real number ra = n=0 a(n)2 Lebesgue measure on [0, 1].
    15 The

    2ω ,

    On some classical problems of descriptive set theory

    851

    namely, type 0 with domain N (here one uses letters k , l, m, n, and so on) and type 1 with domain Nω (here one uses letters x, y, z , a, b, c, and so on). One is allowed to form terms by using substitutions of a term or a variable of type 0 into a variable of type 1 and by using recursive (that is, computable) functions from N to N; for instance, x(2k + y(3n)) is a term. Terms are obviously objects of type 0. The following classes of formulae of this language are distinguished: – elementary formulae, which are of the form t = t , t < t , t t , where t and t are terms (for example, variables of type 0); – analytic formulae, that is, formulae obtained from elementary formulae by means of propositional connectives and quanti?ers; – arithmetic formulae, that is, analytic formulae which do not include quanti?ers of type 1 (over Nω ); – bounded formulae, that is, arithmetic formulae which include quanti?ers only of the form ? k < t and ? k < t, where k is a variable of type 0 and t is a term (in particular, all quanti?er-free formulae are bounded); 0 0 – Σn and Πn , that is, arithmetic formulae of the respective forms ? k1 ? k2 ? k3 . . . ? (?) kn ? and ? k1 ? k2 ? k3 . . . ? (?) kn ?,

    where ? is a bounded formula; 1 1 and Πn , that is, analytic formulae of the respective forms – Σn ? x1 ? x2 ? x3 . . . ? (?) xn ? and ? x1 ? x2 ? x3 . . . ? (?) xn ? ,

    where ? is an arithmetic formula. E?ective hierarchy. The free variables of analytic formulae can be replaced by particular elements of N (type 0) or Nω (type 1), which are called parameters in this case. (Such a replacement is essential only for type 1, since any natural number is de?nable by a quanti?er-free formula.) This yields a classi?cation of point sets from the point of view of the parameters entering the de?nition rather than just from the point of view of the de?ning formula. i For a given ‘vector’ a = a1 , . . . , aj ∈ (Nω )j we denote by Σn (a) the class (k, ) i that are de?nable by Σn -formulae of all point sets in spaces of the form N i with parameters from the list a1 , . . . , aj . The class Πn (a) is de?ned similarly, i i and we write ?i n (a) = Σn (a) ∩ Πn (a). In the special cases j = 1 and j = 0 i i we write Σn (a) and Σn and do the same for Π and ? . In addition, we de?ne i i i Σn (P ) = a1 ,...,aj ∈P ∩Nω Σn (a1 , . . . , aj ) for any set P and we de?ne Πn (P ) and ω i ( P ) similarly. If a set P ∩ N is recursively closed, then Σ ( P ) coincides with ?i n n i Σ ( a ), and a similar assertion holds for Π and ? . n a∈P ∩Nω The classes whose notation includes the letters Σ , Π , and ? are said to be e?ec1 1 tive, in contrast to the projective classes Σ1 n , Πn , and ?n . However, the projective hierarchy is only a particular case of the e?ective hierarchy.
    i ω i i Proposition 1.5. Σi n = Σn (N ), that is, X ∈ Σn if and only if X ∈ Σn (a) for ω some a ∈ N , and similar assertions hold for Π and ?. 0 Proof. All sets de?nable by Σ1 formulae in the spaces of the form N(k, ) are obvi0 ω ω ously open, and hence Σ1 (N ) ? Σ0 1 . Conversely, if X is open, say, in N , then

    852

    V. G. Kanovei and V. A. Lyubetskii

    0 X = n Nsn , where sn ∈ N<ω , and hence X is de?nable by the Σ1 formula ? n n ? m < a(n) (x(m) = b(2 (2m + 1) ? 1)) (with the parameters a and b), where a(n) = lh sn (the length of a ?nite sequence sn ), and b(2n (2m + 1) ? 1) is equal to 0 sn (m) for m < lh sn and to 0 for m lh sn . Thus, Σ1 (Nω ) = Σ0 1 . This implies the desired result for closed sets, for Fσ , and for Gδ , as well as the fact that arithmetic formulae (with parameters) de?ne Borel sets of ?nite rank. Concerning projective classes, the quanti?er ? x (according to our conventions, ? x ∈ Nω ) corresponds to a projection, whereas the quanti?er ? x corresponds to the combination complement– projection–complement.

    (?0 ?0 ) (? ? )
    0 1 1 0 1 1

    ? i ? j ?(i, j ) ?? ? n ?((n)1 , (n)2 ) ? i ? j ?(i, j ) ?? ? n ?((n)1 , (n)2 ) ? x ? y ?(x, y) ?? ? z ?((z )1 , (z )2 ) ? x ? y ?(x, y) ?? ? z ?((z )1 , (z )2 ) ? i ? j ?(i, j ) ?? ? x ? i ?(i, x(i)) ? i ? j ?(i, j ) ?? ? x ? i ?(i, x(i)) ? x ? j ?(x, j ) ?? ? y ?((y)0 , (y)1 (0)) ? x ? j ?(x, j ) ?? ? y ?((y)0 , (y)1 (0)) ? i ? x ?(i, x) ?? ? x ? i ?(i, (x)i ) ? i ? x ?(i, x) ?? ? x ? i ?(i, (x)i )

    (? ? ) (? ? ) (?0 ?0 ) (? ? )
    0 1 1 0 0 0 0 0 1 1

    (? ? ) (? ? ) (? ? ) (? ? )

    Table. The map i, j → 2i (2j + 1) ? 1 is a bijection of N2 onto N; (n)1 and (n)2 denote the inverse functions, that is, (n)1 = i and (n)2 = j whenever 2i (2j +1) ? 1= n. If z ∈ Nω and n ∈ N, then (z )n ∈ Nω is de?ned in subsection 1A.

    Transformation of analytic formulae. Equivalences in the table enable one to reduce complicated analytic formulae, by simplifying the quanti?er pre?x, to a form which permits one to directly evaluate the type of the set de?ned by the formula. We note that the next-to-last equivalence (?0 ?1 ) expresses the countable axiom of choice, and (?0 ?1 ) expresses the dual statement. 1 As an elementary example, we note that, if ?(x, y, i, j ) is a Σn formula and n 1, then, say, the formulae ? x ?(x, y, i, j ), ? i ?(x, y, i, j ), and ? i ?(x, y, i, j ) 1 belong to the same type, in the sense that they can be converted to a Σn form (with 1 1 1 0 0 1 the same parameters) by using the rules (? ? ), (? ? ), and (? ? ). 1D. Elements of the theory of Π1 1 sets. We recall that by a sieve over a space X one means any set R ? X × Q (where Q is the set of all rational numbers) or, equivalently, a system {Rq }q∈Q of sets Rq = {x ∈ X : x, q ∈ R} ? X, which are called the elements of the sieve R. In this case we assign to any point x ∈ X the set R(x) = {q : x ∈ Rq } ? Q. This leads to the following partition of the space X into two sets: E (R) = {x : R(x) is well ordered}, E(R) = {x : R
    (x)

    the so-called outer set,

    is not well ordered}, the so-called inner set

    On some classical problems of descriptive set theory

    853

    (the well ordering is understood in the sense of the natural order of the rational numbers). Each of these sets admits a further partition into constituents, Eξ (R) = {x ∈ E : otp R(x) = ξ } and Eξ (R) = {x ∈ E : otp MIS(R(x) ) = ξ }

    (ξ < ω1 ), where otp S is the order type of a set S ? Q (if S is well ordered), and MIS(S ) is the largest well-ordered initial segment of S . onto We ?x once and for all a recursive bijection n → qn : N ?→ Q; let q → nq be the ω inverse bijection. This induces a homeomorphism of N × Q onto Nω × N, which enables us to classify sieves in terms of the projective hierarchy, so that a sieve of class K over X = N(k, ) is any set R ? X × Q of class K . For Borel and projective i i classes K = Σi n , Πn , and ?n this is equivalent to the condition that every element Rq of the sieve R belongs to K. Theorem 1.6 (the sifting theorem). Suppose that X = N(k, ). (a) If R ? X × Q is a Borel sieve, then the set E (R) belongs to Π1 1 , and all the constituents Eξ (R) and Eξ (R) are Borel sets. Conversely, for any Π1 1 set X ? X ( that is , with open closed elements ) such there is a sieve R ? X × Q of class ?0 1 that X = E (R). (b) (e?ective version of the theorem) If a ∈ Nω and R ? X × Q is a sieve of 1 1 the class ?1 1 (a), then E (R) is a Π1 (a) set. Conversely, for any Π1 (a) set X ? X 0 there is a ?1 (a) sieve R ? X × Q such that X = E (R). Proof. For any sieve R ? Nω × Q we have x ∈ E (R) ?? ? f : N → Q f monotone decreasing =? ? n ( x, f (n) ∈ / R) .
    1 (a), then the right-hand side can readily be reduced Thus, if R is a sieve of class Σ1 1 to the Π1 form with a as a parameter by means of transformations in the table in subsection 1C (and the recursive bijection n → qn introduced above to replace Q by N). 1 To prove the converse, consider a Π1 (a) set X = {x ∈ Nω : ? y ?(x, y, a)}, where ? is an arithmetic formula of the form Π ψ(x, y, a, . . . ) for some block (pre?x) Π of quanti?ers of the form ? n, ? n (of type 0), and ψ is a bounded formula. For example, let ? be ? i ? j ? k ψ(x, y, a, i, j, k). The rule (?0 ?1 ) of the table in subsection 1C reduces this de?nition to the form ? z ? i ? k ψ(x, y, a, i, z (i), k ), and other rules of the table reduce the de?nition of X to the form X = {x ∈ Nω : ? y ? m Φ(x, y, a, m)}, where Φ is a bounded formula. Since Φ is bounded, the determination of the truth of Φ(x, y, a, m) can be represented as a computation by a computer program (depending only on the structure of Φ and not on the values of x, y, a, m), where x, y, a are loaded as in?nite strings of numerical values x(n), y(n), a(n), n ∈ N, and the result is obtained after ?nitely many steps. If s ∈ N<ω , then we write s ∧ 0 ∈ Nω for the extension of s by zeros. Let

    S xa = the set of all s ∈ N<ω such that if the computation of Φ(x, s ∧ 0, a, m) for every m < lh s is carried out without using the values (s ∧ 0)(k ), k lh s, then the result of the computation is ‘false’ (that is, ? Φ(x, s ∧ 0, a, m)).

    854

    V. G. Kanovei and V. A. Lyubetskii

    For any s, t ∈ N<ω we set s <LS t if either t ? s or s < t lexicographically (the Luzin–Sierpi? nski order). One can readily see that x ∈ X ?? S xa has no in?nite branches ?? S xa is well ordered in the sense of <LS . However, the ordering <LS is countable and dense in itself; it admits a maximal onto element and has no minimal element. Fix a recursive bijection f : N<ω ?→ Q 1 = {q ∈ Q : q 1} which is order preserving, that is, s <LS t ?? f (s) < f (t). According to what was proved above, the sieve R = { x, f (s) : s ∈ S xa } satis?es the condition X = E (R). It remains to note that R is a sieve of class ?0 1 (a); indeed, the right-hand side of the de?nition of S xa , viewed as a formula with the 0 variables x and s, can be reduced both to the Σ1 (a) form (with the external quan0 ti?er “there is a computation”) and to the Π1 (a) form (“for any computation”). The Borel property of the constituents is a classical result. Corollary 1.7. Every Σ1 2 set is a union of ?1 Borel sets. Proof. By the sifting theorem, every Π1 1 set is a union of ?1 Borel sets, and therefore every Σ1 set is a union of ? projections of Borel sets, that is, of ?1 sets of 1 2 class Σ1 . However, any set of the last type is again a union of ?1 Borel sets by 1 Theorem 1.6. Theorem 1.8. Suppose that R is a Borel sieve over a space N(k, ). (i) If a Σ1 1 set A is included in E (R), then there is an ordinal ? < ω1 such that A ? ξ<? Eξ (R). (ii) The set E (R) is Borel if and only if there is an ordinal ? < ω1 such that Eξ (R) = ? for any ξ > ?. (iii) The class ?1 1 coincides with the class of all Borel sets. Uniformization. Let X and Y be arbitrary spaces. If P ? X × Y, then one often writes P (x, y) instead of x, y ∈ P . We recall that the set dom P = {x : ? y P (x, y)} ? X is called the projection of P (on X). A set P ? X × Y is said to be uniform if and only if for any x ∈ X there is at most one y ∈ Y such that P (x, y). In fact, this means that P is the graph of a partial function X → Y. If P ? Q ? X × Y, P is uniform, and dom P = dom Q, then one says that P uniformizes Q. Theorem 1.9 (Novikov–Kond? o–Addison, [62], [43], or [86], § 7.11). Every set P ? Nω × Nω of class Π1 can be uniformized by a set of the same class. Every set 1 1 P ? Nω × Nω of class Π1 (a) (a ∈ Nω ) can be uniformized by a set of the same class. 1E. Digression: encoding by points of the Baire space. Elements of the space Nω can be used to encode mathematical objects of very di?erent nature provided that, informally speaking, these objects contain only countably many ‘bits’ of information.

    On some classical problems of descriptive set theory

    855

    Example 1.10.1 (encoding of countable ordinals). We recall that q → nq is a bijection of Q onto N. By WO we denote the set of all w ∈ Nω such that Qw = {q ∈ Q : w(nq ) = 0} is well ordered by the order of Q. In this case let |w| = otp Qw be the order type of Qw ; this means that |w| < ω1 . We set WOγ = {w ∈ WO : |w| = γ }. This useful encoding of countable ordinals admits a simple interpretation in terms of sieves. We write Lq = {x ∈ Nω : x(nq ) = 0}. This de?nes the Lebesgue 1 set E (L) obviously coincides with binary sieve L = {Lq }q∈Q . In this case the Π1 WO, and WOγ = Eγ (L) for any γ < ω1 . Suppose that w ∈ WO and k ∈ N, w(k ) = 0. We de?ne w k ∈ WO as follows: w k (n) = 0 for w(n) = 0 and qn < qk , and w k (n) = 1 otherwise. It is clear that {ξ : ξ < |w|} = {|w k | : w(k ) = 0}. Example 1.10.2 (encoding of Borel sets). Let us ?x, once and for all, a recursive enumeration without repetition, N<ω = {sk : k ∈ N}. We set BC0 = {k : k ∈ N}, where k ∈ Nω is a constant function (that is, k(i) = k for all i). For k ∈ BC0 we write Bk = Nsk?1 (a Baire interval in Nω ; see subsection 1A) for k 1 and Bk = ? for k = 0. If ξ > 0, then we de?ne BCξ as the family of all points c ∈ Nω η<ξ BCη such that {(c)n : n ∈ N} ? η<ξ BCη , B for any c of this kind. (For the de?nition of (c)n , and we let Bc = Nω n (c)n see subsection 1A.) This introduces the set BC = ξ<ω1 BCξ ? Nω of Borel codes and a Borel set Bc ? Nω for each code c ∈ BC.16 Remark 1.10.3. The construction of BC and Bc admits another approach. We set (c)s = (. . . ((c)s(0))s(1) . . . )s(n?1) for any c ∈ Nω , s ∈ N<ω , n = lh s (and, separately, (c)Λ = c for the empty sequence Λ). One can readily see that Tc = {s ∈ N<ω : ? n < lh s ((c)s
    n

    is not a constant)}

    is a tree in N<ω , and we have c ∈ BC if and only if Tc is a well-founded tree, that is, Tc has no in?nite branches. Moreover, s ∈ Tc is a maximal element of Tc if and only if (c)s is a constant function. Further, if c ∈ BC, then we can de?ne a Borel set Bc (s) ? Nω for each sequence s ∈ Tc as follows: Bc (s) = Nsk?1 for (c)s = k (the constant k ) and k 1, Bc (s) = ? for (c)s = k and k = 0, and ∧ Bc (s) = Nω B ( s n ) if ( c ) is not a constant, that is, if s is not a maximal c s n element of Tc . This easily implies that Bc (Λ) = Bc and, in general, Bc (s) = B(c)s for any s ∈ Tc . When de?ning an encoding of some mathematical structures by objects of simpler type, the most interesting question is as follows: what are the properties of relations on encoding objects that correspond to the main relations among the encoded structures themselves? In this case the most important question is the de?nability of the relations thus induced. The following proposition contains the most interesting results in this direction.
    encoding uses the operation of complementing countable unions. In terms of this operation one can easily express the complement itself, and hence the operations of countable union and countable intersection as well. (For the code of the complement of Bc one can take c ∈ Nω de?ned by (c )n = c ? n.) Thus, every Borel set X ? Nω has the form Bc for a suitable c ∈ BC.
    16 This

    856

    V. G. Kanovei and V. A. Lyubetskii

    Proposition 1.11. 1 (i) The sets WO and BC belong to Π1 ; more precisely, each of them is de?n1 able in ZFC by an explicitly given Π1 formula. 1 1 (ii) There exist a Σ1 formula σ( · , · ) and a Π1 formula π ( · , · ) such that |w| |z | ?? σ(w, z ) ?? π (w, z ) for any w, z ∈ WO. The same holds for < and =. ω 1 (iii) If R is a sieve of class ?1 1 (a), a ∈ N , then there exist Σ1 (a) formulae 1 σ( · , · ) and σ ( · , · ) (that is, Σ1 formulae with the single parameter a) and 1 Π1 (a) formulae π ( · , · ) and π ( · , · ) such that x ∈ E|w| (R) ?? σ(w, x) ?? π (w, x), x ∈ E|w| (R) ?? σ (w, x) ?? π (w, x), for any w ∈ WO and x ∈ Nω . 1 1 (iv) There exist a Σ1 formula σ( · , · ) and a Π1 formula π ( · , · ) such that x ∈ Bc ?? σ(c, x) ?? π (c, x) for any c ∈ BC and x ∈ Nω . 1 1 formula ?λ ( · , · , · ) and a Π1 formula ψλ ( · , · , · ) such (v) There exist a Σ1 that λ(Bc ) = m/n ?? ?λ (c, m, n) ?? ψλ (c, m, n) for any c ∈ BC and m, n ∈ N. (The measure λ on Nω was introduced in subsection 1B.) 1 1 (vi) There exist a Σ1 formula ?cat ( · , · ) and a Π1 formula ψcat( · , · ) such that Bc ∩ Nsk is meagre ?? ?cat(c, k ) ?? ψcat(c, k ) for any c ∈ BC and k ∈ N. ({sk }k ∈N is a ?xed recursive enumeration of N<ω .) Proof. (i) The relation w ∈ WO is equivalent to the non-existence of an in?nite decreasing chain of elements of Qw (in the notation of Example 1.10.1), which is 1 expressible by a Π1 formula. Further, c ∈ BC is equivalent to the condition that ω for any a ∈ N there is an n for which (s)a n ∈ / Tc (in terms of Remark 1.10.3). (ii) If w, z ∈ WO, then the condition |w| |z | is equivalent to the existence of an order isomorphism of the set Qw onto an initial segment of Qz and to the non-existence of an order isomorphism of Qz onto a proper initial segment of Qw . Order isomorphisms of this kind do not belong to Nω , but they can readily be encoded by points of Nω . (iii) The relation x ∈ E|w|(R) is equivalent to the existence of an order isomorphism between the sets Qw and R(x) and to the non-existence of an order isomorphism between Qw and a proper initial segment of R(x) , or vice versa. This yields the desired formulae σ and π . The formulae for E|w| (R) can be obtained by using similar simple considerations. (iv) If c, x ∈ Nω , then by a c, x-function we mean any function f : N<ω → {0, 1} such that for every s ∈ N<ω if (c)s is a constant function k for some k , then f (s) = 1 ?? x ∈ Nsk?1 for k 1, f (s) = 0 for k = 0, and if (c)s is not constant, then f (s) = 1 ?? ? m (f (s ∧ m) = 0). Clearly, for any c ∈ BC there is a unique c, x-function f = fcx , and the relation x ∈ Bc is equivalent to fcx (Λ) = 1. It follows that x ∈ Bc is equivalent (for c ∈ BC) to the existence of a c, x-function f with f (Λ) = 1 and to the non-existence of a c, x-function f with f (Λ) = 0. (v) By a λ-approximation of a set X ? Nω we mean a pair U, V of Fσ sets such that U ? X , V ∩ X = ?, and λ(U ∪ V ) = 1. Clearly, λ(U ) = λ(X ) in this case. We note that if pairs Un , Vn are λ-approximations of sets Xn , then the

    On some classical problems of descriptive set theory

    857

    natural idea of considering the pair V = n Vn , U = n Un as a λ-approximation of the set X = Nω n Xn does not work, because V need not be an Fσ set. However, this construction can be modi?ed as follows. Suppose that Vn = k Vnk ? n, where all the Vnk are closed. For any given j we choose in each Vn a closed subset Vnj = k<k (n,j ) Vnk ? Vn such that Vnj ? Vn,j +1 and λ(Vn Vnj ) 2?(n+j ). ?(n+j ) Then Vj = n Vnj is a closed subset of V with λ(V Vj ) = 2?j +1 . n2 Hence, V = j Vj is an Fσ set, V ? V , and λ(V V ) = 0. Thus, the pair V , U is a λ-approximation of X . Let Φ(V , U, {Unk }n,k ∈N, {Vnk }n,k ∈N) be a formula expressing the fact that an Fσ set V is constructed from the closed sets Vnk in the way described above and that U = n,k ∈N Unk . Let us now use this approach to construct the formulae ?λ and ψλ . Here we need a separate encoding of Fσ sets. We write F [z ] = Nω (z )n (k )=1 Nsk and Fσ [z ] = n F [(z )n ] for each z ∈ Nω . By an approximation code for c ∈ Nω we mean any pair of maps γ, δ : N<ω → Nω satisfying the following conditions: 1, then, ?rst, (γ (s))n (j ) = 1 (1) if s ∈ Nω is such that (c)s = k and k for all n and j such that Nj ∩ Nk ?1 = ?, whereas (δ (s))n (j ) = 0 for Nj ∩ Nk ?1 = ?, in which case we clearly have Fσ [δ (s)] = Nsk?1 = Bc (s), and, second, (δ (s))n (k ? 1) = 1 and (δ (s))n (k ) = 0 for k = k ? 1, in which case Fσ [δ (s)] = Nω Nsk?1 ; (2) if s ∈ Nω , (c)s = k, and k = 0, then (γ (s))n (j ) = 1 ? j , in which case we have Fσ [γ (s)] = ? = Bc (s), and (δ (s))n (j ) = 0 ? j , in which case Fσ [δ (s)] = Nω ; (3) if (c)s is non-constant, then Φ(V , U, {Unk }n,k ∈N, {Vnk }n,k ∈N), where V = Fσ [γ (s)], U = Fσ [δ (s)], Unk = F [(γ (s ∧ n))k ], and Vnk = F [(δ (s ∧ n))k ]. Clearly, approximation codes γ, δ do exist for any Borel code c ∈ BC, and for each of these codes and each s ∈ Tc the pair Fσ [γ (s)], Fσ [δ (s)] is a λ-approximation of the set Bc (s), in particular, Fσ [γ (Λ)], Fσ [δ (Λ)] is a λ-approximation of the set Bc (Λ) = Bc . Thus, the formulae ?λ (c, m, n) := ? γ, δ ( γ, δ is an approximation code for c ∧ λ(Fσ [γ (Λ)]) = m/n), ψλ (c, m, n) := ? γ, δ ( γ, δ is an approximation code for c =? λ(Fσ [γ (Λ)]) = m/n), satisfy the equivalences (v). On the other hand, it is easy to verify (though the veri?cation is a rather lengthy procedure which we omit) that the subformulae within the outer parentheses in both formulae are arithmetic, and hence have the desired type. (vi) We can apply the same construction; however, by an approximation of a given set X ? Nω we mean here a pair of the form U, F , where U ? Nω is open, F is a meagre Fσ set, and X U ? F . ( stands for the symmetric di?erence.) The main technical point is to construct an approximation of a set X = Nω n Xn from given approximations of the Borel sets Xn , but this problem can be solved without di?culty. Historical and bibliographical remarks. The sets of class Σ1 1 (on the real line) were introduced by Suslin [91] under the name ensembles (A). They were also known

    858

    V. G. Kanovei and V. A. Lyubetskii

    as analytic sets, Suslin sets, and A sets. Their prehistory can be traced back to the note [3] of Aleksandrov, and even to the memoir [47] of Lebesgue, where there is a construction (which was called later the Lebesgue binary sieve; see Example 1.10.1) implicitly providing an example of an non-Borel Π1 1 set (for this topic, see [48].) The history of the discovery of the operation A and A sets has been a subject of special studies; the reader can ?nd facts, comments, and further references concerning this topic, for example, in [95], [50]. The perfect kernel property for Σ1 1 sets (Theorem 1.4) is usually associated in the literature with the names of Aleksandrov, Hausdor?, and Suslin (though there is no theorem of this kind in the corresponding papers [3], [23], [91]). The result ?rst appeared in [51] with a reference to Suslin (without indicating a speci?c publication). (For more details, see [97], § 3.3.) The theorems concerning measurability and the Baire property for Σ1 1 sets also ?rst appeared in [51]. The notion of sieve was introduced by Luzin in [55]; however, it ?rst appeared in the context of a proof in [63] (and in [61] in a somewhat di?erent form, in connection with the operation A). The systematic application of this notion in the theory of Σ1 1 and Π1 cons [57]. Theorem 1.8 1 sets, including Theorems 1.6 and 1.8, was given in Le? was proved in the classical works [5], [46], [57] (for a more modern exposition, see [35]). The assertion (iii) (Suslin’s theorem) follows from (ii). The uniformization theorem, Theorem 1.9, actually claimed in its initial form [62] that any Π1 1 set can 1 be uniformized by a Σ1 set. The improvement to Π is due to Kond? o [43], and the 2 1 1 result for classes of the form Π1 (a) to Addison [1], [2]. Projective sets were introduced by Luzin [52] as Lebesgue projective sets, though the reference to Lebesgue is not well grounded, as mentioned in [97], § 3.1. The systematic use of analytic formulae to study projective point sets (instead of the geometric constructions typical for the style of Luzin and Novikov) was started by Addison [1], [2]. The encoding of Borel sets was used by Solovay [89] to solve the measurability problem for projective sets, but the roots of this encoding (and of the encoding of countable ordinals) can be traced back to earlier studies in recursion theory (see, for instance, [86], 7.9). The results in (v) and (vi) of Proposition 1.11 go back to work in the late 1960s concerning projective sets ‘with large sections’ (see the references in [41]). The standard modern reference on classical descriptive set theory (that is, without forcing, constructibility, and the e?ective hierarchy) is Kechris’ book [42]. Among earlier sources available in Russian, we note the survey paper [5], related chapters in the Topology [46] of Kuratowski, and also [35] and Chapter 8 in [11]. Problems of classical descriptive set theory are discussed in the surveys [38], [40], and [97]. § 2. G¨ odel’s constructibility Classical descriptive set theory came to a halt at the questions of whether or not all Π1 1 sets satisfy the perfect kernel property, whether or not all sets of the second projective level are measurable, and whether or not all of them have the Baire property. The subsequent study of these problems became possible only after the development of the appropriate methods of mathematical logic, such as constructibility and forcing. On the other hand, these tools were developed mainly as tools aimed at solving classical problems concerning point sets.

    On some classical problems of descriptive set theory

    859

    This section presents investigations of the aspects of constructibility that are essential in the study of regularity properties of projective sets. 2A. Set-theoretic universe. A speci?c feature of G¨ odel’s constructibility theory is that its constructions and arguments, in their most general and natural form, do not con?ne themselves to the purely topological structure of point sets. On the contrary, they appeal to the structure of the set-theoretic universe as a whole and even to the relationships between di?erent universes, for instance, those obtained by forcing. Ordinals and ranks. Ordinals, or (?nite and trans?nite) ordinal numbers, play a special role in the structure of the set-theoretic universe. We assume that the reader is somewhat acquainted with these notions and recall only that in modern set theory every ordinal ξ is identi?ed with the set of smaller ordinals, in other words, ξ = {α : α < ξ }. In particular, 0 = ?, 1 = {0}, 2 = {0, 1}, . . . , ω = N = {0, 1, 2, . . . }, ω + 1 = ω ∪ {ω}. The class of all ordinals is denoted by Ord. The cardinals are initial ordinals, that is, those not of cardinality equal to that of any smaller ordinal. For instance, ω = N = ?0 is the smallest in?nite ordinal, and ω1 = ?1 is the smallest uncountable ordinal and the ?rst uncountable cardinal.17 We recall that rk x ∈ Ord denotes the set-theoretic rank of x, de?ned by rk x = supy∈x rk y, where sup X stands for the smallest ordinal strictly bigger than all ordinals in X . (For instance, rk ? = 0.) This yields the von Neumann hierarchy, which consists of all sets of the form Vξ = {x : rk x < ξ }, ξ ∈ Ord; the universe V of all sets coincides with ξ∈Ord Vξ . Models of ZFC axioms. We assume that the reader is somewhat acquainted with the Zermelo–Fraenkel set theory ZFC, and we do not dwell on the presentation of its axioms (see [11], Chap. 1). As usual, by a model of ZFC one means any structure of the form M; ε , where M is any set equipped with a binary relation ε such that the axioms of ZFC hold in the structure (provided that the membership sign is interpreted as ε). One distinguishes standard transitive models, in which case M is a transitive set (that is, x ∈ y ∈ M implies that x ∈ M) and ε is simply the restriction of the ‘true’ membership ∈ to M. It follows from the G¨ odel incompleteness theorem that the existence of at least one model of ZFC of any kind cannot be proved in ZFC. On the other hand, there exist structures of the form M; ε satisfying all axioms of ZFC for which M is a true class rather than a set. The most elementary example is given by V; ∈ , where V is the universe of all sets. Such structures are not models in the rigorous sense,18 because their domains are not sets. Therefore, G¨ odel’s theorem cannot be applied to these structures. However, they are quite useful in many applications. In particular, the existence of a model of ZFC (even in this improper sense) in which a proposition Φ holds means that Φ does not contradict the axioms of ZFC.
    17 It is customary to use the notation ? , ? , or in general ? , ξ ∈ Ord, if only cardinal 0 1 ξ characteristics are important, and the notation ω, ω1 , or in general ωξ , if ordinal characteristics of the cardinal and its connection with other ordinals are important. 18 Sometimes they are informally called models, for instance, the class L is called the constructible model. The notion of interpretation is a more exact term for structures whose domains are true classes. See [86], 4.7 and 9.5 for details; in the present case we mean an interpretation of ZFC theory in itself.

    860

    V. G. Kanovei and V. A. Lyubetskii

    In particular, this category of structures contains the class L of all constructible sets and its extensions obtained by forcing. Hereditarily countable sets. It is sometimes useful to consider models of weaker theories, in particular, of ZFC? , that is, ZFC without the power set axiom. A natural model of ZFC? is the set HC of all hereditarily countable sets, that is, of all sets x such that the transitive closure TC(x) is at most countable. (TC(x) is the smallest transitive set containing x.) In particular, all natural numbers and sets of natural numbers, all elements and countable subsets of Nω , and all countable ordinals belong to HC. On the other hand, it is clear that P(N) ∈ / HC, and hence the power set axiom fails in HC. It is an easy exercise to show that the other axioms of ZFC hold in HC (or, more precisely, in the structure HC; ∈ ). The Skolem–L¨ owenheim theorem yields a variety of countable models of ZFC? . Proposition 2.1. If X ? HC is a countable set, then there is a countable transitive set M ∈ HC such that X ? M and M is a model of ZFC? . 2B. General notion of G¨ odel’s constructibility. Among all possible sets, one can obviously distinguish sets that admit a simple de?nition or an explicit construction by means of simple operations; let us say that these sets are ‘constructible’. This is an intuitive notion; it depends both on the choice of admissible tools of de?nition or construction and on the choice of the initial sets to which the de?nitions or constructions can be applied. Fortunately, it turns out that all reasonable versions of constructibility can be reduced to a very few really di?erent concepts. The de?nition of G¨ odel constructibility is the most known and most useful. The de?nition of constructible sets is known in several versions giving, however, the same result. The most convenient version for our purposes is that of [20], which is directly based on the eight G¨ odel operations (presented here in the form given in [29]): F1 (X, Y ) = {X, Y }, F2 (X, Y ) = X Y, F3 (X, Y ) = X × Y, F4 (X, Y ) = {x : ? y ( x, y ∈ X )}, F6 (X, Y ) = { x, y, z : y, z, x ∈ X }, F5 (X, Y ) = { x, y ∈ X : x ∈ y}, F7 (X, Y ) = { x, y, z : z, y, x ∈ X },

    F8 (X, Y ) = { x, y, z : x, z, y ∈ X }. De?nition 2.2 (constructible sets). We de?ne a well ordering of the class T = {0, 1, . . . , 8} × Ord × Ord as follows: i, ξ, η i , ξ , η if max{ξ, η } < max{ξ , η }, if max{ξ, η } = max{ξ , η } and ξ, η < ξ , η lexicographically, or if ξ = ξ , η = η , onto and i < i . There is a unique order isomorphism K : T ; ?→ Ord {0}. Let K0 , K1 , K2 be the inverse functions, that is, if K (i, ξ, η) = γ , then K0 (γ ) = i, K1 (γ ) = ξ , and K2 (γ ) = η . It is easy to see that for K0 (γ ) > 0 one has K1 (γ ) < γ and K2 (γ ) < γ . This enables one to de?ne a sequence of sets Fγ by induction on γ ∈ Ord by means of the following scheme: ? for γ = 0; ? ?? Fγ = FK0 (γ ) (FK1 (γ ) , FK2(γ ) ) for γ > 0 and K0 (γ ) > 0; ? ? {Fν : ν < γ } for γ > 0 and K0 (γ ) = 0. Finally, L = {Fγ : γ ∈ Ord} is the class of all constructible sets.

    On some classical problems of descriptive set theory

    861

    De?nition 2.3 (relative constructibility). For any set X ? L, let ? = ?(X ) be the smallest ordinal such that X ? {Fξ : ξ < ?}. (For example, if X = a ∈ Nω , then we always have ?(a) = ω.) Let us rede?ne K in De?nition 2.2 to be the unique onto order isomorphism K : T ; ?→ Ord {0, ?}. Thus, the inverse functions K0 , K1 , K2 are now de?ned on the set Ord {0, ?}. Let us de?ne Fξ [X ] by induction on ξ ∈ Ord in accordance with the scheme of De?nition 2.2 but with the additional special condition F? [X ] = X . (We note that Fξ [X ] = Fξ for ξ < ?, and hence X = F? [X ] ? {Fξ [X ] : ξ < ?}.) The family L[X ] = {Fγ [X ] : γ ∈ Ord} is the class of all sets constructible relative to X . If x, y ∈ L[X ], then x < [X ] y means that x occurs in the sequence of sets Fγ [X ] earlier than y. A generalization. Suppose that s = {Xξ }ξ<ζ is a ?nite or trans?nite sequence of sets Xξ ? L (ζ ∈ Ord). In general we have s ? L, but we can de?ne L[s] = L[X ], where X = { ξ, x : x ∈ Xξ } ? L. In particular, this de?nition works for classes of the form L[a1, . . . , an ], where a1 , . . . , an ? L, for example, for a1 , . . . , an ∈ Nω . We note that the class L coincides with L[X ] for any X ∈ L. The next theorem was obtained in [20] in this special case, but the general result can be proved similarly. Theorem 2.4. Suppose that X ? L. The class L[X ] satis?es all axioms of ZFC. It contains X and all ordinals, and it is the smallest class with this property satisfying all axioms of ZFC. Moreover, < [X ] is a well ordering of L[X ] order isomorphic to Ord. G¨ odel also proved that the axiom of choice AC and the generalized continuum hypothesis hold in L (in fact, in any class of the form L[a], a ∈ Nω , but the continuum hypothesis is not necessarily true in L[X ] for an arbitrary X ). The following simple result will be used below. Proposition 2.5. Let M be a transitive set closed under the G¨ odel operations and let a ∈ M ∩ Nω . Suppose in addition that the restricted sequence {Fξ [a]}ξ<γ belongs to M for any ordinal γ ∈ M. Then the construction of {Fξ [a]}ξ∈Ord ∩M is absolute for M, that is, it gives the same result in M and in the universe of all sets. 2C. Constructibility in the domain of the Baire space. Suppose that a ∈ Nω . For any ξ ∈ Ord let fξ [a] = Fξ [a] if Fξ [a] ∈ Nω and let fξ [a] = O (with the function O(n) = 0 ? n) otherwise. Thus, fξ [a] always belongs to Nω . Let ω1 denote the ?rst uncountable cardinal in L[a]. Let ?a denote the order < [a] restricted to L[a]. Theorem 2.6. The following assertions hold. (i) If a ∈ Nω , then L[a] = {fξ [a] : ξ < ω1 } = {fξ [a] : ξ < ω1 }, and the L[a] relation ?a well orders L[a] with the order type ω1 . 1 1 (ii) One can ?nd a Σ1 formula ? and a Π1 formula ψ such that x = f|w|[a] ?? ?(w, a, x) ?? ψ (w, a, x) for any w ∈ WO and a, x ∈ Nω . 1 (iii) The set L[a] and the relation ?a belong to Σ2 (a).
    L[a] L[a]

    862

    V. G. Kanovei and V. A. Lyubetskii

    (iv) If a, p ∈ Nω and P ? Nω × Nω is a ?1 2 (p) set, if X = {x ∈ Nω : the set Px(a) = {y ∈ L[a] : x, y ∈ P } is non-empty }, and if yx is the ?a -smallest element of Px for any x ∈ X , then both X and 1 P = { x, yx : x ∈ X } belong to Σ2 (a, p). If, in addition, X is a ?1 2 (a, p) 1 set, then P is a ?2 (a, p) set as well. Proof (a sketch). (i) Any point x ∈ Nω in L[a] occurs in the construction of L[a] at some step before the step ω1 . This is a crucial point in G¨ odel’s proof in [20] of the continuum hypothesis in the constructible universe L based on the Skolem– L¨ owenheim method. (The generalization to L[a], a ∈ Nω , involves no new problems.) This implies both the equality L[a] = {fξ [a] : ξ < ω1 } and the fact that the L[a] length of ?a does not exceed ω1 . Why can ω1 be replaced by ω1 ? The point is that the inductive construction of the sets Fξ [a] is absolute for L[a], that is, it can be carried out in L[a] with the same ?nal result. However, any point of Nω occurs L[a] in L[a] before the step ω1 . (ii) The idea of the proof is to encode the entire G¨ odel construction up to the step ω1 (where obviously the sets appearing are at most countable) by means of points of Nω . In principle this is similar to the encoding of countable ordinals and Borel sets introduced in subsection 1E, but the technical details are much more complicated. The argument was carried out in full detail by Novikov [78] and Addison [1], [2] (in somewhat di?erent versions and under the assumption that V = L). We present a sketch of another proof to give the reader the possibility of seeing the mechanism of arguments of this kind without referring to rather di?cult original papers. We consider structures of the form N; ε , where ε ? N2 is a binary relation viewed as the ‘membership’ relation in N; ε . Let E be the set of all relations ε ? N2 satisfying the following three conditions: (a) if i, j ∈ N and ? n (nεi ?? nεj ), then i = j (extensionality); (b) all axioms of ZFC? (ZFC without the power set axiom; see subsection 2A) hold in N; ε ; (c) the family Ordε = {n ∈ N : it is true in N; ε that n is an ordinal} of all ordinals of the model N; ε has an initial segment order isomorphic to the ordinal ω + 1 (in other words, N; ε is an ω-model). In this case there exists for any n ∈ N a unique element nε ∈ N corresponding to n in N; ε , and there is a unique element ωε ∈ N corresponding to ω in N; ε . Moreover, {nε : n ∈ N} is the set of all ε-elements of ωε . Suppose that x ∈ Nω . It can happen that there is an element k ∈ N (which is unique if it exists) for which it is true in N; ε that k ∈ Nω and k (nε ) = mε whenever x(n) = m. Such an element k will be denoted by xε . Obviously, xε exists for at most countably many points x ∈ Nω . To prove (ii), we take the formula ?(w, a, x) to be ? ε ∈ E (aε , wε , xε do exist in N; ε ∧ xε = f|wε | [aε ] is true in N; ε ). We note that each of the two conjunctive terms of the formula in parentheses can be expressed by an arithmetic formula, and thus the displayed formula is in fact

    On some classical problems of descriptive set theory

    863

    1 a Σ1 formula. (We do not dwell on the fact, say, that ε should be appropriately encoded by a point of Nω , because there are no problems here.) It remains to show that the formula ? thus de?ned satis?es (ii). Suppose that w ∈ WO, a, x ∈ Nω , and ?(w, a, x) holds, that is, one can ?nd an ε ∈ E such that the objects aε , wε , xε do exist in N; ε and xε = f|wε| [aε ] is true in N; ε . Then the ordinal series Ord N;ε has an initial segment order isomorphic to ξ = |w|, and hence it has an initial segment order isomorphic to ξ + ω + 1 (and also initial segments order isomorphic to ξ + ξ , ξ × ξ , and so on). Let us show that, for this reason, the model N; ε contains an essential part of the ∈-structure of ordinary sets. We recall that rk x ∈ Ord is a set-theoretic rank (see subsection 2A). Let M be the set of all elements m such that rk x < |wε | + ωε is true in N; ε . One can readily see that every m ∈ M belongs to the well-founded part WFε of the model N; ε ; this part consists of all m such that the ε-transitive closure TCε (m) does not contain in?nite ε-decreasing chains. (TCε (m) is the smallest set T ? N for which m ∈ T and iεj ∈ T =? i ∈ T .) Therefore, we can de?ne a true set S (m) for any m ∈ M according to the equality S (m) = {S (n) : nεm}.

    Assertion 2.7. The set M contains aε, wε , and xε . The set S = {S (n) : n ∈ M } is transitive. The map m → S (m) is an isomorphism of M ; ε onto S; ∈ , with S (wε ) = w, S (xε ) = x, and S (aε ) = a. We note that from the point of view of the model N; ε the structure M ; ε is a set of the form {z : rk z < ξ + ω}, where ξ = |w|, and every set of this kind obviously satis?es the conditions on M in Proposition 2.5. It follows that the formula xε = f|wε| [aε] is true in M ; ε , because it is true in N; ε by the above assumption. Therefore, x = f|w|[a] holds in S; ∈ by Assertion 2.7. By Proposition 2.5 again, the formula x = f|w| [a] is true in the universe of all sets as well. Thus, ?(w, a, x) implies that x = f|w| [a]. To prove the converse, suppose that x = f|w|[a]. It follows from Proposition 2.1 that there is a countable transitive set M ? HC which contains w, a, x and is a model of ZFC? . Then the formula x = f|w|[a] is true in M; ∈ . Let us consider a relation ε ? N2 such that the model N; ε is isomorphic to M; ∈ . Clearly, ε ∈ E , and the isomorphism (which is uniquely de?ned) sends w, a, and x to the elements wε , aε, and xε , respectively, and these elements really exist in N; ε . It follows that the formula xε = f|wε| [aε ] is true in N; ε . This means that ?(w, a, x) holds. 1 formula ψ : The following formula can be taken as the desired Π1 ? ε ∈ E (aε , wε, xε exist in N; ε =? xε = f|wε | [aε ] is true in N; ε ). (iii) It follows from (i) that x ∈ L[a] ∩ Nω ?? ? w (w ∈ WO ∧ x = f|w| [a]). We 1 replace the equality x = f|w|[a] by a Σ1 formula ?(w, a, x) in (ii) and use the fact 1 that WO ∈ Π1 (Proposition 1.11). Concerning the order ?a , we note that x ?a y is equivalent by de?nition to ? η < ω1 y = fη [a] ∧ ? ξ < η (y = fξ [a]) ∧ ? ξ < η (x = fξ [a]) .
    ?(a,y,η)

    (?)

    864

    V. G. Kanovei and V. A. Lyubetskii

    Moreover, ?(a, y, |w|) ?? ? k (y = fw k [a]) for any w ∈ WO (see Example 1.10.1). This enables us to reduce the formula (?) to 1 form (with the arguments x, y, a) by using (ii) and Proposition 1.11. the desired Σ2 We note that the key point of the argument is the transformation of the quanti?er ? ξ < η in the subformula ? to a quanti?er over N, which does not a?ect the class of the formula. (iv) First of all, x ∈ X ?? ? y (y ∈ L[a] ∧ x, y ∈ P ). This implies that 1 X ∈ Σ2 (a, p) by the ?rst claim of (iii). We note further that x, y ∈ P is equivalent to / P) , x, y ∈ P ∧ ? η < ω1 y = fη [a] ∧ ? ξ < η ? z (z = fξ [a] ∧ x, z ∈
    τ (a,x,η)

    where the formula τ (a, x, η) expresses the fact that x, fξ [a] ∈ / P for every ξ < η . 1 The reduction of the displayed formula to the Σ2 form can be carried out by the same arguments as above. Finally, x, y ∈ P ?? x ∈ X ∧ ? z = y ( x, z ∈ / P ). This implies the last claim of (iv). 2D. Absoluteness. This notion is not directly related to constructibility. However, it becomes necessary after we learn that the universe V of all sets has subclasses, for example, those of the form L[X ], which themselves satisfy the axioms of ZFC and hence can be regarded as valuable set-theoretic universes. Suppose that M is a transitive set or class (for example, a class of the form L[X ]) satisfying all axioms of ZFC (or at least a substantial part of ZFC like ZFC? ). Let Φ be a closed formula with sets in M as parameters. Then one can pose the question of whether or not the formula Φ is true or false in M (rather than just in the universe V), which means that the formula obtained by the relativization of Φ to M (that is, by replacing all quanti?ers ? x and ? x by ? x ∈ M and ? x ∈ M) is true or false (in V). If Φ is simultaneously true or simultaneously false both in M and in the universe V of all sets, then Φ is said to be absolute for M. In fact, we have already encountered the notion of absoluteness in a simple situation when the absoluteness of formulae or of the constructions de?ned by them was quite clear. (See, for instance, Proposition 2.5 and its use in the proof of Theorem 2.6(ii).) The following theorem is of importance because it enables one to establish the absoluteness of a formula by using only its syntactical structure with no regard to its mathematical content. Theorem 2.8 (the absoluteness theorem). Suppose that M is a transitive set or class in which all ZFC? axioms hold. In this case
    1 formula with parameters in M ∩ Nω is absolute for M; (i) every Σ1 1 (ii) if ω1 ? M, then the same assertion holds for all Σ2 formulae with parameω ters in M ∩ N .

    Proof (a sketch). The validity of Proposition (i) (Mostowski’s theorem) uses the fact that by the sifting theorem (Theorem 1.6) the formula ?Φ is equivalent to the assertion that a certain set Q ∈ M, Q ? Q, is well ordered, where Q depends

    On some classical problems of descriptive set theory

    865

    on Φ but not on M. Proposition (ii) (the Shoen?eld absoluteness theorem) was ?rst proved in [85]. The proof is somewhat more complicated than the proof of (i) and can also be found in [35], p. 305. Both assertions are also given in [86], Exercise 12 in Chapter 9, as exercises with hints.
    1 Remark 2.9. The assertion (i) of Theorem 2.8 can also be extended to Π1 formulae, 1 and (ii) to Π2 formulae. Moreover, one-way absoluteness can be extended to the 1 next level; for example, if ω1 ? M, then any Σ3 formula with parameters in M ∩ Nω which is true in M is also true in the universe V of all sets, whereas the converse 1 assertion holds for Π3 formulae. Proposition 1.11 leads to numerous applications of the absoluteness theorem (and the same can be said for some other analogous de?nability results). For example, it follows from 1.11(i) that (BC)M = BC ∩ M, that is, any c ∈ Nω ∩ M belongs to BC if and only if it is true in M that c ∈ BC. It follows from 1.11(iv) that, for any c ∈ BC ∩ M, the set (Bc )M (that is, Bc de?ned in M) coincides with Bc ∩ M. Further, if ω1 ? M and p, q ∈ BC ∩ M, then it follows again from 1.11(iv) that Bp ? Bq is equivalent to Bp ∩ M ? Bq ∩ M, and Bp = Bq is equivalent to Bp ∩ M = Bq ∩ M. Theorem 2.8 also enables us to derive ‘e?ective’ modi?cations of classical theorems of descriptive set theory whose direct proofs would require tedious work with details. The following result is an example.

    Theorem 2.10 (e?ective Suslin theorem). If a ∈ Nω and if X ? Nω is a ?1 1 (a) set, then there is a code c ∈ BC ∩ L[a] such that X = Bc .
    1 1 Proof. Let us consider a Σ1 formula ? and a Π1 formula ψ such that X = {x : ?(a, x)} = {x : ψ(a, x)}. The equivalence ? x (?(a, x) ?? ψ(a, x)) can 1 be expressed by a Π2 formula with a as the only parameter, and hence this formula holds in L[a] as well. It follows that the equivalent formulae ? and ψ de?ne a ?1 1 set in L[a]. Thus, by the classical Suslin theorem (see Theorem 1.8), there is a code c ∈ L[a] ∩ Nω such that both formulae c ∈ BC and ? x (x ∈ Bc ?? ?(a, x) ?? ψ(a, x)) are true in L[a]. However, the latter formula 1 is also of class Π2 with a and c as parameters (Proposition 1.11(iv)), and therefore c ∈ BC and X = Bc in the universe V of all sets (again by Theorem 2.8).

    Historical and bibliographical remarks. For the studies which led to the picture of the set-theoretic universe brie?y described in subsection 2a and to ZFC theory, see, for instance, [19]. The absoluteness Theorem 2.8(ii) was proved by Shoen?eld [85]. The class L of all constructible sets was de?ned by G¨ odel [20]. Speci?c problems of constructibility in the area of the Baire space, including the descriptive de?nability of the G¨ odel sequence restricted to the countable ordinals and the associated well ordering of the continuum, were considered by Novikov [78] and later by Addison [1], [2]. Relative constructibility (that is, classes of the form L[x]) attracted attention already in the 1960s, in particular in connection with the development of forcing. Some references on constructibility, including applications to descriptive set theory, are given in [29], [35], and [11], Chap. 5. A systematic survey of properties of the important set of all constructible points (that is, of the set L ∩ Nω ) will be presented in a forthcoming paper of the authors,

    866

    V. G. Kanovei and V. A. Lyubetskii

    to appear in a volume of Proceedings of the Steklov Institute of Mathematics dedicated to L. V. Keldysh. § 3. Resolvents of classical problems: Part 1 It turns out that the perfect kernel problem for Π1 1 sets and the problems of measurability and the Baire property for sets of the second projective level are closely related to special properties of some particular sets, in the sense close to that meant by Luzin when he used the term resolvents. Suppose that P(K) is the existence problem for a set satisfying some property (say, a non-measurable set or a set without the Baire property) in a given projective class K. Then, as a rule, by using the language of analytic formulae it is not di?cult to ?nd a projective set X such that the problem P(K) admits a positive solution if and only if X is non-empty. Luzin [54] referred to sets X of this kind as resolvents (r? esolvantes ) of the original problems. In a somewhat wider sense, a resolvent of a problem P(K) is understood to be a property p (of a certain set X ) equivalent to a positive solution of the problem. (In Luzin’s sense, p is the non-emptiness of X .) In this section we begin an exposition of investigations on resolvents of classical problems on the regularity properties represented in the diagram in the Introduction; these investigations both revealed the essence of the problems and established relationships among them. 3A. Cohen points and random points. The resolvents used in the main results (Theorem 3.3 and Corollary 3.4 below) are formulated in terms of properties of sets of the form L[a] ∩ Nω , a ∈ Nω , and of sets introduced by the following de?nition. De?nition 3.1. Let M be a transitive model of ZFC, for instance, a class of the form L[X ]. In this case we say that an x ∈ Nω is a Cohen point over M and write x ∈ Coh M if x ∈ / Bc whenever c ∈ M ∩ BC and Bc is a meagre subset of Nω . Suppose in addition that ? is a Borel measure on Nω . We say that a point x ∈ Nω is ?-random over M and write x ∈ Rand? M if x ∈ / Bc whenever c ∈ M ∩ BC and ?(Bc ) = 0. We set Rand M = Randλ M.19 Thus, the Cohen points (over M) are the points avoiding any meagre Borel set with a code in M, and the random points are the points avoiding any zero-measure set. The Cohen points and the random points admit a convenient characterization in terms of forcing; see subsection 4C. We note that Rand M ? 2ω , because λ(Nω 2ω ) = 0. The following lemma will be useful below. Its assertions (1), (2) show that, due to a certain uniformity of measure and category, the non-emptiness of the sets Coh M and Rand M implies their denseness in a rather strong sense. Lemma 3.2. Let M be a transitive model of ZFC. In this case (1) if Rand M = ?, then any Borel set of non-zero λ-measure with a code in M intersects Rand M;
    recall that the measure λ on 2ω was introduced in subsection 1B, and the encoding of Borel sets and the de?nitions of BC and Bc in subsection 1E. The meagre sets are the ?rstcategory sets, and the co-meagre sets are their complements.
    19 We

    On some classical problems of descriptive set theory

    867

    (2) if Coh M = ?, then any non-meagre Borel set with a code in M intersects Coh M; (3) the conditions Rand M = ? and λ(Rand M) = 1 do not depend on the choice of the measure, in the sense that if ? is a ?nite Borel measure on Nω and its code Cod(?) (that is, the function Cod(?)(n) = ?(Nsn )) belongs to M, then Rand M = ? ?? Rand? M = ? and λ(Rand M) = 1 ?? ?(Rand? M) = ?(Nω ). Proof. (1) In the case of a measure suppose that c ∈ BC ∩ M and m = λ(Bc) > 0. The arguments in the proof of Lemma 1.3 yield Borel sets X ? 2ω and Y ? Bc with onto λ(X ) = 1 and λ(Y ) = m and a Borel isomorphism F : X ?→ Y preserving λ with the m coe?cient κ = M , which means that λ(F ”B ) = κ λ(B ) for any Borel B ? X . Moreover, since c ∈ M, it follows from the absoluteness theorem (Theorem 2.8) that one can choose X, Y, F with codes in M. Then F takes Borel λ-null sets B ? X with codes in M to Borel λ-null sets B ? Y with codes in M, and conversely. Therefore, if x ∈ Rand M, then F (x) ∈ Rand M ∩ Bc. (2) We employ a similar argument using the fact that, if A ? Nω is a non-meagre Borel set, then there exist a Baire interval Ns and a Gδ set Y ? Ns ∩ A dense in Ns . One can readily see that the set Y is homeomorphic to Nω , and so on. (3) This assertion follows from Lemma 1.3 in the same way that (1) does. 3B. Main results on resolvents of the regularity properties. Theorem 3.3. For every point a ∈ Nω the following equivalences hold : (i) (ii) (iii) (iv) (v)
    1 PK(Π1 (a)) ?? (L[a] ∩ Nω is a countable set);20 1 LM(Σ2 (a)) ?? (Rand L[a] is a set of full λ-measure); 1 BP(Σ2 (a)) ?? (Coh L[a] is a co-meagre set); LM(?1 2 (a)) ?? (Rand L[a] = ?); BP(?1 2 (a)) ?? (Coh L[a] = ?).

    Corollary 3.4. (I) (II) (III) (IV) (V)
    ω PK(Π1 1 ) ?? ? a ∈ N 1 LM(Σ2 ) ?? ? a ∈ Nω ω BP(Σ1 2 ) ?? ? a ∈ N 1 LM(?2 ) ?? ? a ∈ Nω ω BP(?1 2 ) ?? ? a ∈ N a∈Nω

    (L[a] ∩ Nω is countable); (Rand L[a] is a set of full λ-measure); (Coh L[a] is a co-meagre set); (Rand L[a] = ?); (Coh L[a] = ?).

    Proof. Π1 1 =

    1 1 Π1 (a), and similarly for Σ1 2 and ?2 .

    The properties of the sets L[a] ∩ Nω , Rand L[a], and Coh L[a] on the righthand sides of the equivalences can be viewed as resolvents of the problems on the
    20 The

    condition “L[a] ∩ Nω is countable” is equivalent to the inequality ω1
    L [ a] Nω (ω1

    L [ a]

    < ω1 , and hence

    the right-hand side of (i) is equivalent to the condition ? a ∈ literature more frequently.

    < ω1 ), which occurs in the

    868

    V. G. Kanovei and V. A. Lyubetskii

    left-hand sides of the equivalences, in the sense discussed above. Theorem 3.3 and Corollary 3.4 themselves do not solve the problems on the left-hand sides of the equivalences. For example, nothing can be immediately deduced concerning the question of whether PK(Π1 1 ) is true or false. However, the problems are reduced to a uniform and intuitively more clear setting. Moreover, the relationships among the problems become much more transparent. In particular, we immediately obtain the implications in the diagram in the Introduction that come out of the box PK(Π1 1 ).
    1 1 Corollary 3.5 (Lyubetskii [65], [66], [68]). PK(Π1 1 ) implies LM(Σ2 ) and BP(Σ2 ).

    Proof. If L[a] ∩ Nω is countable, then Rand L[a] is the complement of a union of countably many zero-measure sets, and hence λ(Rand L[a]) = 1; Coh L[a] is a co-meagre set for similar reasons. We prove the implications =? of Theorem 3.3 in this section, and the next section is devoted to the inverse implications. 3C. Uncountable Π1 1 sets without a perfect kernel. Here we prove the implication =? in (i) of Theorem 3.3. (The converse implication will be obtained in subsection 4B below.) The result is proved in the ‘contrapositional’ form, that is, for every a ∈ Nω ,
    1 L[a] ∩ Nω is uncountable =? ? PK(Π1 (a)).

    Proof. Suppose that a ∈ Nω and that L[a] ∩ Nω is uncountable. The set Ξ = 1 { x, w : w ∈ WO ∧ x = f|w|[a]} belongs to Π1 (a) by 1.11(i) and Theorem 2.6(ii). 1 (a) set C ? Ξ By the uniformization theorem, Theorem 1.9, there is a uniform Π1 such that dom C = dom Ξ. In other words, C is the graph of a function η such that 1 dom η = L[a] ∩ Nω and x = f|η(x)|[a] for each x ∈ L[a] ∩ Nω . Thus, the Σ2 (a) set ω R = ran η = {η (x) : x ∈ L[a] ∩ N } ? WO is uncountable, because L[a] ∩ Nω is.21 Obviously, R contains at most one point in common with any constituent WOξ = Eξ (L) of the Lebesgue sieve L (see Example 1.10.1), and hence R has no perfect subsets. (If X ? R is a perfect set, then, by Theorem 1.8, there exists an ordinal ? < ω1 such that X ? ξ<? Eξ (L), a contradiction.) Thus, R is an uncountable 1 Σ2 (a) set without a perfect kernel. 1 To ?nd a Π1 (a) set with the same properties, we note that, by Theorem 1.9, there 1 is a uniform Π1 (a) set C ? Nω × Nω such that R = dom C = {x : ? y ( x, y ∈ C )}. (The uniformity means that for any x there is at most one y such that x , y ∈ C .) If P ? C is a perfect subset, then its projection A = dom P ? R is uncountable, because C and P are uniform; moreover, A is a Σ1 1 set. It follows from Theorem 1.4 that there is a perfect set Y ? A ? R. However, R has no perfect subsets, a contradiction. Another proof of the existence of Π1 1 sets without the perfect kernel property (under the assumption that L[a] ∩ Nω is uncountable for some a ∈ Nω ) is given in [37]. It is more elementary, in the sense that it uses neither sieves nor constituents.
    same result holds if we de?ne R as the set formed by the ?a -smallest elements wξ in the sets WOξ . We note that the proof of the lemma does not directly use G¨ odel’s well ordering ?a of the set L[a] ∩ Nω explicitly (though it uses the sequence {fξ [a]}ξ<ω1 , of course).
    21 The

    On some classical problems of descriptive set theory

    869

    3D. Non-measurable sets of second projective level. In this subsection we prove the implications =? in (ii)–(v) of Theorem 3.3. They are proved in the following ‘contrapositional’ form: (ii ) (iii ) (iv ) (v )
    1 Rand L[a] is not a set of full λ-measure =? ? LM(Σ2 (a)); 1 Coh L[a] is not a co-meagre set =? ? BP(Σ2 (a)); Rand L[a] = ? =? ? LM(?1 2 (a)); Coh L[a] = ? =? ? BP(?1 2 (a)).

    Proof. (iii ) Suppose that a ∈ Nω and Coh L[a] is not a co-meagre set. Then 1 C = cod Icat = {c ∈ BC : Bc ∈ Icat} is a Π1 set by 1.11(vi). However, to present the proof in a form applicable to a more general case below, we proceed in what 1 follows with the weaker assumption that C ∈ Σ2 . Then, by Theorem 1.9, there is 1 ω ω a Π1 set P ? N × N such that c ∈ C ?? ? y P (c, y). We recall that fξ [a] is the ξ th element of L[a] ∩ Nω in the sense of the well ordering ?a of L[a] ∩ Nω . For any ξ < ω1 , if fξ [a] = h satis?es (h)0 , (h)1 ∈ P (in which case (h)0 ∈ C ), then we de?ne Sξ = B(h)0 (the Borel set encoded by (h)0 ). Otherwise we set Sξ = ?. Then Sξ ∈ Icat in any case. Let Xξ = Sξ η<ξ Sη . We claim that the sets S = { w, x : w ∈ Ord ∧x ∈ S|w| } and W = { w, x : w ∈ Ord ∧x ∈ X|w| }

    1 belong to Σ2 (a). Indeed, for S this follows from the equivalence

    w, x ∈ S ?? w ∈ WO ∧ ? h h = f|w|[a] ∧ (h)0 , (h)1 ∈ P ∧ x ∈ B(h)0 ,
    1 1 where WO ∈ Π1 and { w, f|w|[a] : w ∈ WO ∧ a ∈ Nω } is a Π1 set by Theorem 2.6(ii). As for W , the relation x ∈ X|w| is equivalent to the formula x ∈ S|w| ∧ ? k (w(k ) = 0 =? x ∈ / S|w k |) in the notation of Example 1.10.1. Then

    Z=
    η ξ<ω1

    (Xη × Xξ ) =
    η ξ<ω1

    { x, y : x ∈ Xη ∧ y ∈ Xξ }

    1 is a Σ2 (a) set as well, because

    x, y ∈ Z ?? ? w, w ∈ WO |w|

    |w | ∧ w, x ∈ W ∧ w , y ∈ W ,

    1 (see Proposition 1.11). where both WO and the relation |w| < |w | belong to Π1 We claim that the set Z does not have the Baire property in Nω × Nω . Indeed, otherwise Z is a meagre set by the Ulam–Kuratowski theorem, because every crosssection Z y = {x : x, y ∈ Z } is a union of countably many sets of the form Xξ , and hence a meagre set. On the other hand, the projection X = {x : ? y ( x, y ∈ Z )} = ξ<ω1 Xξ of Z obviously coincides with the complement D of the set Coh L[a]. Therefore, D is a non-meagre set in the case under consideration. However, every cross-section Zx = {y : x, y ∈ Z }, x ∈ X , also di?ers from D by a union of countably many sets of the form Xξ , and hence Zx is a non-meagre set as well. Thus, Z itself is not a meagre set by the Ulam–Kuratowski theorem, which contradicts 1 what was said above. We conclude that the Σ2 (a) set Z ? (Nω )2 does not have

    870

    V. G. Kanovei and V. A. Lyubetskii
    onto

    the Baire property. Using some recursive homeomorphism (Nω )2 ?→ Nω , we can transfer this counterexample to Nω . (v ) Here Coh L[a] = ?, and hence the set Z (de?ned in the above argument) belongs to ?1 2 (a). Indeed, Z is the complement of Z = ξ<η<ω1 (Xη × Xξ ), 1 which belongs to Σ2 (a) for the same reasons as for Z . (ii ) and (iv ). Here the arguments are similar to those used above; however, one must consider the ideal Iλ instead of Icat and use Lemma 1.3 (for the e?ective class ω ?1 2 (a)) to transfer the counterexample to N . In general, here we must consider ω sets in the space 2 (because the measure λ is de?ned on 2ω ), for example, to de?ne Sξ = Bfξ [a] ∩ 2ω for fξ [a] ∈ BC (see the beginning of the proof of (v )). The Ulam–Kuratowski theorem is replaced by the Fubini theorem, of course. However, this does not change the arguments substantially. (the implications =? in (ii)–(v) of Theorem 3.3) 3E. Generalization: measurability with respect to an ideal. Obvious similarities between the assertions (ii) and (iv) of Theorem 3.4 on the one hand and the assertions (iii) and (v) on the other hand lead us to the following general approach to equivalences of this kind. Let I be an ideal in the family of all Borel subsets of Nω . A set X ? Nω is called an I-null set if it is covered by a set in I, an I-measurable set if there is a Borel set U such that the symmetric di?erence X U is an I-null set, and an I-full set if Nω X is an I-null set. De?nition 3.6. Let M be a transitive model of ZFC. We say that a point x ∈ Nω is I-random over M and write x ∈ RandI M if x ∈ / Bc whenever c ∈ BC ∩ M and Bc ∈ I. By a σ-CAC ideal we mean any ideal I of Borel subsets in Nω satisfying the following two conditions. 1? . I is closed under countable unions (σ-additivity). 2? . Every family of pairwise I-disjoint Borel sets (that is, all pairwise intersections of these sets belong to I) that do not belong to I is at most countable. (This is called the σ-saturation condition, or the countable antichain condition, brie?y, CAC.) The next theorem generalizes the classical results on measurability and the Baire 1 property for the classes Σ1 1 and Π1 (see Theorem 1.4). Theorem 3.7. If I is a σ-CAC ideal in the algebra of Borel subsets of Nω , then 1 ω every Σ1 1 or Π1 set X ? N is I-measurable. Proof. For any set Z ? Q we write Z = Z {q } if q is the smallest element of Z , and simply take Z = Z if Z has no smallest element. If R ? Nω × Q, then we de?ne R ? R in such a way that R (x) = (R(x) ) for each x ∈ Nω . (We recall that R(x) = {q : x, q ∈ R}.) ω Let us consider a Π1 1 set X = E (R), where R ? N × Q is a Borel sieve. We de?ne R(ξ ) ? R by induction on ξ < ω1 in such a way that R(ξ + 1) = R(ξ ) and R(?) = ξ<? R(ξ ) for any limit ordinal ? (and R(0) = R). Then it is obvious that R(ξ ) and Rq (ξ ) = {x : x, q ∈ R(ξ )} (q ∈ Q) are Borel sets. In addition,

    On some classical problems of descriptive set theory

    871

    Rq (ξ ) ? Rq (η ) for η < ξ and any q . Therefore, by the choice of I, there is an ordinal ξ < ω1 such that Rq (ξ ) Rq (η ) ∈ I for any ξ η and q ∈ Q. On the other hand, if x belongs to the set D = X E ξ (R), then x, q ∈ R(ξ ) R(ξ + 1) for at least one q , and hence D ? q∈Q Rq (ξ ) Rq (ξ + 1). It follows that D is a I-null set (because the ideal I is σ-additive). It remains to note that E ξ (R) = ζ ξ Eζ (R) is a Borel set. The following de?nition expresses the fact that the properties 1? and 2? of a given ideal I with respect to a given transitive model are absolute. For clear reasons, it is simpler to express the absoluteness by using codes of Borel sets rather than the sets themselves. In this connection we write cod X = {c ∈ BC : Bc ∈ X} for any family X of Borel subsets of Nω . We say that X is K-encoded (where K is a class of point sets) if cod X belongs to K. Let M be a transitive model of ZFC (for instance, a class of the form L[a], a ∈ Nω ). A σ-CAC ideal I is said to be M-absolute if 3? the set C = cod I ∩ M belongs to M and the properties 1? and 2? are absolute for M, that is, it is true in M that I = {Bc : c ∈ C } is a σ-CAC ideal. Lemma 3.8. Let M be any transitive model of ZFC. The following σ-CAC ideals are M-absolute : – the ideal Icat of all meagre Borel sets X ? Nω ; – the ideal I? of all Borel sets X ? Nω of ?-measure zero if ? is a Borel measure on Nω whose code (that is, the function cod(?)(n) = ?(Nsn )) belongs to M; – in particular, the ideal Iλ of all Borel sets X ? Nω such that λ(X ) = 0. 1 1 -encoded, and I? is Π1 (cod(?))-encoded. The ideals Icat and Iλ are Π1
    1 Proof. For the ideal Icat the set C = cod Icat is Π1 by 1.11(vi), and hence Icat is 1 Π1 -encoded. Thus, by the absoluteness theorem, Theorem 2.8, the set C = C ∩ M belongs to M, and it is true in M that C = {c ∈ BC : Bc is meagre} = cod Icat. This implies 3?. Indeed, the properties 1? and 2? for Icat are theorems of ZFC, and hence they hold in M . The ideals Iλ and I? can be treated similarly, except for the fact that one must use 1.11(v) (and its analogue for an arbitrary measure ?) instead of 1.11(vi).

    Let us consider the following I-measurability hypothesis for any given class K (for instance, for some projective class) and for any σ-CAC ideal I: MI (K): all sets X ? Nω in K are I-measurable. For instance, we have MI (Σ1 1 ) ? I by Theorem 3.7. 3F. Sets that are non-measurable with respect to an ideal. The following theorem will be proved below. Theorem 3.9. Let a ∈ Nω and let I be an L[a]-absolute σ-CAC ideal that is 1 Σ2 (L[a])-encoded. Then the following equivalences hold : 1 (a) MI (Σ2 (L[a])) ?? RandI L[a] is an I-full set ; (b) MI (?1 / I is a Borel set 2 (L[a])) ?? RandI L[a] ∩ Bc = ? whenever Bc ∈ with a code c ∈ L[a] ∩ BC.

    872

    V. G. Kanovei and V. A. Lyubetskii

    Remark 3.10. Let us say a few words concerning the relationships between this theorem and Theorem 3.3 and Corollary 3.4. The right-hand side of (a) is obviously equivalent to the right-hand sides of (ii) and (iii) in Theorem 3.3 for I = Iλ and I = Icat, respectively. (We note that both ideals satisfy the conditions in Theorem 3.9 by Lemma 3.8.) The right-hand side of (b) looks stronger than the right-hand sides of (iv), (v) in Theorem 3.3 (for the ideals Iλ and Icat), but in fact it is equivalent to these two ideals by Lemma 3.2(1), (2). The left-hand sides of (a) and (b) obviously include the left-hand sides of (ii), (iii) and of (iv), (v), respectively. Thus, since the implications =? in the equivalences (ii)–(v) of Theorem 3.3 have already been established in subsection 3D, it follows that Theorem 3.9 yields nothing new in the direction =? for the ideals Iλ and Icat . However, the scope of Theorem 3.9 is much wider, because the σ-CAC ideals satisfying the properties listed in the theorem are not exhausted by the above two ideals. The implications =? in Theorem 3.9 will be proved below in this subsection. On the other hand, for the same reasons the implications ?= of Theorem 3.9 are su?cient to derive the implications ?= in the equivalences (ii)–(v) in Theorem 3.3. The implications in this direction will be established in § 4 by using forcing. We note ?nally that Theorem 3.9 (for the ideals Iλ , Icat) implies Corollary 3.4 (II)–(V) for obvious reasons. To prove the implications =? in Theorem 3.9, we suppose that I is a σ-CAC 1 (L[a]). It is more convenient to present ideal and the set C = cod I belongs to Σ2 the desired result in the contrapositional form,
    1 (a ) RandI L[a] is not an I-full set =? ?MI(Σ2 (L[a])); (b ) RandI L[a] ∩ Bc = ? for some Borel set Bc ∈ / I with a code c ∈ L[a] ∩ BC =? ?MI(?1 ( L [ a ])). 2

    We ?rst note that the last part of the argument in subsection 3D, in which an I-non-measurable set in Nω is derived from an I2 -non-measurable subset of Nω × Nω , does not work here (I2 stands for the Fubini product). The possibility of going from Nω × Nω to Nω is clear for the ideals Iλ and Icat, but this is hardly the case for an arbitrary σ-CAC ideal I. Fortunately, there is another argument producing counterexamples directly in Nω . However, the result is not as precise as the construction in subsection 3D, because the counterexamples will be obtained 1 1 in the class Σ2 (L[a]) even if C is a Σ2 (a) set. 1 1 (a ) Since C ∈ Σ2 (L[a]), there is a Π1 (L[a]) set P ? Nω × Nω such that c ∈ C ?? ? y P (c, y). Starting from this set C , we de?ne Sξ ∈ I, Xξ , S , and W as 1 in subsection 3D. Of course, the sets S and W are now Σ2 (L[a]) sets by the very choice of C . L[a] Further, we have ω1 = ω1 . (Otherwise the set L[a] ∩ Nω is countable; hence, RandI L[a] is a countable intersection of I-full sets, and therefore itself an I-full L[a] set, which contradicts our assumptions.) It follows that for any ξ < ω1 = ω1 there is a b ∈ L[a] such that {(b)k : k ∈ N} ? WO and {|(b)k | : k ∈ N} = ξ ∪ {ξ },

    and if ξ ω, then |(b)k | = |(b)k | for k = k . (Such an element b encodes an enumeration of all ordinals ξ which is without repetitions if ξ ω.) Let bξ be

    On some classical problems of descriptive set theory

    873

    the ?a -smallest element among all elements b of this kind. Finally, we write Ξηk = {ξ < ω1 : |(bξ )k | = η }, Yηk =
    ξ∈Ξηk

    Xξ ,

    Yη =
    k

    Yηk .

    It is clear that Yη = ξ η Xξ . In particular, the set Y0 = ξ<ω1 Xξ is exactly the complement Nω RandI L[a] of the set RandI L[a]. It follows that Y0 is not an I-null set under our assumptions. Suppose (to arrive at a contradiction) that all sets Yηk (and then all sets Yη as well) are I-measurable. None of the sets Yη can be I-null, since Y0 Yη = ζ η Xζ is a countable union of I-null sets (by the property 1? of the ideal I.) In this case (again by the property 1? !) there exists for any η < ω1 an integer kη such that Yη kη is not an I-null set, and hence there is an integer k such that the set Hk = {η : kη = k } is uncountable. We conclude that Yηk is not an I-null set for any η ∈ Hk . To obtain a contradiction to the property 2? of the ideal I, it remains to note that Yηk ∩ Yη k = ? for η = η . (If x ∈ Yηk ∩ Yη k , then there are ordinals ξ = ξ such that η = (bξ )k , η = (bξ )k , and x ∈ Xξ ∩ Xξ , which is impossible because the sets Xξ are pairwise disjoint.) Thus, some sets Yηk are not I-measurable. It remains to show that each set Yηk 1 belongs to Σ2 (L[a]). Indeed, the sets B = { w, b|w| : w ∈ Ord} and ? = { t, w, k : t, w ∈ WO ∧ |t| ∈ Ξ|w| k }

    1 are Σ2 (a) sets by Theorem 2.6(iv). Let us take any η < ω1 and k and choose a 1 w ∈ WOη ∩ L[a]. Then T = {t ∈ WO : t, w, k ∈ ?} is a Σ2 (a, w) set. Therefore, 1 Yηk = {x : ? t ∈ T ( t, x ∈ W )} is a Σ2 (L[a]) set together with W . (b ) Here we assume that c ∈ BC ∩ L[a], Bc ∈ / I, and RandI L[a] ∩ Bc = ?. Let us repeat the construction in the proof of (a), and let us begin this construction by setting Sξ = B(h)0 ∩ Bc if (h)0 , (h)1 ∈ P and Sξ = ? otherwise. Then Yηk ? Bc , and some sets Yηk are not I-measurable. In addition, every set Yηk belongs to 1 1 Σ2 (L[a]). It remains to show that any set Yηk is a Π2 (L[a]) set as well. In this case we have Y0 = Bc, and hence every Yη = Y0 X is a Borel set. Moreover, for ξ ξ<η η ω we have Yηk ∩ Yηk = ? if k = k , because |(bξ )k | = |(bξ )k | by de?nition if k = k , and the sets Xξ are pairwise disjoint. Therefore, Yηk = Yη k =k Yηk is a 1 Π2 set. A more careful analysis based on the results for the sets ? and W enables 1 us to conclude that Yηk ∈ Π2 (L[a]) (by the same argument as in the last part of the proof in (a)). The values η < ω can be disregarded here. (the implications =? in Theorem 3.9)

    3G. Consistency of the existence of counterexamples. Theorem 3.11. If Nω ? L[a] holds for some a ∈ Nω , then each of the assertions 1 1 PK(Π1 (a)), BP(?1 2 (a)), and LM(?2 (a)) fails. Thus, the conjunction of the nega1 1 tions of PK(Π1 ), BP(?2 ), and LM(?1 2 ) (in other words, the assertion that there are counterexamples in the corresponding classes ) is consistent with the axioms of ZFC. Proof. Under our assumptions, the set L[a] ∩ Nω = Nω is uncountable. Moreover, every singleton {x}, x ∈ Nω , is a Borel set with a code in L[a], and this set

    874

    V. G. Kanovei and V. A. Lyubetskii

    is meagre and of measure zero. Thus, we have Coh L[a] = Rand L[a] = ?. The 1 assertions LM(?1 2 (a)) and BP(?2 (a)) are now violated, by results in subsection 3D, 1 and PK(Π1 (a)) is violated, by results in subsection 3C. To prove the second part of the theorem, we note that the axiom of constructibility V = L implies that Nω ? L[a] for any a, and on the other hand, the axiom of constructibility is consistent with ZFC by G¨ odel’s result. The theorem proved above can be re?ned in connection with the property PK. Let us consider the following modi?cation of PK(K): PK? (K): every K-set P ? Nω × Nω which is the graph of an everywhere de?ned function from Nω to Nω (in this case P is uncountable, of course) contains a perfect subset.
    1 Lemma 3.12. If a ∈ Nω and Nω ? L[a], then PK? (Π1 (a)) fails.

    Proof. Returning to the proof in subsection 3C, we note that the function η de?ned in the course of the proof satis?es the condition Nω = dom η if Nω ? L[a], and hence 1 we have ?PK? (Π1 (a)). Historical and bibliographical remarks. The notions of Cohen and random points (see De?nition 3.1) are due to Solovay [89]. However, Cohen points were introduced by Cohen [15] in a di?erent but equivalent way; in fact, they were the ?rst and most elementary objects given by forcing. For the relationships between Cohen and random points and forcing, see subsection 4C. The proof of Theorem 3.7 uses a method of Selivanowski [83]. Earlier separate proofs of the Lebesgue measurability and the Baire property for Σ1 1 sets (see, for example, [57]) di?er from each other and cannot be generalized to the result of 3.7. A few words concerning Theorem 3.3 and Corollary 3.4. (We recall that the proofs of the implications ?= in 3.3 and 3.4, as well as in Theorem 3.9, were postponed to the next section.) The equivalence (I) was presented in the survey [74] with a reference to Mans?eld and Solovay; their proofs appeared somewhat later in [72] and [88]. The result was obtained independently by Lyubetskii ([17], [65], [67]). Earlier Lyubetskii [64] proved the implication =?. The equivalences (II) and (III) are absent in [74]. As far as we know, the equivalence (II) was ?rst given by Lyubetskii [65]. (For complete proofs of (II) and (III), see [68].) These two equivalences are often referred to unpublished papers of Solovay in the 1960s. (Sometimes (for instance, in [10], p. 457) a reference is given to the paper [88], where these results are simply absent, and measurability and the Baire property are not considered at all.) The equivalences (IV) and (V) of Corollary 3.4 were proved by Lyubetskii [68], [69] (and included in the survey paper [35]). However, these papers have never been translated from Russian and thus the results remained unknown to Western set theorists. Ihoda [Judah] and Shelah re-proved these results in [28]. A few words about some earlier results on the existence of counterexamples. G¨ odel announced in [20] that the axiom of constructibility V = L (that is, the assumption that all sets belong to L) implies the existence of a non-measurable ?1 2 set and of an uncountable Π1 1 set having no perfect subset. The proof of this result (Theorem 3.11 for L instead of L[a]) ?rst appeared in Novikov’s paper [78].

    On some classical problems of descriptive set theory

    875

    Novikov’s counterexample for the perfect kernel property was reproduced in subsection 3C and in Lemma 3.12 with inessential changes. (Following [78], we would have to de?ne the set Ξ in subsection 3C as the set of all pairs {x, w} such that w ∈ WO and x ∈ {fξ [a] : ξ < |w|}. Moreover, Novikov considers ‘absolute’ constructibility, that is, L instead of L[a]. However, this does not change the essence of the arguments.) The counterexample for LM(?1 2 ) given in [78] (again under the assumption that V = L) can be represented as follows: if a function η : Nω → Nω induces a counterexample for PK? (Π1 1 ), then the set { x, y : y <lex η (x)}, where <lex is the lexicographical order on Nω , is a non-measurable ?1 2 set (if the measure of each Baire interval is strictly positive). The construction of counterexamples for measure and category in the classes ?1 2 and Σ1 2 (see subsection 3D) is known from many sources (see, for instance, [10], p. 453 or [92]). Sometimes it is given with a reference to Solovay’s unpublished papers written in the 1960s. (The papers [88] and [89] contain neither the construction nor the results.) The idea of the generalized approach of subsection 3E and, in particular, of the approach used in subsection 3F is taken from [69]. We shall see below in subsection 9C that there are other ideals which di?er from the ideals of meagre sets and zero-measure sets and their intersections and to which Theorem 3.9 can be applied. § 4. Resolvents of classical problems: Part 2 In § 3 we proved the implications =? in Theorems 3.3 and 3.9 and in Corollary 3.4. This showed (see Theorem 3.11, with the reference to G¨ odel’s result on the consistency of the axiom of constructibility V = L) that negative solutions of the problems treated in Corollary 3.4 (that is, the assertions that there are counterexamples to the left-hand sides of the ?ve equivalences) are consistent with the ZFC axioms. The present section contains proofs of the implications ?= in Theorems 3.3 and 3.9 and in Corollary 3.4. The proofs use forcing. The available experience in eliminating forcing from the proofs of statements similar to Theorems 3.3 and 3.9, that is, results not related to independence, hardly gives any hope of obtaining simple proofs free of forcing. However, if only the implications coming out of the block PK(Π1 1 ) in the diagram in the Introduction are considered, then the role of forcing can be reduced to the L[a,x] L[a] = ω1 whenever x ∈ Rand L[a] or x ∈ Coh L[a] single assertion that ω1 (Lemma 4.12). The proof of these implications is completed in subsection 4E. The consistency of positive solutions of the above problems is established in § 7 in a stronger form (including the regularity properties for all ROD sets, and, in particular, for all projective sets). 4A. Basics of forcing. We assume that the reader is somewhat acquainted with forcing, and therefore the text below is rather a review than a self-contained exposition of the basics of this method. In the course of this subsection we ?x a transitive set or a class M satisfying all axioms of ZFC; M is called the ground model. For example, M can be a countable model, a class of the form L[x], or even the universe V of all sets. We assume that P ∈ M is a ?xed partially ordered set, properly called a forcing. Elements of P are

    876

    V. G. Kanovei and V. A. Lyubetskii

    called (forcing ) conditions. If p q , then p is said to be a stronger 22 ‘condition’. The ‘conditions’ p and q ∈ P are said to be compatible if there exists an r ∈ P such that r p and r q ; otherwise p and q are said to be incompatible. A set A ? P is said to be dense (in P) if ? p ∈ P ? q ∈ A (q p); an antichain (in P) if any two p = q ∈ A are incompatible. Finally, a set G ? P is said to be P-generic over M if (1) G ∩ D = ? for any dense set D ? P, D ∈ M; (2) if p ∈ G, q ∈ P, and p q , then q ∈ G. We de?ne t[G] = {s[G] : ? p ∈ G ( p, s ∈ t)} (by ∈-induction on t). The sets t occurring in the text in expressions of the form t[G] are usually called names. For instance, let x ? = { p, y ? : p ∈ P ∧ y ∈ x} (again by ∈-induction). It is clear that x ?[G] = x for any set x. Such a name x ? is said to be the canonical P-name of x. Typically, x ? and x are identi?ed if this leads to no ambiguity. We shall sometimes use this identi?cation if x belongs to N, N<ω , or Ord. Theorem 4.1. If P ∈ M is a partially ordered set and if G ? P is a P-generic set over M, then there is a unique transitive set or class M[G] (the so-called P-generic extension of the model M) such that (i) M ? M[G], G ∈ M[G], the ordinals of M and M[G] coincide, and all axioms of ZFC hold in M[G] ; (ii) M[G] is the smallest class satisfying (i). If x ∈ M[G], then there is a name t ∈ M such that x = t[G]. Theorem 4.2 below contains several of the most important properties of generic extensions, that is, classes of the form M[G], where G is a P-generic set over M for some forcing P ∈ M. We ?rst present the necessary de?nitions. (1) A partially ordered set P satis?es the κ -antichain condition (where κ is an in?nite cardinal) if the cardinality of any antichain A ? P is < κ (strictly); the countable antichain condition (brie?y, CAC) is the ?1 -antichain condition. (2) Partially ordered sets P and P are said to be weakly isomorphic if there are dense subsets D ? P and D ? P order isomorphic to each other. Theorem 4.2. Let P, P ∈ M be partially ordered sets. In this case (i) if a set G ? P is P-generic over M, κ is a regular cardinal in M, and P satis?es the κ -antichain condition in M, then κ is a regular cardinal in M[G], and in particular, if P satis?es the CAC in M, then all cardinals of M remain cardinals in M[G]; (ii) if P, P are weakly isomorphic in M, then any P-generic extension of M is also a P -generic extension of M;
    is, a condition forcing more properties of generic extensions (for these extensions, see below). This is a rather standard convention (though certainly not generally accepted; see, for instance, [10]) which does not always agree with intuition, because for many forcings the order relation is reversed with respect to the inclusion relation ?. However, one has to get used to this.
    22 That

    On some classical problems of descriptive set theory

    877

    (iii) every P × P -generic set over M is of the form G × G , where the set G ? P is P-generic over M and G ? P is P -generic over M[G] (and over M), and furthermore, M[G] ∩ M[G ] = M; (iv) conversely, if a set G ? P is P-generic over M and a set G ? P is P generic over M[G], then the set G × G is P × P -generic over M. The assertions (iii) and (iv) of Theorem 4.2 are known as the product theorem. In the theory of forcing one de?nes the forcing relation, or simply forcing, typically denoted by p M P ?(t1 , . . . , tn ) (verbalizing, p forces ?(t1 , . . . , tn )), where P ∈ M is a partially ordered set, p ∈ P, the elements t1 , . . . , tn ∈ M are understood as names, and ?(x1 , . . . , xn ) is any ∈-formula, that is, a formula in the language of ZFC. This relation satis?es the following theorem. Theorem 4.3. Under the above assumptions, suppose that ?(x1 , . . . , xn ) is an arbitrary ∈-formula. In this case (i) the forcing of the formula ? is de?nable in M in the sense that the family { p, t1 , . . . , tn : p ∈ M ∧ t1 , . . . , tn ∈ M ∧ p
    M P

    ?(t1 , . . . , tn )}

    is de?nable in M by an ∈-formula with P as a parameter ; (ii) if G ? P is P-generic over M and t1 , . . . , tn ∈ M are names, then ?(t1 [G], . . . , tn [G]) is true in M[G] ?? ? p ∈ G (p (iii) the set {p ∈ P : p M P ?(t1 , . . . , tn ) ∨ p and belongs to M for any names tj ∈ M.
    M P M P

    ?(t1 , . . . , tn ));

    ??(t1 , . . . , tn )} is dense in P

    M The symbol M P is P ? means that p P ? for all p ∈ P. The relation V understood as P (that is, the ground model is the universe V of all sets). Let us now discuss the existence of generic sets. One can readily show that there are P-generic sets over M if M is a countable (transitive) model of ZFC. However, this assumption is not always convenient. For example, in some arguments it is desirable to consider generic extensions of classes of the form L[a] or even extensions of the universe V of all sets. In this case one can use Boolean-valued extensions VP of the universe V (for Boolean-valued models, see [29], [70]) as well as the following principle (equivalent in essence).

    Theorem 4.4. Let P be a partially ordered set in the universe V of all sets. The assumption that in a ‘virtual’ wider universe V+ (for instance, of the form VP ) there exists for any p ∈ P a set G ? P which is P-generic over V and contains p does not lead to any contradictions nor ungrounded deductions. 4B. If there are few constructible points, then the Π1 1 sets have the perfect kernel property. The implication from right to left in Theorem 3.3(i) is an elementary corollary to Lemma 4.5. Indeed, if any set of the form L[a] ∩ Nω , a ∈ Nω , is countable, then, by the lemma, every Π1 1 set without a perfect kernel is countable as well.

    878

    V. G. Kanovei and V. A. Lyubetskii

    1 Lemma 4.5 (Solovay [88], Lyubetskii [66]). If a ∈ R and a Σ2 (a) set X ? Nω contains no perfect subsets, then X ? L[a].

    Proof. By the uniformization theorem, Theorem 1.9, it su?ces to prove the lemma 1 1 (a) sets. (See the end of the proof in subsection 3C.) Let us consider a Π1 (a) for Π1 ω set X ? N . By Theorem 1.6, X = E (R) = ξ<ω1 Eξ (R) for a suitable sieve 0 R = {Rq }q∈Q over Nω of class ?1 1 (a) (even of class ?1 (a), but we do not need this fact). Thus, it remains to show that Eξ (R) ? L[a] ? ξ . We note that the set Eξ (R) is at most countable; indeed, it is Borel and without a perfect kernel by assumption. Case 1: ξ < ω1 . Then there is a w ∈ WOξ ∩ L[a]. The statement “Eξ (R) is at most countable” can be expressed by the formula ? z ? x ? n (σ(w, x) =? x = (z )n ),
    1 where σ is the Σ1 (a) formula given by Proposition 1.11(iii). However, the displayed 1 formula is obviously a Σ2 formula with the parameters a, w ∈ L[a], and hence it also holds in L[a] by the absoluteness theorem, that is, there is a z ∈ L[a] ∩ Nω such that the formula ? x ? n (σ(w, x) =? x = (z )n ) is true in L[a]. Again by absoluteness, the last formula also holds in the universe of all sets, which means that Eξ (R) ? {(z )n : n ∈ N} ? L[a]. L[a]

    Case 2: ω1 ξ < ω1 . Let us prove that Eξ (R) = ?. Suppose the contrary: let the constituent Eξ (R) be non-empty. As above, if w ∈ WOξ , then the set Eξ (R) belongs to L[a, w] and is countable in L[a, w]. Let us consider the forcing C(ξ ) = Coll(N, ξ ) designed to ‘collapse’ ξ . Thus, C(ξ ) consists of all ?nite sequences of ordinals < ξ , or, which is the same, of all functions p : m → ξ , where m = {0, 1, . . ., m ? 1} and p q (that is, p is ‘stronger’) if q ? p, that is, p extends q as a function. Every C(ξ )-generic set G ? C(ξ ) produces a onto function f [G] = G : N ?→ ξ , the so-called collapse function for ξ . Conversely, G = {f [G] n : n ∈ N}. By Theorem 4.4, one can consider a C(ξ ) × C(ξ )-generic extension V[G, G ] of the universe V generated by a pair of sets G1 , G2 ? C(ξ ) generic over V (and hence over L[a] as well). By the foregoing, such an extension admits two collapse functions f1 = G1 and f2 = G2 from N onto ξ . Accordingly, there are codes w1 ∈ WOξ ∩ L[f1 ] and w2 ∈ WOξ ∩ L[f2 ] of the ordinal ξ . As proved above, Eξ (R) ? L[a, f1 ] ∩ L[a, f2] = L[a, G1] ∩ L[a, G2]. Since the sets G1 , G2 form a generic pair over L[a], we have Eξ (R) ? L[a] by Theorem 4.2(iii). In other words, since the constituent Eξ (R) is non-empty, there L[x] L[a] exists an x ∈ Eξ (R) ∩ L[a]. However, in this case it is clear that ξ < ω1 ω1 , a contradiction. (Lemma 4.5 and Theorem 3.3(i)) Remark 4.6 (Mans?eld [72]). Taking the contraposition of Lemma 4.5, we see that 1 any Σ2 (a) set X ? Nω with X ? L[a] necessarily contains a perfect subset P ? X . It turns out that the subset can be chosen to have a code in L[a], in the sense that there is a perfect tree T ∈ L[a], T ? N<ω (see the notation in subsection 1A), such that [T ] ? X . Indeed, it follows from considerations related to the uniformization

    L[a]

    On some classical problems of descriptive set theory

    879

    1 theorem (Theorem 1.9) that X can be assumed to be a Π1 (a) set. In this case the 1 formula “X has a perfect subset of the form [T ]” can be reduced to the Σ2 (a) form, and hence it is absolute by Theorem 2.8; thus, there exists a perfect tree T ∈ L[a], T ? N<ω , such that [T ] ? X holds in L[a]. However, the formula [T ] ? X is absolute as well. Lemma 4.5 enables one to prove another result revealing the nature of the version 1 PK? (Π1 (a)) of the perfect kernel hypothesis (subsection 3G). 1 Corollary 4.7. If a ∈ Nω , then PK? (Π1 (a)) ?? (Nω ? L[a]).

    Proof. The implication from left to right was established in Lemma 3.12. To prove 1 the converse implication, suppose that the assertion PK? (Π1 (a)) fails, that is, one ω ω 1 can ?nd a function η : N → N whose graph P is a Π1 (a) set without a perfect kernel. Then P ? L[a] by Lemma 4.5, and hence Nω = dom P ? L[a]. Lemma 4.5 admits other interesting versions and generalizations. We have seen above (Case 2 in the proof of Lemma 4.5) that if R is a ?1 1 (a) sieve, a ∈ ω1 , then L[a] all non-empty constituents Eξ (R) with ω1 ξ < ω1 are uncountable. Some other similar results on ‘distant’ constituents are known. For example, in the above L[a] situation the set Eξ (R) cannot belong to the class Fσ . Generally, if ωα ξ < ω1 and Eξ (R) = ?, then Eξ (R) cannot be a Borel set of level α in the Borel hierarchy (see [93], [36], [40]). The proofs of these theorems are rather too laborious to be presented in this paper and, the main point, are not directly related to the problems discussed here. 4C. Forcing induced by an ideal of Borel sets. We begin the proof of the implications ?= in Theorem 3.9. The principal idea is to ?nd a characterization of random points in terms of forcing. To avoid repetitions, we assume in this subsection that M is a ?xed transitive model of ZFC (for example, the universe V of all sets or a class of the form L[X ]). In the variety of forcings P ∈ M we distinguish those induced by σ-CAC ideals in a natural way. De?nition 4.8. Suppose that I is an M-absolute σ-CAC ideal. By the Borel forcing modulo I we mean the set PI = {p ∈ BC ∩ M : Bp ∈ / I} ordered as follows: p
    23 We write PM I = PI ∩ M.

    q if Bp ? Bq .

    We note that ‘conditions’ p, q ∈ PI are compatible in PI (and in PM I ) if and only if Bp ∩ Bq ∈ / I. Indeed, there is a code c ∈ BC ∩ M such that Bp ∩ Bq = Bc . (To obtain c, we ?rst de?ne codes p and q by the rule (p )n = p, (q )n = q ? n, and thus Bp and Bq are the complements of Bp and Bq , respectively. We now de?ne c in such a way that (c)0 = p and (c)n = q for n 1.) In the non-trivial / I, then c ∈ PI , and of course c p and c q . direction if Bp ∩ Bq ∈ The next lemma shows that PM I is a CAC forcing in M.
    23 Thus, under this de?nition, a forcing consists of codes of Borel sets rather than the Borel sets themselves. If one takes the Borel sets themselves as ‘conditions’, which is often done, then the forcing becomes more intuitive. However, one then faces the fact that a Borel set Bp depends on the universe in which the operation Bp is carried out. For example, if p ∈ M ∩ BC, then Bp di?ers from (Bp )M in general (that is, from the set Bp de?ned in M); in fact, (Bp )M = Bp ∩ M. In our opinion it is generally simpler to deal with codes.

    880

    V. G. Kanovei and V. A. Lyubetskii

    Lemma 4.9. Under the assumptions of De?nition 4.8, the set PM I and the order satis?es the CAC in M , that is , every antichain belong to M. The forcing PM I A ∈ M, A ? PM , is at most countable in M . I Proof. The assertion PM I ∈ M follows readily because I is M-absolute. The relation 1 Bp ? Bq can be expressed by a Π1 formula in view of 1.11(iv). Thus, the ordering M on PI belongs to M by the absoluteness theorem (Theorem 2.8). Finally, the CAC in M follows from the property 3? (with respect to 2?) of the ideal I. Lemma 4.10. Under the assumption of De?nition 4.8, let D ∈ M, D ? PM I , be a dense set in PM . Then there is a set A ∈ M , A ? D , countable in M and such I that the set U = c∈A Bc is I-full. Thus, in this case if x ∈ RandI M, then x ∈ c∈D Bc . Proof. Arguing in M, let us choose a maximal antichain A ? D, A ∈ M. Then A is countable in M by Lemma 4.9. We claim that the set U = c∈A Bc is Ifull. Suppose the contrary: let V = Nω U ∈ / I. Since A is countable, it follows that V = Bp is a Borel set with a code p ∈ M, and hence p ∈ PM I . Since D is dense, there is a ‘condition’ q ∈ D, q p. Since A is maximal, it follows that the ‘condition’ q (and therefore the ‘condition’ p as well) is compatible with some r ∈ A; / I and Bp ∩ Br = ?. However, Br ? U , a contradiction. in particular, Bp ∩ Br ∈ To prove the last part of the lemma, we note that U is a Borel set having a code in BC ∩ M by the choice of A. The forcing PI enables one to use another approach to I-random points, which is based on the following lemma. Lemma 4.11. If a set G ? PM I is generic over M, then there is a unique point πG ∈ Nω satisfying the condition c ∈ G ?? πG ∈ Bc for each c ∈ BC ∩ M. Proof. We set BG = {Bp : p ∈ G}; thus, BG consists of the Borel sets themselves and not their codes. We note that any sets X, Y ∈ BG are compatible, that is, there is a Z ∈ BG such that Z ? X ∩ Y . The set Dn = {p ∈ P : ? s ∈ n 2 (Bp ? Ns )} is dense in P for any n by σ-additivity. It follows that for any n there is a ?nite sequence sn ∈ n 2 (which is unique by compatibility) such that ? p ∈ G (Bp ? Nsn ). Then sn ? sn+1 ? n, and thus there is a unique point πG ∈ Nω satisfying πG n = sn ? n. Let us show that c ∈ G ?? πG ∈ Bc , ? c ∈ BC ∩ M. This equivalence can be proved by induction on ξ , where c ∈ BCξ . The base of induction: ξ = 0. In this case c = k, k ∈ N, and Bc = Nsk . Let n = lh sk . It follows from the pairwise compatibility that c ∈ G ?? sk = tn = πG n ?? πG ∈ Bc . The induction step: let 0 < ξ < ω1 and let the result be valid for any c ∈ η<ξ BCη . By de?nition, Bc = Nω n B(c)n . This readily implies that the set Dc = {p ∈ PM I : Bp ? Bc ∨ ? n (Bp ? B(c)n )} is dense in PM I . Therefore, by the genericity condition, there is a p ∈ G ∩ Dc . Thus, c ∈ G ?? ? n ((c)n ∈ / G), and hence c ∈ G ?? ? n (πG ∈ / B(c)n ) by the induction assumption. However, here the right-hand side is equivalent to πG ∈ Bc.

    On some classical problems of descriptive set theory

    881

    The points of the form πG obtained in this way from PM I -generic sets G are said generic (over M ). to be PM I ? of the pair z = x, y . (UnforLet us denote by ? x, y the canonical PM I -name z tunately, this name di?ers from x ?, y ? .) By the canonical name for a PM I -generic M point we mean the PI -name π = { p, ? n, j : p ∈ PM I ∧ n, j ∈ N ∧ ? y ∈ Bp (y(n) = j )} ∈ M.

    This name certainly depends on I and M, but we do not indicate this dependence explicitly, because both the ideal and the ground model under consideration will always be clear from the context. Then πG = π[G] for any set G ? PM I which is generic over M. Thus, under the assumptions of De?nition 4.8, it follows from Lemma 4.11 that πG is the only point in the intersection p∈G Bp = BG , and BG = {c ∈ BC ∩ L[a] : πG ∈ Bc }. This implies that M[G] = M[πG]. Lemma 4.12. The points PM I -generic over M are exactly the elements of the famM[x] M ily RandI M. Hence, if x ∈ RandI M, then ω1 = ω1 . Proof. Let us consider a set G ? PM I which is generic over M. If c ∈ BC and Bc ∈ I, then c ∈ / G, and hence πG ∈ / Bc by Lemma 4.11. Therefore, πG ∈ RandI M. Conversely, if x ∈ RandI M, then the set Gx = {c ∈ BC ∩ L[a] : x ∈ Bc } is M PM I -generic over M by Lemma 4.10. (The relation Gx ? PI follows directly from the choice of x.) The last assertion of the lemma follows from Theorem 4.2(i) and Lemma 4.9. We recall that forcing is connected with truth in generic extensions by Theorem 4.3(ii). In our case it turns out that forcing of quite simple formulae is connected with truth in the ground model as well.
    1 1 or a Π1 formula with parameters in Lemma 4.13. Suppose that ?(x) is a Σ1 ω M ∩ N and that ? ? is obtained from ? by replacing every parameter z ∈ Nω by the M PM ?. Let p ∈ PM ?(π ) if and only if the set X = {x ∈ Bp : I -name z I . Then p PM ? I ??(x)} is I-null in M.

    Proof. If X is an I-null set, then we assume that c ∈ BC ∩ M satis?es the conditions Bc ∈ I and X ? Bc in M. By the choice of ? (Proposition 1.11(iv) is also used), the relation X ? Bc can be expressed by a formula of type not higher than 1 Π2 . Therefore, x ∈ / Bc =? ?(x) for any x ∈ Bp in every extension of M, by the absoluteness theorem (Theorem 2.8). However, πG ∈ Bp for any generic set G ? PM I containing p. To prove the converse, suppose that X is not I-null. Then by Theorem 3.7, there is a condition q ∈ BC ∩ M such that Bq ∈ / I and Bq ? X in M. In this case q ∈ PM I and q p. Moreover, it follows from the same considerations as above that q forces ?? ?(π), and hence p cannot force ? ?(π). 4D. Two examples. Let us take I to be the ideal Icat of meagre Borel sets or the ideal Iλ of Borel sets of λ-measure zero. (Some other examples will be discussed in subsection 9C.) We obtain two special forcings connected with the problems of

    882

    V. G. Kanovei and V. A. Lyubetskii

    the Baire property and measurability: Cohen forcing : Pcoh = PIcat = {p ∈ BC ∩ M : Bp is a non-meagre set}; random forcing :24 Pλ = PIλ = {p ∈ BC : λ(Bp ) > 0}. M M M Accordingly, PM coh = Pcoh ∩ M = PIcat and Pλ = Pλ ∩ M = PIλ . We recall that λ is a measure on Nω (in fact, on 2ω ) introduced in subsection 1B. Corollary 4.14. Coh M = {all PM coh -generic points over M}. Rand M = {all PM λ -generic points over M}. It should be noted that Cohen forcing is usually associated with another partially ordered set, namely, the set C = N<ω ordered in such a way that s t (s is stronger) if t ? s. However, let us show that C and Pcoh produce the same generic extensions. One can readily de?ne a recursion function h : (Nω )2 → Nω such that h(p, q ) ∈ BC and Bp ∩ Bq = Bh(p,q) whenever p, q ∈ BC. By Proposition 1.11(vi), this implies that if the symmetric di?erence Bp Bq is a meagre set (p, q ∈ BC), then 1 relation, and thus its restriction to PM the binary relation p ≈ q is a Σ2 coh belongs to M. On the other hand, if p ≈ q belongs to PM , then the set coh D = {r ∈ PM coh : Br ? Bp ∩ Bq ∨ Br ∩ (Bp ∪ Bq ) = ?} is dense in PM coh (and belongs to M). We conclude that the equivalence p ∈ G ?? M q ∈ G holds for any PM coh -generic set G over M. Thus, the Pcoh -generic extensions M of M coincide with the P-generic extensions, where P = Pcoh /≈, with the order given by [p]≈ [q ]≈ if Bp Bq is a meagre set. For any s ∈ 2<ω = C we choose in M a code ps ∈ BC ∩ M such that Bps = Ns . Then the map s → [ps ]≈ is an order isomorphism between C and a dense subset of P. (We use the fact that every non-meagre Borel set X ? Nω is co-meagre on some Baire interval Ns .) It remains to apply Theorem 4.2(ii). The random forcing is also usually identi?ed with closed sets (rather than Borel sets) of positive measure. (See subsection 8D below.) The reason is quite clear, namely, each Borel set of positive measure contains a closed subset of positive measure. We note that the well-known Sacks forcing [82] also can be represented in the form PI , where I is the ideal of all at most countable sets, though I is not a σ-CAC ideal, of course. 4E. If there are few non-random points, then all sets of the second projective level are measurable. Here we prove the implications ?= in Theorem 3.9, and thus in the equivalences (ii)–(v) of Theorem 3.3 and (II)–(V) of Corollary 3.4 (see Remark 3.10). The results use the following assertion. Lemma 4.15. Suppose that a ∈ Nω and that I is an L[a]-absolute σ-CAC ideal. 1 For any Σ2 (L[a]) set X ? Nω there is a Borel set U ? Nω with a code in L[a] such that X ∩ RandI L[a] = U ∩ RandI L[a] and U X is an I-null set.
    1 Proof. Let X = {x ∈ Nω : Γ(x, z )}, where z ∈ L[a] ∩ Nω , Γ is a Σ2 formula 1 ? y ?(x, z, y), and ? is a Π1 formula. Then

    x ∈ X ?? Γ(x, z ) is true in L[x, a] ?? ? ξ < ω1
    24 In

    L[a,x]

    (x ∈ Xξ )

    (1)

    other terms, Solovay forcing.

    On some classical problems of descriptive set theory

    883

    by Theorems 2.8 and 2.6(i), where Xξ = {x : ?(x, z, fξ[x?a])} and x?a stands for the ‘junction’ of x and a, that is, (x?a)(2k ) = x(k ) and (x?a)(2k + 1) = a(k ). The L[a,x] L[a] = ω1 of Lemma 4.12 enables one to improve this result as follows: equality ω1 for any x ∈ RandI L[a] : x ∈ X ?? ? ξ < ω1
    L[a]

    (x ∈ Xξ ).

    (2)

    Let γ (w, x, a, z ) be the formula ? y ?(w, x?a, y) =? ?(x, z, y) , where ? is the 1 formula provided by Theorem 2.6(ii), and thus we have Xξ = {x : γ (w, x, a, z )} Σ1 whenever w ∈ WOξ . We set Xξ = Xξ ∩ L[a]. We argue in L[a]. Let us de?ne C and I as in 3? in subsection 3E for M = L[a]. Then Xξ = {x : γ (w, x, a, z )} (in L[a]) whenever ξ < ω1 and w ∈ WOξ by the absoluteness theorem (Theorem 2.8). Therefore, all the sets Xξ are Π1 1 sets. Thus, each set Xξ is I -measurable by Theorem 3.7, and hence there are codes cξ ∈ BC and dξ ∈ C such that Xξ Bcξ ? Bdξ ; in other words, Bcξ Bdξ ? Xξ ? Bcξ ∪ Bdξ . However, the ideal I satis?es condition 2? in L[a] (by the property 3? of the L[a] ideal I). It follows that there is an ordinal ? < ω1 such that Bcξ ( η<? Bcη ) ∈ I for any ξ ?. We argue in the universe of all sets. We write Uξ = Bcξ and Dξ = Bdξ . Then Dξ ∈ I. Applying the absoluteness theorem to the corresponding formulae, we L[a] see that Xξ Uξ ? Dξ for any ξ < ω1 , and Uξ U ∈ I for any ξ ?, where U = η<? Uη is obviously a Borel set with a code in L[a]. Then RandI L[a] ∩ Xξ = RandI L[a] ∩ Uξ by the de?nition of RandI L[a] for any ξ < ω1 , and L[a] RandI L[a] ∩ Uξ ? U for ? ξ < ω1 . The equality (X U ) ∩ RandI L[a] = ? follows now from (2), and U X ? η<? Uη Xη ? η<? Dη , which means that U is the desired set. We can now prove the implications ?= in Theorem 3.9. For convenience of the references we state the result as a separate corollary. Corollary 4.16. (a) Under the assumptions of Lemma 4.15, if RandI L[a] is an I1 full set, then all Σ2 (L[a]) sets X ? Nω are I-measurable ; (b) under the assumptions of Lemma 4.15, if RandI L[a] ∩ Bc = ? for every Borel set Bc ∈ / I with a code in ω L[a], then all ?1 2 (L[a]) sets X ? N are I-measurable. Proof. (a) It follows from Lemma 4.15 that there is a Borel set U such that X ∩ RandI L[a] = U ∩ RandI L[a]. If RandI L[a] is I-full, then X is I-measurable because the Borel set U is. 1 (b) Let us consider a pair of mutually complementary Σ2 (a) sets X, Y ? Nω . ω Lemma 4.15 gives us Borel sets U, V ? N with codes in L[a] such that X ∩ RandI L[a] = U ∩ RandI L[a] and Y ∩ RandI L[a] = V ∩ RandI L[a], and the sets U X and V Y are I-null. It remains to show that the complement C = Nω (U ∪ V ) of U ∪ V is an I-null set. Suppose the contrary; let C ∈ / I. We note that C is also a Borel set with a code in L[a], and hence under our assumptions there exists a point x ∈ RandI L[a] ∩ C . Since the sets X and Y are mutual complements, it follows that x belongs to one of them, say X . Then x ∈ U by the choice of U , a contradiction. (Theorems 3.9 and 3.3 and Corollary 3.4) If we ignore the condition that U a far-reaching generalization. X is an I-null set, then Lemma 4.15 admits
    L[a]

    884

    V. G. Kanovei and V. A. Lyubetskii

    Theorem 4.17. Under the assumptions of Lemma 4.15, for any ∈-formula ?(x) with parameters in L[a] there is a Borel code c ∈ BC ∩ L[a] such that the equivalence “?(x) is true in L[a, x] ?? x ∈ Bc” holds for any x ∈ RandI L[a]. In other words, any set of the form X = {x ∈ Nω : ?(x) is true in L[a, x]}, where ? has parameters only in L[a], coincides with some Borel set with a code in L[a], modulo points that do not belong to RandI L[a]. For instance, this holds for 1 1 (a) or Π2 (a), because the corresponding formulae are absolute any set X in Σ2 for L[a] by the absoluteness theorem (Theorem 2.8). Some other applications of this theorem will be discussed below. Proof. We assume that ? is ?(z, x) with the single parameter z ∈ L[a]. (The case of several parameters can readily be reduced to this case.) We recall that π ∈ L[a] is a L[a] L[a] PI -name such that πG = π[G] for any generic set G ? PI (see subsection 4C). L[a] Let stand for the relation of PI -forcing over L[a]. By Theorem 4.3(iii), the set D = {p ∈ PI
    L[a] L[a]

    :p

    ?(? z , π) or p

    ??(? z , π)}

    and belongs to L[a]. By Lemma 4.10, there is a countable set is dense in PI {pn : n ∈ N} ∈ L[a] of conditions pn ∈ D such that n Bpn is an I-full set. We write u = { n : pn ?(? z , π)} and v=N u = { n : pn ??(? z , π)}.

    Obviously, there exist Borel codes c, c ∈ BC ∩ L[a] such that Bc = n∈u Bpn and Bc = Nω Bc = n∈v Bpn . We claim that c is a desired code. Let x ∈ RandI L[a]. Then x ∈ Bc ∪ Bc . If x ∈ Bc , then x ∈ Bpn for some n ∈ u. On the other hand, L[a] it follows from Lemma 4.12 that x = πG for some set G ? PI which is generic L[a] over L[a]; in fact, G = Gx = {p ∈ PI : x ∈ Bp }. Thus, pn ∈ G = Gx . Therefore, by the de?nition of forcing, the formula ?(? z [G], π[G]) (that is, ?(z, x)) is true in L[a, G] = L[a, x]. Similarly, if x ∈ / Bc, then x ∈ Bc , and the formula ?(z, x) is false in L[a, x]. Historical and bibliographical remarks. Cohen’s method of forcing [15] is perhaps the most important tool in set theory. We recommend [87], [29], [11], Chap. 5, as well as [10], [44], [30] in English as basic references concerning forcing and Theorems 4.1–4.3. Our references to Theorems 3.3 and 3.9 (and Corollary 3.4), whose proofs were begun in § 3 and completed in subsections 4B and 4E, were given in the historical and bibliographical remarks to § 3. The forcing PI for the ideal of sets of measure zero and for the ideal of meagre sets was introduced by Solovay [89], together with the notions of random and Cohen points and the basic constructions in subsections 4C–4E, in particular, including Theorem 4.17. For the equivalence of the two de?nitions of Cohen forcing (subsection 4D), see [89]; however, the arguments there are di?erent. § 5. Combinatorics of eventual domination This short section contains several results connecting the regularity properties of sets at the second projective level with properties of a special partial order relation

    On some classical problems of descriptive set theory

    885

    on Nω that belongs to the family of eventual relations. This family consists of relations characterized by the requirement that some property holds for almost all25 positive integer values. Let f and g be functions with dom f = dom g = ω. We recall the following de?nitions: f ? g means that f (n) g(n) for almost all n ∈ ω. (Here it is assumed that f and g take values in a ?xed ordered set, for example, N or R.) f ?? g means that f (n) ? g(n) for almost all n ∈ ω. f ∈? g means that f (n) ∈ g(n) for almost all n ∈ ω. The relation ? of eventual domination 26 on sets of type Nω or Rω is of special interest. In particular, each ? -increasing ω-sequence {fn }n∈ω of fn ∈ Nω is ? bounded. Indeed, we set f (k ) = supn k fn (k ). Then fn ? f ? n. (This assertion fails for ordinary domination, of course, that is, for the relation f g given by the rule f (n) g(n) for all n.) 1 As an application we prove Theorem 5.4 claiming that LM(Σ1 2 ) implies BP(Σ2 ); however, the proof of this theorem involves some ideas related to Theorem 3.3. The results of this section will be used in the study of regularity properties in some complicated generic models in § 8. 5A. Eventual domination and measurability. We show here how the hypoth? esis LM(Σ1 on the set 2 ) is connected with order properties of
    1

    =

    x ∈ Qω + :
    n∈ω

    x(n) < ∞

    (where Q+ = {q ∈ Q : q 0} stands for the set of non-negative rational numbers). We also consider the family S of all functions ?, ω = dom ?, taking values in the #?(n) family of ?nite sets and satisfying the condition n ( n+1)2 < ∞. We call these functions slow (that is, slowly increasing); the symbol #s stands for the number of elements in a ?nite set s. Theorem 5.1 ([9] or [10], § 2.3). LM(Σ1 2 ) ?? (i) ?? (ii), where ω ? (i) ? a ∈ N ? ? ∈ S (x∈ ? for any x ∈ L[a] ∩ Nω ), (ii) ? a ∈ Nω ? f ∈ 1 (x ? f for any x ∈ 1 ∩ L[a]). Proof. LM(Σ1 ? (i). We ?x some a ∈ Nω . Let i, j → nij be a recursive 2) = 2 bijection from N onto N. Let us consider the probability measure ? on 2ω de?ned in such a way that every set Aij = {u ∈ 2ω : u(nij ) = 1} satis?es the condition ?(Aij ) = (i + 1)?2 and these sets are jointly independent with respect to ? (that Ai j ) = ?(Aij ) ?(Ai j ) (1 ? ?(Ai j )).) We set is, for instance, ?(Aij ∩ Ai j Gx = lim supi→∞ Ai,x(i) for any x ∈ Nω .27 Since i(i + 1)?2 < ∞, it follows that ?(Gx ) = 0 (by the Borel–Cantelli lemma). By Theorem 3.3, it follows from the assumption LM(Σ1 2 ) that λ(Rand L[a]) = 1. Hence, ?(Rand? L[a]) = 1 (Lemma 3.2(3)). Thus, there is a closed set B = [T ] ? 2ω
    25 “Almost 26 In

    all” means all but ?nitely many. the Russian literature, “?nal domination”. 27 We recall that lim sup n∈N Xn = n m n Xm .

    886

    V. G. Kanovei and V. A. Lyubetskii

    of positive ?-measure such that B ∩ Gx = ? for all x ∈ L[a] ∩ Nω , where T ? 2<ω is a perfect tree. One can assume that ?(Cs ∩ B ) > 0 for all s ∈ T (recall that Cs = {u ∈ 2ω : s ? u} is a Cantor interval in 2ω ). We claim that the set ?s (i) = {j : B ∩ Cs ∩ Aij = ?} is ?nite for all s ∈ T and i ∈ N. Indeed, if j ∈ ?s (i), then B ∩ Cs ? 2ω Aij . Hence, since the sets Aij , j ∈ ?s (i), are independent with respect to the measure and each of them has the same measure (i + 1)?2 , we would have ?(B ∩ Cs ) = 0 if ?s (i) were in?nite. We now claim that every ?s is a slow map. To prove this, we note that the set B ∩ Cs of positive measure is disjoint from Aij for any i ∈ N, j ∈ ?s (i). Therefore, (i + 1)?2 =
    i∈N, j ∈?s (i) i

    #?s (i) <∞ (i + 1)2

    again by the Borel–Cantelli lemma. We claim further that there is a unique function ? ∈ S such that ?s ?? ? for all s ∈ T . Indeed, for any k the function ?k (i) =
    s∈T , lh s k

    ?s (i),

    is obviously slow, together with all the functions ?s . Therefore, there is an increasing sequence of natural numbers m0 < m1 < m2 < · · · such that 1 #?k (i) 1.

    mk

    i<mk+1

    It remains to de?ne ?(i) = ?k (i) for mk i < mk +1 . Let us prove that ? is the desired function. Let x ∈ L[a]. Since B ∩ Gx = ?, there exist s ∈ T and i0 such that B ∩ Cs ∩ ( i i0 Ai,x(i) ) = ?. This means that x(i) ∈ ?s (i) for i i0 , and hence x∈??s ?? ?, as was to be proved. (i) =? (ii). We ?x an a ∈ Nω . For any f ∈ 1 there is a function yf ∈ L[a] ∩ Nω such that k yf (n) f (n) 2?n . Let us choose ? according to (i) and then set y(n) = sup ?(n). Thus, y ∈ Nω and yf ? y for any f ∈ 1 ∩ L[a]. For any f ∈ 1 ∩ L[a] we now de?ne f (n) = f [y(n), y(n + 1)), and therefore f (n) is a ?nite sequence of rational numbers. Thus, applying (i) to the set ? 1 ∩ L[a, y], we ?nd a function ? ∈ S satisfying f ∈ ? for each f ∈ 1 ∩ L[a]. #?(n) Then n (n+1)2 < ∞, and one can assume that #?(n) (n + 1)2 for any n. Moreover, using the special form of the functions f , we can assume that ?(n) consists of functions s : [y(n), y(n+)) → Q+ such that y(n) i<y(n+1) s(n) 2?n . i < y(n + 1). Under our assumptions, We set h(i) = sups∈?(n) s(i) for y(n) 2 ?n < ∞, and thus h ∈ 1 . i h(i) n s∈?(n) y (n) i<y (n+1) s(n) nn 2 ? On the other hand, f h for any f ∈ 1 ∩ L[a]. (ii) =? LM(Σ1 2 ). We begin with the following lemma.

    On some classical problems of descriptive set theory

    887

    Lemma 5.2. If X ? 2ω , λ(X ) = 0, and εn ∈ R with εn > 0 for all n ∈ N, then there is a sequence of open-closed sets Cn ? 2ω such that λ(Cn ) < εn and X ? lim supn Cn . Proof. First, there is a system of Cantor intervals Ikl ? 2ω with X ? k l Ikl and l λ(Ikl ) < ε0 2?k ?1 ? k . We index the intervals: let {Jn : n ∈ N} = {Ikl : k , l ∈ N}. Then n λ(Jn ) < ε0 and X ? lim supn Jn . We now set kn = min k : m k λ(Jm ) εn and Cn = kn k<kn+1 Jk for any n. This proves the lemma. (Lemma 5.2) Continuing the proof of the theorem (the implication (ii) =? LM(Σ1 2 )), we take an arbitrary a ∈ Nω and show that λ(Rand L[a]) = 1. This is su?cient by Theorem 3.3. Let {Xξ : ξ < ω1 } be the family of all Borel sets of λ-measure zero that have codes in L[a]. We must prove that λ( ξ Xξ ) = 0. Let us ?x a recursive indexing {Cn : n ∈ N} of all open-closed subsets of 2ω . Using Lemma 5.2 in L[a], we can ?nd for any ξ < ω1 a function xξ ∈ L[a] ∩ Nω such that Xξ ? lim supn Cxξ (n) and λ(Cxξ (n)) < 2?n for any n. We set fξ (k ) = λ(Ck ) if k ∈ ran xξ = {xξ (n) : n ∈ N} and fξ (k ) = 0 otherwise. All functions fξ belong to 1 ∩ L[a], and hence, by the assumption (ii), there is a function f ∈ 1 such that fξ ? f ? ξ . We set K = {k : f (k ) λ(Ck )}. Suppose that x ∈ Nω enumerates all the elements of K in increasing order. We claim that Xξ ? X = lim sup Cx(n) ? ξ,
    n

    and

    λ(X ) = 0.

    First, n λ(Cx(n)) = k ∈K λ(Ck ) k f (k ) < ∞ (because f ∈ 1 ), and hence λ(X ) = 0 by the Borel–Cantelli lemma. Further, if z ∈ Xξ , then the set Kξ = {k ∈ ran xξ : z ∈ Ck } is in?nite, and λ(Ck ) = fξ (k ) f (k ) for almost all k ∈ Kξ . Thus, the set {k ∈ K : z ∈ Ck } is in?nite by the de?nition of K . This implies that z ∈ X , as was to be proved. (Theorem 5.1) 5B. Eventual domination and the Baire property. Among several known results relating to BP(Σ1 2 ) and similar to Theorem 5.1 (see the survey in [10], 2.2 and 2.4), the following theorem ([10], 9.3.3) is the most useful here. This theorem combines several separate earlier results, in particular, those in [96]. A set X ? Nω is said to be ? -bounded if there is an h ∈ Nω such that ? x ∈ X (x ? h). (Boundedness of X is obviously equivalent to the possibility of covering X by a σ-compact set.)
    1 Theorem 5.3. Assume BP(?1 2 ). Then BP(Σ2 ) is equivalent to the statement that ω ω ? every set of the form L[a] ∩ N , a ∈ N , is -bounded in Nω . ω Proof. Suppose that BP(Σ1 2 ) holds and consider an arbitrary a ∈ N . The set ω Coh L[a] is co-meagre by Theorem 3.3. For f ∈ N we set f (k ) = 1 + maxi k f (i) ? k , and Φ(f ) = {x ∈ Nω : x ? f }. The last set is meagre for any f . In addition, this is a Borel set with a code in L[a] for any f ∈ L[a]∩Nω , that is, Φ(f )∩Coh L[a] = ? in this case. Hence, there is an Fσ set Z = n Zn ? Nω such that any Zn is a

    888

    V. G. Kanovei and V. A. Lyubetskii

    closed nowhere dense set and Φ(f ) ? Z for any f ∈ L[a] ∩ Nω . Using this set, we de?ne a number kn ∈ N and an sn ∈ N<ω by induction on n. We set k0 = 0. If kn has already been constructed, then there is an s ∈ N<ω for which Nt ∧ s ∩ Zj = ? whenever j n, and t ∈ N<ω is such that lh t = kn and ran t ? [0, kn). For sn we take any number s of this kind and set kn+1 = kn + 1 + lh sn + max sn (i),
    i<lh sn

    which completes the induction step of constructing sn and kn . We now set h(n) = maxi<lh sn sn (i) ? n, and claim that x ? h for any x ∈ L[a] ∩ Nω . Suppose the contrary: let the set A = {n : x(n) > h(n)} be in?nite. Let A = {an : n ∈ N} be an indexing in increasing order. We set z = u0 ∧ sa0 ∧ u1 ∧ sa1 ∧ · · · ∧ un ∧ san · · · , where un is a sequence of kan ? j<n kaj ? j<n lh saj zeros, and hence every block san is preceded by exactly kan numbers. This implies that z ∈ / Z = n Zn by the de?nition of sn . To arrive at a contradiction, it remains to prove that z ∈ Φ(x), in other words, z ? x . By construction, every z (i) is either zero or a number of the form saj (l), where kaj i. In the latter case we have z (i) h(aj ) x(aj ) x (i), as was to be proved. ω Conversely, suppose that BP(?1 2 ) holds and every set of the form L[a] ∩ N , ω ? ω ω a ∈ N , is -bounded in N . Let us ?x an a ∈ N and prove that the set Coh L[a] is co-meagre; this is su?cient for the validity of LM(Σ1 2 ) by Corollary 3.4. To begin with, we note that Coh L[a] = ?, again by Corollary 3.4. Let us ?x an arbitrary element b ∈ Coh L[a]. Let T be the set of all trees T ∈ M, T ? N<ω , such that [T ] is a nowhere dense (closed) subset of Nω and T has no ?-maximal elements. Then b ∈ / T ∈T [T ], because the union coincides with the complement of Coh L[a]. (Indeed, any meagre set can be covered by a union of countably many nowhere dense closed sets, and the notions used are absolute by Theorem 2.8 and Proposition 1.11(vi).) Further, the set X of all x ∈ Nω such that x(n) = b(n) for almost all n is countable. Let X = {xn : n ∈ N} be an indexing of the elements of X in L[a, b]. It follows from what was said above that X ∩ [T ] = ? for each T ∈ T . We denote by hT (n) the smallest k such that the Baire interval Nxn k is disjoint from [T ]. Thus, hT ∈ L[a, b] ∩ Nω . However, under our assumptions the set L[a, b] ∩ Nω is ? -bounded, that is, there is a point z ∈ Nω such that hT ? z for each T ∈ T . Hence, the dense Gδ set G = m n m Nxn z(n) is disjoint from [T ] for T ∈ T . In other words, G is included in Coh L[a]. 5C. In the class Σ1 2 measurability implies the Baire property. Here we prove the following theorem.
    1 Theorem 5.4 (Raisonnier and Stern [80]). LM(Σ1 2 ) implies BP(Σ2 ).

    We show below that the converse implication fails, a clear violation of the duality between the properties of measure and category which is observed in many

    On some classical problems of descriptive set theory

    889

    other cases. On the other hand, the theorem cannot be regarded as a connection between measure in general and category in general. Indeed, the assertion of the 1 theorem fails, for instance, for the classes ?1 2 and ?3 (see below) and thus is in fact 1 a speci?c feature of the class Σ2 .
    ω Proof. Assume LM(Σ1 2 ) and ?x an arbitrary a ∈ N . Then λ(Rand L[a]) = 1 by Theorem 3.3. We must prove that Coh L[a] is a co-meagre set, in other words, that the union of all nowhere dense closed subsets of Nω with a code in L[a] is a comeagre set. Since 2ω contains a dense Gδ set (with a recursive code) homeomorphic to Nω , it su?ces to prove the claim for the space 2ω instead of Nω . Let M be the family of all closed nowhere dense sets C ? 2ω with code in L[a]. (By a code of a closed set X ? 2ω we mean the tree TX = {u n : u ∈ X ∧ n ∈ N} ? 2<ω .) Thus, let us prove that the union of all the sets C ∈ M is a meagre set in 2ω . By Theorem 5.1, there is a function ? ∈ S such that x∈? ? (that is, x(n) ∈ ?(n) 1 for almost all n) for each x ∈ L[a] ∩ Nω . We claim that n #? (n) = ∞. Indeed, #?(n) 1 let us write U = {n : #?(n) n + 1}. Then n∈U n+1 n∈U (n+1)2 < ∞, and 1 1 therefore n∈ / U n+1 = ∞ and n #?(n) = ∞, as was to be proved. Our ?nal objective is to get from ? a dense Gδ set disjoint from every C ∈ M . This requires some additional work. First of all, if C ∈ M and n ∈ N, then there exist a number k > n and a function σ ∈ [n,k )2 such that the set Cs ∧ σ = {u ∈ 2ω : s ∧ σ ? u} is disjoint from C for any s ∈ n 2. (This argument would not work for the space Nω !) We denote by kC (n) and σC (n) the smallest number k > n and the lexicographically ‘leftmost’ function σ ∈ [n,k )2 of the above form. The set NσC (n) = {u ∈ 2ω : σC (n) ? u} is still disjoint from C . Clearly, if C has a code in L[a], then kC ∈ L[a]. Therefore, by Theorem 5.1, there is a function ψ ∈ S such that kC ∈? ψ for each C ∈ M . Then the function g(i) = 1 + maxi i max ψ(i ) ? i, satis?es kC ? g for all C ∈ M . We note that g is an increasing positive function. We set e0 = 0 and go on with el+1 = g(el ) by induction on l. Let C ∈ M . For any l, if el+1 kC (el ) (this is the case for almost all l, because g eventually dominates kC ), then there is a τ ∈ [el ,el+1 ) 2 such that Cτ ∩ C = ?. We denote by τC (l) the ‘leftmost’ function τ ∈ [el ,el+1 ) 2 with this property. If el+1 < kC (el ), then, to be de?nite, let τC (l) consist of zeros only. Thus, τC maps N into the (countable) set Σ = n<k ∈N [n,k )2.

    Lemma 5.5. There is a function h : ω → Σ such that the set {l : τC (l) = h(l)} is in?nite for any C ∈ M . Proof of the lemma. Again by Theorem 5.1, there is a function η ∈ S such that τC ∈? η holds for any C ∈ M . One can assume that η (l) ? [el ,el+1 ) 2 ? l. Let us equip the space ? = l∈ω η (l) with a measure ν which is the product of the uniform probability measures on the (?nite) sets η (l). We set Aσ l = {w ∈ ? : w (l) = σ } for any l ∈ N and σ ∈ ?(l). These sets are obviously independent with respect to the v (l) ?1 measure ν ; moreover, if v ∈ ?, then l ν (Al ) = l η (l) = ∞, because η ∈ S. v (l) By the Borel–Cantelli lemma, the set Xv = lim supl∈N Al has full ν -measure. ω Let us now take an a ∈ N such that both a (see the beginning of the proof of the theorem) and η belong to L[a]. Then τC ∈ L[a ] for any C ∈ M . In our assumptions, Rand L[a ] = ?, and therefore Randν L[a ] = ? by Lemma 3.2(3).

    890

    V. G. Kanovei and V. A. Lyubetskii

    Thus, there is an h ∈ ? belonging to each of the sets Xv , v ∈ ? ∩ L. This means that the set {l : h(l) = v(l)} is in?nite for any v of this kind, that is, h is the desired function by the choice of η . (Lemma 5.5) To complete the proof of Theorem 5.4, we consider a function h given by the lemma. According to the de?nition of τC , we can assume that h(l) ? [el ,el+1 ) 2 ? l. Let us take a point z ∈ 2ω de?ned by the condition z [el , el+1 ) = h(l) ? l. Let Z = {zn : n ∈ N} be the (countable) set of all z ∈ 2ω such that z (k ) = z (k ) for almost all k . Then it follows from the de?nition of τC and z and from the choice of h that Z ∩ C = ? for any C ∈ M . Thus, for any pair formed by some C ∈ M and some n there is an index j such that Czn j ∩ C = ?; let jC (n) be the smallest index j with this property. Then every function jC , C ∈ M , belongs to L[a, z ], and hence, as above, there is a point r ∈ Nω eventually dominating every function jC , C ∈ M , that is, jC ? r. We write Yn = Czn r(n) . Then the Gδ set U = lim supn Yn is dense in 2ω (here the denseness of Z is important) and is disjoint from any set C ∈ M. (Theorem 5.4) Historical and bibliographical remarks. The relation ? of eventual domination goes back to old papers of Du Bois Reymond in the 1870s (see, for instance, [18]), where it was used to study the comparative rate of growth of in?nite sequences. Hausdor? [22] proved for this relation his famous (ω1 , ω1 )-gap theorem (which was re-proved in [24] and in fact became known from this new proof, because the paper [22] was obviously ahead of its time and moreover was published in a little-known provincial journal). Starting from the 1960s, the relation ? (together with some similar relations including almost disjointness of sets of natural numbers) became the topic of numerous investigations (see, for instance, the surveys [16], [71]). § 6. ‘Elementary’ proof of one of the theorems Let us return to the results indicated by the non-trivial implications in the diagram in the Introduction. Obviously, these results express propositions of a purely descriptive set-theoretic nature and are related to properties of point sets (in contrast to, say, the equivalences in Theorems 3.3 and 3.9 in which some notions related to G¨ odel constructibility are involved). On the other hand, the arguments forming the proofs of these assertions (that is, the proofs above of Theorems 3.3 and 3.9) invoke objects (like arbitrary ordinals and constructible sets) and methods (like forcing) which are beyond the framework of objects naturally considered in descriptive set theory, where the latter objects include: ( ) natural numbers and real numbers, countable ordinals, points of Nω , Polish spaces in general and their points, projective and especially Borel subsets of Polish spaces, countable and trans?nite (of length ω1 ) ‘e?ective’ sequences of points and of projective (or Borel) sets (for example, those arising in the de?nition of constructible sets up to the step ω1 ), as well as simple combinations of these concepts.

    On some classical problems of descriptive set theory

    891

    For example, let us consider the following theorem, which is one of the two implications in the diagram in the Introduction that come out of the block 28 PK(Π1 1 ).
    1 Theorem 6.1 (Lyubetskii’s theorem). PK(Π1 1 ) implies LM(Σ2 ).

    The question of whether or not this theorem can be proved within the framework of the notions listed in ( ) is of interest and importance from the point of view of the philosophy and methodology of mathematics. In this sense it can be compared, for instance, with the question of whether Fermat’s Last Theorem can be re-proved by methods of elementary number theory. If we seek a proof of Theorem 6.1 in the even more restricted framework of classical descriptive set theory as it was in Luzin’s times, then the question remains open. The problem of eliminating the constructibility and forcing from the proof of Theorem 6.1 remains unsolved. However, one can achieve the more modest goal of modifying the arguments in § 3 and § 4, including the use of forcing, so as to essentially keep within the framework of ( ). This section presents such a modi?cation based of some ideas outlined in [69]. We call the proof below ‘elementary’, because here this term refers to restrictions concerning the tools used in the proof rather than to the complexity of the arguments. In fact, this proof is somewhat more complicated, because we are to verify basic properties of forcing in a new situation, properties established long ago in the standard presentation. 6A. Analysis of the proof. The proof of Theorem 6.1 can be obtained from the following parts, which are fragments of the proofs of Theorems 3.3 and 3.9 in §§ 3, 4: Part 1: the implication PK(Π1 ? ? a ∈ Nω (L[a] ∩ Nω countable), which 1) = was proved (in a more e?ective form) in subsection 3C; Part 2: the implication ? a ∈ Nω (L[a] ∩ Nω countable) =? λ(Rand L[a]) = 1; 1 Part 3: the implication that if a ∈ Nω and λ(Rand L[a]) = 1, then all Σ2 (a) sets are λ-measurable. This is the special case I = Iλ of Corollary 4.16. In principle, Part 1 satis?es the requirement of staying within the framework indicated in ( ). (The G¨ odel construction is used only up to the step ω1 .) Part 2 is entirely trivial. However, Part 3 employs forcing, which essentially goes outside the framework of ( ) in the standard presentation, for example, because it involves true classes of sets, in particular, classes of the form L[a] and their generic extensions. Thus, our objective is to prove Corollary 4.16 in the framework of the objects in the list ( ). 6B. Descriptive continua. To begin with, we need a type of structures in ( ) which can adequately enough replace transitive models of ZFC (for example, the classes L[a]) as ground models for generic extensions. By a descriptive continuum we mean any set M ? Nω such that the structure N; M is an L[a]-model of secondorder arithmetic. This includes the following three requirements.
    28 The text below can be applied also to the other implication PK(Π1 ) = ? BP(Σ1 1 2 ) with minor changes, which we omit for lack of space.

    892

    V. G. Kanovei and V. A. Lyubetskii

    Comprehension: if ?(k, l, x1 , . . . , xn ) is an analytic formula (as in subsection 1C), a1 , . . . , an ∈ M, and { k, l : ?M (k, l, a1 , . . . , an )} is the graph of an (everywhere de?ned) function b : N → N, then b ∈ M. Countable dependent choice: if ?(y, z, x1 , . . . , xn ) is an analytic formula, a1 , . . . , an ∈ M, and ? y ∈ M ? z ∈ M ?M (y, z, a1 , . . . , an ), then there is a b ∈ M such that ? k ?M ((b)k , (b)k +1 , a1 , . . . , an ). Absoluteness of well ordering: if w ∈ M WO, that is, Qw = {qn : w(n) = 0} is not a well-ordered subset of Q (in the notation of Example 1.10.1), then there is an a ∈ M encoding a decreasing sequence in Qw in the sense that a(n) ∈ Qw and qa(n+1) < qa(n) for all n. In these de?nitions ?M stands for the relativization of the formula ? to M, that is, every quanti?er ? x and ? x (which means ? x ∈ Nω and ? x ∈ Nω ) is changed to ? x ∈ M and ? x ∈ M, respectively. For example, Nω itself is a descriptive continuum, as well as any set of the form M ∩ Nω , where M is a transitive model of ZFC theory or at least of ZFC? theory (without the power set axiom). Conversely, if M ? Nω is a descriptive continuum, then there is a transitive model M of ZFC? theory (which need not be a model of ZFC) such that M = M ∩ Nω . (We do not use this result below.) We write hgt M = supw∈M∩WO |w| (the height of M) for any descriptive continuum M and recall that |w| < ω1 is the ordinal encoded by w. The following theorem expresses in essence the same property as the absoluteness theorem (Theorem 2.8), and the proof is the same. As usual, a closed analytic formula Φ is said to be absolute for M if Φ ?? ΦM . Theorem 6.2. Suppose that M is a descriptive continuum. In this case 1 (i) every Σ1 formula Φ with parameters in M is absolute for M; 1 (ii) if hgt M = ω1 (this is a typical case below), then every Σ2 formula Φ with parameters in M is absolute for M. 6C. Generic extensions of descriptive continua. In what follows we ?x a point a ∈ Nω and an L[a]-absolute σ-CAC ideal I (see subsection 3E). The descriptive continuum M = L[a] ∩ Nω will be the ground model, and for the forcing we take the M = PL[a] = {p ∈ M ∩ BC : B ∈ set PI p / I}. Since we intend to argue as close to M as I possible and, correspondingly, to refer to L[a] as little as possible, we begin with the translation to the M-terminology of the L[a]-meaning of the notion of L[a]-absolute σ-CAC ideal. Proposition 6.3. The set cod I ∩ M = {p ∈ BC ∩ M : Bp ∈ I} is de?nable in M by 1 M (complementary to BC ∩ M) a Π1 formula with the parameter a, and the set PI 1 is de?nable in M by a Σ1 formula with the parameter a. If the set A ? BC ∩ M is de?nable in M by an analytic formula with parameters in M and Bc ∩ Bc ∈ I for c = c ∈ A, then A is countable, and there is a z ∈ M such that A = {(z )k : k ∈ N}. M is de?nable in M by an analytic Finally (= Lemma 4.10), if a set D ? PI formula with parameters in M, then there is a c ∈ M such that A = {(c)n : n ∈ N} ? D and p∈A Bp is an I-full set.

    On some classical problems of descriptive set theory

    893

    The extension. It was proved in subsection 4C that the forcing PM I naturally produces I-random points x ∈ Nω , that is, elements of the set RandI M. However, the problem is to de?ne an extension of M by x in the framework of the structure of Nω . Our idea is to de?ne the extension as the family of all points of the form F (x), where F : Nω → Nω is a Borel function with a code in M. Let us ?x a recursive homeomorphism H : (Nω )2 ?→ Nω together with a pair onto of mutually inverse functions H1 , H2 : Nω ?→ Nω . We set Fc = { H1 (z ), H2 (z ) : z ∈ Bc } for any c ∈ BC; this is a Borel subset of Nω × Nω . Let BF be the set of all τ ∈ BC such that Fτ is the graph of a (Borel) function from Nω to Nω . If τ ∈ BF, then we set τ ’x = Fτ (x) for any x ∈ Nω . We write M x = {τ ’x : τ ∈ M ∩ BF}.29 It can hardly be expected that M x is again a descriptive continuum in the most general case; however, this holds in some important cases. (See, for instance, Theorem 6.6 below.) Forcing. By a π -formula we mean any analytic formula Φ (see subsection 1C) without parameters in Nω and in which some or all free variables of type 1 are replaced by expressions of the form τ ’π , where τ ∈ BF and π is a special symbol. In this case if x ∈ Nω , then we denote by Φ x the result of replacing every occurrence of the form τ ’π in Φ by τ ’x = Fτ (x); this result is obviously an analytic formula with parameters in Nω . We set Par Φ = {τ ∈ BF : τ ’π occurs in Φ}. M Let us de?ne a binary relation p M I Φ, where it is assumed that p ∈ PI and Φ ω is a closed π-formula with Par Φ ? M = L[a] ∩ N . The de?nition is carried out by induction on the complexity of Φ: (1) (2) (3) (4) (5) (6) if p p p p p Φ is a bounded formula, then p M I Φ ?? {x ∈ Bp : ?Φ x } ∈ I; M ? k Φ(k ) ?? ? k ∈ N (p M Φ(k )); I I M ? k Φ(k ) ?? ? q p ? r q ? k ∈ N (r M Φ(k )); I I M ? x Φ(x) ?? ? τ ∈ BF ∩ M (p M Φ(τ ’π )); I I M ? x Φ(x) ?? ? q p ? r q ? τ ∈ BF ∩ M (r M Φ(τ ’π)); I I M ?Φ(x) ?? ? q p ?(q M Φ).
    I I onto

    M in (3), (5), and (6). The variables q and r range over PI It is clear that the de?nitions (3) and (5) can be reduced to the de?nitions (2), (4), (6) by replacing the quanti?er ? by ???. If Φ is a bounded formula, then the forcing M of the formula ?Φ can be de?ned by using (1), and it can be reduced to the forcing of Φ by using (6). However, one can readily see that both ways lead to the same result.
    I

    29 We write x instead of the more common [x] to avoid confusion with the usual construction of generic extensions.

    894

    V. G. Kanovei and V. A. Lyubetskii

    Theorem 6.4. Suppose that ?(k1 , . . . , kj , x1 , . . . , xn ) is a parameter-free analytic formula with the variables k1 , . . . , kj , x1 , . . . , xn . Then the set F? = p, k1, . . . , kj , τ1 , . . . , τn : k1 , . . . , kj ∈ N ∧ τ1 , . . . , τn ∈ BF ∩ M ∧ p ∈ PM ∧ p M ?(k , . . . , k , τ ’π, . . . , τ ’π)
    I I 1 j 1 n

    is de?nable by an analytic formula with the parameter a, relativized to M. Proof. We use induction on the complexity of ?. In the case of bounded formulae we assume for simplicity that ? is ?(k, x). Then F? = M ∧ τ ∈ BF ∩ M ∧ ? x ∈ B ?(k, τ ’x) p, k, τ : k ∈ N ∧ p ∈ PI p

    1 formula. by the de?nition in (1). However, the formula de?ning this set is a Π2 (This is determined by the term τ ∈ BF; the other terms are even simpler.) Hence, the formula is absolute for M = L[a] ∩ Nω by Theorem 2.8. The inductive step (which can be broken up into cases corresponding to (2)–(6) above) is a rather routine exercise based on the de?nability of the sets PM I and BF ∩ M in M.

    We recall that M = L[a] ∩ Nω and we let RandI M = RandI L[a]. Theorem 6.5. Suppose that x ∈ RandI M and Φ is a closed π-formula with Par Φ ? M. Then Φ x is true in M x M (x ∈ B ∧ p ?? ? p ∈ PI p
    I

    M Φ).

    Proof. We argue by induction on the complexity of Φ. Assume that Φ is a bounded M Φ, then the set X = {x ∈ B : formula. If p ∈ PM p I , x ∈ Bp , and p I ? Φ x } belongs to I and is a Borel set with a code in M, and hence x ∈ / X and Φ x . But the formula Φ x is absolute. Conversely, if the right-hand side of the equivalence in the theorem fails, then standard arguments give the condition M , where x ∈ B and q M ? Φ. However, ? Φ is again a bounded formula, q ∈ PI q I and it follows from what was proved above that Φ x fails. Consider the inductive step for (4). Suppose that Φ is ? y Ψ(y). It follows from the de?nition of M x that Φ x is true in M x if and only if Ψ(τ ’π) x is true in M x for all τ ∈ BF ∩ M. The right-hand side of (4) has a similar structure. This enables us to reduce the equivalence of the theorem for the formula Φ to the induction assumption that the theorem holds for all formulae of the form Ψ(τ ’π). The inductive step in (2) is similar to that in (4): one considers numbers k ∈ N instead of codes τ . For the step (6) the result follows from the equivalence M (x ∈ B ∧ p M Φ) ?? ? p ∈ PM (x ∈ B ∧ p M ?Φ), ?? p ∈ PI p p I I I which can be proved by standard arguments. Theorem 6.6. If x ∈ RandI M, then the set M x is a descriptive continuum. Proof. In principle, the result follows from Lemma 4.12, because the equality L[a] L[a,x] ω1 = ω1 enables one to easily prove that M x = L[a, x] ∩ Nω . Thus, here it is of importance how to prove rather than what to prove. Namely, in accordance

    On some classical problems of descriptive set theory

    895

    with our main goal, we wish to give an ‘M-proof’ which does not appeal to forcing properties for models of ZFC. We restrict ourselves to the veri?cation of comprehension for M x , because the two other conditions can be veri?ed by similar arguments. For simplicity, let n = 1, that is, a formula of the form ?(k, l, x) is considered. Suppose that a1 ∈ Nω ∩ M x and b = { k, l : ?M (k, l, a1 )} ∈ Nω . We claim that b ∈ M x . By de?nition, M such a1 = τ1 ’x, where τ1 ∈ M ∩ BF. By Theorem 6.5, there is a ‘condition’ r ∈ PI that x ∈ Br and r M I ? k ?! l ?(k, l, τ1 ). We set M : B ∩ B = ? ∨ (B ? B ∧ p M ? k ? ! l ?(k, l, τ )) . Dkl = p ∈ PI p r p r 1 I By the choice of r, the set Dk = l Dkl is dense in PM I for any k . In addition, all the sets Dkl and Dk are de?nable in M by Theorem 6.4. Applying Proposition 6.3 (the last part), we ?nd a u ∈ Nω ∩ M such that the set Uk = {((u)k )l : l ∈ N} is included in Dk for any k and the union c∈Uk Bc is an I-full set. Dividing this structure in M in accordance with the relation to the condition r, we can ?nd a v ∈ Nω ∩ M such that every set Vk = {((v)k )l : l ∈ N} satis?es the equality Vk = {((v)k )l : l ∈ N ∧ B((v )k )l ? Br }. In this case the set c∈Vk Bc is an I-full subset of Br (in the sense that the corresponding di?erence belongs to I). We write Vkl = Vk ∩ Dkl . One can assume that Bc ∩ Bc = ? for c ∈ Vkl and c ∈ Vkl , l = l . (Generally speaking, we have only Bc ∩ Bc ∈ I in this case. However, the undesirable intersections can be removed. Indeed, there are only countably many of these intersections, and hence the entire part to be removed is still a set in I, after which the remainder must be encoded in M.) Under this assumption, there is a Borel function Fτ : Nω → Nω with τ ∈ BF ∩ M such that ? x ∈ Bc (τ ’x (k ) = l) (where τ ’y = Fτ (y)) holds for all k and l and c ∈ Vkl . In particular, this holds for the given point x ∈ RandI M. Using standard forcing arguments, one can now show that the point y = τ ’x ∈ M x satis?es the condition ? k ?M (k, y(k ), a1 ), as was to be proved. 6D. Completion of the ‘elementary’ proof of Theorem 6.1. We again M = PL[a] , assume that a ∈ Nω , M = L[a] ∩ Nω, I is an L[a]-absolute σ-CAC ideal, PI I and RandI M = RandI L[a]. The following theorem is analogous to Theorem 4.17. Theorem 6.7. Suppose that ?(x) is an analytic formula with parameters in M. Then there is a Borel code c ∈ BC ∩ M such that {x ∈ RandI M : ?(x) is true in M x } = RandI M ∩ Bc . Proof. We can assume that ? is ?(z, x), with the single parameter z ∈ M. Let cz ∈ BF ∩ M be some code of the constant function F (x) = z ? x. Thus, cz ’π is always interpreted as z . (This is an analogue of z ? in the exposition of forcing in subsection 4A.) Let ε ∈ BF ∩ M be a code of the function F (x) = x ? x. Then ?(z, x) is identical to ?(cz ’π, ε’π) x for any x ∈ Nω . By Theorem 6.4, the set M:p D = p ∈ PI M ?(c ’π, ε’π) or p z I
    I

    M ??(c ’π, ε’π) z

    896

    V. G. Kanovei and V. A. Lyubetskii

    M is de?nable in M, moreover, this set is dense in PM I by (6) in the de?nition of I . As in the proof of Lemma 4.12 (which is applicable here because we recall that M = L[a] ∩ Nω ), this implies the existence of a p ∈ M such that (p)n ∈ D for any M . The last fact means that n and the set {(p)n : n ∈ N} is dense in PI n B(p)n is an I-full set. We set u = {n : (p)n M ?(c ’π, ε’π)} and z I v=N u = { n : pn M ??(c ’π, ε’π)}. z I

    There are Borel codes c, c ∈ BC ∩ M such that Bc = n∈u B(p)n and Bc = Nω Bc = n∈v B(p)n . We claim that c is the desired code. Let x ∈ RandI M. Then x ∈ Bc ∪ Bc . If x ∈ Bc , then x ∈ B(p)n for some n ∈ u. Hence, it follows from Theorem 6.5 that the formula ?(cz ’π, ε’π) x (that is, the formula ?(z, x)) is true in M x . If x ∈ / Bc, then x ∈ Bc , and the formula ?(z, x) fails in M x for the same reasons. To complete the proof of Theorem 6.1, it remains to repeat the simple proof of Corollary 4.16 in which the reference to Theorem 2.8 is replaced by a reference to Theorems 6.6 and 6.2. (Theorem 6.1) § 7. Undecidability of the problems In this section we prove the following two theorems. Theorem 7.1. None of the following implications is derivable in ZFC: ? ? PK(OD); (I) ? PK(Π1 1) = (II) ? BP(?1 ) = ? ? BP(OD); 2 (III) ? LM(?1 ) = ? ? LM(OD). 2 Theorem 7.2. If ZFCI theory is consistent, then the proposition PK(ROD) ∧ BP(ROD) ∧ LM(ROD) does not contradict ZFC theory.30 We recall that OD stands for the class of all ordinal de?nable sets and the symbol ROD for the class of all real-ordinal de?nable sets. (For the exact de?nitions of these notions, see below.) Thus, Theorem 7.1 claims that the existence of counterexamples to the regularity properties (in the strongest possible form, because PK 1 1 holds for Σ1 1 and the properties LM and BP hold for the classes Σ1 and Π1 ) does not imply the existence of e?ective counterexamples, not even under the obviously weakest possible understanding of e?ectiveness as ∈-de?nability with ordinals as parameters. After necessary de?nitions and comments in subsection 7A, we concentrate on the proof of Theorem 7.1, and then, using this, we continue with the proof of Theorem 7.2. 7A. De?nitions and comments on the theorems. One can say that a set x is de?nable if there is an ∈-formula ?(v) that is parameter-free and has only one free
    30 In all metamathematical results, including consistency theorems, we tacitly assume the consistency of ZFC itself. However, Theorem 7.2 uses the stronger assumption that the theory ZFCI is consistent (the latter theory consists of the axioms of ZFC together with the axiom “there is a strongly inaccessible cardinal”).

    On some classical problems of descriptive set theory

    897

    variable v and for which x is the only set satisfying ?(x), that is, ? v (?(v) ?? x = v ). However, this notion admits no formal rigorous de?nition in ZFC; in other words, there is no ∈-formula δ (x) distinguishing at once all de?nable sets. (We do not go into the reason for this.) On the other hand, a wider notion of ordinal de?nable set (that is, a set de?nable by an ∈-formula with ordinals as parameters) admits such a de?nition. Let us consider a formula od x saying the following (see [75]): there is an ordinal α and an ∈-formula ?(v) with ordinals smaller than α as parameters and with a single free variable v such that x ∈ Vα , and x is the only set satisfying Vα |= ?(x). We recall that Vα is the αth von Neumann level (see subsection 2A) and the symbol |= stands for the model-theoretic truth relation for a formula in a structure. We write OD = {x : od x} for the class of all ordinal de?nable sets. Thus, every x ∈ OD is de?nable by an ∈-formula of the form Vα |= ?(x) in which ordinals α can occur as parameters. Conversely, if x is ordinal de?nable informally, then, applying the re?ection principle (see, for instance, Theorem 16 in [29]), we ?nd an ordinal α such that the de?nition can be relativized to Vα , and hence x ∈ OD. The class ROD = {x : rod x} of all real-ordinal de?nable sets,31 that is, the sets de?nable by formulae containing ordinals and elements of Nω as parameters, is de?ned similarly. Here rod x stands for a modi?cation of the formula od x which means that ? can contain not only ordinals but also elements of Nω ∩ Vα as parameters. (For the details relating to ordinal de?nability, see [75] or [29], § 14.) It is clear that Ord ? OD; moreover, L ? OD because for any x ∈ L there 1 is an ordinal ξ such that x = Fξ . Further, Σ∞ ? OD, and the class Σ1 ∞ of ω all projective subsets of N is included in ROD. Thus, Theorem 7.2 implies the following corollary. Corollary 7.3. Suppose that ZFCI theory is consistent. (i) The assertion that all projective sets have the perfect kernel property and the Baire property and are λ-measurable does not contradict ZFC, and hence this assertion is undecidable in ZFC by Theorem 3.11. 1 1 1 1 (ii) Therefore, the assertions PK(Π1 1 ), LM(?2 ), BP(?2 ), LM(Σ2 ), and BP(Σ2 ) (see the diagram in the Introduction ) are also consistent and undecidable in ZFC by Theorem 3.11. Theorem 7.1 is connected with the following form of the regularity problems for point sets: is it possible to e?ectively give counterexamples32 to the regularity properties if such counterexamples do exist? The theorem answers this question in the negative.
    31 The ?rst word re?ects the possibility of taking points of Nω as parameters of a de?nition, along with ordinals. The word real as a noun, as applied to points of Nω , is rather typical for the English-language literature concerning descriptive set theory and is based on the identi?cation, discussed in footnote 12, of the points of Nω with the irrational real numbers. Unfortunately, there is no adequate translation into Russian of the word real in this sense that is concordant with the traditions of Russian mathematical language. 32 See the references in footnote 9 on the discussions in early descriptive set theory concerning ‘e?ective’ examples in contrast to ‘pure’ existence proofs.

    898

    V. G. Kanovei and V. A. Lyubetskii

    The result itself can be presented in a form in which there are no ordinals at all, that is, in a form of ‘pure’ de?nability. However, for the above reasons, the corollary looks more ‘metamathematical’ than the theorem itself. Corollary 7.4. There is no ∈-formula with a single free variable and satisfying at least one of the following three requirements :
    ω (i) probably in ZFC + ? PK(Π1 1 ), it de?nes a subset of N without the perfect kernel property ; ω (ii) provably in ZFC + ? BP(?1 2 ), it de?nes a subset of N that does not have the Baire property ; ω (iii) provably in ZFC + ? LM(?1 2 ), it de?nes a λ-non-measurable subset of N .

    The proofs of Theorems 7.1 and 7.2, given below in this section, include an analysis of three di?erent models of ZFC obtained as extensions of the class L by
    L 1) a single generic collapse function ω ?→ ω1 , which will prove the parts (II) and (III) of Theorem 7.1; onto L 2) a family of ?L 2 generic collapse functions ω ?→ ω1 , which will prove the part (I) of Theorem 7.1; 3) a collapse up to a strongly inaccessible cardinal, which will prove Theorem 7.2. onto

    However, the manipulations in the three models have many common points. 7B. First model; one collapse function. To prove the parts (II) and (III) of Theorem 7.1, we take the class L of all constructible sets as the ground model L L L ) = Coll(N, ω1 ) designed for the ‘collapse’ of ω1 . Thus, and the forcing C(ω1 L L C(ω1 ) consists of all functions p such that dom p ∈ N and ran p ? ω1 . We L L equip C(ω1 ) with the order opposite to inclusion. Then any C(ω1 )-generic onto L L set G ? C(ω1 ) produces a generic collapse function f [G] = G : N ?→ ω1 , and at the same time we have G = {f [G] n : n ∈ N}. By Theorem 4.4, the next theorem implies Theorem 7.1 (II), (III).
    L L ) be a C(ω1 )-generic set over L. Then BP(OD) and Theorem 7.5. Let G ? C(ω1 1 LM(OD) hold in L[G], but LM(?2 ) and BP(?1 2 ) fail in L[G].

    In the course of the proof of this theorem (that is, until the end of subsection 7C) L we ?x some C(ω1 )-generic set G over L. The ‘negative’ part of the theorem is not L[G] L L di?cult. We have ω1 < ω1 , because the function f [G] ∈ L[G] maps ω onto ω1 , ω L . This enables one to obtain a point a ∈ N and hence there is a w ∈ L[G] ∩ WOω1 1 such that L[a] = L[f [G]] = L[G]. The violation of BP(?1 2 ) and LM(?2 ) in L[G] follows now from Theorem 3.11. The ‘positive’ part requires much more work. By Lemma 3.8, it su?ces to show that in L[G] every OD set is I-measurable for any L-absolute σ-CAC ideal I. The proof is based on the following lemma in which Λ (the empty function) is the L L weakest element of C(ω1 ) and the z ?i are the canonical C(ω1 )-names of sets zi (it is clear that z ?i [G] = zi for i = 1, . . . , n).

    On some classical problems of descriptive set theory
    L[x]

    899

    L Lemma 7.6. Suppose that x ∈ L[G] ∩ Nω , ω1 = ω1 , ?(v1 , . . . , vn ) is an ∈-formula, and z1 , . . . , zn ∈ L[x] are arbitrary sets. Then

    ?(z1 ,

    推荐相关:
    江苏七位体彩开奖结果 | 江苏七位体彩开奖结果
    All rights reserved Powered by 江苏七位体彩开奖结果 江苏七位体彩开奖结果 www.jwbw.net
    copyright ©right 2010-2021。
    文档资料库内容来自网络,如有侵犯请联系客服。[email protected]
  • 晋中市通报五起违反中央八项规定精神问题 2019-10-08
  • 人民日报金台锐评:让工作日志减负增效 2019-10-08
  • 帮助孩子成为优秀的人:如何通过编故事来发展孩子的创造力 2019-10-02
  • 人民日报评论员:民生改善是梦想的最好诠释 2019-10-02
  • 辽宁大连:玩具卡住男童手  消防耐心帮解困 2019-09-30
  • 可再生能源电价附加资金补助目录公布 2019-09-13
  • 慈善实践与新时代道德建设 2019-09-08
  • 王子文再登封面 黑白光影间酷女孩玩转高级时尚 2019-09-06
  • 【大家谈】激励实干担当,谱写奋斗“进行曲” 2019-09-06
  • 她主动借腹给我生儿子,中途又移情别恋 有故事的人 2019-09-03
  • 90后创业者成电商谷第100家园企 ——凤凰网房产北京 2019-09-03
  • 拥有大智慧的中国古人就把“子”和“女”结合在一体,造出一个会意字“好”字。一直就用这个“好”的感觉结果去衡量其它任何生存环境中的万物万事所给人的感觉。 2019-08-14
  • 中共中央组织部“12380”举报网站 2019-08-08
  • 省委扫黑除恶专项斗争督导组反馈吉安督导情况 胡世忠作表态发言 2019-07-28
  • 实现中华民族伟大复兴是近代以来中华民族最伟大的梦想(认真学习宣传贯彻党的十九大精神) 2019-07-28
  • 足球直播网 久赢在线娱乐平台 重庆时时算法 曾道人特码主 中国福利彩票35选7 大乐透前面对5个多少钱 北京到 河南22选5最新开奖结果 云南11选5任四遗漏 黑客如何网络赚钱 金科娱乐返彩金 吉林11选5任三最大遗漏值 江苏快三预测推荐 中国竞彩网彩网 香港赛马会生肖表2019