Our next goal is to unravel the dynamics on 
. In beginning this task
it is useful to think how the unit interval gets stretched and folded with
each iteration. The transformation of the unit interval under the first three
iterations for 
is illustrated in Figure 2.24.
Figure 2.24: Keeping track of the stretching and folding of the
quadratic map with symbolic dynamics.
This diagram shows that the essential ingredients that go into making a chaotic limit set are stretching and folding. The technique of symbolic dynamics is a bookkeeping procedure that allows us to systematically follow this stretching and folding process. For one-dimensional maps the complete symbolic theory is also known as kneading theory [10].
We begin by
defining a symbol space for symbolic dynamics.
Let 
.
is known as the sequence space on the symbols 0 and 1.
We sometimes use the symbols L (Left) and R (Right) to denote the symbols
0 and 1 (see Figure 2.24). If we define the distance between two sequences
and 
by
then is a metric space.
The metric 
induces a topology on
so we have a notion of open and closed sets in .
For instance, if 
and
, then the
metric 
A dynamic on the space is given by the shift map
defined by 
. That is, the shift map drops the first entry and
moves all the other symbols one place to the left. The shift map is continuous.
Briefly, for any 
, pick n such that 
, and
let 
. Then the usual 
proof goes
through when we use the metric given by equation (2.34) [10].
What do the orbits in look like?
Periodic points are identified
with exactly repeating sequences,
.
For instance,
there are two distinct period one
orbits, given by 
and 
.
The period two orbit
takes the form 
and 
,
and one of the
period three orbits looks like
,
, and
,
and so on. Evidently, there are 
periodic points of
period n, although some of these points are of a lower period. But
there is more. The periodic points are dense in ; that is, any
nonperiodic point can be represented as the limit of some periodic sequence.
Moreover, the nonperiodic points greatly outnumber the periodic points.
What does this have to do with the quadratic map, or more exactly the
map 
restricted to the invariant set ?
We now show that it
is the ``same'' map, and thus to understand the orbit structure and
dynamics of on we need only understand the shift map,
, on the space of two symbols, .
We can get a rough idea of the behavior of an orbit by keeping track of
whether it falls to the left (L or 0) or right (R or 1) at the nth
iteration. See Figure 2.25 for a picture of this partition. That is,
the symbols 0 and 1 tell us the fold which the orbit lies on at the nth
iteration.
Accordingly, define the itinerary of x as the
sequence
where 
if 
and
if 
. Thus, the itinerary of x is an
infinite sequence of 0s and 1s: it ``lives'' in . Further,
we think of S as a map from to . If 
, then it
can be shown that 
is a homeomorphism
(a map is a homeomorphism if it is a bijection and
both f and 
are continuous).
This last result says that the two sets and are the same.
To show the equivalence between the dynamics of on and
on , we need the following theorem, which is quoted
from Devaney.
Theorem. If 
, then is a homeomorphism and 
.
Proof. See section 1.7 in Devaney's book [10].
This theorem holds for all , but the proof is more subtle.
As we show in the next section, the essential idea in this proof is to keep track of the preimages of points not mapped out of the unit interval. The symbolic dynamics of the invariant set gives us a way to uniquely name the orbits in the quadratic map that do not run off to infinity. In particular, the itinerary of an orbit allows us to name, and to find the relative location of, all the periodic points in the quadratic map. Symbolic dynamics is powerful because it is easy to keep track of the orbits in the symbol space. It is next to impossible to do this using only the quadratic map since it would involve solving polynomials of arbitrarily high order.
