Download (0)

Full text




JACEK JACHYMSKI Received 6 November 2003

We show that a discrete fixed point theorem of Eilenberg is equivalent to the restriction of the contraction principle to the class of non-Archimedean bounded metric spaces. We also give a simple extension of Eilenberg’s theorem which yields the contraction principle.

1. Introduction

The following theorem (see, e.g., Dugundji and Granas [2, Exercise 6.7, pages 17-18]) was presented by Samuel Eilenberg on his lecture at the University of Southern California, Los Angeles in 1978. (I owe this information to Professor Andrzej Granas.) This result is a discrete analog of the Banach contraction principle (BCP) and it has applications in automata theory.

Theorem1.1 (Eilenberg). LetXbe an abstract set and let(Rn)n=0be a sequence of equiv- alence relations inXsuch that

(i)X×X=R0R1⊇ ···;

(ii)n=0Rn=∆, the diagonal inX×X;

(iii)given a sequence(xn)n=0such that(xn,xn+1)Rnfor allnN0, there is anxX such that(xn,x)Rnfor allnN0.

IfFis a self-map ofXsuch that givennN0andx,yX,

(x,y)Rn=⇒(Fx,F y)Rn+1, (1.1) thenFhas a unique fixed pointxand(Fnx,x)Rnfor eachxXandnN0.

(The letterN0denotes the set of all nonnegative integers.) A direct proof ofTheorem 1.1 will be given inSection 2. However, our main purpose is to show that Eilenberg’s theorem (ET) is equivalent to the restriction of BCP to the class of non-Archimedean bounded metric spaces. This will be done inSection 3. Recall that a metricdon a setXis callednon-Archimedeanor anultrametric(see de Groot [1] or Engelking [3, page 504]) if d(x,y)maxd(x,z),d(z,y) x,y,zX. (1.2)

Copyright©2004 Hindawi Publishing Corporation Fixed Point Theory and Applications 2004:1 (2004) 31–36 2000 Mathematics Subject Classification: 46S10, 47H10, 54H25 URL:


Then, in fact,d(x,y)=max{d(x,z),d(z,y)}ifd(x,z)=d(z,y), and therefore, each non- Archimedean metric space has the extraordinary geometric property that each three points of it are vertices of an isosceles triangle. We notice that non-Archimedean metrics are useful tools in many problems of fixed point theory (see, e.g., [6, proofs of Theorems 3, 4, and 5] on connections between some nonlinear contractive conditions, [7,8] on converses to contraction theorems, [5, Example 1] concerning a comparison of two fixed point theorems of the Meir-Keeler type). Moreover, there is also a variant of the BCP for self-maps of a non-Archimedean metric space proved by Prieß-Crampe [10] (also see Petalas and Vidalis [9]).

It turns out that, in general, the contraction principle cannot be derived from ET since each mapping satisfying assumptions of the latter theorem need not be surjective unless its domain is a singleton (cf.Corollary 3.3). Therefore, inSection 4we establish a slight extension of ET (cf.Theorem 4.1) which is strong enough to yield the contraction princi- ple. A paper of Grudzi ´nski [4] goes in a similar direction; however, he was able to obtain only some particular cases of the contraction principle via a discrete argument. Finally, we discuss a variant of ET given by Rus [11] (cf. Remarks2.1and4.3).

2. Proof of Eilenberg’s theorem

We give here a direct proof ofTheorem 1.1. Fix anxX. By (i), (x,Fx)R0. Hence by (1.1), we may infer that (Fnx,Fn+1x)Rnfor allnN0. By (iii), we obtain the existence of anxXsuch that


Rn nN0. (2.1)

Hence, again by (1.1), we get that (Fn+1x,Fx)Rn+1; equivalently, (Fnx,Fx)Rnfor allnN, the set of all positive integers, and also forn=0 sinceR0=X×X. Thus, given nN0, we have by the symmetry that (Fx,Fnx)Rn. Hence, by (2.1), we get using the transitivity that


Rn nN0. (2.2)

By (ii), this yields thatx=Fx. We show thatxis a unique fixed point ofF. Lety= F y. Then (x,y)R0, so by (1.1), (Fnx,Fny)Rn, that is, (x,y)Rn for all nN0. Hence by (ii), we get thatx=ywhich completes the proof.

Remark 2.1. Observe that a pointxfrom condition (iii) is uniquely determined: if (xn,x)

Rn, then (x,xn)Rnand by the transitivity, (x,x)Rnfor allnN0which, by (ii), yields thatx =x. Actually, a minor modification of the above proof shows that the as- sumptions ofTheorem 1.1could be weakened: the relationsRnneed not be transitive if we assume the uniqueness of a pointxin condition (iii). This exactly was done in [11, Theorem 5].

3. Eilenberg’s theorem and the contraction principle

Theorem3.1. LetFbe a self-map of an abstract setXandα(0, 1). The following state- ments are equivalent.


(i) There exists a sequence(Rn)n=0of equivalence relations inXsuch that the assump- tions of ET are satisfied.

(ii) There exists a non-Archimedean bounded and complete metricdsuch thatF is an α-contraction with respect tod.

Proof. (i)(ii). Given two distinct elementsx,yX, it follows fromTheorem 1.1(i) and (ii) that the set{nN0: (x,y)Rn}is of a form{0, 1,...,p}for somepN0. Then set p(x,y) :=p. Ifx=y, setp(x,y) := ∞. Next define

d(x,y) :=αp(x,y) x,yX (3.1) under the convention that α=0. Clearly, d(x,y)=0 if and only if x=y. Since the functionp(·,·) is symmetric, so isd. We show that condition (1.2) holds. Fix elements x,y,zinX. Without loss of generality, we may assume thatx,y, andzare distinct. Then (x,z)Rp(x,z)and (z,y)Rp(z,y). Set

k:=minp(x,z),p(z,y). (3.2) Since (Rn)n=0is descending, we get that (x,z), (z,y)Rk. By the transitivity, (x,y)Rk

and hencep(x,y)k. Then, by the definition ofk,

d(x,y)=αp(x,y)αk=maxαp(x,z)p(z,y)=maxd(x,z),d(z,y) (3.3) which means thatdis a non-Archimedean metric. Clearly,dis bounded. We show that dis complete. Let (xn)n=1 be a Cauchy sequence in (X,d). Then there is a subsequence (xkn)n=0such that


< αn. (3.4)

Setyn:=xkn. Sinced(yn,yn+1)< αn, we may infer that p(yn,yn+1)> n. Hence and by the definition ofp, (yn,yn+1)Rn. By hypothesis, there is ayXsuch that (yn,y)Rnfor allnN0. Thenp(yn,y)nwhich yields thatd(yn,y)αn. Hence (xn)n=1is convergent as a Cauchy sequence containing a convergent subsequence.

Finally, we show thatFis anα-contraction. Fix two distinct elementsx,yX. Then (x,y)Rp(x,y), so by (1.1), (Fx,F y)Rp(x,y)+1. Hencep(Fx,F y)p(x,y) + 1 which im- plies that

d(Fx,F y)=αp(Fx,F y)αp(x,y)+1=αd(x,y). (3.5) (ii)(i). Define


(x,y)X×X:d(x,y)αnδ(X) nN0, (3.6) whereδ(X) denotes the diameter ofX. Then it is obvious thatRnare reflexive, symmetric and conditions (i) and (ii) ofTheorem 1.1hold. The transitivity ofRnfollows easily from (1.2). We verify condition (iii) ofTheorem 1.1. Assume that a sequence (xn)n=0 is such that


Rn (3.7)


for allnN0. Hence the seriesn=1d(xn,xn+1) is convergent which implies that (xn)n=0is a Cauchy sequence. By completeness,xnxfor somexX. We prove that (xn,x)Rn. Fix annN0. By induction, we show that


Rn (3.8)

for allkN. By (3.7), condition (3.8) holds fork=1. Assume that (3.8) is satisfied for somekN. By (3.7), (xn+k,xn+k+1)Rn+k. Since (Rn)n=0is descending, we may infer that (xn+k,xn+k+1)Rn. Hence and by the transitivity, (xn,xn+k+1)Rnwhich completes the induction. Now lettingktend to the infinity in (3.8), we obtain that (xn,x)Rnsince Rnis a closed subset of the productX×X. This completes the proof of Theorem 1.1(iii).

Finally, (1.1) is an immediate consequence of the fact that the mappingFis anα-con-


Corollary3.2. ET is equivalent toBCP, the restriction of the BCP to the class of non- Archimedean bounded metric spaces.

Proof. ByTheorem 3.1, the assumptions of ET and BCPare equivalent. Thus we need here only to verify the suitable property of a sequence of successive approximations. That ET implies BCPfollows from the fact that, under the assumptions of BCP, if (Rn)n=0 is defined by (3.6), then by ET,Fhas a unique fixed pointxand (Fnx,x)Rn, that is, d(Fnx,x)αnδ(X); in particular,Fnxx. We show implication BCPET. Under the assumptions of ET, ifdis defined by (3.1), then by BCP,Fhas a unique fixed point x. Moreover, givennN0andxX,

dFnx,x=dFnx,Fnxαndx,xαn. (3.9) Hencep(Fnx,x)nwhich implies that (Fnx,x)Rn. Corollary3.3. Under the assumptions of ET, the intersectionnNFn(X)is a singleton.

Hence a mappingFis not surjective unlessXis a singleton. As a consequence, the contraction principle cannot be derived from ET.

Proof. By Theorem 3.1, a mapping F is a Banach contraction with respect to some bounded and complete metric. Then the diameters of setsFn(X) tend to 0 andF has a fixed pointxwhich implies thatnNFn(X)= {x}. The second statement is obvious.

The last statement follows from the fact that there exist surjective Banach contractions;

for such mappings, ET is not applicable.

4. An extension of Eilenberg’s theorem The letterZdenotes the set of all integers.

Theorem4.1. LetXbe an abstract set and(Rn)nZa sequence of reflexive and symmetric relations inXsuch that

(i)givennZ, if(x,y)Rnand(y,z)Rn, then(x,z)Rn1; (ii)nZRn=X×X, and··· ⊇R1R0R1⊇ ···;



(iv)given a sequence(xn)n=1such that(xn,xn+1)Rnfor allnN, there is anxX such that(xn,x)Rn1for allnN.

IfFis a self-map ofXsuch that givennZandx,yX, condition (1.1) is satisfied, then Fhas a unique fixed pointx, and givenxX, there is akNsuch that(Fk+nx,x)Rn

for allnN.

Proof. By (ii), givenxX, there is a pZsuch that p <0 and (x,Fx)Rp. Then by (1.1), (Fpx,Fp+1x)R0. Denotey:=Fpx. Again by (1.1), we get that (Fny,Fn+1y) Rnfor allnN, so by (iv), (Fny,x)Rn1for somexXand for allnN. By (1.1), (Fn+1y,Fx)Rn. Since (x,Fn+1y)Rn, we may infer from (i) that (x,Fx)Rn1. Thus by (iii),




nZRn=∆, (4.1)

so x is a fixed point ofF. A similar argument as in the proof ofTheorem 1.1 shows thatxis a unique fixed point. Moreover, (Fn+1y,x)Rn, that is, (Fk+nx,x)Rnwith


It is easily seen that ET is subsumed byTheorem 4.1. In particular, condition (i) is weaker than the transitivity of allRn. In view ofCorollary 3.3, the following result shows the advantage ofTheorem 4.1overTheorem 1.1.

Proposition4.2. Theorem 4.1implies the contraction principle.

Proof. Under the assumptions of the contraction principle, define Rn:= (x,y)X×X:d(x,y) 1


nZ. (4.2)

The triangle inequality implies thatTheorem 4.1(i) holds. It is clear thatTheorem 4.1(ii) and (iii) are satisfied. To verifyTheorem 4.1(iv), assume that (xn,xn+1)Rnfor allnN, that is,d(xn,xn+1)1/2n. Then (xn)n=1is a Cauchy sequence, hence convergent to some xX. Since





1 2i =


2n1, (4.3)

we may infer, lettingktend to the infinity, thatd(xn,x)1/2n1, that is, (xn,x)Rn1. ThusTheorem 4.1(iv) holds. Assume thatF:XXis a Banach contraction. Then there is anmNsuch thatFm is a 1/2-contraction. Denote G:=Fm. Clearly, givennZ, (x,y)Rnimplies that (Gx,Gy)Rn+1. ByTheorem 4.1,Ghas a unique fixed pointx, and givenxX, there is akNsuch that (Gk+nx,x)Rn, that is,d(Gk+nx,x)1/2n for allnN. HenceGnxx. A well-known trick with an iterate ofFis to infer that also


Remark 4.3. A variant of ET given by Rus [11] (cf.Remark 2.1) implies the contraction principle forboundedmetric spaces (see [11, Theorem 9]). However, the assumptions of his result also force that a mappingFneed not be surjective unlessXis a singleton. This


can also be shown without a metric argument. Suppose thatF(X)=X. ThenFn(X)=X for allnN. By (1.1),

X×X=Fn(X)×Fn(X)Rn. (4.4) Hence by (1.1), we get thatX×X=∆, that is,Xis a singleton. Thus Rus’ theorem cannot be applied ifFis a surjective Banach contraction on an unbounded metric space.

We close the paper with the following question.

Question 4.4. Is it possible to find such an extension of ET which would be equivalent to the contraction principle?


[1] J. de Groot,Non-Archimedean metrics in topology, Proc. Amer. Math. Soc.7(1956), 948–953.

[2] J. Dugundji and A. Granas,Fixed Point Theory. I, Monografie Matematyczne, vol. 61, PWN—

Polish Scientific Publishers, Warsaw, 1982.

[3] R. Engelking,General Topology, PWN—Polish Scientific Publishers, Warsaw, 1977.

[4] W. Grudzi ´nski,On the discrete Banach principle, Zeszyty Nauk. Politech. Ł ´odz. Mat. (1994), no. 26, 81–88.

[5] J. Jachymski,Equivalent conditions and the Meir-Keeler type theorems, J. Math. Anal. Appl.194 (1995), no. 1, 293–303.

[6] ,Equivalence of some contractivity properties over metrical structures, Proc. Amer. Math.

Soc.125(1997), no. 8, 2327–2335.

[7] ,A short proof of the converse to the contraction principle and some related results, Topol.

Methods Nonlinear Anal.15(2000), no. 1, 179–186.

[8] ,General solutions of two functional inequalities and converses to contraction theorems, Bull. Polish Acad. Sci. Math.51(2003), no. 2, 147–156.

[9] C. Petalas and T. Vidalis,A fixed point theorem in non-Archimedean vector spaces, Proc. Amer.

Math. Soc.118(1993), no. 3, 819–821.

[10] S. Prieß-Crampe,Der Banachsche Fixpunktsatz f¨ur ultrametrische R¨aume[The Banach fixed point theorem for ultrametric spaces], Results Math.18(1990), no. 1-2, 178–186 (German).

[11] I. A. Rus,Discrete fixed point theorems, Studia Univ. Babes¸-Bolyai Math.33(1988), no. 3, 61–


Jacek Jachymski: Institute of Mathematics, Technical University of Ł ´od´z, ˙Zwirki 36, 90-924 Ł ´od´z, Poland



Boundary Value Problems

Special Issue on

Singular Boundary Value Problems for Ordinary Differential Equations

Call for Papers

The purpose of this special issue is to study singular boundary value problems arising in differential equations and dynamical systems. Survey articles dealing with interac- tions between different fields, applications, and approaches of boundary value problems and singular problems are welcome.

This Special Issue will focus on any type of singularities that appear in the study of boundary value problems. It includes:

• Theory and methods

• Mathematical Models

• Engineering applications

• Biological applications

• Medical Applications

• Finance applications

• Numerical and simulation applications

Before submission authors should carefully read over the journal’s Author Guidelines, which are located at Au- thors should follow the Boundary Value Problems manu- script format described at the journal site http://www Articles published in this Spe- cial Issue shall be subject to a reduced Article Proc- essing Charge of C200 per article. Prospective authors should submit an electronic copy of their complete manuscript through the journal Manuscript Tracking Sys- tem at to the following timetable:

Manuscript Due May 1, 2009 First Round of Reviews August 1, 2009 Publication Date November 1, 2009

Lead Guest Editor

Juan J. Nieto,Departamento de Análisis Matemático, Facultad de Matemáticas, Universidad de Santiago de

Compostela, Santiago de Compostela 15782, Spain;

Guest Editor

Donal O’Regan,Department of Mathematics, National University of Ireland, Galway, Ireland;

Hindawi Publishing Corporation




Related subjects :