Figure 4.19: (a) Forward iteration of the horseshoe map. (b) Backward iteration
of the horseshoe map.
The forward iteration of the horseshoe map is shown in Figure 4.19(a). The horseshoe is a mapping of the unit square D,
which contracts the horizontal directions, expands in the vertical
direction, and then folds.
The mapping is only defined on the unit square. Points that leave
the square are ignored.
Let the horizontal strip be all points on the unit square
with 
, and let horizontal strip 
be all points with
. Then a linear horseshoe map is defined by the transformation
where 
and 
.
The horseshoe map takes the horizontal strip to the
vertical strip 
, and
to the vertical strip 
:
The strip is also rotated by 
.
The inverse of the horseshoe map 
is shown in Figure 4.19(b).
The inverse map takes the vertical rectangles 
and 
to
the horizontal rectangles and .
The invariant set 
of the horseshoe map is the
collection of all points that remain in D under all iterations of f,
This invariant set consists of a certain infinite intersection
of horizontal and vertical rectangles.
To keep track of the iterates of the horseshoe map (the rectangles), we will
need the symbols 
with 
The symbolic encoding of the rectangles works much the
same way as the symbolic encoding of the quadratic map (see
section 2.12.2).
Figure 4.20: (a) Forward iteration of the horseshoe map and symbolic names. (b)
Backward iteration. (c) Symbolic encoding of the invariant points constructed
from the forward and backward iterations.
The first forward iteration of the horseshoe map produces two
vertical rectangles called and . is the
vertical rectangle on the left and is the vertical
rectangle on the right. The next step is to apply the horseshoe
map again, thereby producing 
. As shown in Figure 4.20(a),
and produce four vertical rectangles labeled (from
left to right) , 
, 
, and 
.
Applying the map yet again produces eight
vertical strips labeled 
, 
, 
,
, 
, 
, 
, and 
.
In general, the nth iteration produces 
rectangles.
The labeling for the vertical strips is recursively defined as follows:
if the current strip is left of the center, then a 0 is
added to the front of the previous label of the rectangle;
if it falls to the right, a 1 is added. So, for instance,
the rectangle labeled starts on the right. The rectangle
labeled originates from strip , but it currently
lies on the left. Lastly, the strip , starts on the right,
then goes to the left, and then returns to the right again.
To each vertical strip we associate a symbolic itinerary ,
which gives the approximate orbit (left or right) of a vertical strip
after n iterations. The minus sign in the symbolic label
indicates that the symbol 
arises from considering the ith
preimage of the particular vertical strip under f. Also
note that the vertical strips get progressively thinner, so that
after n iterations, each strip has a width of 
.
The backward iterates produce horizontal strips at the nth
iteration. The height of each of these horizontal strips is 
.
From the two horizontal strips and , the inverse map
produces four horizontal rectangles labeled (from bottom
to top) as 
, 
, 
, and 
(Fig. 4.20(b)).
This in turn produces eight horizontal rectangles, 
, 
,
, 
, 
, 
, 
, and 
.
Each horizontal strip can be uniquely labeled with a sequence of
0's and 1's,
where the symbol 
indicates the current approximate
location (bottom or top)
of the horizontal
rectangle.
The fact that the labeling scheme is unique follows from the definition
of f and the observation that all of the horizontal rectangles are disjoint.
Unlike the vertical strips, the indexing for
the horizontal strips starts at 0 and is positive.
The need for this indexing convention will become apparent when we specify the
labeling of points in the invariant set.
Now, the invariant set of the horseshoe map f is given by
the infinite intersection of all the horizontal and vertical strips.
The invariant set is a fractal, in fact, it is a product of two Cantor sets. The
map f generates a Cantor set in the horizontal direction, and the inverse
map generates a Cantor set in the vertical direction. The invariant
set is, in a sense, the product of these two Cantor sets.
