1 Introduction

Let \(\mathbb {Z}\) denote a set of integers, \(\mathbb {N}\) a set of positive integers and \(\mathbb {N}_{0}\) a set of nonnegative integers. Given a nonempty set X, let \(\Delta _{X}\) be the diagonal in \(X\times X\), i.e., \(\Delta _{X}=\left\{ (x,x):x\in X\right\} \).

In [7], Jachymski proved the following result, as an extension of a discrete fixed point theorem due to Eilenberg (see [5, Chapter I, p. 19], [7, Theorem 1.1]). Note that in what follows the powers of a binary relation over a nonempty set are considered with respect to the usual composition of binary relations.

Theorem 1.1

Let X be a nonempty set, \((R_{n})_{n\in \mathbb {Z}}\) a sequence of reflexive and symmetric binary relations over X and F a self-map of X such that the following conditions are satisfied:

  • (r1) \(R_{n}^{2}\subseteq R_{n-1}\) for all \(n\in \mathbb {Z}\);

  • (r2) \(\bigcup _{n\in \mathbb {Z}}R_{n}=X\times X\);

  • (r3) \(\bigcap _{n\in \mathbb {Z}}R_{n}=\Delta _{X}\);

  • (r4) given a sequence \((x_{n})_{n\ge 1}\) such that \((x_{n} ,x_{n+1})\in R_{n}\) for all \(n\in \mathbb {N}\), there exists \(x\in X\) such that \((x_{n},x)\in R_{n-1}\) for all \(n\in \mathbb {N}\);

  • (r5) given \(n\in \mathbb {Z}\), if \((x,y)\in R_{n}\) then \((Fx,Fy)\in R_{n+1}\).

Then F has a unique fixed point \(x_{*}\in X\) and for every \(x\in X\), there exists \(k\in \mathbb {N}\) such that \((F^{n+k}x,x_{*})\in R_{n}\) for all \(n\in \mathbb {N}\).

Note that the original formulation of Theorem 1.1 also contained the superfluous assumption:

  • (r0) \(R_{n}\subseteq R_{n-1}\) for all \(n\in \mathbb {Z}\).

Indeed, since \(R_{n}\) are reflexive (i.e., \(\Delta _{X}\subseteq R_{n}\)) for all \(n\in \mathbb {Z}\), it follows that \(R_{n}\subseteq R_{n}^{2}\), which by (r1) leads to (r0).

Jachymski [7, Proposition 4.2] showed that Theorem 1.1 implies the well-known Banach contraction mapping principle, which we state next:

Theorem 1.2

(The contraction mapping principle) Let (X, d) be a complete metric space and F a self-map of X. If there exists \(q<1\) such that

$$\begin{aligned} d(Fx,Fy)\le q\cdot d(x,y)\quad \text {for all }x,y\in X, \end{aligned}$$
(1.1)

then F has a unique fixed point \(x_{*}\in X\) and, for every \(x\in X\), the sequence \(\left( F^{n}x\right) \) is convergent to \(x_{*}\) (here, \(F^{n}\) denotes the n-th iterate of F).

In [7], Jachymski then raised the problem of finding a result similar to Theorem 1.1 that is equivalent to the contraction mapping principle.

In what follows, we give a definite answer to this problem, by showing that Theorem 1.1 is, actually, equivalent to the contraction mapping principle. We base our approach on a constructive metrization result that is motivated by the fact that under the conditions in Theorem 1.1, the family \(\left\{ R_{n}:n\in \mathbb {Z}\right\} \) is a base for some separable uniformity over X. By the metrization theorem in uniform spaces, the uniformity induced by \(\left\{ R_{n}:n\in \mathbb {Z} \right\} \) is metrizable. We refer to [8, Chapter 6] for more details on uniform spaces.

2 Preliminaries

Definition 2.1

[3]. Let X be a nonempty set and \(C\ge 1\). A map \(\delta :X\times X\rightarrow \mathbb {R}\) is called a C -inframetric (or, simply, an inframetric) over X if it satisfies the following conditions:

  • (d1) \(\delta (x,y)\ge 0\) for all \(x,y\in X\), and \(\delta (x,y)=0\) if and only if \(x=y\);

  • (d2) \(\delta (x,y)=\delta (y,x)\) for all \(x,y\in X\);

  • (d3) \(\delta (x,y)\le C\cdot \max \left\{ \delta (x,z),\delta (z,y)\right\} \) for all \(x,y,z\in X\).

The pair \((X,\delta )\) is called a C -inframetric space (or, simply, inframetric space).

Note that some authors use the term C-quasi-metric [9], quasi-ultrametric [6], weak ultrametric [2], C -pseudo-distance [2] or \(b_{C}\) -metric [10] in place of C-inframetric. A 1-inframetric (which is a metric) is usually referred to as an ultrametric [6] or non-Archimedean metric [1]. Note also that any metric is a 2-inframetric.

Following a previous result due to Frink [4], Schroeder [9] proved that every C-inframetric, with \(C\le 2\), induces an equivalent metric.

Theorem 2.2

(Schroeder [9]) Let X be a nonempty set and \(\delta \) a C-inframetric over X, with \(C\le 2\). Define the map \(d:X\times X\rightarrow \mathbb {R}\) by

$$\begin{aligned} d(x,y)= & {} \inf \left\{ \sum _{k=0}^{n}\delta (z_{k},z_{k+1}):n\in \mathbb {N} _{0},~z_{1},z_{2},\ldots ,z_{n}\in X,~z_{0}=x,~z_{n+1}=y\right\} \nonumber \\&\quad (x,y\in X)\text {.} \end{aligned}$$
(2.1)

Then, d is a metric over X and

$$\begin{aligned} \frac{1}{2C}\delta (x,y)\le d(x,y)\le \delta (x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$

The proof of Theorem 2.2 can be found in [9, Theorem 1.2]. In what follows, we will refer to d as the chain metric induced by the inframetric \(\delta \).

The following result establishes that every Lipschitz mapping with respect to \(\delta \) is also Lipschitz with respect to d, while the Lipschitz constants are equal.

Proposition 2.3

Let X be a nonempty set, \(\delta \) a C-inframetric over X, with \(C\le 2\), and d the chain metric induced by \(\delta \). Let F be a self-map of X for which there exists \(q>0\) such that

$$\begin{aligned} \delta (Fx,Fy)\le q\cdot \delta (x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$
(2.2)

Then,

$$\begin{aligned} d(Fx,Fy)\le q\cdot d(x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$
(2.3)

Proof

Fix \(x,y\in X\) and let \(n\in \mathbb {N}_{0}\), \(z_{1},z_{2},\ldots ,z_{n}\in X\), \(z_{0}=x\), \(z_{n+1}=y\). By the definition of d and using (2.2), it follows that

$$\begin{aligned} d(Fx,Fy)\le \sum _{k=0}^{n}\delta (Fz_{k},Fz_{k+1})\le q\cdot \sum _{k=0} ^{n}\delta (z_{k},z_{k+1}), \end{aligned}$$

and by taking the infimum over all possible finite sequences \((z_{k})\) in X, we obtain (2.3). \(\square \)

3 Main results

We start this section with the announced metrization result.

Proposition 3.1

Let X be a nonempty set and \((R_{n})_{n\in \mathbb {Z}}\) a sequence of reflexive and symmetric binary relations over X such that conditions (r1), (r2) and (r3) are satisfied. Define the mappings \(M:X\times X\rightarrow 2^{\mathbb {Z}}\), \(\mu :X\times X\rightarrow \mathbb {Z}\cup \left\{ \infty \right\} \), and \(\delta :X\times X\rightarrow [0,\infty )\) as:

$$\begin{aligned} M(x,y)=\left\{ n\in \mathbb {Z}:(x,y)\in R_{n}\right\} ,\quad \mu (x,y)=\sup M(x,y),\quad \delta (x,y)=2^{-\mu (x,y)} \end{aligned}$$
(3.1)

for each \((x,y)\in X\times X\) (here, by convention, \(2^{-\infty }=0\)).

Then, \(\delta \) is a 2-inframetric over X such that

$$\begin{aligned} R_{n}=\left\{ (x,y)\in X\times X:\delta (x,y)\le \frac{1}{2^{n}}\right\} \quad \text {for every }n\in \mathbb {Z}\text {,} \end{aligned}$$
(3.2)

and the chain metric d induced by \(\delta \) verifies

$$\begin{aligned} \frac{1}{4}\delta (x,y)\le d(x,y)\le \delta (x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$
(3.3)

Moreover, if (r4) is satisfied, then d is complete.

Proof

By (r2), it follows that \(M(x,y)\ne \emptyset \) for all \(x,y\in X\); hence, \(\mu \) and \(\delta \) are correctly defined.

Since \(R_{n}\) are symmetric for all \(n\in \mathbb {Z}\), it follows that M, \(\mu \) and \(\delta \) are also symmetric.

Using (r0) (which follows from (r1)), we can conclude that either \(M(x,y)=\mathbb {Z}\), or M(x, y) consists of all integers up to \(\mu (x,y)\) (when \(M(x,y)\ne \mathbb {Z}\)). From here, it follows that for every \(x,y\in X\) and \(n\in \mathbb {Z},\) we have the set of equivalences:

$$\begin{aligned} (x,y)\in R_{n}\Leftrightarrow n\in M(x,y)\Leftrightarrow n\le \mu (x,y)\Leftrightarrow \delta (x,y)\le \frac{1}{2^{n}}, \end{aligned}$$
(3.4)

which leads to (3.2). Next, by (r3),

$$\begin{aligned} x=y\Leftrightarrow (x,y)\in \bigcap _{n\in \mathbb {Z}}R_{n}\Leftrightarrow \delta (x,y)\le \frac{1}{2^{n}}\text { for all }n\in \mathbb {Z}\Leftrightarrow \delta (x,y)=0. \end{aligned}$$

We show next that \(\delta \) satisfies the 2-inframetric inequality:

$$\begin{aligned} \delta (x,y)\le 2\max \left\{ \delta (x,z),\delta (z,y)\right\} \quad \text {for all }x,y,z\in X. \end{aligned}$$

This is achieved by proving the corresponding (equivalent) inequality for \(\mu \):

$$\begin{aligned} \mu (x,y)\ge \min \left\{ \mu (x,z),\mu (z,y)\right\} -1\quad \text {for all }x,y,z\in X\text {.} \end{aligned}$$
(3.5)

Indeed, the inequality (3.5) is obvious when any two of x, y, z are equal; hence, we can assume that \(x\ne y\ne z\ne x\) (i.e., \(\mu (x,y)\), \(\mu (x,z)\) and \(\mu (z,y)\) are all finite). Letting \(k:=\min \left\{ \mu (x,z),\mu (z,y)\right\} \), it follows that \(k\in M(x,z)\cap M(z,y)\); hence, \(\{(x,z),(z,y)\}\subseteq R_{k}\), which leads to \((x,y)\in R_{k}^{2}\). Applying (r1), it follows that \((x,y)\in R_{k-1}\); hence, \(k-1\in M(x,y)\), which finally proves (3.5).

Concluding, \(\delta \) is a 2-inframetric over X and the rest of the conclusion follows by Theorem 2.2.

Finally, to prove the completeness of d, it is enough to show that

  • (Q) every sequence \((x_{n})_{n\ge 1}\) in X that satisfies

    $$\begin{aligned} d(x_{n},x_{n+1})\le \dfrac{1}{2^{n+2}}\quad \text {for all }n\in \mathbb {N} \end{aligned}$$
    (3.6)

    has a convergent subsequence.

So, let \((x_{n})_{n\ge 1}\) be a sequence in X like in (3.6). By (3.3), it follows that \(\delta (x_{n},x_{n+1})\le \frac{1}{2^{n}}\); hence, \((x_{n},x_{n+1})\in R_{n}\) for all \(n\in \mathbb {N}\) by (3.2). Using (r4), there exists \(x\in X\) such that \((x_{n},x)\in R_{n-1}\) for all \(n\in \mathbb {N}\), which leads to

$$\begin{aligned} d(x_{n},x)\le \delta (x_{n},x)\le \dfrac{1}{2^{n-1}}\quad \text {for all } n\in \mathbb {N}. \end{aligned}$$

Concluding, \((x_{n})_{n\ge 1}\) is convergent to x (with respect to d). \(\square \)

Remark 3.2

To prove the completeness of d in Proposition 3.1, it is enough to consider the following weaker version of (r4):

  • (\(r4^{\prime }\)) given a sequence \((x_{n})_{n\ge 1}\) such that \((x_{n},x_{n+1})\in R_{n}\) for all \(n\in \mathbb {N}\), there exists \(x\in X\) and a subsequence \((x_{n}^{\prime })_{n\ge 1}\) of \((x_{n})_{n\ge 1}\) such that \((x_{n}^{\prime },x)\in R_{n}\) for all \(n\in \mathbb {N}\).

By a previous observation, it will suffice proving that (Q) holds. So, let \((x_{n})_{n\ge 1}\) be a sequence in X that satisfies (3.6). Clearly, \((x_{n},x_{n+1})\in R_{n}\) for all \(n\in \mathbb {N}\). Next, by (\(r4^{\prime }\)), there exists \(x\in X\) and a subsequence \((x_{n}^{\prime })_{n\ge 1}\) of \((x_{n})_{n\ge 1}\) such that \((x_{n}^{\prime },x)\in R_{n}\) for all \(n\in \mathbb {N}\), which leads to \(d(x_{n}^{\prime },x)\le \delta (x_{n}^{\prime },x)\le \dfrac{1}{2^{n}}\) for all \(n\in \mathbb {N}\) and concludes the proof.

Remark 3.3

It is well known that, under the assumptions in the contraction mapping principle, one can add to its conclusions that

$$\begin{aligned} d(F^{n}x,x_{*})\le \frac{q^{n}}{1-q}d(Fx,x)\quad \text {for all } n\in \mathbb {N}\text { and }x\in X\text {.} \end{aligned}$$
(3.7)

Replaying the argument of Jachymski in the proof of [7, Proposition 4.2], one can see that this additional conclusion of the contraction mapping principle cannot be obtained via Theorem 1.1. However, one can still obtain a weaker version of (3.7), as we explain next.

Explicitly, assume the conditions in Theorem 1.2, and let

$$\begin{aligned} R_{n}=\left\{ (x,y)\in X\times X:d(x,y)\le \dfrac{1}{2^{n}}\right\} \end{aligned}$$

for every \(n\in \mathbb {Z}\). Also, since F satisfies (1.1), it follows that

$$\begin{aligned} d(F^{n}x,F^{n}y)\le q^{n}\cdot d(x,y)\quad \text {for all }n\in \mathbb {N}\text { and }x,y\in X\text {.} \end{aligned}$$

Letting \(m\in \mathbb {N}\) to be (the smallest) such that \(q^{m}\le \dfrac{1}{2}\) and denoting \(G:=F^{m}\), it follows that

$$\begin{aligned} d(Gx,Gy)\le \dfrac{1}{2}d(x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$

Next, the proof of [7, Proposition 4.2] shows that conditions (r1)–(r5) are satisfied, with G in place of F, and that the conclusions of the contraction mapping principle follow via Theorem 1.1. In addition, we also obtain via Theorem 1.1 that for every \(x\in X\), there exists \(k\in \mathbb {N}\) such that \((G^{n+k}x,x_{*})\in R_{n}\) for all \(n\in \mathbb {N}\), which finally leads to the following weaker version of (3.7):

  • (P) for every \(x\in X\), there exists \(k\in \mathbb {N}\) such that \(d(F^{m(n+k)}x,x_{*})\le \dfrac{1}{2^{n}}\) for all \(n\in \mathbb {N}\), with \(m=\left\lfloor \log _{q}\dfrac{1}{2}\right\rfloor +1 \) (here, \(\left\lfloor a\right\rfloor \) denotes the integer part of the real number a).

Consequently, in what follows, when referring to the contraction mapping principle (or, Theorem 1.2), we also include property (P) among the conclusions.

In view of Remark 3.2, our next result is a slight modification of Theorem 1.1, which we prove via the contraction mapping principle.

Theorem 3.4

Let X be a nonempty set, \((R_{n})_{n\in \mathbb {Z}}\) a sequence of reflexive and symmetric binary relations over X and F a self-map of X such that conditions (r1), (r2), (r3), (\(r4^{\prime }\)) and (r5) are satisfied.

Then, F has a unique fixed point \(x_{*}\in X\) and for every \(x\in X\), there exists \(k\in \mathbb {N}\) such that \((F^{n+k}x,x_{*})\in R_{n}\) for all \(n\in \mathbb {N}\).

Proof

Let M, \(\mu \), \(\delta \) and d be defined as in Proposition 3.1. Using Proposition 3.1 and Remark 3.2, it follows that d is a complete metric over X.

We show that F is a contraction with respect to the metric d. Let \(x,y\in X\) with \(x\ne y\). Then \(\mu (x,y)\) is finite and \((x,y)\in R_{\mu (x,y)}\) (from the proof of Proposition 3.1), which by (r5) leads to \((Fx,Fy)\in R_{\mu (x,y)+1}\); hence, \(\delta (Fx,Fy)\le \dfrac{1}{2^{\mu (x,y)+1} }=\dfrac{1}{2}\delta (x,y)\) by (3.2). Clearly, the previous relation is true also when \(x=y\), so we can conclude that

$$\begin{aligned} \delta (Fx,Fy)\le \dfrac{1}{2}\delta (x,y)\quad \text {for all }x,y\in X \end{aligned}$$

which, by Proposition 3.3, finally leads to

$$\begin{aligned} d(Fx,Fy)\le \dfrac{1}{2}d(x,y)\quad \text {for all }x,y\in X\text {.} \end{aligned}$$

Applying the contraction mapping principle for the complete metric space (X, d) and the contraction F, it follows that F has a unique fixed point \(x_{*}\in X\). Also, using property (P) (Remark 3.3, with \(m=1\)), it follows that for every x, there exists \(k_{0}\in \mathbb {N}\) such that \(d(F^{n+k_{0}}x,x_{*})\le \dfrac{1}{2^{n}}\) for all \(n\in \mathbb {N}\). Next, using (3.3), we obtain that

$$\begin{aligned} \delta (F^{n+2+k_{0}}x,x_{*})\le 4d(F^{n+2+k_{0}}x,x_{*})\le \dfrac{1}{2^{n}}\quad \text {for all }n\in \mathbb {N}\text { and }x\in X \end{aligned}$$

which, by (3.2), means that

$$\begin{aligned} (F^{n+k}x,x_{*})\in R_{n}\quad \text {for all }n\in \mathbb {N}\text { and }x\in X \end{aligned}$$

with \(k=k_{0}+2\), concluding the proof. \(\square \)

We conclude with the announced equivalence result.

Theorem 3.5

Theorems 1.1, 1.2 and 3.4 are equivalent.

Proof

The fact that Theorem 1.1 implies Theorem 1.2 was previously discussed in Remark 3.3. Also, we proved Theorem 3.4 via Theorem 1.2 (see also Remark 3.3), which means that Theorem 1.2 implies Theorem 3.4. Finally, it is easy to see that Theorem 3.4 implies Theorem 1.1. \(\square \)