Generalizations to the Converse of Contraction Mapping Principle Citation Wong, James Sai Wing (1965) Generalizations to the Converse of Contraction Mapping Principle. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/DYFP-7769. https://resolver.caltech.edu/CaltechETD:etd-02102004-095235 Abstract Let X be a non-empty abstract set and S be a commutative semi-group of operators defined on X into itself. S is called a contractive semi-group on X if there exists a metric ρ on X such that for each TεS, T≠I, ρ(Tx,Ty)≤λ(T)ρ(x,y) for all x, yεX, where 0≤λ(T)<1. We find sufficient conditions on S in order that S be contractive on X. In the case when S is generated by a finite number of mutually commuting mappings T 1 , T 2 ..., T n , possessing a common unique fixed point in X, these conditions are automatically satisfied. The resulting statement is the following generalization of the converse of contraction mapping principle: Theorem C . Let X be an abstract set with n mutually commuting mappings T 1 , T 2 ..., T n defined on X into itself such that each iteration T 1 k 1 , T 2 ..., T n k n ( where k 1 , k 2 , ..., k n are non-negative integers not all equal to zero) possesses a unique fixed point which is common to every choice of k 1 , k 2 , ..., k n . Then for each λε(0,1), there exists a complete metric ρ on X such that ρ(T i x,T i y)≤λρ(x,y) for 1≤i≤n, and for all x,yεX. This result reduces to that of C. Bessaga by taking n = 1. ( Rf: C. Bessaga, Colloquim Mathematicum VII (1959), 41-43.). Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics) ; contraction mapping principle Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Awards: Caltech Distinguished Alumni Award, 2014 Thesis Availability: Public (worldwide access) Research Advisor(s): Bohnenblust, Henri Frederic Group: Caltech Distinguished Alumni Award Thesis Committee: Unknown, Unknown Defense Date: 1 May 1964 Record Number: CaltechETD:etd-02102004-095235 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-02102004-095235 DOI: 10.7907/DYFP-7769 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 588 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 13 Feb 2004 Last Modified: 10 Feb 2024 00:08 Thesis Files Preview PDF (Wong_jsw_1965.pdf) - Final Version See Usage Policy. 1MB Repository Staff Only: item control page

Generalizations to the Converse of Contraction Mapping Principle Thesis by James Sai Wing Wong In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy California Institute of Technology Pasadena, California 1965 (Submitted May 1, 1964) ii Acknowledgements I wish to express my deep appreciation to Professor H, F. Bohnen- blust for his guidance and enlightenment, and for countless hours of patient discussion. T would also like to thank Professors W. A.J. Luxemburg and C. R. DePrima for the inspiration and training I receiv- ed from them. Finally, I thank my wife, Madeline, for her continuing encouragement and sacrifice. iii Abstract Let X be a non-empty abstract set and J be a commutative semi-group of operators defined on X into itself. SO is called a contractive semi-group on X if there exists a metric P on X such that for each T eg ,T#I, p(Tx,Ty) €< rx(T) p{x,y) for all x, y €X, where 0€ A(T)< 1. We find sufficient conditions on Ps) in order that o be contractive on X. In the case when P is ge- nerated by a finite number of mutually commuting mappings T,, T 1' "2" eee Tae possessing a common unique fixed point in X, these con- ditions are automatically satisfied. The resulting statement is the following generalization of the converse of contraction mapping principle: Theorem C. Let X be an abstract set with n mutually commuting mappings Ty , To beeeee Th defined on X into itself such k k that each iteration T,4........ t "( where k,, k,,..., kK. are non- 1 n 1 2 n negative integers not all equal to zero) possesses a unique fixed point which is common to every choice of Ky 1 Ko pees, Ko Then for each dX € (0,1), there exists a complete metric P on X such that p(T,x, T.y) ¢ » P(x,y) for l¢ i€n, and forallx,yéX. This result reduces to that of C. Bessaga by taking n=1. ( Rf: C. Bessa- ga, Colloquim Mathematicum VII (1959), 41-43.) 0. INTRODUCTION We are here concerned with the classical fixed point theorem of Banach, commonly known as the contraction mapping principle, which states: TheoremA. (S. Banach| 1] ) Let T be a mapping of a complete metric space X into ilself. If for every pair of elements x, y «xX and some fixed A, 0€ A41, p(Tx, Ty) <d plx,y) (1) Then T has a unique fixed point, and the sequence of iterates {tr} for each x €X converge in metric to this unique fixed point. We call the mapping T satisfying (1) a contraction on X. TheoremA has been used extensively in proving the existence and uniqueness of solutions to various functional equations, particularly integral and differential equations ( Kolmogorov and Fomin [2] ). It has been app- lied to prove the convergence of successive approximations of solu- tions to ordinary differential equations ( Luxemburg [3] ) and integral equations in L,- spaces ( Willett [4] ), to prove the Frobenius-Perron theorem on positive matrices ( Samuelson [9] ), and to develop many otherwise difficult existence and uniqueness theorems in various function spaces ( Thampson [6] ). The contraction mapping principle has also been widely used by numerical analysts in the study of con- vergence and error estimates in well-known function spaces ( Schréder [7] ) . Various generalizations and localizations of Theorem A are | given which in one way or other relax the restrictions on the mapping T or the underlying complete metric space X ( Edelstein [2] , Rakotch [9] , Kammerer and Kasriel (10 ). These generalizations also find interesting applications in the study of functional equations ( Edwards [13] ). Moreover, the concept of contractions has been made mean- ingful in spaces more general than metric spaces, and the correspond- ing fixed point theorem is proved { Davis E 2| ). This thesis is an outgrowth of studies related to the converse of Theorem A. The natural converse statement is the following: " Let X be a complete metric space, and T be a mapping of X into itself such that for each xé€ X, the sequence of iterates {r°x} converges to a unique fixed point we X. Then there exists a complete metric on X in which T is a contraction. " This is in fact true, even ina stronger sense. The following converse of Theorem A was due to C. Bessaga. Theorem B. (C. Bessaga (a 3] ) Let X be an abstract set and T be a mapping of X into itself such that for each positive integer k70, the equation TX = x holds for some x Ximpliesx= , the unique fix ed point of T. Then for each x», 04 A<1, there exists a complete me- tric on X such that PP (Tx, Ty) § n p(x, y) foralix, y eX. ( A weaker form of Theorem B, in case X is a compact metrizable space, was also given by Janos [i 4) ). We are interested here in further generalizations of Theorem B. Speci- fically, we ask whether there exists a metric on X in which mutually . commuting mappings Th. Tos eeey Th with common unique fixed point are simultaneously contractions . Note that if Ty 1 Toe coer Th are contractions, then every element of the commutative semigroup & generated by qT ' Ty, eeey Th is again a contraction. Hence we ex- tend the concept of a contraction to the concept of a contractive semi- group. We obtain necessary and sufficient conditions for ¥ to be contractive in terms of the existence of certain level function on X, Sufficient conditions on 4 are also given for 3 to be contractive. In case Q is generated by a finite number of mutually commuting mappings with common unique fixed point, these conditions are auto- matically satisfied. The resulting statement is the following genera- lization of Theorem B. Theorem C. ( fa 5] ) Let X be an abstract set with n mutually commuting mappings T,, T,,...., T,, defined on X into itself such that k k L va eeee tT, where ky ' Kos wee kn are non-negative integers not all equal to zero) possesses a unique fixed point which each iteration T is common to every choice of k,, k pi Kae cees ko Then for each XE (0,1), there exists a complete metric f on X such that P (T,x, T.y) or Pp x,y) for 1<i¢n, and for all x,yeX. In section 1, we introduce basic nolalions and lerminoloyies whic are necessary for all later discussions. Section 2 introduces the concept of a contractive semi-group 8 , and presents a necessary and sufficient condition for R to be contractive. The main theorem is proved in section 3 where sufficient conditions are imposed on Ri to insure that it be contractive. This result is then applied in sec- tion 4 to prove Theorem C. Finally, we make several remarks which lead to questions for further research. References throughout this thesis are given by a number in brac- kets indicating a particular article or book in question. A complete list of references arranged in the order of appearance is given at the end of this thesis. We indicate the end of a proof by the abbreviated notation | | an l. DEFINITIONA AND NOTATIONS Let X be a non-empty abstract set and S be a commutative semi-group of operators on X into itself, containing the identity I. &’ is said to be contractive (completely contractive) semi-group on X if there exists a metric (complete metric) pon X such that for each S é B , £(Sx,Sy) ¢ a(S)p(x,y) for all x,y € X where 0 € A(S) < 1 for SAlIand \(I) =1. We say that Q is a uniformly contractive ( uniformly completely contractive) semi-group on X if there exists a real number \ such that A(S) < vn<1 forall S € P , SAI. Inall later discussions we say dX contractive, completely contractive, or respectively uniformly contractive for short. In order to aviod dealing with the trivial contractive semi-group b = { I } , we assume that & contains at least one other element T, T #1. xX € X is called an QD -invariant set if p xX, Sc x, . Obvious- ly X and the empty set © are 2 ~invariant sets. Consider the set [a } = P fa} ={x : x= Ta for some T ed \, Clearly d [ a] Cc [a 1 and hence [a] is an RS -invariant set. It is the smallest db -inva- riant set containing a. Note that arbitrary unions and intersections pre- serve the S -invariance. Similarly, b 1 Cc d is called an_ invariant set if Q D1 c dD, . An invariant set may be considered as an Q - invaraint set in ~ . Hence remarks on d -invariant sets hold simi- larly for invariant sets. A function X is called contractive on d if O<¢ A(S)<1 forall S <3, SAI, and »(I) =1. The function » is called uniformly contrac- tive on § , if there exists a \such that rA(S)< ~ <1 forall Sé¢ » , SAI. A function Pp is called a level function with respect to» if: (i) its domain of definition Y, is an oe - invariant set; (ii) O£ P(x)< 09 forallx e€ Y: (iii) P (Tx) ¢< Av (T) 8 (x) for all x e€Y, where >is contractive on ; (iv) p(x) = P (x,) = 0 implies x, = x, ; We call the function e a length function on P.) if it satisfies the con- ditions: (i) O< o(S)< 1 forS#Iand o({I) =1; (ii) o (ST) $ e(S) o(T) ; (iid o (S,) = ~(s,) = 0 implies Sy = S,. A length function on ~ is certainly contractive on ps and hence it may be regarded as level function on p: We adapt the following terminologies for arbitrary partially ordered sets. Let P be an arbitrary partially ordered set. Any two ele- ments x, y €P are called_comparable if either x¢y or y¢x holds, otherwise they are called non-comparable . By a_transverse set we mean a subset of P whose elements are pairwise mutually non-compa- rable. A subset J of P is called an ideal if xeP and xy for some ye J implies x€J. An ideal J is called principal if it is of the form { x: xéP,x »y } for some fixed element y € P and it is denoted by <y) . The element y is uniquely determined by J and is called the generator of the principal idealJ. ( Refer to G. Birkoff (a 6| for other termino- logies on partially ordered sets not explained here.) 2. CONTRACTIVE SEMI-GROUPS We first propose to prove a necessary and sufficient condition for s to be contractive. Theorem 1. If S is contractive on X, then there exists a level function on the full set X. Proof. X is certainly an S-invariant set. Since QB is contrac- tive on X, for each T € b: TAI, and for each x € X, we have p P(Tx,x) p(tix,x) < 1 -x(1) THAI, { p(T%x,209 } is a Cauchy sequence. Denote the limit of this for all non-negative integers p. For each T € a sequence by Fed . Weclaim that this limit is independent of T, i.e. for each pair S, T € db: S, T¥I, Pod = Pghd . Note that for Ss, T #1, | p(T*x,8) - p(S x,» | < p(S"x,T'x) <p (8%, 89x) + p(s7Tx, T2x) < AMS) Px, Tex) + AB(T) P(S"x,x) ve Pee + 2 fSs. Since the right hand side tends to zero as n tends to infinity, this ran shows that Pye) = Ps) as desired. We may now denote the com- tos . as n mon limit by Pc), i.e. p(x) = n lim, p(T x,x) where Ted, TA I. Obviously 0 ¢ g (x) < 00. Furthermore, P(Tx) =, lim p(Tx, TY ¢ A(T), lim p(T? *x,x) = A(T) p(x). Finally, for each pair xy : Xo € X, we have: n n n n Pp (x, »x,) gp (x, .T x) + p(T x, +T x) + P(T x5 sX,) n A < pix. T x) + n{T) (x) +X) + p(T Xp 1Xp) In particular by choosing TAI, hence 0 ¢ x(T) <1, and letting n tends to infinity we obtain that P (x,) = P(x.) = 0 implies X= Xp | The existence of a level function on the full set X is not only necessary, as shown, but also sufficient: Theorem 2. If there exists a level function on the full set X, then Ps is contractive. Proof. Let P (x) be a level function with respect to a certain fV/ contractive function >. Define a metric g on X by: ~ P(x) + Ply) ifx fy; P(x,y) = 0 ifx=y. Clearly Pe is a metric on X, and for each T# I, we have P(Tx, Ty) < X(T) 9 (x, y), since forx#y, p (Tx, Ty) < p(Tx) + 9 (Ty) € A(T) P(x) + AT) Py) MT) P(x, y), and for x= y the above inequality is obvious. | 10 The definition of uniformly contractive semi-group depends on the existence of certain uniformly contractive function \. Note that the definition is actually independent of >. Suppose 2 is uniformly contractive with respect to some uniformly contractive function ). Then by Theorem 1 there exists a level function 9 (x) on X satisfying P(Tx) € A Pe for allx€X, andall Té &: TAI. For any real num- ber A, 0< & ¢ O, define an (x) = Face . This new function satis- fies P,(Tx) ¢ “ P,(x) and is easily seen to be again a level function. For any pel ,l1) we can choose SR, such that ~ = M, and hence by Theorem 2, g is uniformly contractive with respect to M. Repeating the arguments in Theorems 1 and 2 with A replacing »(T) throughout, we obtain: Theorem 3. ~ is uniformly contractive if and only if there exists a level function defined on the full set X with respect to a uni- formly contractive function. Theorem 4. x is completely contractive if and only if 2 is contractive and there exists an element wé€X such that Sw= w for some Sef, SAI. Proof. Let X be completely contractive. Choose S € 2g, S Al. There exists by the contraction mapping principle an element weé X, such that Sw=w. Conversely, assume that d is contractive and that there exists w<«X such that Sw=w for some S € O S#I. Con- 11 struct a level function P on X as defined in Theorem 1. The value Pw) of this level function at w must be zero, since (S) 41, and p(w) = p(S4) ¢ AIS) p(w). Define a new metric Pp onX be (2). Let {x} be a Cauchy sequence in X with respect to this new metric. If Pp (x) tends to zero as n tends to infinity, then the sequence {x} has the limit w, since P (x, w) r4 p(x.) + P(w) = p&,) . On the other hand if Pix) does not tend to zero then there exists a subsequence {y,\ C {x} such that S (y) > § >» 0. By assumption there exists a N 70 such that eV) <§ forn, m?N. This implies Yn = Ym foralln,m 7N, and the subsequence {yn} has a limit namely Yue As a Cauchy se- quence, the full sequence has the same limit. | Theorem 4 shows that completely contractive semi-groups are essentially contractive semi-groups. For any non-completely con- tractive semi-group Ss we may always add the point w to X and de- fine Tw=w forallT « 2 to make it completely contractive. Theorem 5. If y,) is contractive on X, then there exists a leng- th function defined on x . Proof, Define o(S) - sup £(Sx.Sv) | igs 41, then 0£o(8) a xfy P(x, y) ¢ A(S) < 1. If£S =I, then o(S) -—1. ForanyS, Te Sand x7x#y, we have. p(STx, STy) < o (S) p (Tx, Ty) for Tx #Ty. But this inequality obviously holds even if Tx = Ty. Moreover Ff (STx, STy) <€ o(S) o(T) 12 plx.y) . Hence by dividing through with Plx,y) we easily conclude ao(ST) 2 o(S)a(T). Finally, assume o{S,) = o(S,) = 0, then for allx,y €X, x#y, @(S,x,S,y) = 9 (S,x,S,y) = 0. This implies the PSX) g%18o existence of ws wy such that S\x = Wy. and S_x = Ww, for all x€X. Now for any x€ X, we have 4 Pp (S, x, S,x) & p (S, x, 8, 5x) + § (S| Sx, 5x) Thus a(S) = a(S.) = 0 implies that 8, = S.- 1 We remark the interesting facl that if x is contractive (uni- formly contractive) on X then 2 is also contractive (uniformly con- tractive) on itself. The converse is obviously not true. 13 3. THE MAIN THEOREM Let X be a non-empty abstract set and S be a commutative semi-group of operators on X into itself, containing the identity I and at least one other element T, T# 1. Weask ourselves the question: what conditions should b satisfy in order that it be contractive or respectively uniformly contractive on X? Theorem 5 gives some nece- ssary conditions for any contractive semi-group in terms of a length function o on 2 . The following result provides a set of sufficient conditions on 2 . Theorem 6. Let X and B be given as above. If r satisfies the conditions: (a) that for each T € Dd: THI, TX, =X and TX, = Xy imply (b) that there exists a length function o defined on 2g ; (c) that for any given invariant set ) Cc A , there exists a finite set (B<9 such that for each T € 5, there corresponds a ve satisfying T = US for some S eh and ¢(T) = ¢(U)o(S); then o is contractive. ( The conditions (a) and (b) have been proved to be necessary and are easily seen to be independent of each other.) Lemma _1. Let X and d be given as in Theorem 6. Suppose that Py if 9 are two level functions defined with respect to the same 14 contractive function A and let x ! x, be their respective domains of definition. If there exist positive constants Cc} ' cy rq Co Pax) for all xeX, MX), then —, can be extended to X such that cP 12 1¥ X, Proof. Define the function P on X,UX, by pe& = c a fy (x) ifxeX,, x¢X. Conditions (i), (ii) of the definition of a level function are obviously satisfied. Condition (iii) is also obvious ifxeX, or Tx¢X,. Suppose 4 now that xEX,, xgX,, and Tx€X,, then A(T) P(x) = A(T) 4 P a(x) 1 c _4 _ , _ 2 c, P, (Tx) 2 Py (tx) = P (Tx). Finally, to prove that P(x,) = P (x,) = 0 implies KX) = Xp, we need to prove only that Pi (x,) = P,(x,) = 0 implies x, = x,. Choose Té€ S. TAI, then P,(Tx,)€ A(T) F(s,) = 0 and hence Tx, = x,. Similarly Tx, =x,. By assumption (a), we conclude xy {| Lemma 2. Let X and PS be given as in Theorem 6. Given a€X then there exists a level function on (a] with respect to the length function 0’. Proof. Define for xé [a] ; P(x) = nel, ao(T) , where Ch, = { T: Ta = x } . since x€ [a] implies that CA, is non-empty we have US Px) € 00, Next we note that (SX) =~ 7 (VIS rea, 78 T) Sx 15 £ oS) pay O (1) =o-(S) P(x). Finally, let xe [a], PG) =0. Con- x sider the invariant set J x7 2g om and denote by 02, the tinite set corresponding to J according to assumption (c). Suppose Ch, # 17 Uy 5, where ULE - . ~ _ Cc > ~ - (Dy Sie Fs) and 5, #I Since Uy € OO, <= Se! there exists Tye C,, (2, then there exists a Te Xr, such that T such that U, = T,S, where S.€ 2 . Since g (S, S.) € o(S;) o(S.) € 0 (S,) <1, so s,8, #1. Now x= T,a = U,S,a = T,8,8, a= 8, 5,x. poo = Tx = S, S, (Tx) . Hence by assump- tion (a), Tx = x for all T ,) . The same conclusion can be reached in For any t< ¥ , note that TS the case when C,, = B,. Indeed, since RB, is finite then there exists aS € Ch,, such that o(S) =0. For any Té 2S: o(ST)< o (S) o(T) =0. Thus ST=S. Therefore, x= Sa=STa=Tx. If now P (x) = P(x,) = 0 then Tx, = xy and Tx, =X, for all T eg . In particular by choosing T # I, we conclude from assumption (a) that x = *,-[] Proof of Theorem 6. Let xX) be an invariant set in X and Py be a level function on x, defined with respect to the length function 0. Suppose a ¢ X, , we claim that Py can be extended to xX U [a] . Denote by Po the level function defined on [a] according to Lemma 2. Consider the set J= {t: Te J, Taex,A[a]}. Clearly, 9 is an invariant set in s . Let & be the finite set corresponding to 9 according to assumption (c). In addition let (R'= { U:uUeE iS 1 ul F, (Ua) #0} and (3 = {u: uc &, P, (Ua) £0} . Define c) = Min 9 (Ua) and Cy = Max, P,(Ua). Choose xeX, N(a] and UE R' VERB 16 consider the sets oar ce and (B. as introduced in Lemma 2. We first note that if ®= @ then for each T € OL, T=U S&S for some U (4 (B,we have P, (&) = 9, (Ta) = PP, (US8a) £ a(S) p, (Ua) =0. Now §,) = 0 implies that Sx =x forall S ¢ Db: since f, (Sx) < ~(S) P, Gx) for allS#I. Pick any S #1, we conclude from F(A = P,(Sx) £ v(S) P,&) that f(s) = 0. Hence in this case the inequality c, Pixs Co Pas) holds in a trivial way. Similar conclusion holds if B'= ©. We may now assume that BA © and Bix ©. It is readily seen from above that P, (x) = 0 if and only if P,(s) = 0. So, we may also assu- me that P&) #0. Suppose 1 # (3: then by repeating the same argument as in Lemma 2, we conclude Tx = x for all TeX: in particular if TAI, then P(x) = P ,(Tx) £ o (T) Pats) implies P{) = 0. Again, the desired inequality holds trivially. Suppose now that CL, = (3... then we may choose Té€ Ce such that P(x) = O{T). Note that Ff, (x) # 0 implies F,(Ua) 4 0, and from the definition of Py. Pp(a) =1. For otherwise there exists V # I such that Va=a, and thus 5a =a for all se $ . In particular a= Ta=x €X,, contradicting a ¢ xX: Thus, C, P,&) =C) p, (Usa) ¢ Co (S) P, (Ua) ¢ P,(Ua)o(S) P, (Ua) & o (S)o(U) Pala) P, (Ua) ra c,o{T) Pala) =c¢,o(T) = Co P(x) . Apply Lemma 1 to extend P 1 over x) U [a] : Let ® be the family of all level functions defined with respect to the length functiong. @) is non-empty for it contains the level function 17 on the empty set®@. Let Xp be the domain of definition correspond- ing to pe. We say P< Pp, if (i) Xp (2 Xp, (ii) Pi = Po on Xp Clearly ¢ defines a partial ordering on O. Suppose now that isa totaly ordered subset of o. Define a level tunction P on UW Xp by ° (x) = =e(x) ifx«€X_ for some P€ . Since is totally ordered, this definition of # is unambiguous. c is clearly an upper bound for y and thus @) satisfies the hypothesis of Zorn's lemma. Therefore there must exists a maximal element Pur é 0) . We claim that X= Xo . For otherwise there exists a€éX, a £Xp M Pu and we may extend Pu to PF 'o) [a \, contradicting the maxima lity of Pu . Knowing the existence of a level function on the full set X, we conclude by Theorem 2 that J is contractive | We remark that if the length function o on 3 is in addition uniformly contractive on 5 , then Theorem 6 together with Theorem 3 imply that 2 is uniformly contractive on X. 18 4, SEMI-GROUPS GENERATED BY A FINITE NUMBER OF ELEMENTS Let X be a non-empty abstract set and Ty ' Tos wees TH ba mu- tually commuting mappings defined on X into itself. Denote by » the commutative semi-group containing the identity which is generated by qT, , Toe eeey Th Obviously, we may restrict ourselves to the case where all the T,'s are different from the identity. In this case, there exists a set of necessary and sufficient conditions for d to be uni- formly contractive. In particular, assumptions (a) and (b) of Theorem 6 are both necessary and sufficient. In fact, we can prove that o is uniformly contractive under assumption (a) and only part of assump- tion (b). Theorem 7. Let X and g be given as above. If x satisfies the conditions: (a) that for each T ep ,/T#I, TX =X and TX, =X, imply (b) that for each pair S, T « ny ST= Ilimplies S=T=TI; then Ps) is uniformly contractive. Corollary, Let X and 2 be given as in Theorem 7. Suppose there exists an element weX, such that for some S € PS , 841, Sw=w, Then Ps is uniformly completely contractive. We will prove this result by applying Theorem 5. For the sake of convenience, we first introduce some useful notations. Let Q de- 19 note the set of n-tuples ( ky Koo see Kk) where the k,'s are non-nega- tive integers. Define 9(k) = a k,; forallké€Q. Note that (k) is finite for allk €Q. We also define a partial ordering on Q by: p ¢ q if and only if P; g q, for alli, and p= q if and only if P,= Ge for alli, 14 ign. Obviously, Q forms a semi-group with respect k to vector addition, and the mapping k —» T = T Th defines a homomorphism of Q into p . We next prove two algebraic lemmas that are important in the proof of Theorem 7. Lemma 3. Every transverse set MCOQ is finite. Proof. The proof is by induction on the dimension n. The state- ment obviously is true forn=1. Let M be a transverse set in Q and let p= (Pp; Pores :P,) be a fixed chosen element of M. Note that n p M may be written as =i i Mir, where M,. = { q: qéeM, qa, = r}. Let Q' = {p: p= (Pp, Pores: Pay) t be the set of all (n-1)-tuples of non-negative integers endowed with the same partial ordering as that of Q. Denote by Qe the set { q: qéQ, a, = r} . For each i and eachr, the mapping f, (a), dgr-+++1G,4) = (Gp rdgre Gy li Geese wey q-p defines an isomorphism with respect to ordering between Q' and Qin Note that Me =MN Qe which is clearly a transverse set. Hence its image fi (M,,) in Q' is again transverse, and by the induction hypothesis is finite. Since each M,. is finite, therefore M is finite. ] 20 Lemma 4. Let P be an arbitrary partially ordered set which satisfies the descending chain condition. Then every ideal JC P may be written as a set union of a family of principle ideals whose generators form a transverse set. Proof. For any ideal J © P, we consider the transverse set R = { x: xeéJ, andif ye J and yéxthenx=y } . We claim that J = such that x >x.. If x, € R, then x € <x)? . Otherwise we may con- 1 tinue to pick another element a) € J such that wy y ao) . Let {x,: i= <x> . LetxeJandx¢R. We may pick an element x, € J 1,2,3,... } be the set of elements in J constructed inductively as above. By the descending chain condition, it has a minimal element, say y. Suppose now zéJandzc¢y. Since y is minimal, we must have y=z. HenceyeR, andxe<y>. | We remark that the set R is uniquely determined by J. To see this we assume that the ideal J may be written as: 1-U «x>- LU) gey x'€R' where R and R'‘ are both transverse in X, Let x€R then there exists a x'é€ R' such that x ¢ ¢x'>, i.e. x }x'. Onthe other hand, for x'é R| there exists a x"e€ R, such that x'<« ¢x">, i.e. x' 2x". Hence we have x}x'2x". Since x, x"€R, and Ris transverse, therefore x' =xeéR. ThusRCR'. Similarly, we obtain R'CR. Proof of Theorem 7. Assumption (a) of Theorem 6 is satisfied by 21 | hypothesis. For each S eS, let K(S) = ip: peq, 7 =§ \. Choose any »€(0,1), and define o(S) “canis) Kh) . Clearly 0¢ cos) <> k, <1 forallS# 1, and o([)=1. Moreover ¢(ST) = cert 3 ¢ to show that o(S,) = o(8,) =Qimplies S, = So. we first note that if 1 for any S € s , K(S) is transverse, then o(S) = Min He) > 0, ( since K(S) is finite by Lemma 3). On the other hand, if K(S) is not transverse, then there exist p,q¢K(S), p>q. Now pP- Asx) = Sx for allxé€X, and T’° 41. Again by assumption (a), we have Sx =0@ for allx¢éX. Hence o(S) = 0 implies that Sx =Qforallxé€X. Now suppose a(S,) = a (S,) = 0, then there exist 0, , 0, such that S)x = 0, and S,x= @, forallxeX. Since 0, = 8,80, = 8,5, 6, = 0, so 5) = S,- We next show that assumption (c) of Theorem 6 is also satisfied. Let 9 c P, be an invariant set. Consider the set J ={p: péQ, TP. SS which is clearly an ideal in Q. By Lemma 4, there exists a transverse set B such that J = 4 épy. Let (= { TP; for some pe B } , Obviously J3¢ G9 andis finite. For Té 9, o(T) = 0, choose any U e (3, and observe UT=T and o(T) = a(T)o(U). On the other hand, if o(1) #0, we may pick peK(T) such that o(T) = Kp) Let re B such that p}r. Thus, T¢ 63. Note that a(T) = Mo) = afr) + Hon y o(U)o(S), where S = pele d . We hence conclude o(T) =a (U)a(S) since the reverse inequality always holds. Now 22 the set (2 Cc 9 satisfies the condition required by assumption (c) of Theorem 6. Apply Theorem 6 and Theorem 3, we conclude that 2g is uniformly contractive. The corollary follows immediately from Theorem 4.{] 23 De REMARKS We first remark that Theorem 7 cannot be extended to the corres- ponding case where & is generated by a countably infinite number of mappings. To see this, we consider the following example: Let X= (0,00) andt,x=x+ ¢,i=1,2,3,.... Clearly X and the com- mutative semi-group S generated by all the T's satisfy the hypothe- sis of Theorem 7. But ~ is not uniformly contractive. Assume the contrary, then by Theorem 3 there exists a level function P on X such that p(Tx)<¢ ~ P(x) forallx«Xandall Te S, T#I, where 0¢A<1. Since 0 ¢ X, therefore p(x) #0 forallx€X. For any m we may write P(T)x) = Pty & »" p(x) . Letting m tend to infinity, we obtain a desired contradiction. Nevertheless in this case 2 is contractive on X. Indeed, pis = »*, forany A €(0,1), is a level function on X. ( Note that in this case the contractive function is clearly not uni- form.) Let X be a metrilizable space and T be a mapping of X into it- self. such that for each positive integer k, the equation Tx = x holds for some x eX implies x = Ww, the unique fixed point of T. We now ask ourselves the question: does there exist a metric in which T is a contraction and which at the same time reproduces the original topo- logy ? The answer is negative even in case X is compact. Suppose X be any compact metrilizable space, and T be a mapping of X into itself which possesses a unique inverse. In this case, we claim that 24 | there does not exist a metric on X which satisfies the above-mentioned requirements unless X is only a singleton set. Assume the contrary, i.e. there exists a metric on X such that p (Tx, Ty) £AP(x,y) for allx,yé€Xand Pp induces a topology same as that givenonX. Since X is compact in the original topology, so it also is compact in the mc- tric topology induced by P. Denote by D the diameter of X with res- pect to P, i.e. D oy ex P(x,y). Choose x,y €X, such thatx# y. Note that plx.y) < » p(T Dx, Ty) < Dn. Letting n tends to infinity, we arrive at the desired contradiction. As a postscript, we list here several questions for further inves- tigation. (i) What is a set of necessary and sufficient conditions for Ms to be contractive ? ( This is not known even in case 2 is generated by a countably infinite number of mappings.) (ii) Assumptions (a) and (b) of Theorem 6 are shown to be nece- ssary for PS to be contractive, ---are they also sufficient ? (iii) Let X be any compact metrilizable space and T a mapping of X into itself satisfying the condition imposed in the previous paragraph. What additional conditions are sufficient to insure the existence of a metric which will reproduce the original topology and at the same time make the mapping Ta contraction? (This is not known even in caseX=(0,1] .) l. bo 10, ll. 12. 25 REFERENCES S. Banach," Sur les operations dans les ensembles abstraits et leur application aux equations integrals ", Fundamenta Mathema- tica 3 (1922), 133-181. A. N. Kolmogorov and S. V. Fomin, Elements of the theory of func- tions and functional analysis . Vol 1 ( Metric and Normed Spaces ) Graylock Press (1957), New York. W.A.J. Luxemburg, " On the convergence of successive approxi- mations in the theory of ordinary differential equations II", Indag. Math. 20 (1958), 540-546. D, W. Willett, " Non-linear vector integral equations as contrac— tion mappings ", Arch. for Rat. Mech. and Anal., 15 (1964), 79-86. H. Samuelson," On the Perron-Frobenius theorem ", Michigan Math. J. 4 (1957), 57-59. A. C. Thompson, " On certain contraction mappings in a partially crdered vector space.", Proc. Amer. Math. Soc. 14 (1963), 438-443. J. Schrdéder," A unified theory for estimation and iteration in me- tric spaces and partially ordered spaces ", MRC No.237, Univ. of Wiscousin, (1961). M. Edelstein," An extension of Banach's contraction principle ", Proc. Amer. Math. Soc. 12(1961), 7-10. E. Rakotch," Note on €-contractive mappings ", Bulletin of Res- earch Council of Israel, 10B (1961), 53-58. W.J. Kammerer and R, H. Kasriel," On contractive mappings in uniform spaces ", Proc. Amer. Math. Soc. 15(1964), 288-290. R. E. Edwards," A fixed point theorem with application to convo- lution equations ", J. of Australian Math. Soc. III (1963), 385- 395. A. 8, Davis," Fixpoint theorem for contractions of a well chained topological space ", Proc. Amer. Math. Soc. 14 (1963), 981-985 26 13. COC. Bessaga," On the converse of the Banach Fixed-point princi- ple ", Coll. Math. VII (1959), 41-43. 14. L. Janos," Converse to contraction mapping principle ", Amer. Math. Soc. Notices 11 (1964), 224. 15. J. S. W,. Wong," A generalization of the converse of contraction mapping principle", Amer. Math. Soc. Notices 11 (1964), 385. 16. G. Birkoff, Lattice Theory, Amer. Math. Soc. Coll. Publications, XXV (1948).