Some Topics in Descriptive Set Theory and Analysis Citation Ramsamujh, Taje Indrallal (1986) Some Topics in Descriptive Set Theory and Analysis. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/8pdn-xf41. https://resolver.caltech.edu/CaltechTHESIS:01202017-145315777 Abstract Coanalytic subsets of some well known Polish spaces are investigated. A natural norm (rank function) on each subset is defined and studied by using well-founded trees and transfinite induction as the main tools. The norm provides a natural measure of the complexity of the elements in each subset. It also provides a "Rank Argument" of the non-Borelness of the subset. The work is divided into four chapters. In Chapter 1 nowhere differentiable continuous functions and Besicovitch functions are studied. Chapter 2 deals with functions with everywhere divergent Fourier series, and everywhere divergent trigonometric series with coefficients that tend to zero. Compact Jordan sets (i.e., sets without cavities) and compact simply-connected sets in the plane are investigated in Chapter 3. Chapter 4 is a miscellany of results extending earlier work of M. Ajtai, A. Kechris and H. Woodin on differentiable functions and continuous functions with everywhere convergent Fourier series. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: Mathematics Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Thesis Availability: Public (worldwide access) Research Advisor(s): Kechris, Alexander S. Thesis Committee: Kechris, Alexander S. (chair) Woodin, W. Hugh Wolff, Thomas H. Luxemburg, W. A. J. De Prima, Charles R. Defense Date: 5 May 1986 Funders: Funding Agency Grant Number Caltech UNSPECIFIED Record Number: CaltechTHESIS:01202017-145315777 Persistent URL: https://resolver.caltech.edu/CaltechTHESIS:01202017-145315777 DOI: 10.7907/8pdn-xf41 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 10017 Collection: CaltechTHESIS Deposited By: Benjamin Perez Deposited On: 20 Jan 2017 23:41 Last Modified: 14 Jun 2023 23:05 Thesis Files Preview PDF - Final Version See Usage Policy. 36MB Repository Staff Only: item control page

SOME TOPICS IN DESCRIPTIVE SET THEORY AND ANALYSIS Thesis by Taje Indralall Ramsamujh In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1986 (Submitted May 5, 1986) -H- For my da.r ling Donna Selochanie -iiiAcknowledgements I would like to express my sincere thanks to my adviser, Professor A. Kechris for his expert guidance and the patience and care with which he supervised this thesis. Thanks are also due to Professors W. H. Woodin, H. Becker, R. Edwards, T. Wolff, and W. Luxemburg for some useful discussions that were related to this work. Special thanks are due to Professor Kechris and his colleagues for giving me access to their unpublished works. I acknowledge Mathematics with Department gratitude faculty knowledge and teaching ability. the has positive had on my influence the mathematical Special mention must be made here of Professors T. Apostol and c. De Prima. The financial assistance Technology is provided by the California Institute of appreciated. So too are my fellow graduate students with whom I have spent four enjoyable years. greatly The department's secretarial staff were also friendly and very helpful. Special thanks are however due to Mrs. L. Chappelle for the wonderful work she did in typing this thesis. Finally I would like to thank my family and my fiancee" for their constant encouragement and their patience with me through the years. - i VAbstract Coanalytic inves:tigated. subsets of some well known Polish spaces are A natural norm (rank function) on each subset is defined and studied by using well-founded trees and transfinite induction as the main tools. The norm provides a natural measure of elements the complexity of the in each subset. It also provides a "Rank Argument" of the non-Borelness of the subset. The work is divided into four chapters. In Chapter 1 nowhere differentiable continuous functions and Besicovitch functions are studied. Chapter 2 deals with functions with everywhere divergent Fourier series, and everywhere divergent trigonometric series with coefficients that tend to zero. Compact Jordan sets (i.e ., sets without cavities) and compact simply-connected sets in the plane are investigated in Chapter 3. results extending earlier work Chapter 4 is a of M. Ajtai, A. miscellany of Kechris and H. Woodin on differentiable functions and continuous functions with everywhere convergent Fourier series. -vContents Acknowledgments Iii Abstract )V Contents v Chapter Q: Descriptive Set-Theoretic Preliminaries 1. Co-analytic subsets and co-analytic norms. 1 2. Well-founded trees and their ranks. 4 3. Tree description and Cantor-Bendixson Analysis. 7 4. Notation and conventions. 2 Chapter 1: The Set of Nowhere Differentiable Continuous Functions on [0,1]. Introduction. 1.0 1. Tree Description: 2. Some natural examples. 2 'a 3. The rank function r is unbounded in w1 on BF. 38 4. Cantor-Bendixson Analysis. 5Z. Chapter 2: The rank functions p and r. The Set of Functions With Everywhere Divergent Fourier Series Introduction. 13 -vi- 1. Tree Description: 2. Some natural examples. 3. Cantor-Bendixson Analysis. 4. The rank function r is unbounded in w 1 on DF. Chapter 3: The rank functions p and r. The Set of Compact Jordan Sets in the plane Introduction. 101 The rank function p • 103 1. Tree Description: 2. Some natural examples. 114 3. The rank function p is unbounded in w 1 on SC. 121 Chapter !: Miscellaneous Results Introduction. 1. 12& A comparison of the Kechris-Woodin and Denjoy rank functions. 2. The Denjoy rank function is unbounded in w 1 on D. 3. The Zalcwasser rank function and comparing tests 129 for everywhere convergence of Fourier Series. 4. The Zalcwasser rank function is unbounded in w 1 on CF References 141 -1- Chapter O In chapter this we shall Set-Theoretic results that we need. review the Descriptive We shall not give proofs but we will give precise references. sl. Coanalytic subsets and coanalytic norms. a complete, separable metric space. denote a Polish space. A Poli sh space is From now on X shall always A set A~ Xis a Borel subset of X if it belongs to the smallest a-algebra of subsets of X which contains all the open subsets of X. be a function. Let Y be a Polish space and f:Y ~ X We say that f is a Borel measurable function if for each open set A in X the set f- 1 [A] is a Borel subset of Y. set A~ A Xis an analvtic subset of X if there exists a Polish space Y and a Borel subset of X x Y such that A is the projection of B onto X, i.e., A = {x € X: 3y € y ((x,y) € B)} A set A~ Xis a coanalvtic subset of X if its complement X - A is an analytic subset of X. A coanalytic subset A of X is said to be comp l et e if for any Polish space Y and coanalytic subset B of Y there is a function f:Y ~ X such that y Polish space IR, of the € B <=> f(y) € A. real numbers has Borel As it is known the a subset which is coanalytic and not Borel it follows that no complete coanalytic subset of X can be Borel. A proof that demonstrates that A ~ X is not Borel by showing that A is complete coanalytic is usually referred to as a "Completeness Argument. 11 -zA norm on a set A k X is just a map 'f':A -> ORD, where ORD is the class of all ordinals. as to a rank (A norm is sometimes also referred function.) The map induces a pre-well-ordering ~'f' on A which is defined by X ~ 'f' y <=> 'f'(X) Two norms are said to be ~ 'f'(y). e qui v a l en t if they induce the same pre-well-ordering. Let A be a coanalytic subset of X. A norm 'f':A -> ORD is said to be a coanalvtic norm if there is an analytic subset B of x2 , and a coanalytic subset C of x2 such that y € A :::> 'ix[{x € A and 'f'(x) ~ 'f'(y)} <=> (x,y) € B <=> (x,y) It is known that every coanalytic subset has a defined on it. € C]. coanalytic norm Moreover this coanalytic norm is always equivalent to one which takes values in w1 , and it is by no means unique. (See [41].) If the set A arises from natural considerations in Real Analysis, Harmonic Analysis or Point-Set Topology (which we shall call Analysis for short) the question of finding a coanalytic norm on A, which naturally reflects in some sense the properties of the elements of A, is of interest. (For instance if the coanalytic norm is such that "simple 11 elements of A have small ranks, i.e., the map 'f' sends "simple 11 elements to small ordinals, then 'f' natural measure of the complexity of the elements of A.) 'f' on A enables us to view A as a natural w induces a The norm 1 -hierarchy. We -3- shall refer to coanalytic norms that arise out of Analysis and that reflect the properties of the elements of the coanalytic set in question as "natural coanalytic norms. 11 The following proposition is basic to our study of natural coanalytic norms. Proposition 1. Suppose A ~ X is a coanalytic subset of X and '(':A ~ w 1 is a coanalytic norm on A. Then A is Borel ~ 'f [A] is countable. Proof. See (41] p. 196 and p. 213. 0 From Proposition 1 we immediately see that to show A is not Borel, it will suffice to show that 'f [A] is unbounded in w1. Such a proof of the non-Borelness of A is usually referred to as a Rank Argument. There is a slight extension of this Rank Argument which depends on the following proposition. Proposition 'f :A ~ 2. Suppose A is a coanalytic subset of X and w1 is a norm on A such that (i) there is an analytic subset B of x 2 such that x,y € A ~ ['f(x) < 'f(Y) ~ (x,y) (ii) € BJ, and 'f is unbounded in w 1 on A. Then A is not a Borel subset of X. Proof. See [26]. 0 -40bserve that if P and Q are coanalytic subsets of X, Remark. Q ~ P and 'f':P --+ w 1 is a coanalytic norm then Q and satisfy 'f' ~Q condition (i) of Proposition 2 . . We end this section with two results which will aid us in constructing coanalytic norms. Proposition ~· coanalytic Let X and Y be Polish spaces and A ~ X, B ~ Y be subsets. Let also f:X --+ Y be a Borel measurable function with f- 1 [B] = A and 'f:B --+ w 1 be a coanalytic norm. the map .p:A --+ w1 defined by .p(x) = 'f'(f(x)) Then is also a coanalytic norm. Proof. See [26]. D Proposition !· Let A be a coanalytic subset of X, 'f':A --+ w 1 be a norm and !:.'f' the coanalytic norm associated iff the initial segments Borel (i.e., the subsets {x: x Proof. '§.2. set. pre-well-ordering. !:.'(' of s.'f' Then are 'f' is a uniformly y} are uniformly Borel in y). See [22]. D Well-Founded Trees and Their Ranks. Let A be any non-empty . We define A* to be the collection of all finite sequences from A (including the empty sequence 0), i.e., A* = A tree T on A u An, where Ao = {0}. n€w is any subset T of A* such that The elements of T are called nodes. a node of any non-empty tree. By definition 0 is always We call 0 the root of such a tree. A subset S ~ T which is also a tree on A is called a subtree of T. Let u be a finite sequence from A and T be a tree on A. We define Tu by U {v € An: u"'v € T}. n€w"" It is easy to verify that Tu is a tree on A. If u is not a node of T then Tu = 0. When u is node of T we shall ref er to Tu as the the node tree at well-founded provided u in T. there is A tree T on A is said to be no sequence <an>n€1N from A such that for each n, <a 1 , ... ,an> € T. Let T be a well-founded tree on A. We define by induction a sequence of trees as follows: Put TO = T, Ta+l = U {v € An: 3a € A(v"'<a> € Ta)}, and n€w"" for A. a limit ordinal. Observe that the sequence <Ta> a€ORD is strictly decreasing, so for sufficiently large a, Ta = 0. Note also that if T is non-empty, then the least a such that Ta = 0 must be a successor ordinal. Definition. Let T be a non-empty well-founded tree. rank r(T) of T by r(T) = least a such that Ta+l = 0 We define the -6- is a If v node of T we define the rank, r(v;T) of v in T by r(v;T) = r(Tvl· If T is the empty tree we adopt the convention that r(T) = -1. T is not well-founded we let r(T) = oo. any a € finite ORD. sequence u from A If It is easy to see that for that each Using this it can be shown that r(T) = sup{r(Tv) + 1: v € T, v -;t:. 0} = sup{r(v;T) + 1: v € T, v -;t:. 0} It turns out that r is a coanalytic norm if we view the set of all well-founded trees on IN = {1,2,3, ... } as a subset of a certain Polish space. tN. . Consider IN *, the set of all finite sequences from A tree T on tN is a subset of tN * and so can be identified with . XT:tN * --+ {0,1} = 2. its characteristic function So a tree on IN can * be viewed as an element of the Polish space 21N . Let WF be the set of all well-founded trees on IN viewed as a subset of 21N*. Then we have the following result: Proposition .§.. WF is a coanalytic subset of 21N * and r:WF --+ w 1 is a coanalytic norm. Proof. See [26] D The final result we need in this section is a classically -1- known result which is a corollary of the recent and much more powerful Kunen-Martin Theorem. We say that s say that s is a Let s be a binary relation on X. st r i ct re l at i on if x s y => ..., (y < x). is we l l - founded if there is no n € IN. Finally s such _that xn+l s xn for all sequence <xn> n€ IN is said to be analytic, if when viewed as a subset of x 2 it is analytic. be well-founded strict relation on X. We Let s We associate with s a tree Ts defined by We define the l en gt h of the relation s as the rank of the tree Proposition .§. Let s be a strict analytic well-founded relation on X. Then < has countable length. Proof. See [41] p. 103. %3. 0 Tree Description and Cantor-Bendixson Analysis. be a coanalytic subset of X. Let A ~ X A very useful way of obtaining a coanalytic norm on A is to associate with each element, x of X, a tree (or a set of trees) such that the tree (resp. set of trees) associated with x is well-founded iff x € A. of associating an ordinal, namely the This provides a way rank of the tree (resp. strict supremum of the ranks of the trees) to each element of A. This gives a norm on A and with a little bit of luck it is usually easy to check that this norm is a coanalytic norm. to such a process Description. of obtaining a coanalytic We shall refer norm as a Tree Another process of obtaining a coanalytic norm on A is to associate with each element, x of X, a nested sequence of closed sets such that this sequence stabilizes at the empty set, 121, iff x € A. shall We illustrate this process by the following example and refer to it as a Cantor-Bendixson Let Analysis. K = <K[0,1],o> be the Polish space of all non-empty compact subsets of [O,l], with o being the Hausdorff metric. Let CS be the subset of K consisting of all countable sets in K. Then it is easy to show that CS is a coanalytic subset of K. Now for A € K define A" by A " = {x € A: x is not an isolated point of A}. Then A" is also in K so that operation on K. " can be viewed as a "derivative" We define by induction a sequence <A a> a€ ORD as follows: Put Ao = A, Aa+l = (Aa) ", and A>.. = n A'A. for 'A a limit ordinal. a<>.. Then it is easy to see that <A a> stabilizes at 121 iff A € cs. Moreover if we define p(A) to be the least a such that Aa+l 121, then p:A -+ w ~4: = 1 is a coanalytic norm. Notations and Conventions. Most of the notations we use will be standard and when we depart from standard practice we shall point this out. When the Polish space X is understood it is usual to talk about Borel (analytic , etc.) sets rather than Borel (analytic, etc.) subsets. The modern practice analytic sets as Ll sets and coanalytic sets as ~1 is to refer 1 sets. n ~1 to Borel -9sets are then of t:;. 1 sets. ~1 1 sets are defined as projections The 2: ~2 !!i sets, and !~ sets are defined as compliments of ~~ sets. We shall have no need to go higher up this hierarchy so we shall bow to tradition and use analytic instead of ~J, etc. We shall always take IN to be the set of positive integers, i.e., IN = {1,2,3, ... }. When we need to non-negative integers we shall use w. we denote by consider the set of Also if u = <a 1 , ... ,am> and u~ the concatenation Finally in referring to results from different chapters Chapter m. we use Proposition m.n to mean Proposition n from -10Chapter 1 Introduction. It was not always clear that there could exist a continuous function which was differentiable at no point. "differentiable" we Such functions of course are called mean having a nowhere (By finite derivative. differentiable continuous ~ functions.) In fact in 1806 M. Ampere [02] even tried to show that no such function could exist and not too many mathematicians disagreed with him (but it must also be said that not many were convinced by his "proof"). Of the early attempts in constructing a nowhere differentiable continuous function mention must be made of B. In Balzano. a manuscript dated around 1830 Balzano constructed a continuous function on an interval and showed that it was not differentiable on a dense set of points. (It was later shown by R. Rychlik [43] that this function was in fact nowhere differentiable.) Around 1873 K. Weierstrass constructed the first differentiable continuous function. nowhere This discovery was published by du Bois-Reymond [12] in 1874 and prior to this no such function was ever published. An example of a nowhere differentiable function published in C. Cellerier [09] was thought (see [53]) to have been discovered as early as 1850 by Cellerier but of this we are very much in doubt. Also a function considered by B. Riemann around often 1860 and very thought of as being nowhere differentiable turns out to be differentiable at certain points (see [15], [16] or [47]). first nowhere So the honour of the discovery of the differentiable continuous function goes to -u- Weierstrass. Later many more examples of nowhere differentiable continuous functions were constructed and it became fashionable to ask that more stringent requirements be satisfied (for instance, instead of being nowhere differentiable, the function required to have no derivative, finite or infinite). Besicovitch [07] constructed a continuous one-sided derivative, finite or infinite. function might be In 1925 A. with no Such functions are called Besicovitch functions in honour of their discoverer. Functions which than satisfy even more stringent requirements the Besicovitch functions have been constructed by A. P. Morse (40]. The status of nowhere differentiable continuous functions took a different twist when in 1931 S. Mazurkiewicz [39] showed that the set of all such functions is a co-meager subset of the set of all continuous functions of period 1. (03].) (See also Banach (So that in the sense of Baire Category the functions which are not nowhere differentiable are exceptional.) abstract proof of continuous functions. the existence of This provided an nowhere differentiable A little later S. Saks [44] showed that the set of all Besicovitch functions was a meager subset of the set of all continuous functions. So we cannot get an abstract existence ; proof as before. However J. Maly [34] recently showed that the Besicovitch functions was co-meager in a certain restricted class of continuous functions, thus retrieving the situation. Let C = <C[0,1],d> be the Polish space of all real valued -12continuous function on [O,l] with d being the supnorm metric given by d(f,g) = sup{ I f(x)-g(x) I: x € [O,l]} Let ND be the set of all nowhere differentiable functions and BF be the set of all Besicovitch functions in C. (It is understood that at the endpoints, considered.) Then coanalytic subsets. it 0 is and 1, one-sided derivatives are easy to show ND are that and BF R. D. Mauldin [36] showed that ND is not a Borel subset (there is a small error in [36]; for the correction see [37]) and in a communication with Kechris (see [25]) indicated that he also had a proof that BF was also not Borel. Kechris later [25] showed that ND and BF are complete coanalytic subsets (and hence they can't be Borel). In function this on chapter we shall investigate a "natural" rank ND, the definition of which is essentially due to Kechris and Woodin (see [23]). We give a Tree Description of ND to get an auxiliary rank function p. Our natural rank function r is then easily defined in terms of p. coanalytic norm on ND. It turns out that r is a The rank function r provides a natural measure of the complexity of the functions in ND. The rank of a function, r(f), measures in some sense how "close" the function f "came to being differentiable." We shall show that the functions with smallest rank, namely 1, are precisely the set BC, of the Banach functions in ND. that at each point at (A Banach function is a function such least one of the Dini derivatives are -rs- infinite. What Banach had essentially shown in his proof of the co-meagerness of ND was that BC was co-meager, hence the name.) The Banach functions are easily seen to be nowhere differentiable but as the rank r(f) increases it becomes more difficult to see that f is nowhere differentiable. So the functions become more complicated as the rank increase. We next consider the ranks of certain natural examples in ND to see that our intuitive idea that natural examples should have small ranks is reasonable. We will also show for each ordinal 1 < a < a 1 , how to construct a function f r(f) = a. € BF such that Since r is coanalytic norm on ND this will provide Rank Arguments of formulate a the non-Borelness of BF and ND. Finally we Cantor-Bendixson Analysis which gives rise to the same rank function r. This Analysis is much more complicated than the ones given in [01] and [26] but it has some interesting aspects. One of the interesting aspects of this Cantor-Bendixson Analysis is that it involves a "simultaneous induction," as opposed to a "parametric induction" which is for instance used in [26] to define the rank function on the set D, of everywhere differentiable functions in C. Tree Description: The Rank Functions p and !:· In this section we study the set ND by associating with each element of ND a countable number of well-founded trees. But first we check that BF and ND are coanalytic subsets. Proposition 1. ND and BF are coanalytic subsets of c. -14Proof. It will suffice to show that C - ND and C - BF are analytic subsets. We have c - ND = {f€C 3x€[0,1] (f is differentiable at x)} Now f is differentiable at x iff 'In 3m such that Vh 1 ,h 2 with O < lh 1 1, lh 2 1 < 1/m and x + h 1 , x + h 2 € (0,1] f(x+h 1 )-f(x) f (x+h 2 )-f(x) we have h1 h2 l Let E(n,m) = {(f,X)€ CX(0,1] : (*) holds}. I (* ) ~ _l n Then it is easy to see that n u E(n,m) is Borel. C - ND n€ IN m€1N is the projection of this Borel set onto C and so it is analytic. E(n,m) is closed, and consequently C - BF = {f€C:3x€(0,](f has a one-sided derivative (possibly infinite) at x)} Now f has a one-sided derivative at x iff 'In 3m and x + ch 1 , x + ch 2 € (0,1] -IS- or 'Vh with O < h < l/m and x + ch € [0,1] we have f (x+chA-f (x)>. c ,., n {**) I or 'Vh with O < h < l/m and x + ch € [0,1] we have f(x+c~A-f(x) ~ -n. We now put F(n,m) = {(f,X)€ CX[O,l] : (**) holds} and proceed before to conclude that C"'."BF is analytic. as D With each f € C and each positive rational M (M should be thought of as being large) reflects the properties of f. we will associate a tree Let ~+ be But first some notation. the set of all positive rational numbers. T~ which Let also R[0,1] be the collection of all non-empty intervals open in [0,1], and Q[0,1] be the set of intervals in R[0,1] with rational endpoints. that Q[0,1] is endpoints a,b(a countable. < b) For and any f quotient f.f(I), of f over I by f.f(I) Definition. as follows: Let f € C and M € ~+. any € interval I € C we define the Observe R[0,1] with difference = f ( b6=~ (a). We define the tree ~ on Q[0,1] <I 1 , ... ,In> € T~ ~ I 1 = [O,l] and Vi = 2, ... ,n we have (i) Ii € Q[0,1], Ii ~ Ii-l , I I 1 I :s: 1/i and (ii) VK,L € R[0,1] with In ~ c,L ~i-l we have I .6f(K)-.6f(L) I :s: M/(i-1). - By Ii we mean the closure of Ii and I Ii I is the length of Ii. We note is in passing that the essential contained in condition (ii). part of the Observe that if M " ;?: immediately have from the definition that TM f result gives the definition fundamental relation M , then we TM" f . ~ between The next f and the associated trees T~. Proposition _g_. C. Then f € ~ VM € q:i+ (T~ is Let f € ND Proof. "~": Suppose for some M € q:i+ , T~ is not Then there is well-founded). well-founded. <Il, ... ,In> € TM f for each n € IN. is differentiable at x. that f that x + hl K, L ~ Im f X + h2 € Im. endpoints a sequence <In> n€ IN n Let {x} - n€1N In. Fix m. Let h 1 I such that We shall show h2 ;t: 0 be such Let also K,L € R[0,1] be such that {x} ~ (K) = {x+hl'x+o 1 } and (L) endpoints < Then = -11- L K Now I .6f(K)-.6f(L) I enough n) I M/m (because K (', L contains an In for a large and f , x+ 0 2 ) - f , x ) h ~ I by the continuity of f, f I ~ 0 2 x+ 0 ) 11 -f, x) , 1 and (*) Since x is an interior point of Im in [0,1] and (*) is true for all m it follows that f is differentiable at x. "e": Suppose now that f M € l!:l + there is a t ND. We shall show that for some sequence <In> n€ IN such that <I 1 , ... ,In> € T~ -18for each n x 0. € IN. Choose x 0 € [O,l] such that f is differentiable at Then it is easy to see that there is a c lies between c • (x-x 0 ) and -c ~ (x-x 0 ) for each x € Since f is differentiable of x 0 , Vn 3m(n) such that Take M = 2c. with 0 l < lhl f(x 0 +h)-f(x 0 ) - < 1/m(n) f "(x0 ) I and x0 + is strictly -i m(n)} and qn = min{l ,x 0 +1/2m(n)}. In € Q[0,1] such that x0 € In !;;;; [pn,qn] and Let For Pn n~ In ~ In-l have = max{O 2 choose (I 1 is of Then I In I :-: ; I qn-Pn I = 1/m(n) :-: ; l/n .So for each n , <In, ... ,In> satisfies condition (i) of the tree T~. satisfies condition x0 € K A L we increasing. m(n) it also [0,1] € We may assume without loss of that course [0,1]). h :-: ; ~ generality ,x 0 [0,1]. 1 0 Vh in+ such that f(x) € and endpoints (ii). We will show that Let K,L € R[0,1] (K) =O{a,b} and Then for all such K,L ~ In (n ;:: 2) we have be such that endpoints (L) = {c,d} . -19- s: 4 •M/4n = M/n. I t.f(L) s: + c {x 0 } ~ K,L!; In. (ii) T~ is for c = M/l . Since x_ € In , for all n it follows that condition satisfied, and so <I, ... ,In> € T~ for each So T~ is not well-founded. Let f € ND and M € ID+. the tree T~ is countable. n € rN. o Since Q[O,l] is countable the rank of Also since T~ ; 2 T~ doe M ; ~ M we have sup{r(T~)+l:M€ I+} = sup{r(T~}+l:N€1N} < w 1 . Definition. We define the rank function p:NDl-... w 1 by Proposition ~· p:ND -... w 1 is a coanalytic norm. Proof. Q(0,1] -... IN be a Borel measurable bijection. Let /3 Define a * map r:C --+ 21N by r(f) = T f -20where Tf is the tree (viewed as an * element of 21N ) given by Tf = {121} V Then f € ND U {<N,.B(I), ... ,(In)> NEIN Tf <:::::> So WF. € sup{r(T~)+l:NE IN} = r(Tf) = r(r(f)). a Borel measurable function. ND ,,-l[WF]. Moreover p(f) = Also it is easy to see that r is Hence by Propositions 0.3 and 0.5 it follows that p is a coanalytic norm. D Our next aim is to show that p(f) is always a limit ordinal. But first we need some definitions and two lemmas. Definition. Let I € R[0,1] and T be a tree on R[0,1]. We define the subtree T~I of T by Let f € ND and M € ~+. For each x r(T~;x) = min{r(T~~I) € [0,1) we define x € I € R[0,1]} If r(T~) ;:: w ·a then there is an x Lemma 4. such that € [0,1] of nested r(T ML f ;x) ;:: w •a. Proof. We shall find a sequence <Ln> nE IN closed -Z1intervals for with each r(T M f;x) ~ 1/n n € IN. w •a. Take L I Ln I < Taking x s 1 = [O,l]. 2/n such that L we n € nEIN n r(~~Ln) ~ w •a will then get We construct Ln by induction on n . Given Ln choose closed intervals L~ and L~ such that L~ u L~ = Ln ; IL~ I, IL~ I < 2/(n+l) and IL~ f't L~ I ~ 1/(n+l). T~~L~ Suppose now that r(T~EL~), 13 Then M ~€Tf~Ln and lul=n+l} + n s max{sup{r(~;T~n~lt-1. : ~E~~L~ and Iv I =2} + n , < w• a. -zz.V€TM~L '' and Iv I =2h} + n) ~- n f which contradicts the induction hypothesis. Thus max{r(T~~L~}, r(T~~L~)} ~ w •a . = { Choose Ln+l L~ if r(T~~L~) ~ L '' n i f r ( TM ~ L ~ ) n < w•a Then Ln+l has the required properties and the induction step is complete. o This completes the proof of the lemma. Definition. Let T be a tree on Q[0,1] and k € IN. We define the subtree [T]k of T by <I 1 ,r 2 , ... ,In> € [T]k ~ <I 1,r 2 , .. ,In> € T and there exists J 2, ... , Jk € Q(0,1] such that <Il'J 2 , ... ,Jk,I 2 , ... ,In> € T. Lemma Proof. 5. Suppose Observe r(T~ ~I) from the ~ w • a. definition Then of for the each k € IN tree that M ~€ [T f ~Ilk and lvl=2} + k w •a , ~ r(<I 1 > ; T~~I) ~ w•a ,since all the nodes in T~~I otherwise - M the above inequality would M r(<I >;{Tf~I]k ~ w·a and so [Tf~I]k has rank~ Proposition 6. For f 1 shall € We w•(a+l). It will then follow that ordinal. Suppose p{f) ~ w • a for some M cD +. show that such that r(T~;x 0 ) ~ w ~a. such that I Ii I ~ hold. Thus w~a. D ND, p{f) is always a limit ordinal. Proof. € not w ~a p(f) ~ p(f) Now define the tree TN by + must 1 implies always be By lemma 4 there exists an x 0 Fix N € p{f) a IN. € ~ limit M Then by definition r(Tf) + 1. 1/i , Ii !;;; Ii-l and x 0 [0,1]). w •a ~ [O,l] Choose I 2 , ... , IN € Q[O,l] € IN. (Here as always I 1 = -24-- It is easy to see that TN is a subtree of Tr~ N ~ M~N Hence r(T f But w • a + N - 2 by lemma 5. ) ~ w •a + N - 2. So p(f) = sup{r(T~ ~ N) + 1 : N € IN} ~ Definition: sup{w• a + N - 1 : N € IN} = w~(a+l). For f 0 ND we define r(f) to be the unique ordinal a € such that p(f) = w •a. is a coanalytic norm on ND. We will now characterize the functions for which r(f) is small. We I t follows immediately that r make the following definition: Definition: Let f € C. We define the amp l i t ud e A(f;x) of the difference quotient of f at x by . If (x+h 1 )-f (x) f (x+h 2 )-f (x) I A(f;x) = l 1m sup ----.-h---h h ,h __.o 1 2 2 1 It follows that f € ND iff A(f;x) > O for each x € (0,1]. Moreover A(f;x) is finite iff all the Dini derivatives at x are finite. can rewrite the set BC, of all the Banach functions as So we -25BC = {f € C Proposition 1· ID+ r(f) = 1 ~ f is a Banach function. Suppose f is not a Banach function. Proof. "=>": x0 = +oo for each x € [0,1]} A(f;x) [0,1] such that A(f;x 0 ) is finite. € such that for all ~ M. I 6f(K)-6f(L) I Fix n. l/n and x 0 € I~ n). Q[O,l] with rAn) R[O,l] € with x0 Choose I~n) K,L € we so that r(f) w , II~n) I ~ Q[O,l] such that € have By the continuity of f we can find IA n) ~ I~n) ~ M/n for all K,L to We can thus find an M € shall show that r(T~) ~ We cannot be 1. suffice K,L Then there is an R[O,l] € Xo and choose with with IAn) € such that I 6f(K)-6f(L) I ~ K,L ~ I~ n). IA n) endpoints close € enough (It will to the endpoints of I~ n) .) !(n) JI f Now choose I ( n) Then it easy € 1 is that Ii see that <I1 (n) (n) I2 , ... ,In > to n. But this r(<I 1 >;T M f) ~ w. So r(T~) ~ now I ( n) such ~ Suppose -(n) Q[0,1] r(<I 1 >;T M f) "e": "' is true I for ~ each (i=3, .. .,n-1). i-1 n € € IN. M Tf' So Hence w and we are done. that r(f) ~ 1. Then r(f) > 1 and so p(f) ~ -26Thus for some M € en+, r(T~) w•2. ~ w So TM must + 1. f have a subtree as shown below: (n) h Let x0 be intervals a limit {IAn) }n~ 2 . point of the set of all midpoints of the Then there are arbitrarily small intervals I in the tree T~ arbitrarily close to x 0 . that x 0 + h 1 , x 0 + h 2 [0,1]. € Then as in the " =;." direction of the proof of Proposition 2 we get that Since this is true for all h 1 , h 2 we get that A(f;x0 ) ~ M. So f is not a Banach function. o Proposition ~- Suppose there is a c > 0 such that A(f;x) each x Then r(f) € {0,1}. ~ 2. ~ c for -27- Suppose r(f) Proof. E ({} + > The 2. p(f) such that r(T~) ~ w ~ 2 + 1. ~ w~3. So there is an M So T~ has a subtree as shown below, where each of the nodes <Il'I~ n) , ... ,rAn) > is of rank at least -w in TM f' 1~ II I~1 Fix n ~ r.> . .. l t E IN and consider the As in the subtree "e" 5: M/(n-1) . Xn rtnl n-1 of T~ direction Proposition 7 we see that there is a such that A{f;xn) l(nl z through the of point xn the € node proof of rA n) ~ rA:: l -zsBut this is true for each n € IN. So for large enough n we will have A(f ;xn) < c, which is a contradiction. :S; o 2. It is easy to construct an example of a function f with Remark. A(f;xn) Hence r(f) -+ O for some sequence {xn} ~ [0,1] but with r(f) will sketch this construction at the end of %3.) = 2. (We From this it follows that the converse of Proposition 8 is false. %2. Before we give our natural examples Some Natural Examples. we will introduce a notation which will prove very handy. be an interval with endpoints x and y (with x necessarily greater than x). define .6f(x,y) = f (y)-f (x) y-x For a We ;t: Let I y , and y not continuous function now turn to our f we natural examples. Weierstrass function: This function is by defined 0¢ f(x) = 2: an sin 7t'(bmx), where O < a < 1 and b is an odd integer n=O such that ab > 1 + 37t'/2. k € In A. N. Singh [46) it is shown that for Z, m € N -7t'(ab)m sin(k7t'/b) • sin 7t'(bmx + k/b) ( k7t' /b) for some e with I e I < 1, by using the Mean Value Theorem. (*) Now it -:Z.9- is clear that the absolute value of the first m terms is less than m-1 m ""' ?r:(ab)n < ?r:(abl '"' ab· Also it is easy to see that there are two n=O integers k 1 , k 2 with I k 1 I, I k 2 I ~ 3b/4 such that But for these k;s (i = 1,2) we have Hence term the last 1 im sup 16.f (x m~ oo 2k . I x + bm+\ in (*) dominates and we have JI = +oo, and so A(f;x) = +oo for each x € (0,1). It is easy to compute directly as in [21] p. 405 that f has right derivative +oo at x = 0 , and left derivative - oo at x = 1. A(f;x) = +oo for each x € [0,1]. that r(f) Thus From Proposition 7 it now follows = 1. Balzano function: iterating a This function is constructed geometrically by basic operation :r 0 on straight lines that are not parallel to one of the coordinate axes. line with endpoints P 0 Consider such a straight = (x 0 ,y0 ) and P 1 = (xl'y1 ). Let Q1 , Q 2 and Q3 be the points which are 3/8, 1/2 and 7/8 the way from P 0 to P 1 on [P 0 ,P 1 ] respectively. -30- Let Q{ be the image of the Q1 when it is reflected in the line y = (y 0 +y 1 )/2 and Q3 be the image of the point Q3 when it is reflected = y 1 . :Jo is defined to be the operation which takes in the line y the line segment P 0 P 1 to the polygonal path P 0 Q{Q 2 Q3P 1 . f 0 (x) = x for x € [O,l]. Jo (graph (f0 )). (graph (fn)). each Now let We define the function f 1 (x) by graph (f 1 ) = In general we define fn+l by graph (fn+l) = Jo It is understood that the operation :r0 is applied to straight line segment of graph (fn). This sequence <fn>n£1N of continuous functions on [O,l]. gives us a It is easy to see that fn converges to a continuous function f. Rychlik [ 43] obtained a parametric representation of f by continuous functions 'f' and cf>, with 'f' strictly increasing as shown below x = 'f'(O, f(x) = 4>(0 E € [O,l]. -'51- Using this representation he was able to show that if € kl k2 = T+ ~ k3 +~ 4 kl kn €; = + ~ •• + n T 4n and we put x~ = I • ; • + kn +.;; 4n , ki e: {0,1,2,3} € ,, = kl + ~ ~ ~ + kn+l T n 4n x'' n f ( x ,, ) - f ( x ; ) n n x" n x''-x" n n x'' n where is the function defined by X(O) =)'.(2) = 5/3, From this that A(f;x) [0,1]. it immediately follows ')((l) ~ = 'X.(3) 1 for Also an easy computation shows that A(f;l) = -1. each x = 2. X e: So by Propositions 7 and 8 we get that r(f) = 2. Kowalewski variant: G. Kowalewski (31] made a modification to the basic Bolzano operation 3' 0 to produce a variant of the Balzano function which was in some sense more natural. modified operation 3' 1. We shall call the Consider a straight line P 0 P 1 which is not parallel to a coordinate axis and with P 0 being lower than P 1 (i.e., if P 0 = (x 0 ,y0 ) and P 1 = (x 1 ,y 1 ) then Yo < y 1 ). Let Q1 , Q2 Q3 be the points which are 3/8, 1/2 and 7 /8 the way from P 0 to P 1 on [P 0 ,P 1 ] respectively. -3Z- be the image of Q1 when it is reflected in the Again we let Q{ line y = (y 0 + y 1 )/2 and Q3 be the image of Q3 when it is reflected in the line y = y 1. The operation :r 1 is defined to be the one which takes the line segment P 0 P 1 to the polygonal path P0 Q{Q 2 Q3P 1 . f. We proceed as before to obtain a continuous function Kowalewski (31] showed by geometrical means that f was nowhere differentiable. Singh (45] gave an analytic representation of this function as follows. A point x € (0,1) can be represented as if the an's and kn's are suitably chosen with kn € {0,1, ... ,7}. f(x) is then defined by where the q n 's are chosen from {-2,-1, ... ,5} according to a prescribed rule. Using this representation Singh showed that if x and x" are two points which first differ in their representation at the n-th place then I x-x "I < (3/8)n-l Moreover a point x '' can be found such that lf(x '')-f(x)I ~ (3/4)n- 2 Thus lf(x~t::~(x) I~ and 3•2n- 3 and so A(f;x) It is easy to see that at x € € - oo . Thus A(f;x) = for each This function was defined by T. Takagi [52]. [O,l] be represented as + • ~. and put = n-2 1 - 'T n· 2 'T ,/ and n The function f(t) is defined by f(t) + oo [0,1] and so from Proposition 7 we have that r(f) = 1. Takagi function: t = + oo for each x € (0,1). = 0, f(x) has right derivative + oo; and at x = 1, f(x) has left derivative x lx-x''I < lx-x"I. = = 0 00 2: n=l Yn , where Yn It is easy to see that f(t) = 1 = oo 2: an n=l 2n , where Let -:34=#of l's among c 1 , ... ,en =#of O's among c 1 , . .. ,en if en = O if en = 1 Moreover it is clear that f is single-valued since the numbers of the form = t m/2n (m,n € IN) (being the only t's representation) give rise to the same value f(t). that A(f;t) ~ 1/2 for each t with two We will prove [0,1]. Let us adopt the convention that the number t does not have en = 1 from some point onwards, € unless t = 1 (in which case en = 1 for all n € number has a unique representation. = 0 then 6f(t , t + 1/2n) = l'l"n - Now if en IN). Then each vn 2n+l1' n+l , and if cn-l = en = 0 then 6f(t , t + 1/2n) = l'l"n - vn. So if t is such that en = O and cn+l = O then 1 - 2 n+l 1'n+2; (*) and if t is such that en = O and cn+l = 1 then 2 n+l 7 n+2' Now let t € Case ill: en = O from some point onwards. that en [0,1]. Then there are there possible cases: = 0 for all n ~ n 0 . Thus r n from (*) for all n ~ (**) n 0 and so A(f ;t) ~ 1. So three is an n 0 such = O for all n ~ n 0 . Thus -ssCase (ii): There are infinitely many O's and infinitely many l's in So there is a sequence {nk} such that the unique expansion of t. en k = 0 and en + 1 = 1 for all k € IN. k 2 _(n +1) But (t - 2 k n+l Tn+2 ) has its nk-th and (nk + 1)-th term = O , so , tJ I = 1 - 2n+lT n+2 using Since (*). at least one of greater than or equal to 1/2 we get that (f;t) Case (iii): f(l) t = O and = 1. (1-2n+lT n+2 ) is 2n+lT n+l ~ 1/2. In this case a direct computation shows that f(l-2-n) = n/2n. This immediately shows that Thus f € A(f; 1) = +oo. So we have shown that A(f;t) and by Proposition 8, r(f) Problem. 1/2 for all t € [0,1]. ND 2. What is the rank of the Takagi function? Cellerier function: is defined by f(x) ~1000. ~ ~ This function was given by Cellerier [09] and = 2: a -nsin(7t'anx) where a is an even integer n=l Using the fact that a is an even integer we obtain as in -36- (21] p. 406 m-1 :L cos(7t'anx) + )...f) n=l where I e I < 1 and A. is a positive number depending only on a , which can be made arbitrarily small by taking a sufficiently large. Similarly we obtain m 6.f ( x,x + alm) where Ie"I a Thus --+ oo, < 1 = :L n=l and where I 11 I, In"' I < 1. 'A " depends only on a and Using this and the fact that a A. " ~ --+ 0 as 1000 we get that Hence A(f;x) ~ shows A(f;l) that 1/2 for each x e: (0,1). = + oo . Thus f e: A direct computation easily ND and by Proposition 8, -37- r(f) :s: 2. What is the rank of the Cellerier function? Problem: Morse-Besicovitch functions: A. P. Morse constructed [40] functions on (0,1] which were such that 1 im sup If ( x) .= f ( z) I = + oo x--.z x z for all z lim sup lf(x)-f(z) I= + oo x-z and (0,1] € for all z € [O,l] X--+Z+ (See also (34].) and were moreover Besicovitch functions. called Morse-Besicovitch functions for Such functions are obvious reasons. Now from the definition of a Morse-Besicovitch function we immediately have A(f;x) = + oo for all x from Proposition 7 that r(f) = 1. We shall denote the class of all [0,1]. € So it follows Morse-Besicovitch functions by MB. Knopp functions: K. Knopp (27] gave a general method of constructing nowhere differentiable functions by using a sequence {un(x)} of functions with certain properties. The sequence un(x) is 00 chosen so that 00 :L II un II converges, therefore n=O to a continuous function. 407-409. :L un (x) converges n=O For the details we also refer to [it] p. Now the construction of Knopp guarantees that A(f;x) = + oo for each x € (0,1). So if a Knopp function f is in ND (it might not be in ND because it is possible that it has a finite one-sided -38- = 0 or x = 1) then we have r(f) s 2 by using derivative at x Proposition 8. then of If in addition we also had that A(f;O) course we would get r(f) = 1. Most = A(f;l) = +oo of the nowhere differentiable functions which are expressed as an infinite series of functions can be obtained by the Knopp method. In particular so can the Weierstrass function. We have seen several natural examples of functions in ND and in all cases we had r(f) s 2. This supports our intuitive idea that natural examples should have rank 1 or cannot make this precise because the Of course we 2. concept of "natural" is rather vague. '§.3. The Rank Function !'. is Unbounded in section aim our there is an f € will be to show BF such that r(f) that = a. w 1 on BF. for each In this 1 s a < w1 To this end we introduce the following definition: Definition: the subtree and 3 Jk ~ I. x € Let f J 1, ... , Jk € € ND and M € IQ+. of by Q (O,l] such For each I <I 1 , ... ,In> € ~, f that Q[0,1] we define € e:> <I 1 , ... ,In> <I 1 , ... ,In,J 1 , ... ,Jk> € T~ T~, f is called the subtree of T~ based in I . [O,l] we also define r(x;T~) = min{r(T~, f): x € I € Q(0,1]}. and For each r(x;T~) Note. is to be s 1. Lemma 9: Suppose r(T M f) nested sequence Ln choose which was ~ Then there is an x € [0,1] such that w. of closed We shall find a intervals <Ln>n€1N with ) = r(T~) for each n € IN. n,f Ln gives us the result. We take L1 = [0,1]. Given ILnl < 2/n Taking x € a r(T~;x), The proof is very similar to Lemma 4. Proof: ~ from r(x;T~) is a tool we'll need only in this section. defined in 1/ n distinguished n n€1N L~,L~ such that r(T~ as in Lemma 4. Now observe that if <I 1 , .. ,In+l> is node of length n + 1 in T 1Mn, f then In+l c L~ or In+l c L~ . Thus any node in T~n , f of length ~n + 1 lies in at least one of M the trees T L ; n M f TL n'' I M which is not in Tr:' f then n which are of length ~ M = max{r(TL; at I Moreover if f v v can only have nodes extending it most n. w by the induction hypothesis, M ), r(TL'' )}. n,f n,f is a node Now let Since we see that -401 n+l = L; n M if r(TL ; ) n,f L''n M if r(TL; ) ) < r (TLM,, n,f n,f { = r(T~) = r(T~) This completes the induction step and we are done. D Consider the square, S with vertices at (0,0), (1/2,1/2), (1,0) and (1/2,-1/2). Let SF be the collection of all Besicovitch It is easy to see functions whose graph lie inside the square S. that S is non-empty / / / / / / / / / / '/ and by definition SF ~ BF. Let f f. C. By a sealed copv of f onto the interval [a,b] we mean the function g defined by g(x) = f(g=~), x f. [a,b]. Let I be a closed interval with rational endpoint and with I I I > 0. R(I) We define = {J ~ I; J is a non-empty interval open in I} Q(I) = {J f. R(I): J has rational endpoints} -41Definition: Let f € C and M € ~ + . M to define the tree T f ~I" Then there is an obvious way M We define T f ~I by and Vi = 2, ... , n we have - (i) Ii € Q{I), Ii ~ Ii-l' I Ii I s I I I Ii (ii) VK,L € and R(I) with In ~ K,L ~ Ii-l we have I 6f(K)-6f(L) I s M/(i-1). It follows immediately that if g f € Proof: € € The rank function r is unbounded in w 1 on SF. It will suffice to show that for each a < w SF such that p{f) prove f C and gH is a scaled copy of C onto I then T~ and T~ ~I are isomorphic. Proposition 10: f € because SF => p{f) ~ ~ we w ·a. 1 there is an For a = 0,1 or 2 there is nothing to know from Proposition Suppose the result is true for a. w ~ 2. that 7 We shall prove it for a. with ,..o(f) ~ w •a. The basic idea is to put scaled copies of f/n and so onto Choose obtain a function - Tlf/n - T~ we should get = sup{r(T~): n E IN ~ w ~a g € c. f € SF Since -4ZSo p(g) > w ·a and hence p(g) here. But there are two problems "concentrated" (0,1)). is Lemma 9). at f an its endpoints € SF (i.e., p(f) ~ •a with xM € (0/3,2/3) This replacing f if if latter such the rank f is r(x;T~), < r(T~) for all that for r(xM;T~) = r(T~) with condition can be by five scaled copies of f interval [0,1]. gt~= Moreover we might get problems with the of So we need to modify our process accordingly. Choose there = 0). "r(T~) ~ sup{r(Tg~Kn): n € IN}" inequality € w ~ (a+l). First the g obtained will not be in SF (because g would be differentiable at x x ~ each (by easily M € ~+ virtue of obtained by onto each fifth of the Define the function g by g(O) = o, and { scaled copy of f onto Kn n even f scaled copy of 2n onto Kn n odd --·--=.. , . ~~·~·,, w<--.A ~v v 0 C, and by construction g has no Then it is clear that g € unilateral finite except derivative, perhaps at x derivative at x = o. = o. Let B = sup{lf(x) I: x or infinite We show that g € [0,1]} > o. at any point, has no right Let x 0 be a point in [0,1] at which B is attained (i.e. I f(x 0 ) I = B) and let xn be the image of x 0 in Kn when f is scaled onto Kn. I K2 n I = 2 since -2n . € ~:~=~~ = ~ for all n So But g(2-2n)-g(O) 2-2n_o l Then g(x 2 n) = B/2- 2 n, I= O for all n € IN. Hence g has € IN. no right derivative at x = 0. Now it is easy to see that the graph of g must the square p{g) lie ~ in S, g € SF. We claim that w~(a+l). Consider now the functions tree given by Tn =(TA of Kn. so n' g~Kn for n odd. Let Tn be the g~K ] 3 where Hn is the middle open third 1 n Then each interval in the tree Tn is open in [0,1] and So Moreover p(f) = sup{r(T~n) + 1: n € IN, n odd} = sup{r(T n> + 4: n € IN, n odd} Since p(f) is a limit ordinal it follows that -4+sup{r(Tn): n IN, n odd} ~ p(f) • € Now let T~ be the tree defined by We claim that T~ 4 is a subtree of Tg. Because of the way Tn was chosen it will suffice to show that for any interval Im in for all K,L € R[0,1] with Im ~ K,L ~ 9 s 4. Now if K contains an encpoint of some Kn then I 6 9 (K) I and for if = I 6g(K) - 6 9 (Kn I s 1 (since The same holds for L. and [0,1] we have I 6~(K)-6 (L) I construction; T~ Tn was a I 6 (K) I 9 some s 2 by n then subtree of Tg~K ',. 1 n So we always have 4 Thus T ~ is a subtree of Tg· Hence r(T~) ~ sup{r(T~): n € IN, n odd} = sup r(Tn): ~ p(f) ~ w• a So p(g) = sup{r(TM) + 1: M € it!+} w •a + 1. ordinal it follows that..o(g) ~ w~(a+l). Since ,p(g) is a limit -+sSuppose now that the result is true for all a < A. where A. is a limit ordinal. Let <an> nE IN be an increasing sequence of ordinals with lim an =A.. with p(hn) ~ For each n Mn € <O IN there is an hn € SF w•(an+l) such that for each M € ([)+ there is an n M = M ). in (1 / 3,2/3) with r(xM;Tn r(Th ) n n an € + also . fn = hn/( Mn+1) such Then that So for each n M r(Th n) n ~ € IN there is Now w•an. M r(T f ) ~ r(Th n) n n ~ w•a n M n Mn r(xM ;T f ) = r(Tfn) for each n € IN. n n n We proceed as before by defining g by g(O) = O and g~Kn 0 = scaled copy of f2 onto Kn scaled copy of fn onto Kn { n even n odd ~ let and -46As before we see that the scaled copy of f 2 in K2 n = 0. ensures that g has no derivative at x clearly in the square, S. So g € for n € JN Also the graph of g is SF. Finally by the same argument as before we get r(T~ ~ sup{r(T~ ): n € JN, n odd} ~ sup{w~ an: JN, n odd} n Thus p(g) ~ w•(>,+1) ~ n € w•A. and we are done. 0 ND and BF are not Borel subsets of c. Corollary 11. Proof. The result for ND follows immediately from Proposition 10 and Proposition 0.1. The result for BF follows from Proposition 10 o and Proposition 0.2. The next result shows that by refining the process given in proposition 10, we could find for each 1 ~ a < w1 an f € BF such that r(f) = a. Proposition 12. r(f) For each 1 ~ a < w1 there is an f € BF such that = a. Proof. For a = 1 we simply take any f E BC "' BF, a -47Morse-Besicovitch function would do nicely. each 2 ~ a < w 1 there is induction on a. For a x e: {0,1) an (such We will show that for an f e: SF ~ BF such that r{f) = a / by = 1 take f e: SF with A{f;x) = +oo for each f can be easily constructed from a Morse-Besicovitch function by literally "squeezing" its graph into the square). Then by Proposition 8 it follows that r(f) Now suppose the result is true for be such that p{f) = oo ~ a and for xM e: {1/3,2/3) with r{xM;T~) = r(T~). as in Proposition 10. each a, M e: a ~ = 2. Let f e: SF 2. fl)+ there is an Let g be constructed from f We claim that p{g) = vP{a+l). This will give us a function g with r(g) = a + 1, so that the result will be true for a + 1. Because of Proposition 10 we need only prove that p(g) ~ w•(a+l). So T~ has a subtree as shown below with each of the nodes v = <I 1 ,I~n) , ... ,rAn)> satisfying r(~n;~) ~ w• a. re", ... l Fix n e: IN defined by and consider the subtree Tn through the node :.::n -41u € Tn <:::::::> M u € Tg' and u ~ ".:n or ~n ~ u. Since it 3xn € way 0. this as in Lemma 4 that rA n) ~ rA:!. l such that r(Tn;xn) ~ w ~a. But from the r(T M g;x) < w • a for each g x ;e 0 follows was constructed (because we know that r(T~ ~ K ) < w • a) in Kn we had . So xn n Now as in Proposition 8 we see that A(g:O) is true for each g t ND, a contradiction. n we get must be ~ M/(n-1). Since that A(g;O) = 0 which implies So we have p(g) = w•(a+l). To complete the proof we need to show tht if the result is true for all a < A., A. a limit ordinal then it is also true for A.. In order to do this we must modify the construction given in Proposition 10 satisfied a < A.. ~(g) (because ~ w•(A.+1)) g we Suppose ended the up with result is there always true for all Let <an>n€1N be a strictly increasing sequence of ordinals with lim a n = A.. that the Choose fn € SF as before in Proposition 10 such r(fn;O) = r(fnJ1) = 1 for each n € IN also. Define g by g(O) = O and gf' L = { scaled copy of 2nf onto Ln n scaled copy of fn where Ln = [1/n+l,1/n] to see that g € SF. n = 1,2,3, ... onto Ln n even n odd Then once again it is easy Also for each odd n, we can show exactly as in Proposition 10 that r(T gl 6 n) ~ w~ an. Thus p(g) = sup{r(T~) + 1: M € ~+} -4-9- f '"'" ) + 1: n e IN, n odd} = A.. ;:: sup r(Tg 0 / / / / / / 1. 1----.,..----1.__~~~~~._,..~~~~~- Lz. So we need to show that p(g) s A., and the proof will be complete. Fix M e ~+ and consider the intervals Ln ( n e IN) . Let B = sup{ I f (x) I: x e [0,1]} > O and suppose B is attained at x 0 (i.e., 2 I f (x ) I 2 0 = B). Let xn be the image of x 0 in L 2 n when 2(2n)f 2 is scaled onto L 2 n. Then g(xn) _ 2B = 2n 4nB ( 2n+ 1) - 2 n+ l · -.501 So lg(x2n)-g(~) I X2n-~ 2B 2n+T ~ 1 1 rn-~ = n ( n+ 1) B > nB 2n+i l21\+I ~ ~ _____ ____ , Lin _L I Zr\ W2 Now let n 0 = [M/B] + 1. L2n+l is L ~ [O,l] in the but Then for all n tree TM g I 6 (K)-6g(L) I 9 ~ no, no subinterval (otherwise we would nB/2 < M if we ~ So for each x € of J !;; K, have take j K,L as [O,l] we have r(~;x ~ sup{r(T~ ;x): n ~ 2n 0 } n ~ sup{o(fn): n So I (T M g) < p(f 2 n ) + w < w ·A. ~ 2n 0 } ~ p(f 2 n ). 0 (otherwise by Lemma 4 we could get 0 an x € [0,1] each M € ({)+. since p(g) with Thus for So w ~A. is a limit = w ·A. and the proof is done. ordinal. This now shows that D -51It r( c • f) follows immediately from the = r(f) for each c ~ 0 and f € ND. definition of r that Proposition 11 thus shows that there are w 1 many essentially distinct Besicovitch functions. Propo~ition 11 also shows that each level of the w1-hierarchy that r induces on ND and BF is nonempty. picture to exhibit this structure as shown below: BF ND ,- - -- - - - -- - - - - - - --'+------ r(f) = ,- - 6). 2 ref)= w r(t) ::a z r(.f) .,. 1 BC natural We draw a -sz.Before we conclude this section we make some remarks about the construction of a function with r(f) = 2,but such that A(f ;~) ~ O for some sequence {~} in [0,1) (that was promised in !.1) . Let ~ be as in the proof of Proposition 10. Choose a function f o , 1/2 and 1 where A ( f ; x) € = +oo except at SF with A(f ;x) :s: 1 . Now define g by g(O) = O and scaled copy of 2n/ 2 f onto ~ n even gtKn = { scaled copy of 2-n/ 2 f onto ~ n odd Then it is easy to verify that g € BF_, The = +oo. reason is because A(g;O) construction of g we have r(T~) Also r(~;O) finite} . w, < So V'M < bu~ ls not in SF. Now w~2 from for each M € ~ +. for each M (otherwise A(g;O) (r<T:) :s: w~2). So p(g) :s: there would be an M with r(T~) > see that r(g) But A(g:~n) is exactly 2. w~2). odd n, where xn is the midpoint of Kn. the w~2 would be (otherwise Since r(f) = 2, we :s: 2-n/ 2 for all So we are done. -s~- s4: Cantor-Bendixson Analysis. In this our last section of Chapter 1 we formulate an alternative description of the rank function r, by means of a Cantor-Bendixson Analysis. Recall the definitions s3. beginning of of R(I) and We will denote by Q(I) Q(I) from the the set of all closed subintervals of I that have rational endpoints and length greater than O. For each we shall define J € Q[0,1] a f E C and, M E IQ+ and sequence closed sets)and a relation Q(W,x,P~,f~J) which reflect the properties of f. M is to be thought of as being large and Q(W,x,P~,f~J) is to witnesses x that E be interpreted P~,f~J". as the Here W will relation range over "W the closed subsets of J. Definition. We define the set PM,f~J by x € PM,f~J e::> sup{l6f(K)-6f(L) I: x € K,L E R(J)} ~ M. We define the sets P~,f~J and the relation Q(W,x,P~,f~J) by induction as follows: Let P~:?~J = {x € J: For all I€ Q(J) with x €I 3H € Q(I}, 3y € int 3 (H), 3V ~ PM,f~J s.t. Q(V,y,P~~III ,f~H)} -54- rl --"'-"' ( • •1 ) [ x y 1 a+l Q(W,x,PM,f~J) <==>For all I 3y € € Q(J) with x I € int 3 (H), 3V ~ W~ 3H € Q(I), PM,f~J such that W(V,y,P~;III ,f~H); and = Va < for A a limit ordinal. By int 3 (H) we mean the interior of H with respect to the topology of J. Observe that our definition is made by use of simultaneous induction on a , M and J. see that P~,f~J is always a closed set. a ~ It is easy to Moreover and 8 ( *) When J is the interval [ O, 1] we shall refer to P~, f ~J -55a simply as PM,f" We will prove < Proposition 16 that f € ND ¢:::> for a So for each N € IN wl such that PM,f = 0. a Thus by using Wl such that PN,f = 0 for all a ~ aN. each M € <O+ Va 3aN in < ( * ) we see a PM, f = for all that if a ~ sup{aN:N € IN} wl ' we have that This allows us to 13 and all M € <O+. 13 = make the following def int ion: Definition. We define a new rank function r 1 on ND by a such thatP~,f = 0 for all M € <O+ ... Our main goal in this section will be to show that r and r 1 define the same rank function. Definition. Let f €ND, M € <O + and J € Q[O,l]. M subset W of J we define the subtree W(Tf~J) of M Tf~J by If x € P~,f~J and W satisfies Q{W,x,P~,f~J) Lemma L~. Proof. For each then We prove the result by simultaneous induction on a, M and J. For a Also the result = 1 the result reduces to Proposition 7. follows trivially for limit ordinals -5GA A because of the way PM,f~J and Q(W,x,PM,f~J) were defined. So assume that M e: <D + and a 11 j for a+ 1, Fix now the result e: Q [ 0 , 1 ] . a, for all Me: <D+ and all J e: Q[0,1]. I 0 e: Q(J) with x e: I 0 . M IN for We must show that that r(W(Tf~J) ~I 0 ) ~ w• (a+). Ne: true is It will for all it is true So fix M,J. suffice to show We shall show that for each the tree W(T~~J)~I 0 has a node of rank ~w·a + (N-1). The result follows immediately from this. So we now N e: fix IN. Choose IN e: Q ( J) such that From the assumptions on x we know that thee exists V ~ W ri PM, f~J such that we also have H e: Q(IN), y e: int 3 (H) Q(V,y,P~~IINI ,f~H). Q(V,y,P~/N,f~H) and and Since by the induction hypothesis we thus get r(V(Tf~~~H);y) ~ w~a. Now choose I' e: Q(H) ri Q(J) with ye: I' and II'I < IJl/N. Then Lemma 5 gives us r([V(T~~~)~I']N) ~ ( ( . )( w•a. I' '"""'""' [ ( •)] ) y '--v---J H ) -57- Choose I' ~ IN th ot such I 2 , . . . , IN € Q ( H) f"I Q ( J) (Here course taken <I 1 , ... , Ii> to be J.) Now = 1, TN for each i € <NH,J2, ... ,Jk> € define the and I1 is of tree TN by .. . , N and [V(T~~~)~I;]N ~ It is then easy to see that r(<J>;TN) ~ r(<H>;[V(T~~~)~I;]N) + (N-1) ~ w~a+(N-1). To complete the proof it will thus suffice to show that TN is a subtree of M W(Tf~J)~I 0 . We must show that I 2 I 0 , W f"I Im ~ 0, and for all K,L ~ Now H ~ Io so I2 ~ Io· I2 € R(J) with € Q(H) and Also W f"I IM ~ V f"I Im ~ 0 since y the € V f"I Im if m ~ N, and i f m > N then V ('\ IM definition of [V(T~~:)~I;]N ~ M/n from 16f(K)-6f(L) I [V(T~~~)~I;]N l6f(K)-6f(L) I the Also ~ M/N ~ M/n (since Now 2 0 by N then of the tree n N then ~ M/N for n if definition if ~ ~ ~ 16f(K;)-6f(L;) I > -58- a 11 K ",L " then I ~(K)-.6.f(L) I € with R(H) ~ Im ~ K " , L " ~ H) . if 1M ~ V f'\ Im '1: 0. PM,f~J f'\ M because Fina 11 y is a subtree of W(~ ~ 3 ) ~ I 0 and the proof is complete. Definition. We also define for each k € = 1 n So TN o the subtree [T]k of T IN by <I 1 ,I 2 , ... ,In> € [T] k <::=> there exists J 2, ... , Jnk <I 1 ,J 2 , ... ,Jnk> € {T]k and Ji~k = Ii+l for all i € Q(J) such that = 1, ..•, n - 1. We can show exactly as in Lemma 5 that the f llowing result is true. Sub-lemma 14. Suppose T is a transitive sub-tree of TM f ~J , I Q(J) and r(T ~I) ~ w ~a. Then for each k € IN the subtree [T~I]k is transitive and r([T~I]k) ~ w~ a. Lemma 15. Let f € ~ ~ J with r(T;x) ~ Q(W,x,PM, f ~ 3 ). Proof. J. € D ND and suppose T is a transitive subtree of w •a. Let also W = {z In particular x € € J: r(T;z) ~ w}. Then P~, f ~ 3 . We prove the result by simultaneous induction on a, M and For a = 1 the result reduces to Proposition 7, and for limit ordinals it follows routinely as in Lemma 13. -59- So assume that the result is true for a, for all M € and all J all M € We have to show that it is true for a + 1, for Q[0,1]. € and all J II)+ II)+ € Q[0,1]. So fix J,M. It will suffice to show that r(T;x) ~ w~(a+l) => Q(W,x,P~~~~J). Now fix I € Q(J) with x € I. We must find H Q(I), y € € int3 (H) and v ~ w f'a PM,f ~J such that Q(V,y,P~~ 1 I 1 , f ~u>· Since r(T;x) has T ~I a ~ subtree w•(a+l) as we have that shown below r(T~I) with ~ each w~(a+l). of the So nodes · in T ~ I • <I 1 ,I 2(n) , ••• ,In(n) > h aving rank ;l:w •a l(N) IL 2. ,,--A---.. r~1· ( .. •x ( ( I y ] ) .....__, H I I (n) n Choose N1 € IN so that 1/N 1 :s: I I I. that 1/N .,,.""' l(N) and put H = I-(NN) • Nl 1 Choose also N ;:: N1 + 1 so Then H I~N) ~ I by definition of the tree T~I. a node w • a. of rank € Q(I) since f(N) Nl ~ Since <I 1 ,I~N) , ..• ,I~N» is ~ w • a in the tree T ~I,/ we have r(T ~I~ N) ) ~ Now let TN be the tree defined by -60- TN is essentially the same tree as Also it is easy to see by a direct verification TN is transitive. M/N 1 that TN is a subtree of T f~H • So int3 (H) by [T~I~N) JN so by Sub-lemma 14, lemma 4 we such that r(TN;y) Moreover r(TN) ;?: w~ a. know ;?: there w• a. is = {z € H: r(TN;z) ;?: w}. Let V Then Q(V,y,P~/Hl, f ~H) by the induction hypothesis. II I we get Q(V,y,P~ ~ 1 I 1 , f ~a>· that Moreover Since 1/N1 :s: since TN is essentially the tree [T~I~N) ]N ~ T we have r(T N;z) Thus V !;;;; W. ;;::i: w ~ r(T;z) Proposition 16. Let f So V f; W f"I PM,f~J' and we are done. € c. Then f there exist a < w 1 such that P~, f that r(~) would get w ~r(f)). "e": Suppose f < w. Finally from the definition of W we know that W ~ PM,f~J' by Proposition 7. Proof: "=>": ;;::i: w • r(f). r(~;x) ;;::i: € ND. € ND <=> o for each M € ft!+, = 0. Then for a fixed M So from Lemma 13, P~ ~ f) € G:i+ we know = 0 (otherwise we w • r(f) for some x, and this would give r(T~) ~ So we are done. Suppose f t ND. Then there is an x € [0,1] such that f is -61differentiable Q( {x} x. at ,x ,P~, f) for all aga € ORD. are done. Proof. verification that So P~, f is never empty and we For each f ND r 1 (f) = r(f). € From lemma 13 we immediately have r 1 (f) need to show that r(f) ~ r 1 (f). Let a and so by lemma 15 r(T~;x) = 0 But this implies that r(T~) < we have that p(f) Final Remarks. of the shows o Proposition 17. P~, f direct A ~ w ·a. r(f). So we only = r 1 (f) and fix M. < w ~a for all x Then (0,1]. € Since this is true for each M w ·a. Thus r(f) ~ ~ a 1 = r 1 (f). 0 In this section we gave an alternative description rank function r, by using a Cantor-Bendixson Analysis . This Cantor-Bendixson Analysis was however very complicated. fact that possibility the trees of any T~ are simple transitive perhaps Cantor-Bendixson rules out Analysis The the (e.g., one which uses a derivative like operation) but this is not clear. So we pose the following problem. Problem. Is there a simple Cantor-Bendixson Analysis which gives rise to the same rank function r? -62.Chapter 2 Introduction. In 1906 P. Fatou (14] asked whether a trigonometric series with coefficients tending to zero must converge on a set of positive measure. N. Lusin (33] answered this question in the negative by constructing such a series which was divergent a.e. (S. B. Stechkin (48] later showed this series was in fact everywhere divergent). Not much later H. Steinhaus (49] constructed such a series which was everywhere divergent. In the years that follow more examples of everywhere divergent trigonometric series with coefficients tending to zero were given, among them being the one by G. H. Hardy and J. E. Littlewood (18]. Steinhaus himself also produced another much simpler example and proved by elementary means that it was everywhere divergent (see (51]). However none of these examples was a Fourier Series. was natural to ask whether there could be an So it everywhere divergent Fourier series (or at least a Fourier Series that is divergent a.e.) Steinhaus (50 ] had shown there was an orthonormal series {'f' n> and an integrable function f such that the orthonormal expansion of f with respect to {'f'n} was everywhere divergent but this orthonormal sequence was of course artificial and so shed no light on the problem. Then Kolmogorov (28] showed in 1923 that there was an integrable function f whose Fourier series was divergent a.e. Using the same idea in 1926 Kolmogorov also showed (see (29]) that there was a function, f whose Fourier _,3_ Series was everywhere divergent. (In fact it turned out that the Fourier series of this f was unboundedly divergent everywhere.) Since then this has remained essentially the only way of constructing everywhere divergent Fourier Series. I t is very the Fourier series. natural to ask whether the conjugate series of series of Kolmogorov is function also a Fourier This turns out to be false but Y. M. Chen [10] showed that there was a function f such that the conjugate series of S(f) is a Fourier series and S(f) diverges unboundedly everywhere. It is also natural to ask whether there is a function whose Fourier series is such that lim sup I (Sn(f;x) I < oo for each x. This was shown to be false because of Carlson's Theorem (see [30]). However J. Marcinkiewicz (see [35]) showed that there is an f such that lim sup I Sn(f;x) I < oo a.e. and S(f) diverges a.e. In another direction we can ask how fast can the coefficients of an everywhere divergent trigonometric series tend to zero. Stechkin [48] showed that there are everywhere divergent trigonometric series whose coefficients tend to zero as fast as permissible. More ~ (min{rk:l~k~n}) 2 = +oo, n=l precisely then r if there n > O exists 1 and such that sequence of for n {'fn} ~ IR ~ 00 the series L: rn cos(nx-'fn+~) diverges for all x and ~. n=l Finally we can ask questions about the -64coefficients of an everywhere divergent trigonometric series with coefficients that tend to zero. How thin for example can this (i.e., how large can the gaps of zeros sequence be? successive nonzero terms be?) between We know that if the sequence is lacunary then trigonometric series will converge on a dense set (see [04], p. 186). A. S. Belov [06) however constructed examples which have large gaps of zeros between successive non-zero terms and which in a sense fall just short of being lacunary. In this chapter we study the structure of the set of all everywhere divergent Fourier series, and the set of all everywhere divergent trigonometric series with coefficients which Let 11' be the unit circle and C(11')w be the Polish tend to zero. space of all sequences of continuous functions on 1J'. We will view 11' as the closed interval [0,27t'] with the points 0 and 27t' identified. An element <fm> of C(11')w will be denoted by f convenient. Let when DS = {f € C(11')w: f is everywhere divergent} DZ= <! € DS: llfm+l-fmll -+ 0 as m -+ oo} DT = {f € DZ: fm is the m-th partial sum of a trigonometric series}, and DF = {f € DZ: f m is the m-th partial sum of the Fourier series of some f} Then DF and DT can be naturally identified with the set of everywhere divergent Fourier Series and the set of everywhere divergent trigonometric series with coefficients tending to zero. -65The sets DF and DT may be viewed as subsets of the space (c 0 ) of all Z-sequences which tend to zero. DF may also be viewed as a subset of the Polish space L 1 ('lf) of all Lebesgue integrable But no matter how we view DF and DT it is easy to functions on ']f. see that they are coanalytic subsets. that DF is a complete coanalytic A. S. Kechris [25] showed subset and, by the general argument he presented there, the same result can be deduced for DT. In this chapter we investigate a natural rank function r on DS. The analysis is very similar to that of Chapter 1 and although the definitions are sometimes slightly more complicated, the proofs are much simpler. norm and provides a sequences in DS. the divergence The rank function r is a coanalytic natural measure of the complexity of the r(f) measures in some sense the uniformity of of f. It turns out that sequences which are uniformly divergent have ranks 1 or 2 (c.f. [01] where it is shown that the functions of rank 1 are those with uniformly convergent Fourier Series). Also sequences which are unboundedly divergent have rank 1 (c.f. Proposition 1.7). The rank function applies naturally to the set of everywhere divergent Fourier series and the set of everywhere divergent trigonometric series with coefficients tending to zero. We consider some natural examples of such series to confirm our intuitive idea that such examples should have small ranks (1 or 2). We also show that for each 1 ~ a with rank a. This will < w1, there is a Fourier series provide Rank Arguments of the non-Borelness of DF and DT. Tree Description: The Rank Functions p and ~· As in Chapter 1 we study the set DS by associating with each ,_,,f DS a countable collection of well-founded trees. € We first check that DS, DZ, DT and DF are coanalytic subsets. Proposition 1. DS, DZ, DT and DF are all coanalytic subsets. Proof. Observe that f € C(T)w - DS iff 3x Vm3n such that (* ) Let E(m,n) = {(f,x) is closed and so € C(T)w X T: n U ( *) holds} . Then E(m,n) E(m,n) is Borel. Hence C(T)w - DS Borel C (T) w and so ID€1N n€1N is the projection analytic. of a set onto is Thus DS is a coanalytic subset of C(T)w. To see that DZ, DT and DF are also coanalytic observe that these sets are just subsets of DS which satisfy added Borel conditions. Thus DZ, DT and DF are intersections of DS with Borel sets and hence are coanalytic. If we view DT and DF as subsets of (c 0 ) then we also have that DT and DF -67- are coanal yt ic subsets of (c 0 ) . This is because the map c k eikx> n£1N is a Borel measurable inJ·ection. { c n } n€~ - < ~ ~ k=-n So DT and DF are pre-images of coanalytic subsets under a Similarly DF viewed as a subset of Borel measurable map. L1 (11') is also coanalytic because the map n f - < L: k=-n is a Borel measurable injection. Let Q (11') be the 0 collection of all closed intervals which have length greater than zero and endpoints in ~~~. ~+ we shall associate a tree With each f € C(11')w and M € T~ on Q ( 11') X IN. Definition. ( i) We define the tree T~ as follows I 1 = 11', k 1 = 1 and for al 1 i = 2, ( ii ) Ii conditions following the € Q ( 11') , I Ii I s 2 ~Ii , ... , n Ii ~ Ii- l and k i hold > ki _1 , -68- . I fm (x)-fm (x) I :s: M/(i-1). 1 2 It follows immediately from the definition that M; . M Tf M; Tf if M :s: Our next result tells us exactly when T~ is well founded for all M € ca+. f Proof. Suppose for some M € "=>": € DS e::> 'IM € ca+ (T~ is well-founded). Proposition _g_. ca+, T~ is not well-founded. rj. Then there is an infinite branch <(In,kn)>nEIN in n ~ In. We shall show that n€1N given. ! converges at x 0 . Choose i such that M/i < €. m1,m 2 . Let c > Now let m1 ,m 2 Since {kn} is strictly increasing there is a j Let {x0 } = ~ o be ki be given. such that kj ~ So from the definition of the tree T~ we have 'Ix € If I fm (x)-fm (x) I :s: M/i) 1 2 In particular since x 0 € I:r we get :s: M/i < .(, and so ! converges at x 0 . Suppose ~ converges at some x 0 . "<=": M ~ 2_ sup{ If m(x 0 ) I: m € IN} + 1. Choose M € ID+ such that Choose also a strictly increasing sequence <kn> such that k 1 = 1, and Let also <In> be a nested sequence of closed intervals in T with x0 € In for all n, such that conditions (i) and (ii) of the definition of T~ holds and (This last condition can be obtained because of the continuity of the functions fm at x 0 .) infinite branch in T~. We shall show that <(In,kn)>n€1N is an It will suffice to verify condition (iii) of the definition of the tree T~. For all x € In and all ml'm 2 € < -fn + I fml (xo) I + I fm2 (xo) I + fn < l/3n + (M-1) + 1/3n < M/1 -70- <l+l+l~l<!':! 3n TI 3n i 1 So condition (iii) is satisfied and we are done. Let f € DS and M rank of ~ is countable. € ID+. Since Q(T) Also since TM f D x IN is countable the ~ TM" f for M ~ M" we have Definition. We define the rank function p:ND -+ w 1 by Proposition ~· Proof. p:ND -+ w 1 is a coanalytic norm. The proof is identical to that of Proposition 1.3. o Our next aim is to show that p(f) is always a limit ordinal. -71We proceed exactly as in Chapter 1. Definition. Let I € Q(11') and T be a tree on Q(11') x IN. We define the subtree T~I of T by <(I 1 ,k 1 ),(I 2 ,k 2 ), ... ,(In,kn)> € 11'~I ~ <(Il'kl ),(I 2 ,k 2 ), ... ,(In,kn)> € T and I 2 ~ I Let f € DS and M € ID+. For each x r(T~;x) = min{r(T~~I): x 4. Proof. Same as that of Lemma 1.4. Definition. € 11' we define int(I), I € Q(11')} r(T~ ~ w ~ a then there is an x Lemma If € Let T be a tree on Q(11') € 11' such that D x IN and p € IN. We define the subtree [T] p of T by <(I 1 ,k 1 ), ... ,(In,kn)> € [T]P ~ <(I 1 ,k 1 ), ... ,(In,kn)> € T and there exist (J2,.22), ... ,(Jp,.2p) € Q(11') X IN such that <(Il'k 1 ),(J 2 ,.e 2 ), ... ,(JP,.2P),(I 2 ,k 2 ), ... ,(In,kn)> € T. -72.- r(T~~I) Suppose ~ Lemma 5. Proof. Same as that of Lemma 1.5. Proposition §. It Proof. Let f € DS. will suffice Then w•a. for each p € ~ D Then p(f) is a limit ordinal. to ~ show that p(f) w •a + 1 => p(f) ~ "' w • (a+l). Suppose p(~) ~ ~ So by lemma 4 there is an x 0 w ~a. w •a + 1. Then for some M € € 11" such that <O+, r(T~) r(T~;x 0 ) ~ w• a. Fix N Ii-l' I Ii I ~ € ~. For i 27t'/i, x 0 € = 1, ... , N choose Ii € Q(1r) such that Ii ~ IN and ki= i. (As usual I 1 = 1r and k 1 = 1.) Now define the tree TN by <(I 1 ,k 1 ), ... ,(Ii,ki)> € TN i = 1, ... , N, and <(I1,k1),(J2,.22), ... ,(Jn,.2n)> € [T~~IN]N => "' -'13Then it is easy to see that TN is a subtree of T~·N. ;;!: w.; a + (N-2) But by Lemma 5. Since this is true for each N € ~ we have ;;!: ;;!: sup{r(TN)+l:N€ IN} sup{w•a+(N-l):N€1N} = w.;(a+l). This completes the proof. Definition. D For f € DS we define r(f) to be the unique ordinal a such that p(f) = w•a. ,._, I t follows immediately that r is a coanalytic norm on DS. Moreover since DZ, DT and DF are intersections of DS with Borel sets, r is also a coanalytic norm on DZ, DT and DF. When we view the elements of DT as formal trigonometric series we shall also use r(S) to denote the rank of the series S. When we view the elements of DF as functions in L1 (T} we shall use r(f} to denote the rank of the function f. Our next goal is to characterize the elements of DS which -74For this we have small rank. introduce a notion of uniform divergence. Definition. Let f € We say that f is strongllJ uniformlv C(T)w. d i v e r g en t if 3c 0 > o 3p0 VnVx3m 1 ,m 2 € [n,n+p 0 ]( I fm (x)-fm (x) I;:: c0 ). 1 2 We say that ,....,f is unbound e d l lJ u n i form l lJ d i v erg en t if VB > OVn3p 0 Vx3m 1,m 2 € [n,n+p 0 ]( I fm (x)-fm (x) I ;::B). 1 2 And we say that f is uni forml lJ divergent if "" It follows immediately that strong uniform divergence ~ uniform divergence unbounded uniform divergence ~ uniform divergence. To make the definitions clear we give the following examples. Example 1· fm(x) = (-l)m Vm € Example _g. fm(x) = log m Vm € IN Example~· fm(x) = { JN vx € 'f. vz € 'f. 1 if m = 2k for some k 0 otherwise. Vx Example_!. T, IN m odd m even x where € € = 21't' { x € [21't'/m,21't'] x = 0 linear on [0,21't'/m] -7S- 21f'. Example 1 is strongly uniformly divergent but not unboundedly uniformly divergent. Example 2 is unbounded uniformly divergent but not strongly uniformly divergent. divergent but neither unboundedly strongly uniformly divergent. Example 3 is uniformly uniformly divergent nor Example 4 is everywhere divergent but not uniformly divergent. Proposition 7. If f is strongly uniformly divergent then r(f) = 1. Proof. ~+. It will suffice to show that r(T~) is finite for each M E: Since f is strongly uniformly divergent we have 3c 0 > o 3p0 'v'n'v'x3m ,m £ [n,n+p 0 ] 1 2 such that If m (x)-fm (x) I ;3: c 0 1 2 (*) We claim that any node in T~ must have length at most i 0 + Po· -7r;,From this it will follow that r(T~) is finite. Suppose <(I 1,k 1 ), ... ,(Iq,kq)> is a node in ~ of length greater than i 0 + Po· Then kq ~ k. ~ k. io+Po io + Po · But from the aefinition of T~ we have which contradicts (*). The Remark. Hence the results follow. concept of strong restrictive to be of much use. have fm+l (x0 ) - fm(x 0 ) --+ uniform in DZ divergence In fact if for some x 0 is £ too T we 0 as m --+ oo , then it is easy to see that <fm> cannot be strongly uniformly divergent. sequences D cannot ever In particular the be strongly uniformly divergent. (Moreover example 3 shows that even the requirement fm+l (x 0 ) fm(x 0 ) strong --+ O for some x 0 , is not necessary in order not to have uniform divergence.) So we shall no longer concern ourselves with strong uniform divergence. Definition. Let ! £ C(l')w and x 0 £ T. We define the a.mp l i t ud e of divergence off at x 0 by It is then clear that f diverges at x 0 iff A(!;x0 ) > 0. We say -77that f div erg es unbounded l v if for each x e: T, A(f;x) = +oo. Proposition ~· (i) Let f e: C(T)w. Then f is unboundedly uniformly divergent ~ f is "" boundedly divergent. (ii) f is uniformly divergent ~ there is a c > O "" such that A(f;x) ~ c for all x e: T. Proof. "<=" (i) The "=>" direction is trivial so we shall only prove the So direction. divergent. suppose f is not uniformly Then For each p e: ~ choose xp such that Now let x 0 be a limit point of the xp's. +oo. unboundedly We claim that A(!;x0 ) < is not unboundedly divergent From this it follows that f "" and this establishes the result. It will suffice to show that for :s: B 0 . 2 Take s > O. Choose p such that p > I f m (x0 )-f m (x0 ) I 1 So let m1,m 2 > n 0 be given. -78by using the continuity of fm and fm at x 0 . Then 1 2 I f ml (x 0 )-fm (x 0 ) I s I fm (x 0 )-fm (xp) I + I fm (xp)-fm (xp) I + 1 2 1 1 2 I fm (xp)-fm (x 0 ) I < Ii + B0 + Ii = 21i + B 0 . 2 2 Since this is true for all Ii > O, we get that If m (x 0 )-f m (x 0 ) I s 1 2 B and we are done. 0 (ii) The "=>" direction is again trivial so we need only do the "e" direction. Suppose f is not uniformly divergent. Let c > O be given. A(~;x ) 0 Then We shall show that there is an x 0 such that < c and this will establish the result. Choose e: = c/2. Then 3n0 such that V'p3xp vim1 m2 € [n 0 ,n 0 +p]( I fm (xp)-fm (xp) I <c/2). 1 2 Let x 0 be a limit point of the xp's. Then as in (i) we have for all ml'm 2 ;::: n 0 that I fm (x 0 )-fm (x0 ) I s c/2. 2 1 we are done. Proposition ~· So A(f;x0 ) s c/2 < c and o Let f € DZ. The following are equivalent: (i) f is unboundedly divergent (ii) r(f) = 1 (iii) f is unboundedly uniformly divergent. Proof. (iii) ~ (i) is obvious, so it will suffice to show that (i) ~ (ii) and (ii) ~ (iii). (i) => (ii): Suppose r(f) > 1. Then for some M € ~+, r(T~) ~ w. So T~ has a subtree as shown below. I!n\ ~10)) ( n, n Let xn be the midpoint of xn's. We claim that rAn) and let x 0 be a limit point of the A(~;x ) 0 So we now prove the claim. < +oo. From this the result follows. Now from the definition of Tj we have It will suffice to show that I fm (x 0 )-f m (x0 ) I 1 2 s; M. -goTake 15 > O and choose, by the continuity of fm 1 and fm 2 at x , n > 0 I fm (xn)-fm (x0 ) I < 15, I fm (xn)-fm (x 0 ) I < 15. 1 1 2 2 Then as in Proposition 8 by using (*) we get M + 215. Since (ii) => (iii): is this Suppose f ,.., true for all 15 > Ifm (x 0 )-fm (x 0 ) I 1 2 O we have ~ that is not unboundedly uniformly divergent. Then 't/X € I2 'Vm1,m2 € [1,qN+N-1] I fm (x)-fm (x) I ~ I fm (x)-fm (xq ) I + Im (xq )-fm (xq ) I + 1 2 1 1 N 1 N 2 N Ifm (xq )-f m (x) I < M/3 + B 0 + M/3 ~ M 2 N 2 Also for each i = 2, ... , N-1 we have 't/x € r 2 and 'Vm 1 ,m 2 € n-2 I fm (x)-fm (x) I ~ l: II fq +k+l (x)-fq +k(x) II 1 2 k=O N N N-2 ~ l: llfq +k+l-fq +k(x) 11 k=O N N M M M ~ (N-1) ·~ < N < T· So our claim is verified and we are done. Proposition 10. Let f £ DS and suppose f D is uniformly divergent. Then r(f) :s: 2. Proof. In view of Proposition 8 (ii) it will suffice to prove that: "there is a c > O such that A( f ;x) 2." So assume its hypothesis. T~ has a subtree as shown € IN consider ~ c for each x € Now suppose r(T~) below with each T ~ r(f) :s: ~ w; 2. So of the nodes through the node (r(l2.) k(.2>) t Fix n and As the in the subtree proof of Proposition 9 we see that there is a point xn But this is true for each n € "(i) € (ii)" of IA n) such that 11-1. enough n we get A(~;xn) < c which is a contradiction. 2. ~ So for large Hence r(f) :s: 0 Remark. We know that example 4 is not uniformly divergent. It is -&zeasy to see however that it has rank difficult to construct an f for some {xn} ~4). 2. ~ 1f. 2. In fact it is not DF with r(f) = 2 and A(!;xn) € ... O (We sketch this construction at the end of The converse of Proposition 10 is therefore false. Some Natural Examples. In this section we investigate the ranks of some natural examples to once again verify our intuitive idea that they should be 1 or 2. Kolmogorov functions: Kolmogorov [29] integrable function whose divergent. It turned out that the Fourier series of this function Fourier constructed series was in fact unboundedly divergent everywhere. a was Lebesgueeverywhere Such functions are now called Kolmogorov functions in honour of their discoverer. follows immediately from the definition of a Kolmogorov that it has rank 1 (because of Proposition 9). It function For more details on the Kolmogorov construction see [04] p. 455-464, or [30]. Lusin Series: as follows: This series was given by Lusin [33] and is defined Let 00 F(z) = H0 (z) + where Hp(z) = 9(Z) = 2 ...!... H (z) ~ zA.P p=1 IP P ! zm(p+l) 9 p (z ~ e-27rim/(p+l» m=u ! k2. ! Zn and A.p = k=l n=O Lusin [33] showed that F(eix) was everywhere divergent. s 1 = Re F(eix) and s 2 = Im F(eix). Now put Then it is easy to see that s 1 and s 2 are trigonometric series with coefficients tending to zero. Lusin [33] also showed that [48] showed that s1 both s 1 was divergent a.e.. s2 and are Later Stechkin everywhere From Proposition 9 we thus get r(S 1 ) = 1 divergent. unboundedly r(S 2 ) = and 1. Steinhaus Series: Steinhaus [49] gave an example of an everywhere divergent trigonometric series with coefficients which tend to zero. The coefficients were defined by recurrence relations and were not capable of simple analytic expressions. We shall therefore refer to the simpler example Steinhaus later gave in [51] as the Steinhaus series. 00 s "' The L n=2 This series is defined by cos n(x-log log n) log n proof that S is everywhere divergent is very elementary. Moreover it is easy to see from the proof given in [04] p. 76 that the amplitude of divergence of S at each x is at least 1/2. proposition 10 we have r(S) ~ 2. So by We shall see however that the Steinhaus series is a special Belov Series (which we will define in a moment). This will enable us unboundedly divergent everywhere. to show that Thus r(S) = 1. S is in fact Hardy-Littlewood Series: s These series are defined by 00 L np-l/ 2 cos(a log n + nx), ~ n=l P ' > p ~ 0, a > O. Hardy and Littlewood (18] had considered these series with the added restriction that a with a l(mod 4). ii!! artificial and we = 1/log (a), where a is a positive integer It is clear that this restriction is purely shall show that it can be removed. Hardy-Littlewood series are also special Belov Series. The We shall show that for p > 0, Sp is unboundedly divergent everywhere, and that for p = O the amplitude of divergence of Sp at each x is at least 1/3000 fa . So by Propositions 9 and 10 we have r(Sp) = 1 for p > 0, r(SP) :s: 2 for p = O • Problem: What is the rank of Sp when p = O? Herzog Series: We shall consider a series given by F. Herzog (20]. slight modification of the Let F(z) = where Tm(z) = 1 + zm + z 2 m + ~ ~ ~+ z[m/l 2 ]m and the exponents km form an increasing sequence of positive integers such that z common when m '!:. n . Put s 1 ~ Re F(eix). km Herzog (20] showed that -gsthere is a universal constant C > O such that for each x there are infinitely many m's such that at least one of has a real part with absolute value greater than Cm. immediately follows that Now let G(z) = s2 Proposition 10. But s 1 is unboundedly divergent everywhere. 00 L n=l Then divergence of it also follows L m=l (-l)m - m· s 2 diverges boundedly at x = 0. Belov Series: that the amplitude of at each x is at least C. 00 so From this it {2[~] + 2} Hence by Proposition 9 we The following theorem was proved by Belov (06] and enabled him to produce numerous examples of everywhere divergent trigonometric series with coefficients that tend to zero. Theorem ~ (Belov). that for some a also that ~ Let g(y) be a function defined on [l,oo) such 1 it has a second derivative on [a,oo). Assume (i) for x a, g '' (y) is positive, non-increasing and tends to ~ zero as y (ii) (iii) g "(y) 1 0¢ , as y -+ oo g'' (y) -+ • g ,, ( + y and -+ ()() , A. Jg'' (y) ) ..... 1 as y ..... oo for arbitrary A. • Then for each N there exists n 2 > n 1 N with n 2 1/1000/g'' ( N 2 ) such that for all n 1 5; n 5; n1 + 1 > n 2 , all the values of cos g(n) have the same sign and I cos g(n) I > cos(31t'/8). Corollary B. Let {r n> be a non-increasing sequence which tends to 00 zero and put Sg ~ 2: n=l r n cos g(n). Then (i) 1 im (r n/ /g"Il) = +()() , implies Sg diverges unboundedly n ..... 0¢ (ii) there is a constant C > O such that r n ~ C/g'' ( n) for all · l'1es Sg h as amp l 1tu ' d e o f d'.ivergence at 1east C~cos(31t'/8) n , imp f ooo Corollary B follows easily from Theorem A. If we have a g that satisfies the hypotheses of Theorem A and we put f(y) = g(y) + us an axy + bx + c, (a ~ 0) then Corollary B will give everywhere divergent trigonometric series, Sf with coefficients that tend to zero. (Here x should be viewed as a parameter rather than as a variable.) way Belov series. We shall call series that are produced this It follows immediately from corollary B that for any Belov series S, r(S) ~ 2. We shall now show that the Steinhaus series is a Belov series and that it is unboundedly divergent. Let g(y) = yloglogy. Put f(y) = g(y) - x•y. Then g satisfies the hypotheses of Theorem A. log y. Also g'' (y) = rn/ /g'' (n) .... +oo as n .... oo, sf 00 r-.; l: n=2 So if we put r n 1/log n then Hence 00 cos n(x-loglogn) cos(nloglogn -nx) = 2: log n log n n=2 diverges unboundedly at each x. 1. = So the Steinhaus series has rank Now we shall show that Hardy-Littlewood series are also Belov series. Let g(y) = y log y and put f(y) = g(y) + x•y. satisfies the hypotheses of Theorem A. rn = np-l/ 2, + So if i~ > p > 0 then nlim (rn//g''(n)) = +oo; and if r = .... oo n n- 11 2 then (r n/ Jg'' ( n)) ~ 1/ fa for all n. cos(alogn Also g'' (y) = a/y. Then g nx) diverges unboundedly 00 Thus Sp ,. ., when l: n=l t > p > O, and uniformly when p = 0. 3. Cantor-Bendixson Analysis. In this section we formulate an equivalent description of the rank function r on DZ by means of a Cantor-Bendixson Analysis. that r is unbounded in the beginning of s1. w This will make it easy for us to show 1 on DF. Recall the definition T~ from For each N € IN we define the tree T~ , N by -s~- TM where g g is the sequence defined by gm = fm+N· The "' Cantor-Bendixson Analysis is very similar to that in Chapter 1. We shall define a sequence <P~, f , N) which ref le ct the properties of f. Q(W , x M is again P~, f, N) is pa M,f ,N to to be be thought of interpreted as as being large W witnesses and x € W will range over the closed subsets of T. Definition. For each M € cD+, ~ € DZ, N € IN we define PM,f,N by "' x € P f N e:> m, ' sup{ I fm (x)-fm (x) I : 1 2 m1 ,m 2 ~ ~ N} M. We define the sets P~, f, N and the relation Q(W , x , P~, f, N) by induction as follows: Let p~, f, N = PM,f ,N and Q{W,x,P~, f, N) e:> x € W A PM,f ,N· pa+l = {X€P~,f,N: for all I€Q(T) with x € int(I), m,f ,N 3m ~ 1/ I I I, 3y € I, 3V ~ PM,f,N s.t. Q{V , Y , P~~ I I I ,f ,N+m)} Q(W , x , P~~~, N) 1/ I I I, e:> for all I € Q(T) with x € int(I), 3m ~ -'a93y € I, 3V ~ W A PM,f,N s.t. Q(V , y , P~, f If ,f ,N+m) and for A. a limit ordinal we let pA M,f ,N = n a<>-. pa M,f,N x Q(W < Q(W,x,P~' f, N). ,...., Observe that our definition induction on a, M and N. closed set. Also is made of simultaneous a: s: 8 => P~, f , N !:; P~, f , N and P~,f,N simply as P~,f ~ use It is easy to see that Pa M,f ,N is a M s: M / => P~, f , N !;;;; P~ ; , f , N . DS by for each M € When N = 1 we shall refer to We will show in Proposition 14 that f tD +I 3a < w 1 such that P~, f = 0. € As in chapter 1 this will allow us to make the following definition: Definition. We define a new rank function r 1 on DS by r 1 (!) = least a such that PM~ f = 0 for all M € tD+ • Our goal will then be to show that r = r 1 on DZ. It will turn out that r 1 is the same as r on DS except for an initial segment of length w where r differs from r 1 by at most 1. Definition. Let f £ DS, M € tD+ and N € IN. For each subset W of 11' -90we define the subtree W(T M f , N) of TM f , N by Lemma 11. € P~, f, N and W satisfies Q(W , x , P~, f, N) then We prove the result by simultaneous induction on a, M and Proof. N. If x = 1 the result follows from Proposition 9 and for limit For a ordinals the result follows trivially. true for a, for all M and all N. We have to show that it is true for a + 1, for all M and for all N. Q(T) with x € int(I 0 ). the tree W(T 2M f, Nl ~Io So fix n Ia and x € has a int(I(n)). So fix M, N. Fix now Io It will suffice to show that for each n Choose I(n) IN. € Assume that the result is € € IN node of rank at least w•a + (n-1). € Q(T) such that I I(n) I :s: l/n, I(n) ~ From the assumptions on x we know that there exists m ~ l/ I I(n) I, y € I(n) and V ~ P M,f,N such that Q(V , y , ~ pa M ~ I I ( n) I , f, N+m Since ). 1/n we also have ~ Q(v I y I Pa ). M/n,f ,N+m ~ By the induction hypothesis we thus get - 912M/n r(V (T f, N+m):y) I"") l . r { ] I x ] 1 y ~ Iz Io Now choose r2 € Q('f) with y € int(I ) 2 sup{ I fm (z)-fm (z) I :N5:m 1 ,m 2 5:N+m} 5: 2M/n. 1 y 2 r2 ~ and I(n) such that (This is possible because PM/n,f,N+m .) € Let Tn be the tree defined by <('f,1),(I 2 ,m+2), ... ,(I 2 ,m+i)> and <('f,1),(J 2 ,.e 2 ), .•• ,(JP,.eP)> € € Tn i = 2, .••, n [[V(T~~'~m) ~I 2 ln ,_., Then it is easy to see that So to complete the proof i t will suffice 2M subtree of W(T f, N) Ho· Tn. show that T n is a Let <(J1,k 1 ), ... ,(Jn,kn), •.. ,(Jp,kp)> be a node in We must show that J 2 ~ [ki,kp] we have to r 0 , W f'i JP # 0 and \:/z € JP \:/m 1 ,m 2 € -92.- (*) I fN+m (z)-fN+m (z) I s 2M/i 1 2 Now from the definition of Tn , J 2 must be I 2 Also W f'. JP :2 V ('. Ip '1: 0 since y Io· > p n then Now if i v ('. (*) so J 2 = I 2 c- I(n) c- V f'i Im if p s n, and if by the definition of [V(T f2M/n 'N+m) ~I2ln Im '1: 0 n then > € I follows from the definition of the tree Also if i s n then (*) follows because of the way we chose I 2 . So Tn is indeed a subtree of W(Tf2M,N)~I 0 and we are done. D Recall the definition of a trans it iv e tree and the subtree [T]k of T from §4 Chapter 1. We have exactly as in Sub-lemma 1.14 the following result. Sub-lemma I £ ID(l') Suppose 12. and r(T ~I) ~ T w ~a. is a transitive Then for each k subtree £ It-I of the subtree D Lemma 13. TM f, N Let f with a Q(W,x,PM, f, N). DZ and suppose T is a transitive subtree of £ r(T;x) ~ w. a. In particular x W = {Z€1l' : r(T ; z)~w}. Let € a PM, f, N' Then -93Proof. The result is proved by simultaneous induction on a, M and N. For a = 1 the result follows from Proposition 9, and for limit ordinals it is trivial as in Lemma 11. is true for a, all M and all N. a + 1, all M and all N. Assume that the result We have to show that it is true for So fix M and N. It will suffice to show that r(T;x) ~ w ~ (a+l) ~ Q(W , x , P~:~, N). Now fix I € Q('lr) with x We must find m ~ 1/ I I I, y int(!). € and V ~ W A PM,f ,N such that Q(V , y , P~ ~ 1 I 1 , f, N+m). ~ we have that w~(a+l) as shown below with r(T~I) each of ~ w~(a+l). the So nodes T~I I € Since r(T;x) has a subtree <(Il'k 1 ), ... ,(IAn),kAn))> having rank at least w •a in T~I. [ . x [ •1 ] y 1 I r Itn) k111l) \ " Choose p such that p 1/ I I I. at the Now let ".:n node ".:p ' II ~ k(p) 1/III and let m = p . n >. = <(I1,k1), ... ,(In(n) ' k(n)) is transitive and r(Tv ) ~P Then m ~ p ~ Then the tree TV ~P ~ w~ a . So by -94-Sublemma 12, r([Tv ]P) ;!: w~ a . Let Tp be the tree defined by ~P <(1',l),(J 2 ,.2 2 +1-m), ... ,(Jn,.2n +1-m)> € Tp ¢::::::> <(Jl'.21), ... ,(Jn,.2n)> € [Tvp]P Then TP is transitive and it is easy to see that TP is a subtree M/p of Tf,N+m Moreover TP has rank at least w ~ a . So by lemma 4 there is a y r~P) c I such that r(TP;y) Let V € Then by the w ~a ;i: induction hypothesis l/III thus Q(V, y, P~;p,f,N+m). Since Q(V , Y , P~ ~ 1 I 1 , f, N+m). We have now found our m, y and l/p < remains to show that V ~ W A PM,f,N . we ~ C(1')w. = 0. Proof. DS. that r(T~) where ()( Suppose f < = w~r(f). i'(~) € !;;;;; W. 0 ~+, 3a < w1 such that P~, f "=>": It So V !;;;;; W A P M,f,N and we are done. € v. So V w • Also from the definition of W we have that W !;;;;; P M,f,N Let f have Now from the definition of Tp we have that r(Tp;z) ;!: w implies r(T;z) Proposition 14. = Then f € DS ¢::::::> for each M € Then for a fixed M € ([)+ we know So by lemma 11 we must have P~, f (otherwise we would get an x € = 0 , P~, f and this -95- would make r(T~) ~ w • r(f) ) . Suppose "<=": f Then there is an x DS. € T such that f A direct verification shows that Q( {x} , x , P~, f) converges at x. holds for all a € € ORD. So P~, f is never empty and we are done. 0 Proposition 15. Proof. For each f € DZ, r(f) = r 1 (~). Use Lemmas 11 and 13. Remark. 0 By modifying the proof of Proposition 13 we can show that r(T~) ~ w ~ ( a+l) implies P~, f -;e 0, for all f € DS. This shows that r and r 1 can differ by at most 1 if r(!) < w , and that r(~) = r 1 (~) for all ! 4. £ DS with r(f) ~ w • The rank function, r is unbounded in w 1 on DF. The main aim of this section is to prove the following result. Proposition 16. For each 1 s: a < w 1 there is an f € L1 (T) such that r(f) = a. Proof. The proof is by induction on a. We shall show that for each a there is an fa that r(f a> are = a. chosen bounded by € L1 (11') given by fa = >..a~ f + </;a' such Here f is a Kolmogorov function and >..a and </;a inductively. >..a will be a c< 3 >-function which is 1 and which is zero only on a prescribed closed countable set oa. We shall also need some other auxiliary functions besides the Kolmogorov function. Let </; be a continuous function whose Fourier series has partial sums that are bounded in absolute value by 1, and converges everywhere except at x = 0. Let .tf> be a continuous function whose Fourier series converges everywhere except at x = O where it diverges unboundedly. For the existence of such functions see [04] p. 127-128. Now for a = 1 take o 1 = 0 and </lo = O to get r(f 1 ) = 1. For a = 2 we take o 2 = {O} and i/; 2 = </; to get a function f 2 whose Fourier series diverges unboundedlly everywhere except at x diverges boundedly. = O where it From propositions 9 and 10 we get r(f 2 ) = 2. For a = 3, we take o 3 = {21t'/n:n~2} V o 2 and i/13 = ~ i/12 + 00 L: 4-n i/;(x - 2;). n=2 3 In this case we see that PM, f3 = 0 for all M € (I+ but O € -97- Ii I 0 I I I The general situation splits into three cases: Case ill: a = JJ + 2 for some ordinal /J. In this case we take o a = o JJ+ 1 V o where O is the set which consists of a sequence of points from each of the intervals complementing o .B+l that converge to the left endpoint monotonically '' x Ps Pz. (x,y) ~ 'Il' - o .B+l' Pi ~ x, Enumerate o as a 00 <// .B+l + L r n=l -n x,y € o .B+l · = 12 countable sequence <xn> n€ IN and put .pa In this case we get that .p(x-xn). o € P .B+ 1 1,fa but P~, fa = 121 for all M € ID+ so r(fa) = a. Case (ii): a = A. + 1 where A. is a limit ordinal. In this case we choose an increasing sequence of successor ordinals an with lim = A.. an +\, 2n1t'] Let o~ be a scaled copy of on onto [n2 the function obtained by using a -1 Pl nf; a I = but o~ Then ;f1 € Let o; n = <//a (x) + an-1 for all n, so O 1,fa € instead of on. 121 for all = n€1N o; n and Then o € M € n 00 u Put 00 00 L: 2: n=l m=l However pA.+l M,fa possible element a P L: m=l n = 121 for all M € ID+ because O is the only of pA. M, fa pA. must be infinite. M, fa = for any M € So we get that r(f a) = a. = A. a limit ordinal. In this case we repeat the construction given in case (ii) except that we put -99- oa remains the same as in case (ii). Because of the term 0(x), fa now diverges unboundedly at x = 0. any M € en+. So 0 t P~, fa for Since O was the only possible element in follows that P 27t' know that n+l = 0 for M,fa € all M € cD +. t p"-M, fa it But we an-1 PMn, fa for large enough Mn's. and hence r(f a) = A. = a. So we are done. 0 We are now in a position to promised at the end of section 1. function f such that r(f) uniformly divergent. Take the construction We wanted to construct a = 2 but whose Fourier series is not Kolmogorov function and o c( 3 ) with I A. I ~ 1 and A. = O only on o. € we We proceed exactly as in case (iii). f 0 to be a Choose a A. give = {27t'/n:n;?:2}. Now define f by 00 f(x) where ~ and ~ = A. ~f 0 (x) + p(x) + l: are as above. n=2 Then f has the required properties because A(S(f);~) = 4-n for each n ?!: 2. -roeCorollary 17. DS, DZ, DT and DF are all coanalytic but not Borel sets. Proof: The rank function r is a coanalytic norm on each of these sets and is unbounded in w 1. So by Proposition 0.1, they can't be Borel. o Final Remarks. We have seen how to use the Cantor-Bendixson Analysis in order to show that r is unbounded in w 1 on DF. again is it very plausible that there is Cantor-Bendixson Analysis but this is not very clear. the .following Problem. no Once simple So we pose problem. Is there a simple Cantor-Bendixson Analysis which gives rise to the same rank function r? -101- Chapter 3 Introduction. Let K = <K(rR 2 ),d> be the Polish space of all compact, non-empty subsets of the plane, rR 2 with d being the Hausdorff metric given by d(A,B) = sup{dist(x,B) , dist(A,y) X€A,y€B} In this chapter we shall be interested in certain subsets of K. To define these subsets we need to introduce some definitions. Let A € K. Y:[a,b] y -+ By a path in A we mean a continuous function A where a and b are real numbers with a < b. The path is said to be a arc if Y is an injective function. to be a Jordan loop if Y:[a,b) -+ Y is said A is injective and Y(a) = Y(b). So Jordan arcs are homeomorphic to [0,1] and Jordan loops are homeomorphic to the unit circle 11'. Let be a Jordan loop in A. By the Jordan curve Theorem we know that Y divides the plane into two open components, exactly one of which is bounded. We call the bounded component the inside of Y, written ins(Y). A is said to have a ca vi t y if there is a Jordan loop Y in A such that ins(Y) <t A. A set without any cavities is called a Jordan set. We now define the following subsets of K. Let JS be the collection of all Jordan sets in K, PC be the collection of all path-connected simply-connected sets sets in in K, and K. be the collection of all Ajtai (see [24])(see also H. SC M. Becker[05]) showed that PC is a Ill ...., 2 but not !i subset of K. The -IOZquestion was raised as to whether PC is ~~· H. Becker (05] also showed that JS is not a ~I subset of K. This is still open. !I complete and that SC is The question raised by Becker as to 1 whether SC is JI Nl is also open (but see the final remark at the end of this chapter). We mention in passing that the collection of all connected sets in K is a closed subset of K (see (42] p.8). Remarks. All of the Descriptive Set Theory we have used so far can be classified as the Classical Theory. known as the Effective Theory. functions and effective analogues of obtained (see The There is also what is In the Effective Theory recursive relations are defined on Polish spaces and the (41]). Borel, and analogues are L:l "' 1 subsets, designated etc. as are JII, :Li subsets, etc. (:LI is referred to as "light-face sigma and one" and :L 1 is referred to as "bold-face sigma one one," etc.) "' 1 Ajtai actually showed that PC was JI 12 , and Becker showed that JS was JI~. These results are slightly stronger than what was stated above but the proofs are the same. We shall say no more about this because we are mainly interested in the classical theory. In this chapter we shall define and study a natural norm on JS. This norm is obtained by associating, with each set in JS, a collection of well-founded trees as in chapters 1 and 2. The well-founded trees are defined on sets with cardinality the same as ~ (unlike the case in chapters 1 and 2 where the trees were -10:5defined on countable sets). The norm provides a natural measure of the complexity of the sets in JS. It measures in some sense how "close the set came" to possessing a cavity. The sets of least possible rank are the convex sets, and if a set is locally path connected then it lies in the first or second level. give some natural examples of sets with small ranks. show that this norm is unbounded in w1 on SC. We also Finally we This provides a Rank Argument of the fact that JS is coanalytic but not Borel. It also shows that SC cannot be an analytic subset of K. '31. Tree Description. associating with well-founded trees. In this section we study the sets in JS by each A € JS a countable collection of But first we check that JS is a coanalytic subset. Proposition 1. JS is a coanalytic subset of K. We shall show that K - Proof. JS is an analytic subset of K. Observe that A € K - JS <::::::) there is a continuous function Y:[0,1] ~ 1R 2 such that y is a Jordan loop in A and ins(Y) ~ A Let E = {(A,Y)€KXC 2 : (*) holds}. (Here c 2 is the Polish space of all continuous functions from [0,1] to 1R 2 .) E is a Borel set. (*) Then it is easy to see that So K - JS is the projection of a Borel set onto K and hence is analytic. Thus JS is coanalytic. D With each A € K and each M € ~ + we shall associate a tree, -104T~ which reflects in some way the properties of A. Here M should be thought of as being large. The trees ~ will be defined on the set of all Jordan arcs in A. This set has the same cardinality as JR. Before we give the definition of T~ we need some notation. For a Jordan arc Y:[a,b] -. !R 2 we define between the endpoints of Y. the closed path, .Y:[a,b+l] Y(t) -+ I YI to be the distance We define the closure y of y to be !R 2 given by Y(t) t € (a,b) = { Y(a) t =b + 1 Y linear on [b,b+l] Let Y:[a,b] -+ !R 2 be a closed path. Then !R 2 - Y[a,b] is a union of open connected sets with exactly one element of the union being unbounded. We define the inside, ins(Y) of y by ins(Y) = union of all unbounded components of JR 2 - Y[a,b] Finally let Y1 :[a,b] -. !R 2 and Y2 :[c,d] -. !R 2 be paths. "'l ~ Y2 if Y1 [a,b] ~ Y2 [c,d]. We also define We say that llY 2 -Y 1 11, for Y1 ~ "'2 by llY 2 -Y 1 11 This = sup{dist(x,y) definition is "very x,y€{Y 1 (a),Y 1 (b)} V (Y 2 [c,d]-Y 1 [a,b])} close to", but not the same as Hausdorff metric distance between the sets Y2 [c,d] and Y1 [a,b]. the -105- We Definition. define the tree as follows: <Y 1 , ... ,Yn> € T~ ~ (i) Y1 , ... , Yn are Jordan arcs in A (ii) 3r € IR 2 such that B(r,1/M) ~ (IR 2 -A) A ins(Y i) for all i (iii) Yi~ = 1, ... , n, and Yi+l' llYi+l-Yill ~ M/i for all i = 1, ... , n - 1. Here B(r,1/M) is the open disk with radius 1/M and center r. Our next result gives the basic relation between the set A and the associated trees T~. Proposition ~· A € JS ~ V'M € co+(T~ is well-founded). Proof. Suppose A "e": € JS. Then there exist M € and a Jordan loop Y:[a,b] ~ A in A such that B(r,1/M) ~ (IR 2 -A) A ins(Y). B(r, 1/M) . . . . . .. . . We claim that T~ has an infinite branch. from this. The result will follow To prove the claim we shall construct an increasing sequence <bi> iE IN such that for all i, bi < [b1,b], I Y(b)-y(t) I ~ M/i. b and for all t € -to~- Since y is continuous at b, 3b 1 € {a,b) such that for all t € [bl'b], I Y(b)-Y(t) I such that induction :S: M. And given bi we can choose bi+l € (bi,b) for all t € we obtain [bi+l'b], s: I Y(b)-Y(t) I sequence our So M/(i+l). Now by = let Then it is easy to see that Yi is a Jordan arc in A and for each n, <y 1 , ... , Yn> € M TA. So <Yi> i€ IN is an infinite branch in T~ and the claim is proved. "~" : Now suppose that for some M € ID+, T~ is not well-founded. Then there is an infinite branch <Y 1>i€ IN in T~. Without loss of generality we are Yi:[ai,bi] A, Yi -+ may assume that the YJ..'s of that = Yi+l ~ [ai,bi], and the ai's decrease to a and the bi's increase to b (a and b being finite real numbers). definition such the tree T~ it follows that From the ! im Yi (a1) and J. -+OO l im i -+OO lim Yi(ai) = lim Yi(bi) i-+oo i-+oo Moreover since A is compact this limit is in A. Let Y(b) = Y:[a,b] lim -+ A be defined by Then it is YHai,bi] clear that = Yi and Y is Y(a) = continuous. i-+oo Moreover y is one to one on (a,b) since the Yi's are one to one on [ai,bi]. Thus Y can intersect itself at most once. We claim that there is an r € IR 2 such that B(r,1/4M) !;;;; (IR 2 -A) A -t07ins(Y). Indeed choose k ~ (IR 2-A) A ins(Yk). . such that B{r,1/M) tree such that M/k < 1/4M. Choose r € rR 2 From the definition of the T~ we know that for each n ~ k, Yn[an,bn] - Yk[ak,bk] lies in a disk of diameter 1/4M which contains the point Yk(ak). for all n ~ Thus k So the disk B{r,1/4M) lies in the inside of each of the paths y n' n ~ k and consequently in the inside of Y. ~---------- B \~-(a.,) , t /4M) / / I I I \ \ Now if Y is \ a ' ........... ---- Jordan loop I / / then A suppose Y is not a Jordan loop. Y(b) = Y(c). y, = { I t JS Then 3c and we € {a,b) such that Y(a) Let Y" be the path defined by Y~[a,c] i f B{r,1/4M) YHc,b] i f B(r,l/4M) ~ ins(Y~[a,c]) and B(r,l/4M) ~ ~ are done. ins(Y~[a,c]) ins(Y~[c,b]) So = -1 os- Then is "Y" a well-defined Jordan loop and this shows A t JS. that o Definition. We define for each A € JS, the rank function p(A) by p(A) = sup{r(~)+l : M€ ID+} We emphasize here that we are using convention that the empty tree has rank -1. Proposition 3: Proof. For each A E: JS, p(A) < Let A E: JS. w 1. Fix M E: ID+ and consider the tree T~. It is easy to see that the relation -s , defined by u ~ v <=> u,v € T~ and v extends u is a strict analytic relation. and so ~ is also Since A E: JS, T~ is well-founded well-founded. It therefore Proposition 0.6 that -s has countable length. is just the rank of T~ , so r(T~) < w 1 . follows from But the length of -s Thus p(a) = sup{r(T~)+l : ME:ID+} = sup{r(T~)+l : NE: IN} < w1 . Proposition _i. Let A E: JS. 0 Then p(A) is either a limit ordinal or the immediate successor of a limit ordinal. -f09- Proof. It will suffice ,o(A) ~ w•(a+l). left, with show that if Suppose ,o(A) ~ w~a + 2. we have r(T~) ~ w ·a + 1. the to the ,o(A) ~ w ~a + 2 then Then for some M € ID+ So T~ has a subtree, as shown below on nodes ( n) <yl, ... ,Yn > having ranks that are increasing and with limit w ~a. (n·L) times I ,,(n+kl We claim that r(T~ ~ n) ~ w ~ a + n. readily. o n+k From this the result follows So we need to prove our claim. Let T n be the tree defined by <Y 1 , ... ,Y 1 >(i times) € Tn <Y1, ... ,Yn, ... ,Yn+k> € i = 1, ... , n - 1 T~:::) <Yl' · · · ,Yl,Yn, ... ,Yn+k> € Tn "= ,,,,,,,,. (n-1•) times Then it is easy to check that Tn is a subtree of T~ ~ n) ~ w ~ a + n and we are done. D -1\0Remark. We use the convention that O is a limit ordinal. It is clear that p(A) can never be 1 but we shall later see that p(A) can be other immediate successors of limit ordinals. Let A Proposition ~· € JS. Then p(A) = O e:> each path-component of A is convex. Suppose P is a path-component of A which is not Proof. "~": convex. Then there exist x,y € P such that the segment [x,y] So there is a point z on [x,y] such that z t A. (JR 2 -A) is open and so there exists E > i P. Since A is closed, O such that B(z, E) A A = 0. B(z,£) 8 (w, 1/M) Since P is path-connected there is a path in P connecting x and y, and by a standard result (see [13] p. 29) it follows that there is a Jordan arc that y B(w, E/4) in P connecting x and y. ~ ins(Y). M ~ max{ I x-y I ,4 Then Iy I Now let Choose w € B(z, E/2) such M € co+ be such that ~ M/l and B(w,1/M) ~ (JR 2-A) A ins(Y). -litSo <y> € T~ and hence p(A) > o. "e": Suppose p(A) > 0. Jordan arc Y Then there exist M in A such that B(r,1/M) ~ (IR 2-A) f'\ 4:1+, r € ins(Y) • --- Let P be the path-component of A that contains clear that P is not convex. So we are done. Proposition JS Let A € and path-connected. Then p(A) = O or w. Proof. suffice to w. I t will Then for some M subtree as shown below. iR 2 and a _ .... 6. € 4:1+ € • 1(1) t we D suppose show that have p(A) r(T~) Then it is Y. that ~ is locally Suppose w. ~ A w. So t~I.) t~l "~) "~\ TM p(A) > A has a -llZ.Here the Y ( i) 's J initial point are not necessarily distinct arcs. of Y An) and Yn be the Let xn be the terminal point of y An) . From the definition of the tree T~ we have that so I xn -y n I :s: M/n. I Y ( n) I :s: M/n, n Let r n € JR 2 be such that for each n for j = 1, ... , n. Since rn € ins(Y (n)) it follows that {rn}n€1N is bounded because J y(n) is an arc in A. By Let r be a limit point of {rn}n€1N J going to subsequences I rn-r I < l/2M for all n if ~ 2. necessary we may assume that From this it immediately follows that B(r,l/2M) ~ (JR 2 -A) f'i ins(Y n( n)) for all n ~ 2. Let x be a limit point of the sequence <xn>n€1N . because A is closed. Let U = B(x,l/4M). Since A Then x € A is locally path-connected there is an open set V ~ U with x € V such that v n A is path-connected. Since V is open and x € V we have for some large enough k that xk,yk € V. ____ u -+-'-----V -lt3- Since V A A is path-connected there is a path in V A A connecting This path together with Y~ k) gives us a closed path xk and yk. Y in A with B(r,1/2M) k (JR 2-A) A ins(Y). a Jordan loop Y/ in (as A B(r,1/2M) k (JR 2-A) A ins(Y /). Now we can extract from y in (13) p. 29) such So A t JS, a contradiction. that Hence the result follows. 0 Remarks. The converse of Proposition 6 is false. When we consider some natural examples in the next section we will see two that are not locally path-connected but which nonetheless have rank w. Definition. Let A pseudo-ca vi t v if k JR 2 . We there exist r say € that JR 2, c a Ha.usdor ff and a sequence A has > O <Y n> n€ IN of Jordan arcs in A such that for each n € IN (i) B(r,€) k (JR 2 -A) A ins(Y n) (ii) Yn k (iii) I Y n I --. O as n --. oo, Y n+l' Proposition 1· pseudo-cavity. Proof. and Let A € JS and suppose that A has a Hausdorff Then p(A) ;:!: w ~ 2. From the hypothesis we have that there exist r € JR 2 , c > O and a sequence <y n> n€ IN of Jordan arcs in A such that Yn k Yn+l' I YI --. O as n --. oo and B(r,€) k (JR 2 -A) A ins(Y n). By -114-considering a subsequence of <yn>nEIN , if necessary we may assume that I Y n I ~ 1/n for all n E IN. Choose II Y n -y l. II ~ M E ~ diam(A) ~+ such M ~ that M for all n E IN. max{l/ c ,diam(A)}. Then Now consider the tree, T shown below. It is easy to see that T is a subtree of 1. So r(T M A) ~ w + 1. Thus p(A) ~ T~. Moreover r(T) =w + + 2 and hence by Proposition w 4 we get that p(A) ~ w ~ 2. D Remark. The converse of Proposition 7 is also false. We shall give example in Hausdorff an of a set JS which has no pseudo-cavity but still has rank w ~ 2 in the next section. 'S 2. Some Natural Examples. Before we give our natural examples we shall obtain two results which will aid us in calculating the ranks of some of the sets considered below. Lemma 8. Suppose A E JS and p(A) > w • Then there is a disk B(r, 8) such that 'tic > O there is a Jordan arc I YI < c and B(r,l/M) ~ (JR 2-A) f'\ ins(Y). Y in A such that -nsSuppose Proof. p(A) > Then for w. subtree as shown in Proposition 6. can find an r Now take € some M IO+, € T~ has a Also as in Proposition 6 we ~ 2 such that o = 1/2M. I Y (n) I n Since -t for all n ~ 2. O as n -t oo the result follows immediately. Suppose A Lemma 9. there is 0 a € Jordan arc in JS and p(A) > Y Then for all in A, such that Jordan arc Proof. Suppose p(A) > w ~ 2. y" w ~ 2. A with Y !;;; y", "<:/ IY"I E > O o > O there is a o and < Then for some M € llY-Y"ll < IO+, T~ has a subtree as shown below where each of the nodes <yl(n) , ... ,Yn(n) > M is of rank at least w in TA" . •1 • .(I) Now choose n such that 1/n < also so that l/(n+m) < E and let Y be Y ( hypotheses imposed on them. Y Choose m ( Then from the and y " o and let y " be YA~~ m). properties of T~ it follows readily that g). fulfill the 0 -llb- The Hausdorff ~: the plane IR2: Let r n(n=-3,-2,-1, ... ) be the following points in r -3 = (0,1/2), r -2 = (0,-3/2), r -1 = (2,-3/2) and rn = · n) (2•2 -n,1/2·(-1) for n Let A be the union of the line 0. ~ Then it is easy segments [rn , rn+l] (n = -3,-2,-1, ... ). to see that A is an example of a compact simply-connected set which is not locally connected. The set A was first considered by Hausdorff (see (19] p. 180). Now it is clear that A has a Hausdorff pseudo-cavity so p(A) ~ w ~ 2. And on the other hand we easily see that p(A) Some ~ w ~ 2 because of lemma 9. other examples of rank consists of Warsaw circle)(see the graph w~2: exactly known example of a set of rank called the Hence p(A) is exactly w • 2. w~2 (42] Another commonly is the "sin(l/x)-circle" (also p. 321). of the function f(x) The sin(l/x)-circle = sin(l/x) on the interval (0,2/7('] together with the line segments shown below on the left. - rir- :~ It is clear Hausdorff saw. that the sin(l/x)-circle A set of rank w~2 is homeomorphic to the which is not homeomorphic to the Hausdorff saw is shown above on the right. This set is a particular compactification of the real line IR , with an arc as the remainder (see [42] p. 321). The argument that this set has rank w ~ 2 is identical to that for the case of the Hausdorff saw. Some sets of rank w which are not locally path-connected. first example is essentially a The two-sided Hausdorff saw and is shown below on the left. Another example is the Hausdorff saw together with its inside. (It is easy to show that the Hausdorff saw separates the plane into two open components exactly one of which is bounded. The bounded component is called the inside.) The final example is much more complicated. consisting of the sn = (2-n+l ,l) for n three_- quarter segements, Let A be the set where [r n'sn]: rn = (2-n+l,O), ~ 1 and ro = (O,O) and so = (1,0); and the circles of radii 2-n (n€ IN) with centres at the origin and the missing quarters being in the first quadrant (see [32) p. 175). is a Then A compact path-connected. simply-connected set which is not locally Now since none of these three sets is convex it follows from Proposition 5 that they must be of rank at least w. But Lemma 8 also shows that these sets must be of rank at most w. So they have rank exactly w. A set of rank w + 1: <Y n> n€ IN (i) Consider the two-sided Hausdorff saw A. be a sequence of Jordan arcs in the inside of A which are pairwise disjoint and also disjoint from A Let -119(ii) tend to A as n (iii) are such that I Y n I -+ oo, and -+ O ad n -+ oo. Let B be the set consisting of A and the Y n's. (Here we follow the customary abuse of language and identify y n with its image.) Then B has rank w + 1. us by R. Edwards. This example was essentially suggested to Instead of the two-sided saw A, Edwards used a pseudo-arc (i.e., a set which separates the plane into two open components but which itself contains no Jordan arc). f \ ,,.- :0\ ,_• / I A First observe that for some large enough M the tree T~ is of rank w. This is because there is a fixed disk D (shown in broken line above) such that D ~ (IR 2-B) f\ ins(y n) for all n, and as n -+ oo . I yn I -+ O Thus p(B) ~ w + 1. Now from the definition of the tree T~ we know that the rank of T~ must be at most the supremum of the ranks of T~ where P is a path-component of B. M So r(TB) ~ w for any M € ID+, because each path-component P of B is either an arc or A, both of which have r(T~) < w. that B has rank exactly w + 1. Thus p(B) ~ w + 1. So we get -120- A set of rank w • _g which has no Hausdorff pseudo-cavity: This is the the last example we are going to give. Let B be set constructed as in the previous example except that the arcs Yn are all extensions of a Jordan arc Yo in the inside of A. Then for some large enough M € ~+ we see that T~ has rank at least w + 1. So p(B) ~ w~2 because of Proposition 4. Lemma 9 it follows that B has rank at most w~2 . Also from Thus p(B) = w ~ 2 and we are done. Remark. Let A be a Hausdorff saw. We define the amplitude of A by amp(A) = lim inf sup{llY-Y 'II: Y" ~ Y and I YI, I Y "I n-.oo ~ l/n where Y and Y " are Jordan arcs in A} Then by considering Hausdorff saws with amplitudes decreasing to zero instead of Jordan arcs in the pen-ultimate example we can obtain a set of rank exactly w ~ 2 + 1. -t.zt'§.3. The Rank Function p is Unbounded in w 1 on SC. In this the last section of chapter 3 our main goal will be to prove the following result. Proposition 10. The rank function p is unbounded in w 1 on SC. Proof. We will show by induction that for each a < w 1 there is set Aa € SC with p(Aa) ~ w •a . For a = O, 1 and 2 the result is clear because of the natural examples presented in the previous section. w; 3. We will first construct a set A3 € SC such that p(A 3 ) ~ The induction steps for successor ordinals and for limit ordinals will essentially be the same as this construction. be the Hausdorff saw shown below. 1/2. 1/4 l/S -----~----~~ ..L 4 B(r, 1/3) Let A2 -122Then a direct calculation shows easily that r(Tl ) ~ w + 1. Let 2 Ai be the set obtained from A2 by removing the line segments BC, CD and DE. copies of Now let A3 be the set obtained by inserting scaled Ai that fit exactly in the broken-line squares, Sn shown in the set below. E B I 1 .--·-B1 : s,_ __ ! _ _ _ t1 I I I I I Bo ,----·----- 3. ! I I I 1 I I I I '----------8 (r, I/~) c D -r2!Observe that the squares (n=0,1,2, ... ). Note simply-connected. Sn above also that have sides the We claim that p(A 3 ) set ~ of length 2-n compact and is A3 w~3 • To prove this it will suffice to show that r(T~ ) ~ w ~ 2 + 1. 3 Let Bn and En be the top left and right vertices, Note that there is exactly one respectively of the square Sn. Jordan arc Yn that connects Bn to En in A 3 (the broken lines are not parts of the set A 3 ). By considering the extensions of Yn in the square Sn we see that This is because there is a scaled copy of A 2 in the square Sn and the set consisting homeomorphic to the set A2. of A; 2 and the joining B and E. arc, Yn is Thus n~O} ~ Now each of the arc Yn Jordan w~ 2 . is an extension of the Jordan arc Y So we have a situation as shown below, -IZ4- where the ranks of the nodes <Y,Yn> in T 2 are unbounded in A3 w• 2. Thus <y> has rank w•2 + 1 so r(Ti_ ) 3 + 1. We thus have that p(A 3 ) ~ w ~ 3. Now suppose that the result is true for We construct Aa+l exactly as in the case of A3 . a, where a Just let ~ 3. A~ be the set obtained from Aa by removing the segments BC, CD and DE. Then insert scaled copies of A~ in the squares Sn in the same set used for A3 . p(Aa+l) ~ w~(a+l). Finally suppose that the result is true for all a < A., where A. is a An identical argument limit ordinal. sequence of ordinals with lim an shows Let <an>nE:IN be an increasing = A.. We proceed as before by inserting a scaled copy of A" in the square Sn. an once again that p(AA.) ~ w ~A.. that We obtain easily This completes the proof. D Remarks. We can show with a bit more effort that the sets Aa obtained above successor ordinal. have rank w •a , whenever a is a A slight refinement of the process at the limit ordinal stages will also (The set AA. exactly produce a set of rank exactly w •A. . , that we constructed above, turns to have rank exactly w~(A.+1).) Corollary g. JS is a coanalytic but not Borel subset of K. SC is -12.S- not an analytic subset of K. Suppose JS is an analytic subset of K. Proof. Let < be the relation defined by {A,M,u) <S (B,N,v) e:> A = B, M = N € ~+ and v extends u in T~. Then it is easy to see that ~ is a strict well-founded relation. So by Proposition 0.6, < has countable length, a say. would mean that p(A) But this ~ a for any A € JS, which is a contradiction. So JS is not analytic. The same argument shows that SC is not analytic. o We have seen that the rank function p, that we defined on JS, is a natural one and, although we haven't proved that p is a coanalytic norm, we were still able to get many of the analogous results in chapters 1 and 2. The question arises now as to whether p is a coanalytic norm. The difficulty here lies in the fact that the trees T~ (from which p is obtained) are "too big." It is very plausible however that p is a coanalytic norm so we make the following conjecture. Conjecture. The rank function p is a coanalytic norm. We will now describe briefly how to obtain a coanalytic norm p; on JS by making the trees T~ "smaller." p ; is not very natural and not very easy to work with either. It will however be very easy to see that p; is a coanalytic norm. Fix, once and for -126- all, a countable set ~' of Jordan arcs such that ~ is dense in the set of all Jordan arcs in the plane. For each A we now define a tree S~ in a similar way to T~. £ K, M £ Ill+, A typical node in S~ will be <f 1, ... ,fn> as shown below. B (r , VM) A The fi's are chosen from ~ under conditions which will ensure that they converge to a closed curve in A. So the curve f 1 is chosen so that its distance from A is small and so that there is an open ball not in A which is in ins(f 1 ). f 2 is chosen closer to A and also close enough to f 1 so as to ensure that same open ball is - - contained in both ins(f 1 ) and ins(f 2 ). The basic idea is to concoct S~ in such a way that if S~ has an infinite branch then A t JS. The converse result is always easy to obtain because ~ is dense in the set of Jordan arcs. The reason why the rank function p ", so obtained, is a coanalytic norm is because ~ is countable. Proposition 1.3. The proof is the same as that of -127- Final Remarks. As was mentioned in the introduction a natural question is whether SC is coanalytic. Below is an idea of H. Becker of how one might go about proving this (if it is indeed true!). We have that A € SC ~ path in A connecting x and y). A € JS and Vx,y A, 3Y (Y is a So if the path y can be chosen to be Borel in A it would follow that SC is coanalytic. can be chosen to be hyper-arithmetic in A (i.e., will follow that SC is € (If the path y .t..i in A) then it IIi .) Now one way of showing that the path y can be chosen in a Borel way is to use induction of the rank of A. The result is obvious for sets of rank 0 (because these are just the compact convex sets) but we have not been able to show that the induction step works. Problem. So the following question remains open. Is the set SC coanalytic? -rzschapter 4 Introduction. In this chapter we collect together a number of miscellaneous results about natural rank functions that are similar to those considered in the previous chapters. Let C = C[0,1] be the Polish space of all continuous real-valued functions on [O,l], and D be the subset of C consisting of all everywhere differentiable functions. (It is understood here that one sided derivatives are considered at the endpoints O and It was 1.) s. Mazurkiewicz shown by coanalytic subset of c. [38] that D is a complete Later A. S. Kechris and W. H. Woodin [26] defined a natural coanalytic norm on D, which we shall refer to as the Kechris-Woodin rank function. Also there is a given by Denjoy [11] which recovers any function f € process D from its derivative f" in a many steps, where a is a countable ordinal. This process provides another rank function on D, which is known as the Den joy rank function. sl is devoted to a comparison of the Kechris-Woodin and Denjoy rank functions. In %2 we show that there are functions of arbitrarily large Denjoy rank by using a simple construction. (This result was obtained before by A. Denjoy [11] but the constructions there were very complicated.) This provides another Rank Argument of the non-Borelness of D. Let now L 1 (11') be the Polish space of all Lebesgue integrable -129- functions on the unit circle 11', and CF be the set of functions in L1 (11') with everywhere convergent Fourier series. Let also EC be the functions in CF that are continuous, i.e., EC = CF f"I C(1!'). Ajtai is and A. S. Kechris (01] showed that EC a M. complete coanalytic subset of C(1!'). From this it follows easily that CF is a coanalytic subset of but not construction of Hurewicz z. Zalcwasser L 1 (11'). By specializing a (54] (see also D. Gillespie and W. [17]), Ajtai and Kechris obtained a natural coanalytic This norm is referred to as the Zalcwasser rank norm on EC. function. Borel In s3 we use the Zalcwasser rank to compare tests of everywhere convergence of Fourier series. It is well known that the Dini and Jordan tests are non-comparable but it is clear that in some sense the Dini test is much more powerful. We make this sense precise by associating with each test an ordinal, called its strength, by using the Zalcwasser rank function. Finally in s4 we show that the Zalcwasser rank function is unbounded in w1 on CF. s 1. This provides a Rank Argument of the non-Borelness of CF. A Functions. Comparison of the Kechris-Woodin and Den joy Rank For the details of the constructions of these rank functions we refer to (26] and (08] p. 96. Below we give a brief description. rank function. Let f [0,1] we define P; € C and c € First is the Kechris-Woodin <D+. For a closed subset P of by f: If P; £If = {x € P: 'ti open nghbd U of x 3I, J ~ U -t!O- with I, J € Q[0,1] and I A J A P ~ 0 The notation here is as in chapter 1 (Q[0,1] is the set of all closed subintervals of [O,l] with rational endpoints and length >O, etc.). It is easy to see that P ~, f is closed. We may thus define by induction a sequence <P ca, f> U€ ORD by putting 0 p CI f = [0,1] p>.. = 'SSS pca I f c, f a<>.. If f € D then Pc: f pa+l CI f = for >.. a limit ordinal. is nowhere dense in P, so P~, f is a strictly decreasing sequence of closed sets. countable a( c,f). ordinal a( c,f) such Thus there exists a least that = for 0 all a The Kechris-Woodin rank function is now defined by If I K-W = least a such that P~, f = 0, for all c € co+ = sup{a(c,f): c € co+}. We now describe the Denjoy rank function. Let E be a closed subset of [0,1] and g be a measurable function on [0,1) . We define the set S 'E) by S 'E) = {x € E: for all intervals I with x € I, g is not integrable on I A E}. Sg(E) is called the respect to E. For f set of € no n-summab i lit 1J points of g with C we define also the set Gf(E) by Gf(E) = {x € E: for all intervals I with x 2:1 I f(bn)-f(an) I diverges} € I, -f31- where {(an,bn)}n€1N is the sequence of open intervals complimenting E in [0,1] and Li denotes that the summation is taken over only those intervals (an,bn) that intersect I. Gf(E) is called the set of divergence points off with respect to E. It is easy to see that Sg(E) and Gf(E) are both closed subsets of E. then Sf ,(E) and Gf(E) are both nowhere dense denotes the derivative of E.) Moreover if f € D in E. (Here f' We can thus define a sequence of closed sets <Df>a€ORD for a given f € D as follows: Put D~ = [0,1], Df+l = sf ,(Df) v Gf(Df) and D~ = U Df for A. a limit ordinal. a<A. As before we see that there is a least countable ordinal, a(f) such that Df = 0 for all a ~ a(f). defined by If I DJ = a(f). that If I DJ ~ If I K-W . Lemma 1. Proof. Let f € D. Our goal in this section will be to show We first prove the following result. Then x € Df ~ 'Ve € ~+(x € P~, f). We prove the result by induction on a. is nothing to prove because D~ € The Denjoy rank function is now For a = 0, there = [0,1], and P~, f = [0,1] for all c Also if the result for all a ordinal then it follows easily for A.. < A., where A. is a limit So we only need to deal with the successor ordinal case now. Suppose the result is true for a. We shall show that x neighbourhood U of x. € R a+l c , f. Let x € of+l Fix c € To this end fix an open We need to show that 31,J ~ U with I,J € -132.Q[0,1] and I have two cases: Case x € a A J A Pe: , f (i) x € 'I: 0 such that sf .-(Df)' and (ii) x ill: I 6f(J)-6f(I) I Gf(Df). € Then for I, -f " is not integrable over I Df As f" is unbounded on I A Df there is a y If "(y)-6f(I) I J and £ Q[0,1] y € ~ J e: + 1. such x In particular f " is I such that whenever A Df. on Q[O,l]. A any interval I with unbounded € I Choose I. I ~ U with £ I A Df ~ U with Also we can choose J that definition of the derivative f ". € We e:. I 6f(J)-f "(y) I s 1 from the We thus get ~e:+l-l=e: By the induction hypothesis Df ~ P ae: , f , so y € I A J a f"i P e: , f and hence I AJA P~,f 'I: 0. Then for Here {an,bn)} complementing Df in [0,1] that intersect I. x € I and I £ Q[0,1]. any interval I are the with intervals ~ Choose I U with As L: I f(bn)-f(an) I = +oo we must have = l im sup I 6f([an,bn]) I n-+oo =+ So there is an N € the continuity of f IN such that we can oO • I 6f([aN,bN])-6f(I) I choose J ~ U with J ~ € e: + 1. By Q[0,1] and -13~- ~[+1-1=[ Now I must contain at least one of the endpoints aN'bN (otherwise (aN'bN) A I = 0, a contradiction). Since D~ ~ P~, f that I (', J A P~, f ~ 0. So at least one of aN,bN is in I (', by the induction hypothesis, we see This completes the proof. D Proposition ~- Proof. For each f Suppose = a. If I K-W and consequently D~ D, If I DJ ~ If I K-W . € = 0. Th en f or a 11 Thus ~ If I DJ E a € = ll::t+, pa E, f If I K-W and we are done. Remarks. = 0, o It is easy to see that lflDJ = 1 iff f' is integrable and it was shown in [26] that If I K-W = 1 iff f' is continuous. Now consider function f given by f(x) __ { x 2 sin( 1/x} XE (0,1] x = 0 0 Then f' is bounded in [0,1] and so is integrable. 1. But it was shown in [26] that Proposition 2 is false. Thus (fl DJ = Jf J K-W = 2, so the converse of In fact much more than this can be said. Let BD 1 = {fED; If '(xll~ 1 for all XE(0,1]}. It was shown in [26 ] that the Kechris-Woodin rank function is unbounded in w 1 on BD 1 . But -134- lfJ DJ = 1, for all f E each function in BD 1 is integrable, so BD . 1 We thus get that for each a ~. w 1 , there is an fa such that l'f:LoJ = 1 but !flK-W ~ a. s2. The Denjoy Rank Function is Unbounded in w1 on Q. main goal of this section is to prove the The following result. Proposition~ (Denjoy). such that lflDJ Proof. there ~ For each a< w1 , there is an f nothing D a. For a = 1 consider the We prove the result by induction on a. is € For a = 2 = { x 2 sin(x- 2 ) x € to prove. we function f 2 given by f 2 (x) It is a standard x = 0 0 fact (0,1] that f 2 is not integrable on any interval which contains the point x = O. Sf ;((0,1]) 2 = {O} and Gf (0,1] = 0. 2 So In fact we have oi 2 = {O} and D~ 2 = -135We shall now construct a function f 3 such that = 3. of lf 3 1DJ The same construction works for the successor ordinal our induction, and with a slight modification for limit ordinal cases as well. and obvious Let x = a be = 1/2, the first maximum of f 2 to the left of x and g be the function obtained by reflecting the graph of f 2 ~[0,a] in the line x = 1/2 and by joining the two maxima with a straight line. I ..L. lz 1 I I I Now choose a differentiable function h on [0,1] such that h' is continuous on (0,1] and h(.!.) = n -l)n n {log n f or a 11 n 2x -2x log(l/x) ~ h(x) ~ log(l/x) Let gn be a scaled copy of interval [1/(n+l),1/n]. g ~ , for x € that € fits and 0,1). exactly We define the function f x € 3 [l/(n+l),1/n] x = 0 in by the -;zx Y-=- --- ---103(1/x) / / / / / 0 ------ --- -- --- ---- 1 _.l_ ""if" 11t1 ....... ...... ............ ..................... Y~ 3:L.. 10~ (1/X) ''-.' "' It is easy to see that f 3 D. € It is also clear that = {0,1,l/2,1/3, ... }. o 1f 3 is countable. so o 2 f 3 = {o} Also Gf and hence D~ 3 3 o1 f3 = = 12! because (Di 3 ) = {O} by the choice of h. = 0. Thus I f 3 I DJ = 3. This completes the proof of the result. D Remark 1. Using the process above we can actually check that at the successor ordinals we get a function fa+l with However at a limit ordinal A we get a The reason for this is because by its definition the Denjoy rank can never be a limit ordinal. -137Remark It was 2. pointed out in [26] that although Denjoy rank function is not a coanalytic norm, satisfy condition (i) with Proposition 3 of Proposition 0.2. the D and I ~1 03 This together provides another Rank Argument of the non-Borelness of D. 'S 3. The Zalcwasser Convergence of Rank Fourier Function and Tests We Series. shall description of the Zalcwasser rank function. refer to [Ol]. Let f = <fn>n€1N be a C(T), P a and let be closed subset for first Everywhere give a brief For more details we sequence of functions in of T. We define the everywhere convergent sequence then it can be shown that P~,f o sci l lat ion wp(!;x) , of f at x with respect to P by = inf inf 15 Now define P ~ , f is closed and I y-x I< 5,y€P}. k by ; (If nowhere dense in P. We can decreasing sequence Z~, f by induction as follows: Put z~, f C. =T , z~+. fl = (Za( I f ) (; I f <. thus define a and z~, f n = a<A. Z a£ , f for A. a limit ordinal. As in the case of the Kechris-Woodin rank function we see that there is a least countable ordinal for all a ~ a( c,f). a( c,f) such that Z~, f = 0 We then define the Zalcwasser rank function by I ~ I z = least a such that z ~ , f = 0 for all £ € <O + The Zalcwasser rank function applies naturally to the set CF of all functions in L 1 (11') with everywhere convergent Fourier series by letting I f I z = I <Sn (f)> I z for f € CF where s (f) are the partial sums of the Fourier series of f. n Let now J be a test for everywhere convergence of Fourier series. We define the strength, S(J) of J by S(J) = sup{ If I 2 +1:J shows that the Fourier series of f is everywhere convergent} The aim of this section is to compute the strengths of the -1'59- Lipschitz, Jordan and Dini tests for everywhere convergence. For convenience we give the tests below. If f is of bounded variation on 11' then the Fourier Jordan Test: series of f converges everywhere. Dini Test: If at each f(x+t)+f(~-t)-2f(x) point x 11' the some 8x of dt converges for J8x0 integral > 0, then the Fourier series of f converges everywhere. Lipschitz Test: continuity JJ(8) If f is continuous on 11' and the modulus of satisfies JJ(8)log 8 -+ O as 8 -+ O then the Theorem in Fourier series of f converges uniformly on y, We will need the following definition and calculating the strength of the Jordan test. Definition: A sequence neighbourhood of x 0 and of functions converging for converge continuouslv at x 0 c "</ for all x with 8 and all n Theorem c. < x defined > O 3 8 > O and N ~ in a = x 0 , is said to to a limit function f neighbourhood of x 0 , if I x-x 0 I <fn> , defined in a € ...i such that N we have I fn (x)-f(x) I < Let f be a function of bounded variation on 1J'. Then -140the exhibits phenomenon Gibbs at each essential (non-removable) point of discontinuity and converges continuously at each of the other points. Proof. See (55] p. 61-62. Lemma 4. Let f be a function of bounded variation on 'f. 1f1 2 Proof. 0 ={ 1 if f Then has no essential discontinuity 2 otherwise If f has no essential discontinuity then Sn(f) is the same as the Fourier series of continuous function on 'I which is of bounded variation. So Sn(f) converges uniformly in 'f, But from (01] we know that If I z = 1 iff Sn(f) converges uniformly. So we are finished with the first part. Now If I z ~ 2. suppose f has an essential discontinuity. Then Let {xn} be the countably many points of essential discontinuity of respective jumps. = f I l im f(x)- l im f(x) I X--+Xn + X--+Xn - be their Then by Theorem C we get that the oscillation of the sequence Sn(f) in 'I is given by w (x) T ={ idn if x = xn o otherwise, where 2 is the Gibbs constant. Since f is of bounded variation -141there are finitely many xn's , or there are infinitely many xn's 0 ~ as So n {x : wT(x)~ £:} is a finite set. fixed £: > O. a fixed < £: This shows that Z~, f = 0, = 0 for each Thus If I z :.:; 2 and we are done. Proposition _Q: D Let 3' L' 3' J and 3' D be the Lipschitz, Jordan and Dini Then S(J L) = 2, S(J 3 ) = 3 and S(J D) = w1. tests respectively. Proof. for For 3' L there is nothing to prove because 3' L is a test for uniform convergence. The result for J 3 follows immediately from Lemma 4. So we need to show that S(J D) = w1 . D(T) all everywhere differentiable functions in (26] be of indicated it can shown function is unbounded in - w1 on D(T). that Consider the set the on T. As Zalcwasser rank But for any f Dini test shows that Sn(f) converges everywhere in 1'· € D(T), the So we get that S(JD) = w1 . D %4. The Zalcwasser Rank Function is Unbounded in w1 on CF. This final section of Chapter 4 is devoted to proving the following result. Proposition 6. For each a < w1 , there is an f € CF such that If I z ~ a. Proof. The proof is once again by induction on a. there is nothing to prove. For a = 1 For a = 2 we use a well known example of a function whose Fourier series converges everywhere but not -(42uniformly. Using this function we construct by a general process, a function of rank 3. The general case for successor ordinals and limit ordinals is essentially the same and is carried out as in Proposition 3. Let a € IN and put nk =a k2 . Define fa by ,, where Q(x,n) is the Fejer trigonometric polynomial given by -Q(x,n) = nL: sin(2n-i)x i=l l n L: sin(2n+i)x i=l i It is easy to see that fa is continuous and for sufficiently large a it is shown in [04] p. 125-127 that Sn(fa) converges everywhere, but not uniformly in any interval containing x = O. From this it follows easily that I fa I z = 2. Now let ga = b~fa where b = b(a) is chosen so that X€1!',k€1N} = 1 Observe that for a given open interval I with O € I, we can make the partial sums Sk(ga;x) arbitrarily small outside I by taking a large enough. Let <In> be a sequence of disjoint open intervals with 2K/n € In. Choose an large enough so that -143- I Sk(ha ;x) I ~ 2-n for all k n where the function ha n € JN, all x t In is defined by ha (x) = ga (X-27r/n). n n !A 00 Now observe that the sum, 2: n=l Sk(ha ;x) converges for each k, and n 00 that f 3 (x) = lim 2: Sk(ha_ ;x) is a well defined function. k-.oo n=l -n easy to verify that I f 3 I z = 3. This completes the proof. Remark. Observe I ~I z , satisfy the It is o that CF and Zalcwasser rank function condition (i) of Proposition 0.2. This together with Proposition 6 gives a Rank Argument of the non-Borelness of CF. -14-4References (All articles and Journals in Russian are transliterated using the British 2979 System. Everything else is as it is.) [01] Ajtai, M. and Kechris, A. S., The set of continuous functions with everywhere convergent Fourier series, to app ear. [02) Ampere, M., Recherches sur quelques points de la theorie des fonctions derivees etc., Ecole Polytechnique, Bd. 6, Cah. 13(1906), p. 148-181. [03) Banach, S., Uber die Baire'sche Kategorie gewisser Funktionenmengen, Studia Math., 3(1931), p. 174-179. [04] Bary, N. K., A treatise on trigonometric se ri es , Vol. 1, Macmillian, New York (1964). [05] Becker, H., Some theorems and questions about some natural examples in Descriptive Set Theory, Mimeographed notes (May 1984). [06] Belov, A. S., Study of some trigonometric series, Mathematical Notes 13(1973) , p. 291-298. [07] Besicovitch, A., Diskussion der steitgen F1:1.nktionen im Zusamenhang mit der Frage uber ihre Differentiierbarkeit, Izvestiya Akad. Nauk 19(1925), p. 97-122 and p. 527-540. [08) Bruckner, A. M., Diff er entiation of real functi o n s , Lecture notes in Math., Vol. 659, Springer-Verlag, New York (1978). [09] Cellerier, C., Note sur les principes fondamentaux de 1 1analyse, Bull. des Sci. Math., Ser. 2, Vol. 4(1890), p. 142-160. [10] Chen, Y. M., A remarkable divergent Fourier series, Proc. Japan Acad., 28(1962), p. 239-244. [11] Denjoy, A., M.emoire s ur la derivation et s on calcul invers e, IIIe Partie, Gauthier-Villars, Paris (1954). [12) Du Bois-Reymond, P., ,Yersuch einer Klassification der willkurlichen Funktionen reeler Argumente, J. fur Math., 79(1874), p. 21-37. [13) Falconer, K. J., The geometry of fractal sets, -145Camb. Univ. Press, Cambridge (1985). [14] Fatou, P., Series trigonometriques et series de Taylor, Acta Math., 30(1906), p. 335-400. [15] Gerver, J., The differentiability of the Riemann function at certain rational multiples of 7'!:, Amer. J. of Math., 92(1970), p. 33-55. [16] Gerver, J., More on the differentiability of the Riemann function, Amer. J. of Math., 93(1971), p. 33-41. [17] Gillespie, D. C. and Hurewicz, W. A., On sequencs of continuous functions having continuous limits, Transac. Amer. Math. Soc. 32 (1930), p. 527-543. [18] Hardy, G. H. and Littlewood, J. E., Some problems of Diophantine approximations : A remarkable trigonometric series, Proc. Nat. Acad. Sci., 2(1912), p. 583-586. [19] Hausdorff, F., Set theory, Chelsea Publ., New York (1962). [20] Herzog, F., A note on power series which diverge everywhere on the unit circle, Michigan Math. J., 2(1953-54), p. 175-177. [21] Hobson E., Th e th e ory of the functions of a r e al var i abl e, Vol. 2, Dover Publ., New York (1957). [22] Kechris, A. S., Descriptive Set Theory, Mimeographed notes (M.I.T. Fall 1973). [23] Kechris, A. S., Examples of !i sets and norms, Mimeographed notes of Oberwolfach talk (April 1984). [24] Kechris, A. S., Descriptive Set Theory and Analysis, Mimeographed notes, Caltech-UCLA seminar (Jan. 1985). [25] Kechris, A. S., Sets of everywhere singular functions, to appear. [26] Kechris, A. S. and Woodin, W. H., Ranks of differentiable functions, to appear. -14'[27] Knopp, K., Ein einfaches Verfahren zur Bildung stetiger nirgends differenzierbarer Funktionen, Math. Zeit., 2(1918), p. 1-26. [28] Kolmogorov, A. N., Une serie de Fourier-Lebesgue divergent presque partout, Fund. Math., 4 (1923), p. 324-329. [29] Kolmogorov, A. N., Une serie de Fourier-Legesgue divergent partout, C. R. de l'Acad. des Sci. Paris, 183 (1926), p. 1327-1329. [30] Korner, T. W., Everywhere divergent Fourier series, Colloq. Math., 45(1981), p. 103-118. [31] Kowalewski, G., Ueber Bolzanos Nichtdifferenzierbare stetige Funktion, Acta Math., 44(1923), p. 315-319. [32] Kuratowski, K., Topology, Vol. II, Academic Press, New York (1968). [33] Lusin, N. N., Uber eine Potenzreihe, Rendi. Circ. Matern. di Palermo, 30(1911), p. 386-390. (34] Maly, J., Where the continuous functions without unilateral derivatives are typical, Transac. Amer. Math. Soc., 283(1984), p. 169-175. [35] Marcinkiewicz, J., Sur les series de Fourier, Fund. Math., 27(1936), p. 38-69. [36] Mauldin, R. D., The set of continuous nowhere differentiable functions, Pacific J. of Math., 83(1979), p. 199-205. [37] Mauldin, R. D., The set of continuous nowhere differentiable functions: A correction, Pacific J. of Math., 121(1986), p. 119-120. [38] Mazurkiewicz, S., Uber die Menge der differenzierbaren Funktionen, Fund. Math., 27(1936), p. 244-249. [39] Mazurkiewicz, S., Sur les fonctions non derivables, Studia Math., 3(1931), p. 92-94. [ 40] Morse, A. P., A continuous function with no unilateral derivatives, Transac. Amer. Math. Soc., 44 (1938), p. 496-507. (41] Moschovakis, Y. N., Descriptive Set Theory, North Holland Publ., New York (1980). [42] Nadler, Jr., S. B., Hyperspaces of sets, Marcel Dekker, -147New York (1978). [43) Rychlik, K., Veber eine Funktion aus Bolzanos handschriftlichen Nachlasse, Ceska Spolenost. nauk, Prague Trida matematicko pritodoved Vestik (1921-22), p. 1-20. [44] Saks, S., On the functions of Besicovitch in the space of continuous functions, Fund. Math., 19(1932), p. 211-219. [45) Singh, A. N., On Bolzano's non-differentiable function, Bull. de l'Acad. Polonaise des Sci., (1928), p. 191-220. [46] Singh, A. N., The theory and construction of nondifferentiable functions, Lucknow Univ. Studies, No. 1 (1935). [ 4 7) Smith, A., The differentiability of Riemann's function, Proc. Amer. Math. Soc., 34(1972), p. 463-468. (48) Stechkin, S. B., 0 trigonometricheskikh Ryadakh Raskhodyashchikhsya v Kazhdoi tochke, Izvestiya Akad. Nauk, 21(1957), p. 711-728. [ 49) Steinhaus, H., Sur un serie trigonometrique divergente, C. R. de la Soc. Sci. Varsovie, 5(1912), p. 223-227. (50) Steinhaus, H., An example of a thoroughly divergent orthogonal development, Lond. Math. Soc. Proc. (2), 20(1921), p. 123-126. [51] Steinhaus, H., A divergent trigonometrical series, J. of Lond. Math. Soc., 4(1929), p. 86-88. [52) Takagi, T., A simple example of a continuous function with no derivative, Proc. Physic-Math. Soc. of Japan, Ser II, 1(1903), p. 176-177. (53) Young, G. C., On infinite deriatives, Quart. J. of Math., 4 7(1916), p. 148-163. [54) Zalcwasser, Z., Sur une propriete du champes des fonctions continues, Studia Math., 2 (1930), p. 63-67. (55] Zygmund, A., Tr i gonometric series, Vol. 1, Camb. Univ. Press, Cambridge (1959). TH•Clll