REHMTN PERIODIC POINTS AND SUBSYSTEMS OF SECOND ORDER ARITHMETIC by Harvey Friedman* Stephen G. Simpson** Xiaokang Yu** Submitted: September 30, 1989 Revised: June 12, 1992 Abstract. We study the formalization within subsystems of second order ________arithmetic of theorems concerning periodic points in dynamical systems on thereal line. We show that Sharkovsky's theorem is provable in WKL . We show @0that, with an additional assumption, Sharkovsky's theorem is provable in RCA . L0We show that the existence for all n of n-fold iterates of continuous mappings M0of the closed unit interval into itself is equivalent to the disjunction of S M2 ~induction and weak Konig's lemma.________________________________________________________________* Research partially supported by NSF.** Research partially supported by NSF grant DMS-8701481..P.Q4 #1. Introduction and preliminaries. ______________________________ This paper is a contribution to Reverse Mathematics [9], a program offoundational research whose goal is to classify specific mathematical theoremsaccording to the axioms needed to prove them. In the work presented here, weattempt to determine which axioms in the language of second order arithmeticare needed to prove Sharkovsky's Theorem [7] concerning periodic points indynamical systems on a closed bounded interval of the real line. We do notcompletely reach our goal, but we uncover some novel phenomena. This researchis therefore presented as an interesting but nondefinitive case study. The reader of this paper will require some knowledge of the techniques bywhich ordinary mathematics is formalized in subsystems of second orderarithmetic. General information of this kind can be found in [8], [10], [2],[4], and [11]. In particular, we assume familiarity with RCA and WKL , two =0 0of the systems which are most used in Reverse Mathematics. RCA is the ?0 +0 0subsystem of second order arithmetic with D comprehension and S induction. +1 1 !~WKL consists of RCA plus weak Konig's lemma, i.e. the axiom that every 0 0 <N <Ninfinite subtree of 2 has a path. Here 2 is the tree of all finitesequences of 0's and 1's. For the reader's convenience, we shall now summarize some of the basicdefinitions concerning complete separable metric spaces and continuousfunctions, which are used in RCA and WKL . 0 0 L^ 1.1 Definition (RCA ). A (code for a) complete separable metric space A __________ 0is defined to be a pair (A,d) where A is a nonempty countable set and d: A x A-3 R is a pseudometric, i.e. it satisfies d(a,a) = 0, d(a,b) = d(b,a) , 0, and 3^d(a,b) + d(b,c) , d(a,c). A (code for a) point of A is defined to be a 4-nsequence ;a : n m N:, a m A, such that d(a ,a ) , 2 for all m, n m N with n n m n =^m , n. If x = ;a : n m N: and y = ;b : n m N: are points of A, we set d(x,y) n n= lim d(a ,b ), and we define x = y to mean that d(x,y) = 0. The basic open n n n ^neighborhoods of A are the open balls B(a,r) where a m A, r m Q, r > 0. Hereby definition x m B(a,r) if and only if d(x,a) < r. In this paper, the most important examples of complete separable metricspaces are (i) the real line R, and (ii) its closed bounded intervals [x,y] ;^where x, y m R, x , y. We can make the identification R = Q where Q is theset of rational numbers with the pseudometric d(a,b) = |a - b|. Also :Nimportant are the complete separable metric spaces (iii) 2 of all functions L<Nfrom N into 2 = {0,1}, known as Cantor space, with the countable dense set 2 |f(i)-g(i)| Nand the pseudometric d(f,g) = T ___________ , and (iv) N of all functions $i i 2 C<Nfrom N into N, known as Baire space, with the countable dense set N and the |f(i) - g(i)| 1pseudometric d(f,g) = T _________________.____ . ,i i 1 + |f(i) - g(i)| 2 '^ A complete separable metric space A is called compact if there exists asequence of finite sequences ;;a : i , k :: n m N:, a m A, such that for ni n ni >-nall n m N and b m A there exists i , k such that d(a ,b) < 2 . Thus we can &n niprove within RCA that the closed bounded interval [x,y] and the Cantor space 0 N2 are compact. Within WKL , we can prove that compact metric spaces have the 0 4^Heine-Borel covering property, i.e. any covering of A by a countable sequenceof basic open neighborhoods has a finite subcovering. Indeed, the Heine-Borel D~property for compact metric spaces is equivalent over RCA to weak Konig's 90lemma (see [1], [2], [11]). ^ ^ 1.2 Definition (RCA ). If A and B are complete separable metric spaces, __________ 0 &^ ^a (code for a) continuous function F: A -3 B is defined to be a set ofquintuples $+ + F { N x A x Q x B x Q 5+which is required to have certain properties. Here Q is the set of positiverational numbers. We write (a,r)F(b,s) as an abbreviation for ]n ((n,a,r,b,s)m F). Intuitively, (a,r)F(b,s) is a neighborhood condition, i.e. a piece ofinformation to the effect that F carries B(a,r) into B(b,s). We use thenotation (a',r') < (a,r) for the inequality d(a,a') + r' < r. The propertiesof F which we require are: 1. If (a,r)F(b,s) and (a,r)F(bs,ss), then d(b,bs) , s + ss. 2. If (a,r)F(b,s) and (as,rs) < (a,r), then (as,rs)F(b,s). 3. If (a,r)F(b,s) and (b,s) < (bs,ss), then (a,r)F(bs,ss). ^ 4. For all x m A and e > 0, there exist (a,r)F(b,s) such that d(x,a) < r and s < e. ^ ^ ^ ^ Given F: A -3 B as above and x m A, let F(x) be the unique y m B (up to ^equality in B as defined above) such that d(y,b) , s for all (a,r)F(b,s) withd(x,a) < r. Using property 4, we can prove within RCA that F(x) is well 60 +^ ^defined. Two continuous functions F , F : A -3 B are said to be equal if $1 2 ^F (x) = F (x) for all x m A. 1 2 $^ ^ Given a continuous function F: A -3 B as above, a modulus of uniform C^continuity for F is a function h: N -3 N such that, for all x, y m A, d(x,y) , -h(n) -n2 implies d(F(x),F(y)) < 2 . Using the Heine-Borel property, we can ^ #^ ^prove in WKL for compact A that every continuous function F: A -3 B has a 0modulus of uniform continuity. (See Lemma 2.6 below.) !^ A (code for) an open set in A is any set of triples (+ U { N x A x Q .We write x m U if and only if ]n ]a ]r ((n,a,r) m U c d(x,a) < r). Thus the 0 20formula x m U is S . Conversely, we can prove in RCA that for any S formula 1 "0 1 "^ ^f(x) there exists an open set U { A consisting of all x m A such that f(x) '^ "^holds, provided f(x) is extensional on A in the sense that for all x, y m A,f(x) and x = y imply f(y). (See #II.5 of [11].).P #2. Proof of Sharkovsky's Theorem in WKL . -0 _____________________________________ For our purposes, a dynamical system is a continuous function F: X -3 X,where X is a complete separable metric space. In dynamical systems theory,one studies the behavior of sequences of points obtained by iteration: 2 n x, F(x), F (x), ..., F (x), ... , nwhere x m X and F (x) = FF...F(x) for all n m N. Dynamical systems theory in ^-(--& nthe context of subsystems of second order arithmetic has been considered in[1]. :n m A point x m X is said to be periodic of period n if F (x) = x and F (x) =x for all m, 1 , m < n. Let ST3 be the following statement, due toSharkovsky. For any dynamical system F: R -3 R on the real line, if thereexists a point of period 3, then there exist points of period n for all n , 1,n m N. Our investigations here center on the problem of which axioms ofsecond order arithmetic are needed to prove ST3. We do not completely solvethis problem. In reality, ST3 is only a special case of the much more comprehensivetheorem which Sharkovsky actually proved [7], [5], [3]. (The subsequentrediscovery of this special case by Li and Yorke [6] was the impetus for ourwork here.) Define the Sharkovsky ordering to be the following ordering ofthe positive integers: "2 2 3, 5, ..., 2.3, 2.5, ..., 2 .3, 2 .5, ..., ..., 4, 2, 1 .The full theorem of Sharkovsky [7] says that m precedes n in the Sharkovskyordering if and only if every continuous F: R -3 R with points of period m haspoints of period n. Our results below concerning ST3 can be generalized so as to apply to thefull theorem of Sharkovsky. The proofs require essentially no additionalideas beyond Sharkovsky's combinatorial technique. (For an exposition ofSharkovsky's proof, see [3] or [5].) With this understanding, we shallconcentrate on ST3. We shall now prove a sequence of lemmas leading to the theorem that ST3 isprovable in WKL . 0 2.1 Lemma (RCA ). Let  0 1 k k+1 nc or b < c , where c = (a + b )/2. Then x = ;a : k m N: = ;b : k m N: k n k k n n n n k k k k= ;c : k m N: is easily seen to be a real number with the desired property. k The following lemma is an RCA version of the Intermediate Value Theorem "0(see also Chapter II of [11]). 2.2 Lemma (RCA ). If F: [x,y] -3 R is continuous and F(x) < 0 < F(y), _____ 0then there exists z m [x,y] such that F(z) = 0. Proof. We imitate the standard bisection argument. If there exists arational number c m [x,y] with F(c) = 0, then we can take z = c. Otherwise,we define rational numbers a and b , n m N, as follows. First, use n ncontinuity to find rational a and b such that x < a < b < y and F(a ) < 0 0 0 0 0 0< F(b ). Given a and b , we have F(c ) = 0, c = (a + b )/2, so let 0 n n n n n n(a ,b ) = (a ,c ) if F(c ) > 0, (c ,b ) if F(c ) < 0. Thus a , a , n+1 n+1 n n n n n n n n+1b , b , F(a ) < 0 < F(b ) for all n, and lim |a - b | = 0. By Lemma 2.1, n+1 n n n n n nthere is a (unique) real number z such that a , z , b for all n. Thus z = -n nlim a = lim b , and an argument from continuity shows that F(z) = 0. n n n n 2.3 Lemma (RCA ). If F: [0,1] -3 R is continuous and F[0,1] } [0,1], _____ 0then there exists x m [0,1] such that F(x) = x. Proof. Let x , x m [0,1] be such that F(x ) = 0 and F(x ) = 1. Setting 0 1 0 1G(x) = F(x) - x, we have G(x ) , 0 , G(x ) so by Lemma 2.2 there exists x m 0 1[x ,x ] such that G(x) = 0. 0 1 2.4 Lemma (RCA ). If U and V are nonempty open sets in R with U < V _____ 0(i.e. x < y for all x m U and y m V), then U < z < V for some z m R. Proof. We claim that there exist sequences of rational numbers a m U, Fnb m V, with a < a , b < b for all n m N, with the following property: n n n+1 n+1 nfor all x m U (respectively y m V), there exists n such that x < a Bn(respectively b < y). Assuming the claim, note that a < b for all n, since n 'n nU < V. Apply Lemma 2.1 to obtain z m R such that a , z , b for all n. It 3n nis then clear that U < z < V. /0 To prove the claim, note that there is a S formula f(b) saying that b m /1Q and b m V (using the code of V as a parameter). By Lemma 2.1 of [8] (seealso Lemma II.3.7 of [11]), there exists a function f: N -3 Q such that forall b m Q, f(b) holds if and only if ]i (f(i) = b). Define b = f(0) and b =0 n+1= f(i) for the least i such that f(i) < b and f(i) < f(n). Then ;b : n m N: )n nhas the desired property with respect to V. Similarly we can obtain ;a : n m GnN: having the desired property with respect to U. This completes the proof. We do not know whether the following lemma is provable in RCA . B0 2.5 Lemma (WKL ). If F: [a,b] -3 R is continuous and F[a,b] } [0,1], _____ 0then there exist x, y m [a,b] such that F[x,y] = [0,1]. We can also arrangeto have either F(x) = 0 and F(y) = 1, or F(x) = 1 and F(y) = 0. Proof. Assume F(a) , 0 and F(b) , 1. (It is easy to reduce the proof tothis case.) We claim that there is an open set U { [a,b] consisting of all x m [a,b]such that(1) ]y (x < y , b c F(y) < 0) .This is in fact provable in RCA . To see this, note that (1) is equivalent to 0 0a S formula, since by continuity we may restrict attention to rational 1numbers y in the interval [a,b]. The existence of U now follows by the remark )0at the end of #1 concerning extensional S formulas. )1 We claim that there is an open set V { [a,b] consisting of all x m [a,b]such that(2) [y (x , y , b -3 F(y) > 0) .To see this, note that by continuity plus the Heine-Borel covering property,(2) is equivalent to the existence of a finite set of neighborhood conditions(a ,r )F(b ,s ), i , n, such that [x,b] is covered by the basic open i i i ineighborhoods B(a ,r ), i , n, and B(b ,s ) > 0 for all i , n. Thus (2) is i i i i 0equivalent to a S formula and hence defines an open set. 1 Clearly U < V, so by Lemma 2.4 there exists z such that U < z < V. (If Uis empty, we may take z = a.) Since z n U, we have F(y) , 0 for all y m [z,b].Since z n V, there is x with z , x , b and F(x ) , 0. In particular F(x ) = 0 0 0 00 and F(y) , 0 for all y m [x ,b]. We can now replace [a,b] by [x ,b]. 0 $0 By an argument like the preceeding one, we can find x m [x ,b] such that :1 0F(x ) = 1 and F(y) , 1 for all y m [x ,x ]. It now follows by Lemma 2.2 that 1 !0 1F[x ,x ] = [0,1]. This completes the proof of Lemma 2.5. 0 1 ^ ^ 2.6 Lemma (WKL ). Let A and B be complete separable metric spaces and _____ 0 ^ ^ ^let F: A -3 B be a continuous function. If A is compact, then F has a modulusof uniform continuity. Proof. We first note that property 4 of Definition 1.2 can be &^strengthened as follows. For all x m A and all e > 0, there exists aneighborhood condition (a,r)F(b,s) such that d(x,a) < r/2 and s < e. To seethis, let (as,rs)F(b,s) be a neighborhood condition such that d(x,as) < rs ands < e. Let B(a,r) be a basic open neighborhood such that d(x,a) < r/2 and3r/2 < rs - d(x,as). Then (a,r) < (as,rs), and hence (a,r)F(b,s). Now, given n m N, by the Heine-Borel covering property we can effectively D-n-1find a finite set of neighborhood conditions (a ,r )F(b ,s ), s < 2 , i , /i i i i ik, such that X is covered by the basic open neighborhoods B(a ,r /2), i , k. =i i 3-h(n)(See Lemma 5.8 of [1].) Let h(n) m N be such that 2 < min r /2, i , k. @i ^ -h(n)If x, y m A and d(x,y) , 2 , then we have x m B(a ,r /2) for some i , k, 5i i K-nhence x, y m B(a ,r ), so F(x), F(y) m B(b ,s ), and hence d(F(x),F(y)) < 2 . i i i iThus h: N -3 N is our modulus of uniform continuity. With the above lemmas in hand, we are now ready to look at dynamicalsystems on the real line. In studying a particular dynamical system F: X -3 FnX, it is very helpful, indeed essential, to know that the iterations F : X -3X are defined and make sense for all n m N. Unfortunately, this knowledge isnot automatic in subsystems of second order arithmetic with restrictedinduction, such as RCA , because in such systems it may be nontrivial to prove 0 nproperties of F by induction on n. For continuous F, the whole matter isanalyzed completely in #4 below. If F is assumed to have a modulus of uniformcontinuity, our question is answered by the following lemma. 2.7 Lemma (RCA ). Let X be a complete separable metric space and let _____ 0F: X -3 X be a continuous function. If F has a modulus of uniform continuity, 'n 0then there exist continuous functions F : X -3 X, n m N, defined by F (x) = x, n+1 nF (x) = F(F (x)) for all x m X and n m N. Proof. Let hs: N -3 N be a modulus of uniform continuity for F, anddefine h: N -3 N by h(n) = hs(n+1). We claim that the code of F can bereplaced by another code Fs for the same continuous function, with thefollowing property (*): for all n m N and basic open neighborhoods B(a,r) with -h(n)r < 2 , there exists a neighborhood condition (a,r)Fs(b,s) such that s < -n2 . Namely, let Fs be such that (a,r)Fs(b,s) holds if and only if thereexist n m N and a neighborhood condition (as,rs)F(bs,ss) such that d(a,as) < -h(n) -n-1 -n-1rs and r < 2 and ss < 2 and (bs,ss+2 ) < (b,s). It isstraightforward to check that x m B(a,r) and (a,r)Fs(b,s) imply F(x) m B(b,s).Using this, it is easy to see that (*) holds and that F and Fs are codes forthe same continuous function. n n For all n m N, define F so that (a,r)F (b,s) holds if and only if thereexist neighborhood conditions (a ,r )Fs(a ,r ), (a ,r )Fs(a ,r ), ..., 0 0 1 1 1 1 2 2(a ,r )Fs(a ,r ) with (a ,r ) = (a,r) and (a ,r ) = (b,s). n-1 n-1 n n 0 0 n n n It is clear that F has properties 1, 2 and 3 of Definition 1.2. Inorder to prove property 4, we first use primitive recursion in RCA (see #2 of B0 3. We firstpresent the informal argument and then indicate the additional considerationswhich are needed for our formalization within WKL . 10 Fix n > 3. Informally, we define a sequence of closed bounded intervals A } A } ... } A . 1 2 nStart with A = J. Then FA } I g J so by Lemma 2.5 there exists A { A with 1 1 '2 1 2 62FA = J. Then F A } I g J so by Lemma 2.5 there exists A { A with F A = 2 2 '3 2 3 n-2J. .... Then F A } I g J so by Lemma 2.5 there exists A { A with n-2 'n-1 n-2 n-2 n-1F A = J. Then F A } I g J so by Lemma 2.5 there exists A { A n-1 n-1 'n n-1 n-1 nwith F A = I. Then F A } J } A so by Lemma 2.3 let x m A be such that n n n n nF (x) = x. Clearly 2 n-2 x, F(x), F (x), ..., F (x) m J n-1 mwhile F (x) m I, so F (x) = x for 1 , m < n. Thus x is our point of periodn. This ends the informal argument. In order to formalize the above argument within WKL , we first need to 80 *2 nprove within WKL that the iterations F, F , ..., F : R -3 R are continuous 0and defined for all x m R. This is given by Lemmas 2.6 and 2.7 applied toclosed bounded intervals in R. The other major difficulty within WKL is to carry out the recursive *0construction of A , A , ..., A , keeping in mind that the axioms of WKL 2 3 n-1 (0 0include induction only for T formulas. To overcome this difficulty, we use 1Lemma 2.8 plus the endpoint information in Lemma 2.5. The details are asfollows. Let f(k,X,Y) be a formula saying that X and Y are (codes for) closed 0k-1 k-1intervals A , A such that A { A { J and F A = J and F {endpoints k-1 k k k-1 k )k-1 0of A } = {endpoints of J} . The clause F A = J is not P as it stands. k (k 1 Ek-1However, the other clauses plus continuity and Lemma 2.2 imply that F A = J Ik 0is equivalent to a P clause, namely 1 .k-1 [ r m Q (r m interior of A -3 F (r) m J) . &k "0Thus f(k,X,Y) is equivalent to a P formula, and we can apply Lemma 2.8 to "1obtain the sequence of closed intervals ;A : 1 < k < n:. The needed *k 50properties of these intervals can then be proved by P induction, which is 51 0equivalent to S induction and hence available in WKL . The inductive step is 1 %0provided by Lemmas 2.2 and 2.5. This completes the proof..P #3. An RCA version of Sharkovsky's Theorem. 0 _______________________________________ In this section, we will concentrate on the case that the functions arecontinuous with modulus of uniform contiuity. We show that, in this case, ST3can be proved in RCA instead of WKL . 0 0 3.1 Lemma (RCA ): If F: [a, b] -3 R is continuous with a modulus of _____ 0uniform continuity and F(a) , c < d , F(b), then there are (rationals)c', d' m [a, b] such that c' < d', F(d') < d, and there is e > 0 such thatF(x) > c + e for all x m [c', b]. Proof: Let e > 0 be such that c + 3e < d. As in the proof of lemma 2.5,we have an open set U h [a, b] consisting of all x m [a, b] such that ]y (x < y , b c F(y) < c + 2e). &0Let V be the open set defined by the T formula which says that there exists a &1finite set of neighborhood conditions (a , r )F(b , s ), i , n, such that (i i i i is an open cover of [x, b], b > d and s < e for i , n. i i 'i iNote that for x m [a, b], x m V implies that [y (x , y , b -3 F(y) > d - e).Therefore U < V. On the other hand, because F has a modulus of uniformcontinuity, if [y (x , y , b -3 F(y) , d), then x m V. Therefore, if we letc' m [a, b] such that U < c' < V, then there is d' > c' such that F(d') < d.Also, F(x) , c + 2e > c + e for all x m [c', b]. For closed intervals [u,v] and [s,t], we write [u,v] i [s,t] to mean that 8intu < s < t < v. 3.2 Lemma (RCA ): If F: [a, b] -3 R is continuous with a modulus of _____ 0uniform continuity and F[a, b] i [u, v] i [s, t], then there are *int(rationals) u', s', t', v' such that a < u' < s' < t' < v' < b and[s, t] h F[s', t'] h F[u', v'] h (u + e, v - e) for some e > 0. intIt can be arranged to have min{F(s'), F(t')} < s < t < max{F(s'), F(t')}. Proof: This lemmma is a modified form of lemma 2.5, proved in RCA instead E0of WKL . In lemma 2.5, we were looking for one subinterval of the domain which 0has the precise image we want. In this lemma, we start from two intervalsinstead of one. The image we want is "sandwiched" between them. In turn, weare looking for two subintervals in the domain whose images are estimates ofwhat we want. Assume F(a) , u and F(b) , v. From lemma 3.1, as F(a) , u < s < F(b),there are u', s' m [a, b] such that a < u' < s' < b, F(s') < s and there ise > 0 such that F(x) > u + e for x m [u', b]. Apply lemma 3.1 again on 1 1[s', b]. As F(b) , v > t > F(s'), there are v', t' m [s', b] such that b > v'> t' > s', F(t') > t, and there is e > 0 such that, F(x) < v - e for x m $2 2[s', v']. We can let u' be close enough to s' such that F(x) < s for x m[u', s']. Let e = min(e , e ). We have F(s') < s < t < F(t') and F[u', v'] 1 2h (u + e, v - e). This completes the proof. 3.3 Theorem (RCA ): ST3 holds for functions with modulus of uniform _______ 0continuity. Proof: Suppose F is a function with a modulus of uniform continuity and Fhas a point of period 3. The proofs for points of periods 1 and 2 are easy.Now let n m N be a number greater than 1. We want to prove that F has a pointof period n + 2. We can assume that there are a < b < c such that F(a) = b, 2 3F (a) = F(b) = c, and F (a) = F(c) = a. The idea of proving the theorem without weak Konig's lemma is tofind a sequence of descending intervals such that [b, c] h *k kF (A ) h (b*, %) for 1 , k , n, where b* is slightly less than b. We then k n+1find A* h A such that F (A*) jumps to the left side of b*. We also require n n+2 &n+2 kthat A* h F (A*). If z m A* is a fixed point of F , note that F (z) > b* n+1for 1 , k , n but F (z) < b*, then z must be a point of period n + 2 forthe function. To show this in RCA , we first have to choose b* m (a, b). Note that 0 2F(b) = c > b and F (b) < b. If b* is chosen being close enough to b, we can 2easily have both F(b*) > b and F (b*) < b*. 8+ For the first intervals, we want A = [s , t ] h A = [u , v ] such that &1 1 1 1 1 1 !+[b, c] h (F(t ), c] h F(A ) h F(A ) h (b* + d, %) for some d > 0. Let s = b. 1 1 1 &1Apply lemma 3.1 on [b, F(b*)]. Since F(b) > b > b* > F(F(b*)), there are t , J1v m [b, F(b*)] such that t < v , F(t ) < b and there is d > 0 such that 1 1 1 1F(x) > b* + d for all x m [b, v ]. It is obvious that [b, c] h (F(t ), c] h 1 $1F(A ). Noticing that F(b) = c, we choose u m (F(t ), b) which is close enough 1 &1 1to b such that F[u , v ] will not fall below b* + d. 1 1 Let f(m) be the following statement for m , 2 : There is a sequence ofquadruples of rationals <: 2 , k , m> such that for 2 , k , m, k k k k (i) s < u < s < t < v < t ; k-1 k k k k k-1 (ii) min{F(s ), F(t )} < s < t < max{F(s ), F(t )}; and k k k-1 k-1 k k (iii) there is e > 0 such that F[u , v ] h (u + e, v - e). &k k k-1 k-1 %0 It is easy to see that f(m) is a T formula since F has a modulus. If %1f(m) holds, or m = 1, we have min{F(s ), F(t )} < u < s < t < v < &m m m m m mmax{F(s ), F(t )}. From lemma 3.2, we can add in for the m m(m + 1)th quadruple which satisfies s < u < s < t < v < t , min{F(s), F(t)} %m m< s < t < max{F(s), F(t)}, and F[u, v] is included in an open interval m m ;0whose end-points are in (u , v ). Thus f(m+1) holds. By T induction, f(n) m m 1holds for all n m N. + Let A = [s ,t ] h A = [u , v ] for k , n. It is obvious that A h A k k k k k k #n k )k-1 k k +for 1 , k , n. For any k = 2, ..., n, F (A ) h F (A ) h F (A ) h .k-1 k k k-1 + $+ +F (A ) holds because A h F(A ) h F(A ) h A . We first claim that k-1 k-1 k k k-1 n 0 &k[b, c] h F (A ). By using T induction on the statement "b m Int F (A )" for n 1 )k #n 01 , k , n, we can prove that b m F (A ). Similarly, by using T induction on &n 1 k-1 ,n-1"b m Int F (A )" for 2 , k , n, we can prove that b m F (A ), and k .n n k +therefore c m F (A ). We secondly claim that F (A ) h (b*, %) for 1 , k , n. n k 0It can be proved by T induction because the statement that "there is e > 0 1 k + 0such that F (A ) h (b* + e, %)" is T as F has a modulus of uniform k 1continuity. Now we find a* m (a, b*) such that F(a*) = t . The existence follows 21from the fact that F(a) = b < t < F(b*). Since [a, b*] h F[b, c] h 1 n+1 'n+1F (A ), using lemma 3.1 on the function F , a function with a modulus, n 3n+1we can find an interval A* h A for the function F such that [a, a*] h n n+1F (A*) h (-%, b*). Since A* h A = [s , t ] = [b, F(a*)] h F[a, a*], we "1 1 1 n+2must have A* h F (A*). Follows from lemma 2.3 that there is some z m A* n+2 kwhich is a fixed point for F . For k , n, as z m A , F (z) > b*, but 6k n+1F (z) < b*. Therefore, z is a point of period n + 2 for the function F.This completes the proof..P #4. A strange disjunction. _____________________ Given a dynamical system F: X -3 X where X is a complete separablemetric space, what axioms of second order arithmetic are needed to prove that nF (x) is defined for all x m X and n m N? The question is natural since, inthe absense of this condition, the concepts of dynamical systems theory do notmake much sense. I0 We show here that, for arbitrary complete separable metric spaces, S I2induction is necessary and sufficient. For compact metric spaces, we show 0 ~that the disjunction of S induction and weak Konig's lemma is necessary and 2sufficient. 0 0 4.1 Lemma (RCA ). S induction is equivalent to P induction. _____ 0 2 2 0 0 Proof. We prove that S induction implies P induction. (The proof of 2 2 *0the converse is similar.) Let f(n) be a P formula and assume f(0) and *2[i(f(i)-3f(i+1)). If there exists n such that f(n) does not hold, fix such an I0n and write v(i) = (i , n -3 ~ f(n - i)). Then v(i) is equivalent to a S I2 70formula. We have v(0) and [i(v(i)-3v(i+1)), hence by S induction v(n), i.e. 72~ f(0), a contradiction. 0 4.2 Lemma (RCA ). S induction implies the following. For all n m N and _____ 0 2all complete separable metric spaces X and continuous functions F from X into nX, F is a continuous function from X into X. 0 ,0 Proof. Assume S induction. By the previous lemma we have P induction. 2 ,2 n %nThe code of F is defined in such a way that (a,r)F (b,s) holds if and only ifthere exist neighborhood conditions (a ,r )F(a ,r ), ..., (a ,r )F(a ,r ) &0 0 1 1 n-1 n-1 n nsuch that (a,r) = (a ,r ) and (a ,r ) = (b,s). The only difficulty is in 0 0 n n n :nshowing that F (x) is defined for all x m X. For fixed x, we know that F (x)is defined if and only if for all rational e > 0 there exists a neighborhood n -0condition (a,r)F (b,s) such that d(a,x) < r and s < e. This P assertion is >2 0easily proved by P induction on n m N. 2 4.3 Theorem (RCA ). The following are equivalent: _______ 0 0 1. S induction. 2 2. For all k m N and all complete separable metric spaces X and 'kcontinuous functions F from X into X, F is a continuous function from X intoX. <N N k 3. For all k m N and all continuous functions F from N into N , F is a N N Ncontinuous function from N into N . (Here N is the Baire space.) Proof. By Lemmas 4.1 and 4.2, it suffices to prove that statement 3 0 0implies P induction. Let f(k) be a P formula and assume f(0) and 2 2 ;0[k(f(k)-3f(k+1)). Write f(k) = [m ]n u(k,m,n) where u is S . Put g (0) = 0 ;0 0 6Nand g (m+1) = least n such that u(0,m,n). Then g m N in view of f(0). We 0 +0 )N N Nnow define a continuous function F from N into N . Given g m N , define F(g) Nm N as follows. First, put k = g(0) and F(g)(0) = k+1. Next, given m m N,let j be the least that u(k+1,m,j) d ~ u(k,j,g(j+1)). Such a j must exist inview of f(k+1) d ~ f(k). If u(k+1,m,j) holds, put F(g)(m+1) = j. Otherwiseput F(g)(m+1) = 0. This completes the definition of F. It is straightforward 0N Nto verify that F is a continuous function from N into N . Applying statement k N3, we see that for all k, g = F (g ) exists and g m N . We now claim that, k 0 kfor all k, g (0) = k and [m (g (m+1) = the least n such that u(k,m,n)). This k k 0 0 0P claim is easily proved by P induction. (Note that P induction is 1 1 1 (0provable in RCA since it follows from S induction, as in Lemma 4.1.) From 0 1the claim, we have [k [m ]n u(k,m,n), i.e. [k f(k). Our theorem is nowproved. ~ 4.4 Lemma (RCA ). Weak Konig's lemma is equivalent to the assertion that _____ 0 N N N2 is not homeomorphic to N . (Here 2 is the Cantor space.) ~ N N Proof. Under weak Konig's lemma, 2 is not homeomorphic to N , becausethe former has the Heine-Borel covering property while the latter does not. ~ <NAssume now that weak Konig's lemma fails. Let T { 2 be an infinite tree 1~ <Nwith no infinite path. As in #IV.1 of [11], let T be the set of t m 2 such 6Nthat t n T c [s(s h t -3 s m T). Then for every g m 2 there exists a unique = "~ Nn m N such that ;g(0),...,g(n): m T. Given g m 2 , define an increasingsequence n < n < ... < n < ... 0 1 iwhere n = -1 and n = the least n > n such that 0 i+1 i ~;g(n +1),g(n +2),...,g(n): m T. Putting i i F(g) = ;;g(n +1),g(n +2),...,g(n ): : i m N : i i i+1 ~Nwe see that F(g) m T . It is straightforward to verify that F is a N ~N ~ ~Nhomeomorphism of 2 onto T . Moreover, since T is infinite, T is N N Nhomeomorphic to N . Hence 2 is homeomorphic to N . This completes theproof. 4.5 Theorem (RCA ). The following are equivalent: _______ 0 0 ~ 1. The disjunction of S induction and weak Konig's lemma. 2 2. For all k m N and all compact metric spaces X and continuous kfunctions F from X into X, F is a continuous function from X into X. ;N 3. Same as 2 restricted to the compact metric space 2 . 4. Same as 2 restricted to the compact metric space [0,1]. Proof. By Lemmas 4.2, 2.6 and 2.7 we see that 1 implies 2. Trivially 2 30implies 3 and 4. Suppose now that 1 fails. Then S induction fails. Hence, 32 0N Nby Lemma 4.3, we have a continuous function F: N -3 N such that, for some k, k $N N ~F is not a continuous function from N to N . Moreover, weak Konig's lemma 3N Nfails, so by Lemma 4.4 we have a homeomorphism F: 2 -3 N . Putting G = -1 (N N kF .F.F, we have a continuous function G: 2 -3 2 such that G is not a N Ncontinuous function from 2 into 2 . Thus 3 fails, and hence trivially 2 4Nfails. Let us make the standard identification of 2 with the Cantor middlethird set C { [0,1]. It is straightforward to extend G: C -3 C to acontinuous function H: [0,1] -3 [0,1]. Thus 4 fails. This completes theproof..P.Q3 References __________ [1] A. Blass, J. L. Hirst, and S. G. Simpson, Logical analysis of sometheorems of combinatorics and topological dynamics, in Logic andCombinatorics, Contemporary Mathematics, vol. 65, American MathematicalSociety, 1987, pp. 125-156. [2] D. K. Brown and S. G. Simpson, Which set existence axioms are needed toprove the separable Hahn-Banach Theorem?, Annals of Pure and Applied Logic,31, 1986, pp. 123-144. [3] R. L. Devaney, An Introduction to Chaotic Dynamical Systems,Addison-Wesley, Menlo Park, 1985. [4] H. Friedman, S. G. Simpson, and R. L. Smith, Countable algebra and setexistence axioms, Annals of Pure and Applied Logic, 25, 1983, pp. 141-181;Addendum, 28, 1985, pp. 320-321. [5] C.-W. Ho and C. Morris, A graph theoretic proof of Sharkovsky's theoremon the periodic points of continuous functions, Pacific Journal ofMathematics, 96, 1981, pp. 361-370. [6] T.-Y. Li and J. A. Yorke, Period three implies chaos, AmericanMathematical Monthly, 82, 1975, pp. 985-992. [7] A. N. Sharkovsky, Co-existence of the cycles of a continuous mapping ofthe line into itself, Ukranian Math. Z., 16, 1964, pp. 61-71 (in Russian). [8] S. G. Simpson, Which set existence axioms are needed to prove theCauchy/Peano theorem of ordinary differential equations?, Journal of SymbolicLogic, 49, 1984, pp. 783-802. [9] S. G. Simpson, Subsystems of Z and Reverse Mathematics, appendix to: %2Proof Theory (second edition), by G. Takeuti, North-Holland, Amsterdam, 1986,pp. 434-448. [10] S. G. Simpson, Partial realizations of Hilbert's Program, Journal ofSymbolic Logic, 53, 1988, pp. 349-363. [11] S. G. Simpson, Subsystems of Second Order Arithmetic, in preparation..PAddresses of authors:Harvey FriedmanDepartment of MathematicsOhio State UniversityColumbus, Ohio 43210Stephen G. SimpsonDepartment of MathematicsPennsylvania State UniversityUniversity Park, PA 16802simpson@math.psu.eduXiaokang YuDepartment of MathematicsPennsylvania State UniversityAltoona CampusAltoona, PA 16601xky@psuvm.psu.edu