AS A PARTICULAR CASE OF THE CONTRACTION PRINCIPLE

(1)

A DISCRETE FIXED POINT THEOREM OF EILENBERG

AS A PARTICULAR CASE OF THE CONTRACTION PRINCIPLE

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=R0⊇R1⊇ ···;

(ii)^∞_n₌₀Rn=∆, the diagonal inX×X;

(iii)given a sequence(xn)^∞_n₌0such that(xn,xn+1)∈Rnfor alln∈N0, there is anx∈X such that(x_n,x)∈R_nfor alln∈N0.

IfFis a self-map ofXsuch that givenn∈N0andx,y∈X,

(x,y)∈Rn=⇒(Fx,F y)∈Rn+1, (1.1) thenFhas a unique fixed pointx∗and(Fⁿx,x∗)∈R_nfor eachx∈Xandn∈N0.

(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,z∈X. (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:http://dx.doi.org/10.1155/S1687182004311010

(2)

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 principle. 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 anx∈X. By (i), (x,Fx)∈R0. Hence by (1.1), we may infer that (Fⁿx,Fⁿ⁺¹x)∈Rnfor alln∈N0. By (iii), we obtain the existence of anx∗∈Xsuch that

Fⁿx,x∗

∈Rn ∀n∈N0. (2.1)

Hence, again by (1.1), we get that (Fⁿ⁺¹x,Fx∗)∈R_n+1; equivalently, (Fⁿx,Fx∗)∈R_nfor alln∈N, the set of all positive integers, and also forn=0 sinceR0=X×X. Thus, given n∈N0, we have by the symmetry that (Fx∗,Fⁿx)∈Rn. Hence, by (2.1), we get using the transitivity that

Fx∗,x∗

∈Rn ∀n∈N0. (2.2)

By (ii), this yields thatx∗=Fx∗. We show thatx∗is a unique fixed point ofF. Lety∗= F y∗. Then (x∗,y∗)∈R0, so by (1.1), (Fⁿx∗,Fⁿy∗)∈Rn, that is, (x∗,y∗)∈Rn for all n∈N0. Hence by (ii), we get thatx∗=y∗which completes the proof.

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

∈R_n, then (x,x_n)∈R_nand by the transitivity, (x,x)∈R_nfor alln∈N0which, 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.

(3)

(i) There exists a sequence(R_n)^∞_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,y∈X, it follows fromTheorem 1.1(i) and (ii) that the set{n∈N0: (x,y)∈R_n}is of a form{0, 1,...,p}for somep∈N0. Then set p(x,y) :=p. Ifx=y, setp(x,y) := ∞. Next define

d(x,y) :=α^p⁽^x^,^y⁾ ∀x,y∈X (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 (x_n)^∞_n₌₁ be a Cauchy sequence in (X,d). Then there is a subsequence (xkn)^∞_n₌0such that

dx_kn,x_kn+1

< αⁿ. (3.4)

Setyn:=xkn. Sinced(yn,yn+1)< αⁿ, we may infer that p(yn,yn+1)> n. Hence and by the definition ofp, (y_n,y_n+1)∈R_n. By hypothesis, there is ay∈Xsuch that (y_n,y)∈R_nfor alln∈N0. Thenp(yn,y)≥nwhich yields thatd(yn,y)≤αⁿ. Hence (xn)^∞_n₌₁is convergent as a Cauchy sequence containing a convergent subsequence.

Finally, we show thatFis anα-contraction. Fix two distinct elementsx,y∈X. Then (x,y)∈R_p(x,y), so by (1.1), (Fx,F y)∈R_p(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⁾⁺¹=αd(x,y). (3.5) (ii)⇒(i). Define

Rn:=

(x,y)∈X×X:d(x,y)≤αⁿδ(X) ∀n∈N0, (3.6) whereδ(X) denotes the diameter ofX. Then it is obvious thatR_nare 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

xn,xn+1

∈Rn (3.7)

(4)

for alln∈N0. Hence the series^∞_n₌1d(x_n,x_n+1) is convergent which implies that (x_n)^∞_n₌0is a Cauchy sequence. By completeness,x_n→xfor somex∈X. We prove that (x_n,x)∈R_n. Fix ann∈N0. By induction, we show that

xn,xn+k

∈Rn (3.8)

for allk∈N. By (3.7), condition (3.8) holds fork=1. Assume that (3.8) is satisfied for somek∈N. By (3.7), (x_n+k,x_n+k+1)∈R_n+k. Since (R_n)^∞_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 R_nis 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-

traction.

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 BCP^∗are equivalent. Thus we need here only to verify the suitable property of a sequence of successive approximations. That ET implies BCP^∗follows from the fact that, under the assumptions of BCP^∗, if (Rn)^∞_n₌₀ is defined by (3.6), then by ET,Fhas a unique fixed pointx∗and (Fⁿx,x∗)∈Rn, that is, d(Fⁿx,x∗)≤αⁿδ(X); in particular,Fⁿx→x∗. We show implication BCP^∗⇒ET. Under the assumptions of ET, ifdis defined by (3.1), then by BCP^∗,Fhas a unique fixed point x∗. Moreover, givenn∈N0andx∈X,

dFⁿx,x_∗=dFⁿx,Fⁿx_∗≤αⁿdx,x_∗≤αⁿ. (3.9) Hencep(Fⁿx,x∗)≥nwhich implies that (Fⁿx,x∗)∈R_n. Corollary3.3. Under the assumptions of ET, the intersection_n_∈_NFⁿ(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 setsFⁿ(X) tend to 0 andF has a fixed pointx∗which implies that_n_∈_NFⁿ(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)_n_∈_Za sequence of reflexive and symmetric relations inXsuch that

(i)givenn∈Z, if(x,y)∈Rnand(y,z)∈Rn, then(x,z)∈Rn−1; (ii)_n_∈_ZR_n=X×X, and··· ⊇R−1⊇R0⊇R1⊇ ···;

(iii)_n_∈_ZR_n=∆;

(5)

(iv)given a sequence(x_n)^∞_n₌1such that(x_n,x_n+1)∈R_nfor alln∈N, there is anx∈X such that(x_n,x)∈R_n−1for alln∈N.

IfFis a self-map ofXsuch that givenn∈Zandx,y∈X, condition (1.1) is satisfied, then Fhas a unique fixed pointx∗, and givenx∈X, there is ak∈Nsuch that(F^k⁺ⁿx,x∗)∈Rn

for alln∈N.

Proof. By (ii), givenx∈X, there is a p∈Zsuch that p <0 and (x,Fx)∈R_p. Then by (1.1), (F⁻^px,F⁻^p⁺¹x)∈R0. Denotey:=F⁻^px. Again by (1.1), we get that (Fⁿy,Fⁿ⁺¹y)∈ Rnfor alln∈N, so by (iv), (Fⁿy,x∗)∈Rn−1for somex∗∈Xand for alln∈N. By (1.1), (Fⁿ⁺¹y,Fx∗)∈R_n. Since (x∗,Fⁿ⁺¹y)∈R_n, we may infer from (i) that (x∗,Fx∗)∈R_n−1. Thus by (iii),

x∗,Fx∗

∈

n∈N0

Rn=

n∈ZRn=∆, (4.1)

so x∗ is a fixed point ofF. A similar argument as in the proof ofTheorem 1.1 shows thatx∗is a unique fixed point. Moreover, (Fⁿ⁺¹y,x∗)∈Rn, that is, (F^k⁺ⁿx,x∗)∈Rnwith

k:=1−p.

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

2ⁿ

∀n∈Z. (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 alln∈N, that is,d(xn,xn+1)≤1/2ⁿ. Then (xn)^∞_n₌1is a Cauchy sequence, hence convergent to some x∈X. Since

dxn,xn+k

≤ ∞ i=n

dxi,xi+1

≤ ∞ i=n

1 2ⁱ ⁼

1

2ⁿ⁻¹, (4.3)

we may infer, lettingktend to the infinity, thatd(xn,x)≤1/2ⁿ⁻¹, that is, (xn,x)∈Rn−1. ThusTheorem 4.1(iv) holds. Assume thatF:X→Xis a Banach contraction. Then there is anm∈Nsuch thatF^m is a 1/2-contraction. Denote G:=F^m. Clearly, givenn∈Z, (x,y)∈Rnimplies that (Gx,Gy)∈Rn+1. ByTheorem 4.1,Ghas a unique fixed pointx∗, and givenx∈X, there is ak∈Nsuch that (G^k⁺ⁿx,x∗)∈R_n, that is,d(G^k⁺ⁿx,x∗)≤1/2ⁿ for alln∈N. HenceGⁿx→x∗. A well-known trick with an iterate ofFis to infer that also

Fⁿx→x∗andx∗=Fx∗.

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

(6)

can also be shown without a metric argument. Suppose thatF(X)=X. ThenFⁿ(X)=X for alln∈N. By (1.1),

X×X=Fⁿ(X)×Fⁿ(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?

References

[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–

64.

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

E-mail address:jachym@mail.p.lodz.pl

(7)

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 diﬀerential equations and dynamical systems. Survey articles dealing with interac- tions between diﬀerent 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 http://www.hindawi.com/journals/bvp/guidelines.html. Au- thors should follow the Boundary Value Problems manuscript format described at the journal site http://www .hindawi.com/journals/bvp/. 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 http://mts.hindawi.com/according 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;

juanjose.nieto.roig@usc.es

Guest Editor

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

donal.oregan@nuigalway.ie

Hindawi Publishing Corporation http://www.hindawi.com

AS A PARTICULAR CASE OF THE CONTRACTION PRINCIPLE

Full text

A DISCRETE FIXED POINT THEOREM OF EILENBERG