REHMTN.Q3 ,~ MEASURE THEORY AND WEAK KONIG'S LEMMA $by * * Xiaokang Yu and Stephen G. Simpson May 24, 1989 Abstract ________ We develop measure theory in the context of subsystems of second orderarithmetic with restricted induction. We introduce a combinatorial principle ~WWKL (weak-weak Konig's lemma) and prove that it is strictly weaker than WKL ~(weak Konig's lemma). We show that WWKL is equivalent to a formal version ofthe statement that Lebesgue measure is countably additive on open sets. Wealso show that WWKL is equivalent to a formal version of the statement thatany Borel measure on a compact metric space is countably additive on opensets.___________________________________* The research of both authors was partially supported by NSF GrantDMS-8701481..P.Q4 -~ MEASURE THEORY AND WEAK KONIG'S LEMMA by Xiaokang Yu and Stephen G. Simpson # 1. Introduction. ____________ ~ Weak-weak Konig's lemma is the following combinatorial principle: 5]" 1If T h Seq is a tree without a path, then lim { ______ = 0 . 2 )[' lh(s) .n 2 3s m T 2lh(s)=nHere Seq denotes the full binary tree, i.e. the tree of all finite sequences 2of 0's and 1's ordered by inclusion. WWKL is the subsystem of second order *0 .~arithmetic consisting of RCA plus weak-weak Konig's lemma. A much better 0 8~known system is WKL , which consists of RCA plus weak Konig's lemma: every 0 0 =~infinite tree T h Seq has a path. It is obvious that weak Konig's lemma 2 ~implies weak-weak Konig's lemma. We shall give models to show that RCA does not imply WWKL , and WWKL +0 0 0 $~does not imply WKL . Just as weak Konig's lemma is equivalent to the 0Heine-Borel theorem (see Simpson [7], #IV.1), it can be shown that weak-weak ~Konig's lemma is equivalent to a weak version of the Heine-Borel theorem. Inthis paper, we establish this equivalence and extend it to a discussion of thecountable additivity of measures on compact metric spaces. In doing so, wewill examine some more general forms which nevertheless remain equivalent to ~weak-weak Konig's lemma. For general background on subsystems of second order arithmetic, seeSimpson [7], [8]. # 2. Models of WWKL . 0 _______________ The purpose of this section is to exhibit w-models showing that RCA does H0not include WWKL and WWKL does not include WKL . We will use the usual 0 0 0 :wnotation for the Lebesgue measure m on the Cantor space 2 . Here w is the wset of natural numbers, 2 is the set of functions from w into {0,1}, and m is w wthe unique Borel measure on 2 such that m({f m 2 : f(m) = i}) = 1/2 for all mm w and i m {0,1}. Subsets of w are identified with characteristic functions win 2 . If p is a class of subsets of w, m(p) has the usual meaning. First let us look at REC, the minimum w-model of RCA , consisting of the 90 :0 wrecursive sets. Jockusch [3] has shown that there is a P class p h 2 which :1 %1has no recursive element, and m(p) > _. Let T h Seq be a recursive tree such %2 2that p = {f: f is a path through T}. Thus T has no path in REC, yet ]" 1 lim { ______ = m(p) > 0. [' lh(s) n 2 s m T lh(s)=n ~Hence weak-weak Konig's lemma fails in REC. Thus REC is an w-model of RCA J0 <~which is not a model of WWKL . (It follows that weak-weak Konig's lemma 0cannot be proved in RCA .) 0 Next, we shall construct an w-model of WWKL which is not a model of 00WKL . We use letters X, Y, Z,... for subsets of w. We always identify a 0set with its characteristic function. For sets X and Y, X p Y is the setZ such that Z(2m) = X(m) and Z(2m + 1) = Y(m). X is said to be random over 1,Y wY if for every D class b (i.e. b h 2 is Borel with code recursive in Y), 1m(b) = 1 implies X m b. Define a sequence of sets X , n m w, as follows. 5n 0 n n+1 nLet X = O, X be random over X , and X = X p X . Let n )n 9 n ( m = Y: ]n (Y , X ) . ( T 9Here Y , X means that Y is Turing reducible to X, i.e. recursive in X. TClearly m is an w-model of RCA . 0 Theorem. m is a model of WWKL . _______ 0 PROOF: Suppose T is a binary tree in this model, i.e. there is n such Gn n 9 ( 1,Xthat T , X . Let d = Y: ]Z = Y (Z is a path of T) . d is D . If T ( T 9 1the set of paths through T is of positive measure, then by the 0-1 law (cf.Halmos [2], p. 201, and #10 of Sacks [6]), m(d) = 1, so that X m d. From ?nthe definition of d, there is Z, a path of T, such that Z = X . Thus T @T nhas a path in the model. This shows that m is a model of WWKL . z @0 Theorem. m is not a model of WKL . _______ 0 PROOF: Let A and B be two disjoint recursively enumerable subsets ofw which are not recursively separable. We claim that there is no Y m m whichseparates A and B. To prove this, it suffices to show that for all n m w nthere is no Y , X which separates A and B. We prove this by induction Ton n. For n = 0, it follows from our assumption. Suppose that our claim has %n 9 X (been proved for n. Let d = Z: ]Y , Z (A h Y c B f Y = O) . Since A and B ( T 9 nare inseparable by any Y , X , from Theorem 5.3 of Jockusch and Soare [4] T Kn n 71,Xrelativized to X , we see that m(d) = 0. Hence X n d because d is D . 2n 1 n n+1 XIf Y , X , then Y , X , and hence Y can not separate A and B. This T T n ~ 0proves our claim. Since weak Konig's lemma is equivalent to S separation >1(Lemma 2.6 of Simpson [9]), it follows that m is not a model of WKL . z D0 # 3. Definition of Measures and Countable Additivity. _______________________________________________ A positive measure on a compact complete separable metric space X isdefined as a positive bounded linear functional on the separable Banach spaceC(X). Here we are following the approach taken in Chapter 2 of Rudin [5]. Weshall use many concepts of analysis developed in the language of second orderarithmetic. The purpose of this section is to briefly review the conceptsthat we shall need. Unless otherwise stated, we are working within RCA . G0 A real number is coded as sequence of rational numbers which >nis strongly Cauchy in the sense that for any n m N and m , n, |r - r | < Dn m 1___ . A complete separable metric space is (coded by) a set A h N together n 2with a function d: AxA --3 R such that d is a pseudo-metric on A. A point ^x in the completion X = is a sequnce which satisfies that .n $1for any n m N and m , n, d(a ,a ) < __ . A space is compact if there is a n m n $2 B1sequence of finite subsets of A, , such that A is an ___ -net of #n n n B2X. We can prove in WKL that compactness defined this way implies Heine-Borel 0compactness. (See Brown-Simpson [1].) A separable Banach space is a set A hN together with operations of addition and scalar product, a distinguishedelement 0, and a function | |: A -3 R such that (A, +, ., 0) forms a vectorspace over Q and | | is a pseudo-norm on this vector space. The points of the ^separable Banach space B = (A,| |) are the points of the completion of A underthe metric d which is defined by d(a,b) = |a - b|. For a detailed discussionof these concepts, see Brown-Simpson [1] and Simpson [8]. ^ Let X = (A,d) be a (code for a) compact complete separable metricspace. A basic function code p is a triple ;a,r,s: with r,s m Q, a m A, and0 , s < r. For p = ;a,r,s: and x m X, it is understood that ^ 1 if d(a,x) , s ! ! r - d(a,x) p(x) = 8 ____________ if s < d(a,x) < r ! r - s ! ! 6 0 otherwise.There is also a (code for a) basic function for the constant 1 function.A (code for a) polynomial is ;;q ,t :: n , m: where m m N, the q 's !n n nare basic functions, and the t 's are rational numbers. If p is such a n 7]"polynomial and x m X, it is understood that p(x) = { t q (x). 7[' n n 6n,m Let P be the set of all (codes for) polynomials. For p,q m P, thesum p + q is the polynomial coded by p^q, the concatenation of p and q.For p = ;;q ,t :: n , m: m P and r m Q, the scalar product rp is the n npolynomial ;;q ,rt :: n , m:. It is easy to verify that (P, +, ., 0) forms n na vector space over the rational field. Furthermore, there is a norm | | on(P, +, ., 0) such that |p| = sup{|p(x)|: x m X}. The existence of thissupremum norm can be proved in RCA , as X is compact. Let C(X) be the "0 ^separable Banach space (P,| |). We say that g is a point of C(X), denotedby g m C(X), if g is a sequence of polynomials ;p : n m N: such that for 5n "1any n m N and m , n, |p -p | < ___ . It is understood that for every x m n m n "2X, g(x) = lim p (x). The (finite) sum, product, quotient, maximum, and n nminimum can be defined accordingly so that C(X) is closed under thoseoperations. A probability measure (or simply a measure) on X is a bounded linearfunctional m on C(X) such that m is positive and m(1) = 1. With sucha functional, for any open set U, we can talk about the measure of U,which is defined as m(U) = sup{m(g) : g m C(X), 0 , g , 1 and g = 0 onX\U}. In general, it cannot be proved in systems weaker than ACA that this A0supremum exists. Since m(U) need not exist as a real number, the statementsof the following theorem are provable only in the comparison sense, withoutassuming the existence. For instance, m(U) , m(V) is taken to mean that forevery g such that 0 , g , 1 and g = 0 on X\U, there is h such that 0 , h , 1and h = 0 on X\V and m(g) , m(h). Theorem (RCA ). Basic properties: _______ 0 1. m(X) = 1 and m(O) = 0. 2. If U is open and C = X\U, then m(U) = 1 - m(C). 3. If U and V are open and U h V, then m(U) , m(V). 4. If U and V are open, then m(U) + m(V) = m(U g V) + m(U f V). 5. If U is open, m(U) = sup{m(C): C h U}, where C is closed. Proof: See Yu [10]. Now, let us see some examples of measures.Example 1. Lebesgue measure: The Lebesgue Measure m on [0,1] is the_________ -Llinear functional that for every polynomial p, &1 %~ m (p) = p(x)dx, L ` &0the Riemann integral of p from 0 to 1. It is easy to prove within RCA that H0such a linear functional exists. We can also prove that for every basic openinterval I h [0,1], m (I) = the length of the interval I. LExample 2. Probability measures on the Cantor space: Any probability measure_________ wm on the Cantor space 2 can be considered, within RCA , as a non-negative 70function M: Seq --3 R such that M(; :) = 1 and M(s^0) + M(s^1) = M(s), 2 wwhere M(s) = m(I ) = m({f m 2 : s h f}). Also, any function M: Seq --3 R s 32such that M(; :) = 1 and M(s^0) + M(s^1) = M(s) , 0 can be made into aprobability measure m on the Cantor space by proper definitions of the valuesof basic functions in such a way that M(s) = m(I ). 1s One important feature of measures is countable additivity. We say that mis countably additive, if whenever U is open and ;U : n m N: is a sequence 6nof open sets such that U = g U , then m(U) = sup{m( g U ): k m N}. Keep in n n n n,kmind that these suprema need not exist (provably in RCA ), and the equation 70here is in the comparison sense. There are two obvious results: Lemma (RCA ). m is countably additive if and only if for every sequence _____ 0of basic open balls ;I : n m N:, if g I = X, then sup{m( g I ): k m N} n n n 'n n,k= 1. Lemma (RCA ). If m is countably additive, U = g U , where U and _____ 0 *n 7n &]"the U 's are open sets, then m(U) , { m(U ). And if the U 's are n [' n n &n !]"pairwise disjoint, then m(U) = { m(U ). ![' n !n The countable additivity of measures can be proved in WKL , because in >0this case X is Heine-Borel compact. But what we really need is only aweaker form of Heine-Borel compactness. From the definition, the countable 9]"additivity of the Lebesgue measure m asserts that if { (b - a ) < 1, $L [' n n 9n ^ & ^ &then 8 a , b : n m N* is not an open covering of [0,1]. This is a weak 6 n n7 6 7version of Heine-Borel theorem. =~ If we consider measures on the Cantor space, weak-weak Konig's lemmastates that M is countably additive, where M is the measure such that for 0 0 1s m Seq , M (s) = ______ . The following combinatorial principle (*) can be 2 0 lh(s) 2interpreted as the countable additivity of an arbitrary probability measure onthe Cantor space.(*) For any probability measure M on the Cantor space, &]" M(T) = lim { M(s) = 0 &[' !n $lh(s)=n %s m Tif the tree T h Seq has no path. 2 ~ # 4. Weak-weak Konig's lemma for measures on the Cantor space. ________________________________________________________ In this section we want to show that the general principle (*), defined *~above, is no stronger than the weak-weak Konig's lemma and they are equivalentto the countable additivity of Lebesgue measure. Theorem 1 (RCA ). The following are equivalent. _________ 0 ~ 1. Weak-weak Konig's lemma. 2. The countable additivity of the Lebesgue measure m . 0, there is n m N such that { __ < e. Thus 0[' n 52 .s m T -lh(s)=n ! ! ! ! ^ & ]" ^ & m ( a , b ) = { m ( a , b ) < e . L 6 7 6 s s7 [' L 6 s s7 - s m T s m T lh(s)=n lh(s)=n ! ! ! ! ^ & ^ &As [0,1]\ a , b h g c , d , it follows that 1 - e < 6 7 6 s s7 6 n n7 - i,n s m T lh(s)=n ^ &m ( g c , d ). L 6 n n7 i,n PROOF of 3 -3 1: Trivial. PROOF of 2 -3 3: Suppose that a measure M, a tree T, and a number n M0m N is given. The measure M on the Cantor space can be considered as a map N ]" M(s)(i)from Seq into 2 . We will write M(s)[n] = { _______ . Then M(s), as 2 &[' i+1 42 /i- ~ 1 - _____ . L 6 7 6 s s7 n +2 - ~ 0 s m T 2 lh(s),mHence ! ! ! ! ^ & 1 1 m ( cs, ds ) > 1 - _____ - _____ . L 6 7 6 s s7 n +2 n +1 - ~ 0 0 s m T 2 2 lh(s),mThen, it is easy to prove that ! ! ]" ! ! ^ & 1 1 { (d - c ) , m ( cs, ds ) - _____ > 1 - ___ . [' s s L 6 7 6 s s7 n +2 n ~ - ~ 0 0 s m T s m T 2 2 lh(s),m lh(s),mTherefore, ]" ]" ]" 1 { M(s) = 1 - { M(s) , 1 - { (d - c ) < ___ . [' [' [' s s n ~ ~ 0 s m T s m T s m T 2 lh(s)=m lh(s),m lh(s),mThis completes the proof. z B~ Remark. Another principle which is equivalent to weak-weak Konig's lemma ______(provably in RCA ) can be formulated as follows: 0 Let Seq be the set of all sequences of natural numbers. If S is abounded subtree of Seq, if M: S --3 R is non-negative such that M(; :) = 1and M(s) is the sum of all M(t)'s, where the t's are the immediatesuccessors of s, then for every subtree T of S which has no path, !]" M(T) = lim { M(s) = 0. ![' n s m T lh(s)=n # 5. Countable Additivity of Measures ________________________________ Theorem 1 shows that it is provable in WWKL that every measure on the 10Cantor space is countably additive. Naturally, we expect the same result forany compact complete separable metric space within WWKL . 70 Theorem 2 (WWKL ). Any measure on any compact complete separable metric _________ 0space is countably additive. F^ PROOF: Let us assume that a compact complete separable space X=(A,d) isgiven as follows: (a) There is a sequence of finite sets A h N such that ;nA f A = O for n = m, and A = g A . (b) d is a pseudo-metric which is n m n nbounded by one. For a,b m A, d(a,b) = lim d (a,b), here d : AxA -3 Q and (n n n 1 "1d (a,b) , d(a,b) , d (a,b) + __ . (c) For every n, A is a _____ -net, n n n n n+1 4 4i.e., for every x m X, for any n, there is a m A such that d(a,x) < 3n 1____ n+1 .4 Let S = {s m Seq : [ s(n) is a (code of a) subset of A }. S is n < lh(s) "na complete bounded tree. Suppose that is an open cover of X )i .^ A^ &with J = being basic balls. Let T = 8s m S : [ s(n) = O i i i (n < lh(s)6 7 .6 /. [ [ [ ^ 2 2 & n , m < lh(s) a m s(n) b m s(m) d (a,b) < ____ + ____ /. '6 m+1 n+1 m+1 7 44 4 <& ] [ ^ 5 & ~ i , lh(s) a m s(lh(s)-1) d (a,b ) < r - ______ * . We want to 6 lh(s) i i lh(s) 7 34 7show that T is a subtree of S which has no path. First, we prove that T is a subtree. Suppose s h t , t m T ands n T. We must have an i , lh(s) < lh(t) such that d (a,b ) < r - 6lh(s) i i 5_____ for any a m s(lh(s)-1) = t(lh(s)-1). Since t(lh(s)-1) = O, there is lh(s)4 25a* m t(lh(s)-1) such that d (a*,b ) < r - _____ . For any a m lh(s) i i lh(s) 04 2 2t(lh(t)-1), d (a*,a) < ______ + _____ holds. Therefore, d (a,b ) , lh(t) lh(t) lh(s) lh(t) i 4 4 @1 1d(a,b ) , d(a*,b ) + d(a*,a) , d (a*,b ) + d (a*,a) + ______ + ______ i i lh(s) i lh(t) lh(s) lh(t) >4 4 5 2 2 1 1 5< r - _____ + _____ + _____ + ______ + ______ , r - _____ . Hence i lh(s) lh(t) lh(s) lh(s) lh(t) i lh(t) 4 4 4 4 4 4t n T, a contradiction. To show that T has no path, let us assume there is f h T. For any n,there is a m f(n). Let x = . x is an element of the space X n nbecause the sequence converges. For any n and any m > n, d(a ,a ) , ?n m 1 2 2 1 3 3d (a ,a ) + ____ < ____ + ____ + ____ < ____ . Therefore, d(a ,x) , ____ . m+1 n m m+1 n+1 m+1 m+1 n+1 n n+1 4 4 4 4 4 4It is clear that the choice of the sequence does not affect the limit element. 93Actually, we can prove that for any a m f(n), d(a,x) , ____ . Since is an open cover of X, there is i such that d(x,b ) + d < r for some d 7i i ,2> 0. Let n m N be such that n , i and ___ , d. Then for any a m f(n), -n ,4 43 5d (a,b ) , d(a,b ) , d(x,b ) + d(a,x) < r - d + ____ , r - ____ . This n+1 i i i i n+1 i n+1 34 4shows that f[n+1] n T, a contradiction. Now, let us assume m is a measure on X and e is a positive realnumber. We want to prove that there is m m N such that 1 - e < m(g J ). Hi Di,mSuppose that there is no m m N make 1 - e < m(g J ). We will find a 4i 0i,mcontradiction. For any n and any a m A , we can find a pair of rational )n !1 2 e 1numbers, s and r , such that ____ < s < r < ____ and m(V ) < _ . ___ , a a n+1 a a n+1 a 4 a 4 4 2here V = {x m X : s < d(a,x) < r }. Notice that the way to find s and r a a a "a a -a ,2 .4are constructive. Let k m N be larger than _____ . Consider some sequence of .e "1 2rationals such that ____ < u < u < ... < u < ____ . Select i n+1 0 1 3k n+1 !4 4some polynomials q for j , k - 1 such that 0 , q , 1 , q (x) = 1 for x j !j jsatisfies u , d(a,x) , u , q (x) = 0 for x satisfies d(a,x) , u or 3j+1 3j+2 j $3ju , d(a,x), and T q , 1. Since T m(q ) , 1, for some j, m(q ) < 3j+3 j j j j je 1_ . ___ holds. Then we let s = u and r = u .4 a a 3j+1 a 3j+2 2 Let p be the basic function . For s m S, let A = g s(n) a a a s Cn