graph(g) =

We have already seen that the restriction of f ’1 to graph(g) is a contraction,

so all points on graph(g) converge under the iteration of f ’1 to the ¬xed point,

p. So they belong to W u (p). This completes the proof of the theorem.

Notice that if f (0) = 0, then p = 0 is the unique ¬xed point.

136 CHAPTER 7. HYPERBOLICITY.

Chapter 8

Symbolic dynamics.

8.1 Symbolic dynamics.

We have already seen several examples where a dynamical system is conjugate

to the dynamical system consisting of a “shift” on sequences of symbols. It is

time to pin this idea down with some formal de¬nitions.

De¬nition. A discrete compact dynamical system (M, F ) consists of a

compact metric space M together with a continuous map F : M ’ M . If F is

a homeomorphism then (M, F ) is said to be an invertible dynamical system.

If (M, F ) and (N, G) are compact discrete dynamical systems then a map

φ : M ’ N is called a homomorphism if

• φ is continuous, and

•

G —¦ φ = φ —¦ F,

in other words if the diagram

F

M ’’’ M

’’

¦ ¦

φ

¦φ

¦

N ’’’ N

’’

G

commutes.

If the homomorphism φ is surjective it is called a factor. If φ a homeomorphism

then it is called a conjugacy.

For the purposes of this chapter, we will only be considering compact discrete

situations, so shall drop these two words.

137

138 CHAPTER 8. SYMBOLIC DYNAMICS.

Let A be a ¬nite set called an “alphabet”. The set AZ consists of all bi-

in¬nite sequences x = · · · x’2 , x’1 , x0 , x1 , x2 , x3 , · · · . On this space let us put

the metric (a slight variant of the metric we introduce earlier) d(x, x) = 0 and,

if x = y then

d(x, y) = 2’k where k = max [x’i , xi ] = [y’i , yi ].

i

Here we use the notation [xk , x ] to denote the “block”

[xk , x ] = xk xk+1 · · · x

from k to occurring in x. (This makes sense if k ¤ . If < k we adopt the

convention that [xk , x ] is the empty word.) Thus the elements x and y are close

in this metric if they agree on a large central block. So a sequence of points {x n }

converges if and only if, given any ¬xed k and , the [xn , xn ] eventually agree

k

for large n. From this characterization of convergence, it is easy to see that

the space AZ is sequentially compact: Let xn be a sequence of points of AZ ,

We must ¬nd a convergent subsequence. The method is Cantor diagonalization:

Since A is ¬nite we may ¬nd an in¬nite subsequence ni of the n such that all the

xni are equal. In¬nitely many elements from this subsequence must also agree

0

at the positions ’1 and 1 since there are only ¬nitely many possible choices of

entries. In other words, we may choose a subsequence nij of our subsequence

ni j ni

such that all the [x’1 , x1 j ] are equal. We then choose an in¬nite subsequence

of this subsubsequence such that all the [x’3 , x3 ] are equal. And so on. We

then pick an element N1 from our ¬rst subsequence, an element N2 > N1 from

our subsubsequence, an element N3 > N2 from our subsubsubsequence etc. By

construction we have produced an in¬nite subsequence which converges.

In the examples we studies, we did not allow all sequences, but rather ex-

cluded certain types. Let us formalize this. By a word from the alphabet A we

simply mean a ¬nite string of letters of A. Let F be a set of words. Let

XF = {x ∈ AZ |[xk , x ] ∈ F}

for any k and . In other words, XF consists of those sequences x for which no

word of F ever occurs as a block in x. From our characterization of convergence

(as eventual agreement on any block) it is clear that XF is a closed subset of

AZ and hence compact. It is also clear that XF is mapped into itself by the

shift map

σ : AZ ’ AZ , (σx)k := xk+1 .

It is also clear that σ is continuous. By abuse of language we may continue to

denote the restriction of σ to XF by σ although we may also use the notation

σX for this restriction. A dynamical system of the form (X, σX ) where x = XF

is called a shift dynamical system.

Suppose that (X, σX ) with X = XF ‚ AZ and (Y, σY ) with Y = YG ‚ B Z

are shift dynamical systems. What does a homomorphism φ : X ’ Y look like?

For each b ∈ B, let

C0 (b) = {y ∈ Y |y0 = b}.

139

8.1. SYMBOLIC DYNAMICS.

(The letter C is used to denote the word “cylinder” and the subscript 0 denotes

that we are constructing the so called cylinder set obtained by specifying that

the value of y at the “base” 0.) The sets C0 (b) are closed, hence compact, and

distinct. The ¬nitely many sets φ’1 (C0 (b)) are therefore also disjoint. Since φ

is continuous by the de¬nition of a homomorphism, each of the sets φ’1 (C0 )(b)

is compact, as the inverse i age of a compact set under a continuous map from

a compact space is compact. Hence there is a δ > 0 such that the distance

between any two di¬erent sets φ’1 (C0 (b)) is > δ. Choose n with 2’n < δ. Let

if x, x ∈ X. Then

[x’n , xn ] = [x’n , xn ] ’ φ(x) = φ(x )

since they are at distance at most 2’n and hence must lie in the same φ’1 (C0 (b).

In other words, there is a map

¦ : A2n+1 ’ B

such that

φ(x)0 = ¦([x’n , xn ]).

But now the condition that σY —¦ φ = φ —¦ σX implies that

φ(x)1 = ¦([x’n+1 , xn + 1])

and more generally that

φ(x)j = ¦([xj’n , xj+n ]). (8.1)

Such a map is called a sliding block code of block size 2n + 1 (or “with

memory n and anticipation n”) for obvious reasons. Conversely, suppose that

φ is a sliding block code. It clearly commutes with the shifts. If x and x agree

on a central block of size 2N + 1, then φ(x) and φ(y) agree on a central block

of size 2(N ’ n) + 1. This shows that φ is continuous. In short, we have proved

Proposition 8.1.1 A map φ between two shift dynamical systems is a homo-

morphism if and only if it is a sliding block code.

The advantage of this proposition is that it converts a topological property,

continuity, into a ¬nite type property - the sliding block code. Conversely, we

can use some topology of compact sets to derive facts about sliding block codes.

For example, it is easy to check that a bijective continuous map φ : X ’ Y

between compact metric spaces is a homeomorphism, i.e. that φ’1 is continuous.

Indeed, if not, we could ¬nd a sequence of points yi ∈ Y with yn ’ y and

xn = φ’1 (yk ) ’ x = φ’1 (y). Since X is compact, we can ¬nd a subsequence

of the xn which converge to some point x = x. Continuity demands that

φ(x ) = y = φ(x) and this contradicts the bijectivity. Form this we conclude

that the inverse of a bijective sliding block code is continuous, hence itself a

sliding block code - a fact that is not obvious from the de¬nitions.