Mathematical Preliminaries - Semantics of Probabilistic Processes: An Operational Approach - page 16

or

for all x ∈ X and y ∈ Y , we have h · x>c>h · y .

n

Here the hyperplane is a set of the form { z ∈ R | h · z = c } .

Definition 2.18 Let ( X , d ) be a metric space. A function f : X ₒ X is said to be

a contraction mapping if there is a constant ʴ with 0 ≤ ʴ< 1 such that

d ( f ( x ), f ( y )) ≤ ʴ · d ( x , y )

for all x , y X .

In the above definition, the constant ʴ is strictly less than 1. It entails the following
property whose proof crucially relies on that constraint on ʴ and is worth writing
down.

∈

Theorem 2.8 (Banach Fixed-Point Theorem) Every contraction on a complete
metric space has a unique fixed point.

Proof Let ( X , d ) be a complete metric space, and f be a contraction mapping on
( X , d ) with constant ʴ . For any x 0 ∈

=

X , define the sequence ( x n )by x n + 1 : f ( x n )

for n ≥ 0. Let a : = d ( x 0 , x 1 ). It is easy to show that

≤ ʴ n

d ( x n , x n + 1 ) · a

by repeated application of the property d ( f ( x ), f ( y )) ≤ ʴ · d ( x , y ). For any ʵ> 0,

ʴ n

it is possible to choose a natural number N such that

1 − ʴ a<ʵ for all n ≥ N .Now,

for any m , n ≥ N with m ≤ n ,

d ( x m , x n ) ≤ d ( x m , x m + 1 ) + d ( x m + 1 , x m + 2 ) +···+ d ( x n − 1 , x n )

ʴ m ʴ m + 1 ʴ n − 1 ≤ · a + · a +···+ · a

ʴ m 1 − ʴ n − m
1 − ʴ

=

a

ʴ m

<

1 − ʴ a<ʵ

by repeated application of the triangle inequality. So the sequence ( x n ) is a Cauchy
sequence. Since ( X , d ) is complete, the sequence has a limit in ( X , d ). We define
x ∗ to be this limit and show that it is a fixed point of f . Suppose it is not, i.e.
a ∗ : d ( x ∗ , f ( x ∗ )) > 0. Since ( x n ) converges to x ∗ , there exists some N

= ∈ N such

that d ( x n , x ∗ ) < a 2

for all n ≥ N . Then

d ( x ∗ , f ( x ∗ )) d ( x ∗ , x N + 1 ) d ( x N + 1 , f ( x ∗ )) ≤ +

d ( x ∗ , x N + 1 ) d ( x N , x ∗ )

≤ + ʴ ·

a 2 + a 2 = a ∗ ,

<