Content-Type: multipart/mixed; boundary="-------------0012051554166" This is a multi-part message in MIME format. ---------------0012051554166 Content-Type: text/plain; name="00-487.keywords" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="00-487.keywords" Continuous Map, Discontinuous Map, Representation, Subshift, Symbolic Dynamics ---------------0012051554166 Content-Type: application/x-tex; name="duan.tex" Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="duan.tex" %%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%% % LaTeX File % % Symbolic Representations of Iterated Maps % % by Xin-Chu Fu, Weiping Lu, Peter Ashwin and Jinqiao Duan % duan@iit.edu % % Submitted to: Transactions of Ameri. Math. Soc. % %%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%% \documentclass[12pt]{article} \usepackage{amssymb} \topmargin -1.3cm \textheight 24cm \textwidth 15cm \oddsidemargin 0.5cm \unitlength 0.93mm %\setlength{\textwidth}{15.5cm} %\setlength{\textheight}{23cm} %\setlength{\oddsidemargin}{1cm} %\setlength{\topmargin}{-1cm} %\setlength{\unitlength}{0.93mm} \def\a{\alpha} \def\b{\beta} \def\d{\delta} \def\ep{\varepsilon} \def\f{\varphi} \def\e{\eta} \def\l{\lambda} \def\L{\Lambda} \def\p{\psi} \def\r{\rho} \def\s{\sigma} \def\S{\Sigma} \def\x{\xi} \def\N{\mathbb{N}} \def\Z{\mathbb{Z}} \def\Q{\mathbb{Q}} \def\R{\mathbb{R}} \def\C{\mathbb{C}} \def\T{\mathbb{T}} \newcommand{\MA}{{\mathcal{A}}} \newcommand{\MI}{{\mathcal{I}}} \newcommand{\MP}{{\mathcal{P}}} \newcommand{\MR}{{\mathcal{R}}} \newcommand{\MS}{{\mathcal{S}}} \def\rep{representation } \newcommand{\card}{\mbox{card}} \newtheorem{defn}{{\sc Definition}}[section] \newtheorem{thm}{{\sc Theorem}}[section] \newtheorem{lem}[thm]{{\sc Lemma}} \newtheorem{pro}[thm]{{\sc Proposition}} \newtheorem{cor}[thm]{{\sc Corollary}} \newtheorem{rem}{\sc Remark}[section] \newtheorem{eg}{\sc Example}[section] \def\proof{{\noindent\em Proof.} } \def\qed{\hfill $\Box$ \newline \vspace{2mm}} \renewcommand{\theequation}{\thesection.\arabic{equation}} \catcode`\@=11 \@addtoreset{equation}{section} %\renewcommand{\baselinestretch}{2.0} \begin{document} \title{ Symbolic Representations of Iterated Maps } \author{} \date{November 14, 2000 } \maketitle % authors: \begin{center} {\large Xin-Chu Fu$^{1}$}, {\large Weiping Lu$^{2}$}, {\large Peter Ashwin$^{1}$} and {\large Jinqiao Duan$^{3}$} \vspace{0.2cm} 1. {\em School of Mathematical Sciences, Laver Building\\ University of Exeter, Exeter EX4 4QJ, UK}\\ 2. {\em Department of Physics, Heriot-Watt University \\ Riccarton, Edinburgh EH14 4AS, UK} \\ 3. {\em Department of Applied Mathematics\\ Illinois Institute of Technology, Chicago, IL 60616, USA} \vspace{0.2cm} \end{center} \begin{abstract} \noindent This paper presents a general and systematic discussion of various symbolic representations of iterated maps through subshifts. We give a unified model for all continuous maps on a metric space, by representing a map through a general subshift over usually an uncountable alphabet. It is shown that at most the second order representation is enough for a continuous map. In particular, it is shown that the dynamics of one-dimensional continuous maps to a great extent can be transformed to the study of subshift structure of a general symbolic dynamics system. By introducing distillations, partial representations of some general continuous maps are obtained. Finally, partitions and representations of a class of discontinuous maps, piecewise continuous maps are discussed, and as examples, a representation of the Gauss map via a full shift over a countable alphabet and representations of interval exchange transformations as subshifts of infinite type are given. \vspace{0.3cm} \noindent {\bf Key words:} \ Continuous Map, Discontinuous Map, Representation, Subshift, Symbolic Dynamics \end{abstract} % \begin{center} \section{Introduction} % \end{center} It has long been known that interesting behaviour can occur when iterating continuous maps. Such maps define discrete dynamical systems, which have been used as simplified prototypical models for some engineering and biological processes; see, e.g.~\cite{May, Hao89, Fu98}. Through the Poincar\'e section maps, discrete dynamical systems have also been used to study continuous dynamical systems, e.g.~\cite{GH83, Wiggins88}. Considerable progress has been made in the last two decades in the understanding of dynamical behaviour of nonlinear continuous maps. These systems, while mostly studied individually because of their distinct nature of nonlinear interactions, show similar dynamical features, especially when the parameters of the systems are close to some critical values where abrupt change in behavior takes place. The universality of such behavior has been a key subject in the study of nonlinear dynamics. A mathematical framework has, however, yet to be established under which a class of dynamical systems, such as one-dimensional continuous maps, can be described by a unified model. Such a framework will improve our understanding of general properties of dynamical systems and may be useful in our effort to classify dynamical systems. Shifts and subshifts defined on a space of abstract symbols are special discrete dynamical systems which are called symbolic dynamics systems. Symbolic dynamics is a powerful tool to study more general discrete dynamical systems, because the latter often contain invariant subsets on which the dynamics is similar or even equivalent to a shift or subshift. Moreover, there are a number of definitions of chaos, namely (1) the Li-Yorke definition; (2) Devaney's definition; (3) topological mixing; (4) Smale's horseshoe; (5) transversal homoclinic points; and (6) symbolic dynamics. The symbolic dynamics definition is especially important of these definitions, as it unifies aspects of many of the definitions. More precisely, it implies the first three definitions, is topologically conjugate to the fourth one and occurs as a subsystem of the fifth. Furthermore (see for example Ford \cite{Alekseev}) symbolic dynamics is very important for analysis of applications of nonlinear dynamics in physical sciences. For a dynamical system, we can study it either directly or via other systems which are better understood. Symbolic representations are methods to study dynamical systems through shifts and subshifts. In the study of hyperbolic dynamics of homeomorphisms, symbolic dynamics is one of the most fundamental models. Since the discovery of the Markov partitions of the two dimensional torus by Berg \cite{Berg} and the related work by Adler and Weiss \cite{Adler2}, symbolic representations of hyperbolic systems through the Markov partitions have been studied extensively (e.g., see \cite{Adler}). The equivalence between Smale's horseshoe and the symbolic dynamical system $(\S(2), \s)$ (see \cite{Smale}) implies that the former has a symbolic representation through the full shift $(\S(2), \s)$. A similar symbolic representation has also been revealed by Wiggins (see \cite{Wiggins88}) on higher dimensional versions of the Smale's horseshoe. Earlier works in \cite{Zhang} and \cite{Fu96} established that, under certain conditions, the restrictions of a general continuous self-map $f: X \rightarrow X$ to some horseshoe-like invariant subsets are topologically conjugate to $\s|_{\S(N)}$ or $\s|_{\S(\Z_+)}$ (see \cite{Fu96}), where $(\S(\Z_+), \s)$ is the symbolic dynamics system with a countable alphabet. These results actually demonstrated the partial symbolic representation of a class of maps as a full shift over a countable alphabet. Motivated by the above work, we study in this paper symbolic representations of continuous self-maps by using a more general and systematic approach. We present a unified model for all continuous maps on a metric space, by representing a map as a general subshift $(\S(X),\s)$. We show that the subshifts of $(\S(X), \s)$ may be used as such a unified model for all continuous self-maps on a metric space $X$. And it is shown that at most the second order representation is enough for a continuous map. In particular, when $X$ is a closed interval, we show that the dynamics of one-dimensional continuous maps to a great extent can be transformed to the study of subshifts of a symbolic dynamical system. We also discuss quasi-representations, and by introducing distillations, partial representations of some general continuous maps are obtained. Finally, partitions and representations of a class of discontinuous maps, piecewise continuous maps, are discussed, and as examples, a regular representation of the Gauss map via a full shift over a countable alphabet and regular representations of interval exchange transformations as subshifts of infinite type are given. \section{Some Definitions, Notation and Lemmas} Before turning to the next section to discuss representation theorems, we recall some definitions, introduce some notation, and provide some lemmas. Let $(X,d)$ be a metric space and denote by $\S(X)$ the space $X^{\Z_+}$ which consists of functions from the nonnegative integers $\Z_+$ to the metric space $X$. $x \in \S(X)$ may thus be denoted by $x=(x_0, x_1, \cdots, x_i, \cdots)$, $x_i \in X, i \ge 0$. Further, let $\S(X)$ be endowed with the product topology, so $\S(X)$ is metrizable. The metric on $\S(X)$ can be chosen to be $$ \r(x, y)=\sum^{+\infty}_{i=0} \frac{1}{2^i} \frac{d(x_i, y_i)}{1+ d(x_i, y_i)}, \;\;\;\; x=(x_0, x_1, \cdots), \;\; y=(y_0,y_1, \cdots) \in \S(X). $$ The shift map $\s: \S(X) \rightarrow \S(X)$ is defined by $(\s(x))_i=x_{i+1}, \; i=0,1, \cdots.$ Since $ \r (\s(x), \s(y)) \le 2 \r(x, y), $ $\s$ is continuous. $(\S(X), \s)$ is a general symbolic dynamics system (see \cite{Wiggins88, Fu92, Fu98}). We call $X$ the symbol space or alphabet, and $\S(X)$ the symbol sequence space. When $X$ is chosen as $\{0,1,\cdots, N-1 \}$ and the metric $d$ on $\{0,1,\cdots, N-1 \}$ is the discrete metric: $$ d(m,n)=\left\{\begin{array}{ll} 0, \;\;\;\; m=n\\ 1, \;\;\;\; m\ne n \end{array} \right., $$ then $(\S(X), \s)$ becomes the usual symbolic dynamics system $(\S(N), \s)$ as in \cite{GH83}. Let $\S \subseteq \S(X)$ be closed, and invariant for $\s$, i.e., $\s(\S) \subseteq \S $, then $(\S, \s)$ forms a subsystem of $(\S(X), \s)$. We call $(\S, \s)$ a subshift of the full shift $(\S(X), \s)$, denoted by $(\S, \s) \le (\S(X), \s) $. We denote by $C(X)$ the set of all continuous self-maps on $X$ and $M(X)$ the set of all self-maps on $X$. We also call the iteration system of an $f \in M(X)$ a dynamical system, denoted by $(X, f)$. For two dynamical systems $f_1 : X_1 \rightarrow X_1 $ and $f_2 : X_2 \rightarrow X_2 $, where $X_i$ are metric spaces and $f_i \in M(X_i), i=1,2,$ if there exists a homeomorphism $h: X_1 \rightarrow X_2 $ such that $hf_1=f_2h$, then we call $f_1$ is topologically conjugate to $f_2$, denoted by $f_1 \sim f_2$. If $h$ is continuous and surjective, but not necessarily invertible, and if $hf_1=f_2h$, then we call $f_1$ is topologically semi-conjugate to $f_2$, and also call $f_2$ a factor of $f_1$ (and $f_1$ an extension of $f_2$). We call $f_1$ and $f_2$ are weakly conjugate if each is a factor of the other. We give the following definitions for various symbolic representations: \begin{defn} If for an $f \in M(X)$, there exists a subshift $(\S, \s)$ of certain a symbolic dynamical system and a surjective map $h: \S \to X$, and a countable subset $D \subseteq \S$, such that $h$ is one-to-one and continuous on $\S\setminus D$, finite-to-one on $D$, and $f\circ h = h \circ \s $, then we call the subshift $(\S, \s)$ a {\rm regular representation} of the dynamical system $(X, f)$. If $D=\varnothing$, we call the subshift $(\S, \s)$ a {\rm faithful representation} of the dynamical system $(X, f)$. If $h$ is a topological conjugacy, we call $(\S, \s)$ a {\rm conjugate representation} of $(X, f)$. If $\s|_{\S}$ and $f$ are weakly conjugate, we call $(\S, \s)$ a {\rm weakly conjugate representation} of $(X, f)$. If $h$ is a topological semi-conjugacy, i.e., $(X, f)$ is a factor of $(\S, \s)$, we call $(\S, \s)$ a {\rm semi-conjugate representation} of $(X, f)$. If $(\S, \s)$ is a factor of $(X, f)$, we call $(\S, \s)$ a {\rm quasi-representation} of $(X, f)$. In all the above representations, we call a correspondence between symbol sequences in $\S$ and points in $X$ (either from $\S$ to $X$ or from $X$ to $\S$) a {\rm coding}. \end{defn} {}From the definition above, among the six representations, conjugate representation is the strongest one, since it implies all the others. A weakly conjugate representation is always a semi-conjugate representation and a quasi-representation. A faithful representation is also a semi-conjugate representation. Quasi-representation is the weakest one, but it still tells us some information. For example, if $(\S, \s)$ is a quasi-representation of $(X, f)$, then $h_{\rm top} (f)\ge h_{\rm top} (\s |_{\S})$, while the latter is usually easier to calculate ($h_{\rm top} (\cdot)$ denotes the topological entropy). In the definition of a regular representation, we allow $h$ to be possibly discountinuous on $D$ so that we can apply this definition to symbolic representations of some discontinuous maps. Note that weak conjugacy is strictly weaker than conjugacy (\cite{Lind}). For example, the Fibonacci subshift (consists of all sequences of $0$'s and $1$'s with $1$'s separated by $0$'s) and the even subshift (consists of all sequences of $0$'s and $1$'s with $1$'s separated by an even number of $0$'s) are weakly conjugate, but they are not conjugate since one is a subshift of finite type and the other is a subshift of infinite type. Throughout this paper, for $a \in I=[0, 1]$, we denote by $r_m(a)$ the $m$-adic fraction $$ r_m(a)=\sum^{+\infty}_{i=0} \frac{a_i}{m^{i+1}} \ , $$ and when $a\ne 0$, we require that there are infinite number of non-zero $a_i$'s, $ i \ge 0$, and denote $a_i$ by $r^i_m(a)$. Unless indicated otherwise, we will always make this choice when we write an $m$-adic fraction expansion of a real number. For an integer sequence $x \in \S(N), x=(x_0, x_1, \cdots, x_i, \cdots)$, we also denote in form by $r_m(x)$ the $m$-adic fraction $$ r_m(x)=\sum^{+\infty}_{i=0} \frac{x_i}{m^{i+1}} \ , ~~\mbox{where} \ m \ge N. $$ For $ a, b \in I,$ let \begin{eqnarray*} d_0(a, b) & = & |a-b|, \\ d_1(a, b) & = & \sum^{+\infty}_{i=0}\frac{1}{2^i}|r^i_2(a)-r^i_2(b)|, \end{eqnarray*} and denote by $I_k$ the metric space $(I, d_k),\ k=0,1.$ Define the metric $\r_k$ on $\S(I_k)$ as $$ \r_k(x,y)=\sum^{+\infty}_{i=0} \frac{1}{2^i} \frac{d_k(x_i,y_i)}{1+d_k(x_i,y_i)}, \ \ k=0,1. $$ The lemmas below are necessary for the proof of the theorems in the following sections. \begin{lem} \label{lem_metric} Suppose $x=(x_0, x_1,\cdots,x_i, \cdots), y=(y_0, y_1,\cdots,y_i, \cdots) \in \S(X)$, then \begin{eqnarray*} \r(x,y) < \frac{1}{2^{2N+1}} ~~ & \Longrightarrow &~~ d(x_i, y_i)< \frac{1}{2^N},~\forall ~i \le N;\\ \mbox{For}~ \d > 0, ~d(x_i, y_i)< \d,~\forall ~i \le N ~~ & \Longrightarrow &~~ \r(x,y) < 2 \d+ \frac{1}{2^N}. \end{eqnarray*} \end{lem} \proof Otherwise, if there exists $i_0\le N,$ such that $d(x_{i_0}, y_{i_0})\ge 1/2^N, $ then $$ \r(x, y)\ge \frac{1}{2^{i_0}}\frac{\frac{1}{2^N}}{1+\frac{1}{2^N}}\ge \frac{1}{2^N}\frac{1}{1+2^N}\ge \frac{1}{2^{2N+1}} ~ . $$ This is a contradiction. So we have the first inequalities. We can check directly the second inequality. \hfill $\Box$ \begin{lem} \label{lem_compact} If $A\subseteq I$ is compact in $I_1$, then $A$ is also compact in $I_0$; and if $\S\subseteq \S(I)$ is compact in $\S(I_1)$, then $\S$ is also compact in $\S(I_0)$. \end{lem} \proof $\forall a, b \in I$, $$ d_0(a, b)=|a-b|=|\sum^{+\infty}_{i=0}2^{-(i+1)}(r^i_2(a)-r^i_2(b))| \le \frac{1}{2}d_1(a, b). $$ So any limit points of $A$ in the metric $d_1$ are also limit points of $A$ in the metric $d_0$. Hence compactness of $A$ in $I_1$ implies compactness of $A$ in $I_0$. Similarly, we can check the compactness of $\S$ in $\S(I_0)$. \qed We say a subshift $(\S, \s)$ satisfies the condition (\ref{condition}) if \begin{eqnarray} \forall \ x=(x_0, x_1,\cdots ), \ y=(y_0,y_1, \cdots )\in \S, \ x=y \mbox{ if and only if } x_0 = y_0. \label{condition} \end{eqnarray} \begin{lem} \label{lem_condition} For any $(\S, \s) \le (\S(I_1), \s)$, there exists $(\S^*, \s) \le (\S(I_1), \s)$ such that $\s|_{\S} \sim \s|_{\S^*}$, and $(\S^*, \s)$ satisfies the condition (\ref{condition}). \end{lem} \proof $\forall \x \in \S, \x=(\x_0, \x_1, \cdots, \x_i, \cdots). $ Rewrite $\x_i$ by $$ \x_i=r_2(\x_i)=\sum^{+\infty}_{j=0} \frac{\x_{ij}}{2^{j+1}}, \ \ i=0, 1, \cdots. $$ Let \begin{eqnarray*} r(\x)&=& 0.\x_{00}\x_{10}\x_{01}\cdots\x_{k0}\x_{k-1,1}\cdots\x_{1,k-1}\x_{0k} \cdots \ \ \ \mbox{(binary fraction),}\\ R(\x)&=& (r(\x), r(\s(\x)), \cdots, r(\s^k(\x)), \cdots). \end{eqnarray*} {}From $R(\x)=R(\e)$ we have $r(\x)=r(\e)$, thus $\x_{ij}=\e_{ij} \ , \ i,j=0,1, \cdots.$ As a result, $\x=\e$, that is, $R$ is one-to-one. Whenever $\x, \e \in \S$ with $\r_1(\x, \e)<1/2^{2N+1}$, from Lemma~\ref{lem_metric} we have $d_1(\x_i, \e_i)<1/2^N, i\le N.$ So $\x_{ij}=\e_{ij} \ , \ i,j\le N$. Denote \begin{eqnarray*} r(\x)&=&\sum^{+\infty}_{k=0}2^{-(k+1)}(r(\x))_k \ , \\ r(\e)&=&\sum^{+\infty}_{k=0}2^{-(k+1)}(r(\e))_k \ , \end{eqnarray*} we have \begin{eqnarray*} (r(\x))_k&=& (r(\e))_k \ , \ \ k\le \frac{1}{2}(N+1)(N+2),\\ (r(\s(\x)))_k&=& (r(\s(\e)))_k \ , \ \ k\le \frac{1}{2}N(N+1),\\ & \cdots &\\ (r(\s^l(\x)))_k&=& (r(\s^l(\e)))_k \ , \ \ l\le N, \ k\le \frac{1}{2}(N+1-l)(N+2-l),\\ & \cdots & \end{eqnarray*} Take $N=2M.$ Denote $N_l=\frac{1}{2}(N+1-l)(N+2-l)$. Then for $l\le M$, we have \begin{eqnarray*} d_1(r(\s^l(\x)), r(\s^l(\e)))&=&\sum^{+\infty}_{k=0}\frac{1}{2^k} |(r(\s^l(\x)))_k-(r(\s^l(\e)))_k|\\ & \le &\sum^{+\infty}_{k=N_l+1}\frac{1}{2^k}=\frac{1}{2^{N_l}}\le 2^{-\frac{1}{2}(M+1)(M+2)}<\frac{1}{2^M} \ , \end{eqnarray*} therefore $$ \r_1(R(\x), R(\e))\le \sum^{M}_{l=0}\frac{1}{2^l}\frac{2^{-M}}{1+2^{-M}} +\frac{1}{2^M}<\frac{3}{2^M} \ , $$ which implies that $R: \S \to R(\S)$ is continuous. Take $\S^*=R(\S)$. Let $\tilde \x, \tilde \e \in\S^*$, then $\exists~ \x, \e \in \S,$ such that \begin{eqnarray*} \tilde \x &=& (r(\x), r(\s(\x)), \cdots, r(\s^k(\x)), \cdots),\\ \tilde \e &=& (r(\e), r(\s(\e)), \cdots, r(\s^k(\e)), \cdots) \end{eqnarray*} Let $N=\frac{1}{2} (2k+1)(2k+2)$, when $$ \r_1 (\tilde \x, \tilde \e)< \frac{1}{2^{2N+1}}, $$ from Lemma~\ref{lem_metric} we have $$ d_1(r(\s^i(\x)), r(\s^i(\e))) < \frac{1}{2^N}, ~ i \le N. $$ We get $\x_{ij}=\e_{ij}, ~i \le k,~j\le 2k$, and therefore $d_1(\x_i, \e_i) \le \frac{1}{2^{2k}},~i \le k$. Again from Lemma~\ref{lem_metric} we have $$ \r_1(R^{-1}(\tilde \x),R^{-1}(\tilde \e)) < \frac{1}{2^{2k-1}}+\frac{1}{2^k}. $$ Therefore $R^{-1}: \S^* \to \S$ is also continuous, hence $R$ is a homeomorphism. And $\forall \x \in \S,$ $$ R\s (\x)=(r(\s (\x )), r(\s ^2(\x )), \cdots, r(\s ^k(\x )), \cdots)=\s R(\x ), $$ so $\s|_{\S} \sim \s|_{\S^*}$, while the subshift $(\S^*, \s)$ satisfies the condition (\ref{condition}). \hfill $\Box$ \begin{lem} \label{lem_factor} The full shift $(\S(I_1), \s)$ is a faithful representation of $(\S(I_0), \s)$. And $\forall ~(\S, \s) \le (\S(I_1), \s)$ with $\S$ compact, there exists a subshift $(\S', \s) \le (\S(I_0), \s)$, such that $\s|_{\S} \sim \s|_{\S'}$. \end{lem} \proof $\forall a,b \in [0, 1]$, $$ d_0(a, b) \le \frac{1}{2}d_1(a, b). $$ So $\forall \x, \e \in \S(I_1)$, $$ \r_0(\x, \e)\le \r_1(\x, \e), $$ hence the identity mapping $i: \S(I_1)\rightarrow \S(I_0)$ is continuous. Moreover, the following diagram commutes: $$ \begin{array}{ccc} \S(I_1) & \mathop{\longrightarrow}\limits^{\s} & \S(I_1) \\ i\downarrow & & \downarrow i \\ \S(I_0) & \mathop{\longrightarrow}\limits^{\s} & \S(I_0) \end{array} $$ So $(\S(I_1), \s)$ is a faithful representation of $(\S(I_0), \s)$. $\forall ~ (\S, \s) \le (\S(I_1), \s)$ with $\S$ compact, $i: \S \to \S'=i(\S)=\S \subseteq \S(I_0)$ is a homeomorphism, therefore $(\S, \s)\le (\S(I_0),\s)$ and $\s|_{\S} \sim \s|_{\S'}$. \hfill $\Box$ The result in Lemma~\ref{lem_factor} can be generalized to: \begin{pro} If $(\S,\s)$ is a compact subshift of a faithful representation of $(X, f)$ under coding $h$, then $(\S, \s)$ is a conjugate representation of $(h(\S), f)$, a compact subsystem of $(X, f)$. \hfill $\Box$ \end{pro} \begin{rem} \label{rem_factor2} $ \forall f \in M(I), \ \ f|_{I_0}$ is a factor of $f|_{I_1}$. \end{rem} For the identity mapping $i: I_1 \rightarrow I_0$, from the proof of Lemma \ref{lem_factor}, we have $$ d_0(i(x), i(y))=d_0(x, y)\le \frac{1}{2}d_1(x, y), \ \ \forall x, y \in I_1 \ . $$ So $i: I_1 \rightarrow I_0$ is continuous. $\forall f \in M(I)$, it is obvious that the following diagram commutes: $$ \begin{array}{ccc} I_1 & \mathop{\longrightarrow}\limits^{f} & I_1 \\ i\downarrow & & \downarrow i \\ I_0 & \mathop{\longrightarrow}\limits^{f} & I_0 \end{array} $$ So $f|_{I_0}$ is a factor of $f|_{I_1}$. \section{Conjugate Representations} \label{conjugate} As discussed in \cite{Adler}, representing a general dynamical system by a symbolic one involves a fundamental complication: it is difficult and sometimes impossible to find a coding of a continuous one-to-one correspondence between orbits and symbolic sequences, and especially when we desire the shift system to be one of finite type and with a finite (or at most countable \cite{Fu92, Fu96, Kitchens}) alphabet. % Therefore sometimes we need either to abandon the quest of finding a % conjugate representation for a given dynamical system, or to abandon the % quest of representing only by a subshift % of finite type with a finite (or countable) alphabet. In this section, we will discuss conjugate representations of general continuous maps through general subshifts, which usually involve an uncountable alphabet. For a metric space $(X,d)$, there exists a huge number of continuous self-maps on $X$. The dynamics on $X$ is therefore diverse. The following theorem shows that the general subshifts of $(\S(X), \s)$ can be used as a unified model for all continuous self-maps on the space $X$. \begin{thm} \label{th_conj_rep} Let $(X, d)$ be a metric space, $\forall f \in C(X), \exists (\S, \s) \le (\S(X), \s)$, such that $ (\S, \s)$ is a conjugate representation of $(X, f)$. \end{thm} \proof Define a mapping $h: X \rightarrow \S(X)$ as $$ h(x)=(x, f(x), f^2 (x), \cdots, f^n (x), \cdots), $$ then $h$ is a one-to-one mapping. Since $f$ is continuous, for any positive integer $N$ and any sequence $\{ x_n\} \subset X$ with $ \lim_{n\rightarrow +\infty }x_n=x_0 \in X$, we have $$ \lim_{n\rightarrow +\infty }d(f^k(x_n), f^k(x_0))=0, \ \ k=0, 1, \cdots, N. $$ {}From \begin{eqnarray*} 0 & \le & \r(h(x_n), h(x_0))=\sum^{+\infty}_{i=0} \frac{1}{2^i} \frac{d(f^i(x_n), f^i(x_0))}{1+d(f^i(x_n), f^i(x_0))}\\ & \le & \sum^{N}_{i=0} \frac{1}{2^i} \frac{d(f^i(x_n), f^i(x_0))}{1+d(f^i(x_n), f^i(x_0))}+\sum^{+\infty}_{i=N+1} \frac{1}{2^i} \ , \end{eqnarray*} we have $$ 0 \le \lim_{n\rightarrow +\infty}\r(h(x_n), h(x_0)) \le \frac{1}{2^N} \ , \ \forall N \ge 1, $$ that is, $h: X \rightarrow \S(X)$ is continuous. Suppose we have a sequence $\{ \x^{(n)}=(\x^{(n)}_0,\x^{(n)}_1,\cdots,\x^{(n)}_i), \cdots \} \subset h(X)$ with $$ \lim_{n\rightarrow +\infty}\x^{(n)}=\e=(\e_0,\e_1,\cdots, \e_i, \cdots) \in h(X), $$ then $$ \lim_{n\rightarrow +\infty}\r(\x^{(n)}, \e)=0. $$ {}From $$ 0 \le \frac{d(\x^{(n)}_0, \e_0)}{1+d(\x^{(n)}_0, \e_0)} \le \r(\x^{(n)}, \e) \rightarrow 0 \mbox{ as } n \rightarrow +\infty, $$ we obtain $$ \lim_{n\rightarrow +\infty}d(\x^{(n)}_0, \e_0)=0. $$ So $h^{-1}: h(X)\rightarrow X$ is also continuous, and therefore $h$ is a homeomorphism from $X$ to $h(X)$. Moreover, $$ hf(x)=(f(x), f^2(x), \cdots)=\s h(x), \ \ \forall x \in X, $$ i.e., $ hf=\s h. $ Take $\S =h(X)$, then $\S $ is invariant for the shift map $\s $, and $\S $ is a closed subset of $\S (X)$. So $(\S, \s) \le (\S(X), \s)$, and $f$ is topologically conjugate to $\s|_{\S}$. \qed \begin{rem} The theorem above shows how to symbolize $(X, f)$ to $(\S, \s)$. Although the phase space of the latter may be more complex than that of the former, the map action of the latter is definitely simpler than that of the former. If we can understand the construction of the space $\S$ by some means, then the dynamics of $f$ on $X$ can be known accordingly. \end{rem} We note that the subshift $(\S, \s)$ in the proof of Theorem \ref{th_conj_rep} satisfies the condition (\ref{condition}), i.e., $$ \forall \ x=(x_0, x_1,\cdots ), \ y=(y_0,y_1, \cdots )\in \S, \ x=y \mbox{ if and only if } x_0 = y_0 $$ This is a restriction under which Theorem \ref{th_conj_rep} is reversible, as stated below. \begin{thm} \label{th_conj_rep2} Suppose $(X, d)$ is a compact metric space, $(\S, \s) \le (\S(X), \s)$, and $(\S, \s)$ satisfies condition (\ref{condition}); then there exists a compact subset $X_0 \subseteq X$, and a continuous self-map $f$ on $X_0$, such that $(\S, \s)$ is a conjugate representation of $(X_0, f)$. \end{thm} \proof Let $(\S, \s)$ be a subshift of $(\S(X), \s)$ satisfying condition (\ref{condition}). Define $\f: \S \rightarrow X$ as $$ \f((x_0, x_1,\cdots))=x_0, \ \ \forall \ (x_0, x_1,\cdots) \in \S. $$ Then $\f$ is a one-to-one mapping. Denote $\f(\S)$ by $X_0$. $\forall (x_0, x_1,\cdots), (y_0,y_1, \cdots) \in \S,$ \begin{eqnarray*} d(\f((x_0, x_1,\cdots)), \f((y_0,y_1, \cdots))) & = & d(x_0, y_0)\\ & < & (1+d(x_0, y_0))\r((x_0, x_1,\cdots), (y_0,y_1, \cdots)), \end{eqnarray*} $\forall \ep > 0, $ let $\d=\ep /(1+\ep)$, then $0 < \d < 1.$ Whenever $\r((x_0, x_1,\cdots), (y_0,y_1, \cdots)) < \d$, \begin{eqnarray*} \frac{d(x_0,y_0)}{1+d(x_0,y_0)} & < & \r((x_0, x_1,\cdots), (y_0,y_1, \cdots)) < \d, \\ d(x_0, y_0) & < & \frac{\d}{1-\d}, \\ d(\f((x_0, x_1,\cdots)), \f((y_0,y_1, \cdots))) & < & (1+\frac{\d}{1-\d})\d=\ep, \end{eqnarray*} so $\f: \S \rightarrow X_0$ is continuous. Since $X$ is compact, $\S(X)$ is also compact and so is $\S$. As a result, $\f: \S \rightarrow X_0$ is a homeomorphism and hence $X_0 \subseteq X$ is compact. Take $f: X_0 \rightarrow X_0 $ as $f=\f \s \f^{-1}$, then $f$ is continuous, and $f|_{X_0} \sim \s|_{\S}$. \qed Naturally, one would like to ask if Theorem \ref{th_conj_rep2} still holds for subshifts $(\S, \s)$ which don't satisfy the condition (\ref{condition})? The answer is yes if one can construct another subshift $(\S^*, \s)$ such that $(\S, \s) \sim (\S^*, \s)$, and $(\S^*, \s)$ satisfies the condition (\ref{condition}). This can be done at least for one-dimensional self-maps, as shown in the following example. \vspace{0.3cm} \noindent {\sc Example} \ Let $X=[0, 1], d(x,y)=|x-y|, \S=\S(2)=\{(x_0, x_1, \cdots, x_i, \cdots): x_i=0, 1, i \ge 0 \}$. Take $\S^*=R(\S)=\{R(x): x \in \S \}$, where $R: \S \rightarrow \S(X)$ is defined as \begin{eqnarray*} R(x) & = & (r_{10}(x), r_{10}(\s(x)), \cdots, r_{10}(\s^k(x)), \cdots),\\ r_{10}(x)& = & 0.x_0x_1 \cdots x_k \cdots \ \ \mbox{(decimal fraction)}, \forall x=(x_0, x_1, \cdots, x_k, \cdots) \in \S, \end{eqnarray*} then it can be verified (see Remark~\ref{rem_embed} in Section~\ref{quasi} for detail) that $R: \S \rightarrow \S^*$ is a topological conjugacy. So $\s|_{\S} \sim \s|_{\S^*}$, while $(\S^*, \s)$ satisfies the condition (\ref{condition}). \vspace{0.3cm} In the following theorem, we reach a more general conclusion for the case of $X=[0,1]$. That is, when $X=[0,1]$, Theorem \ref{th_conj_rep2} holds for all subshifts $(\S, \s)\le (\S(I_0), \s)$ with $\S$ compact in $(\S(I_1), \s)$, regardless of the condition (\ref{condition}). \begin{thm} \label{th_symb_rep} $\forall ~ (\S, \s) \le (\S(I_0), \s)$ with $\S$ compact in $\S(I_1)$, there exists an $f \in C(I_0)$ and $\L \subseteq I_0$ with $\L$ compact and invariant for $f$, such that $(\S, \s)$ is a conjugate representation of $(\L, f)$. \end{thm} \proof Since $\S$ is compact in $\S(I_1)$, $(\S, \s)$ is also a subshift of $(\S(I_1), \s)$. {}From Lemma \ref{lem_condition}, there exists a subshift $(\S^*, \s)$ of $(\S(I_1), \s)$ with $\S^*$ also compact, such that $\s|_{\S} \sim \s|_{\S^*}$, and $(\S^*, \s)$ satisfies the condition~(\ref{condition}). {}From Lemma~\ref{lem_factor}, $(\S^*, \s)$ is also a subshift of $(\S(I_0), \s)$ satisfying the condition~(\ref{condition}) {}Similar to the proof of Theorem \ref{th_conj_rep2}, it can be shown that there exists a compact subset $\L \subseteq I_0$, and a continuous self-map $f$ on $\L$ such that $(\S^*, \s)$ is a conjugate representation of $(\L, f)$, a subsystem of $(I_0, f)$. Therefore $(\S, \s)$ is a conjugate representation of $(\L, f)$. \qed Putting Theorem \ref{th_conj_rep} and Theorem \ref{th_symb_rep} together, we have the following representation theorem for one-dimensional continuous self-maps. \begin{thm} \label{th_rep} $\forall f \in C(I_0), \exists (\S, \s)\le (\S(I_0), \s)$, such that $(\S, \s)$ is a conjugate representation of $(I_0, f)$; conversely, $\forall (\S, \s) \le (\S(I_0), \s)$ with $\S$ compact in $\S(I_1), \exists f \in C(I_0)$ and $\L \subseteq I_0$, where $\L$ is compact and invariant for $f$, such that $(\S, \s)$ is a conjugate representation of $(\L, f)$. \hfill $\Box$ \end{thm} \section{The Second Order Representations}\label{sec_second} Theorem \ref{th_conj_rep} indicates that $\forall f \in C(X), (X, f)$ can be embedded in $(\S(X), \s)$, denoted by $(X, f)\hookrightarrow (\S(X), \s)$. This embedding relation means that the system $(X, f)$ may be represented by a subshift of $(\S(X), \s)$. Naturally, one may further consider the representation of the system $(\S(X), \s)$ itself. To do so, one can regard $\S(X)$ as a symbol space and denote by $\S^2(X)$ the symbol sequence space $\S(\S(X))$, i.e., $$ \S^2(X)=\{x=(x_0, x_1, \cdots, x_i, \cdots): x_i\in \S(X), i\ge 0 \}. $$ We specify a metric $\r^{(2)}$ on $\S^2(X)$ by $$ \r^{(2)}(x, y)=\sum^{+\infty}_{k=0} \frac{1}{2^k} \frac{\r(x_k, y_k)}{1+\r(x_k, y_k)}, $$ where $\r$ is the metric on $\S(X)$. We denote by $\s_2$ the shift map on $\S^2(X)$, and if no confusion caused, we also denote by $\s$ the shift map on $\S^2(X)$. And so we get a general symbolic dynamics system $(\S^2(X), \s)$. Similarly, we can define general symbolic dynamics system $(\S^k(X), \s_k)$ (or denote by $(\S^k(X), \s)$ if no confusion caused) for $k\ge 3,$ and call it the $k$-th order symbolic representation of dynamics on $X$. For higher order symbolic sequence spaces, we have the following general result. \begin{thm} \label{th_homeo} Suppose $(X, d)$ is a metric space. Then $\S^2(X)$ is homeomorphic to $\S(X)$. In general, for $k\ge 2,~ \S^k(X)$ is homeomorphic to $\S^{k-1}(X)$. \end{thm} \proof For $\tilde x, \tilde y \in \S^2(X)$, denote \begin{eqnarray*} \tilde x = (\tilde x_0, \tilde x_1, \cdots,\tilde x_i, \cdots), \ \ \tilde y = (\tilde y_0, \tilde y_1, \cdots,\tilde y_i, \cdots); \end{eqnarray*} and \begin{eqnarray*} \tilde x_i = (x_{i0}, x_{i1}, \cdots, x_{ij}, \cdots), \ \ \tilde y_i = (y_{i0}, y_{i1}, \cdots, y_{ij}, \cdots), \end{eqnarray*} where $x_{ij}, y_{ij} \in X$. Define $h: \S^2(X) \to \S(X)$ as: $$ h(\tilde x) = (x_{00}x_{10}x_{01} \cdots x_{i0}x_{i-1,1}\cdots x_{1,i-1}x_{0i}\cdots), $$ then $h$ is one-to-one and onto. When $$ \r^{(2)}(\tilde x , \tilde y) < \frac{1}{2^{2(2N+1)+1}}, $$ from Lemma~\ref{lem_metric}, we have $$ \r(\tilde x_i, \tilde y_i) < \frac{1}{2^{2N+1}}, ~ i \le 2N+1, $$ therefore $d(x_{ij}, y_{ij}) < 2^{-N}, ~ i\le 2N+1,~ j\le N$, so we get $$ \r(h(\tilde x), h(\tilde y)) < \frac{1}{2^{N-1}} + \frac{1}{2^{N_1}}, $$ where $N_1= \frac{1}{2} (N+1)(N+2) + N+1$. On the other hand, let $x=(x_0x_1 \cdots x_k \cdots), y=(y_0y_1 \cdots y_k \cdots) \in \S(X)$, when $\r(x,y)< 2^{-(2N+1)}$, where we suppose $N=\frac{1}{2} (2k+1)(2k+2)$, we have $d(x_i, y_i)< 2^{-N}, ~ i \le N$. Let \begin{eqnarray*} h^{-1}(x)=\tilde x = (\tilde x_0, \tilde x_1, \cdots,\tilde x_i, \cdots), & & \tilde x_i=(x_{i0}, x_{i1}, \cdots, x_{ij}, \cdots),\\ h^{-1}(y)=\tilde y = (\tilde y_0, \tilde y_1, \cdots,\tilde y_i, \cdots), & & \tilde y_i = (y_{i0}, y_{i1}, \cdots, y_{ij}, \cdots), \end{eqnarray*} then $d(x_{ij}, y_{ij}) < 2^{-N}, ~ i+j \le 2k+1$, therefore $d(x_{ij}, y_{ij}) < 2^{-N}, ~ i\le k,~ j \le k$. This implies $\r(\tilde x_i, \tilde y_i) < 2^{1-N} + 2^{-k},~i \le k$, therefore $\r^{(2)}(\tilde x, \tilde y)< 2^{2-N}+2^{1-k} + 2^{-k}$, i.e., we have $$ \r^{(2)}(h^{-1}(x), h^{-1}(y)) < \frac{1}{2^{N-2}} + \frac{1}{2^{k-1}} + \frac{1}{2^{k}}. $$ Hence both $h$ and $h^{-1}$ are continuous, and therefore $\S^2(X)$ is homeomorphic to $\S(X)$. Similarly, we can check that for $k\ge 2,~ \S^k(X)$ is homeomorphic to $\S^{k-1}(X)$. \qed On the other hand, define $\f: \S(X)\rightarrow \S^2(X)$ as $$ \f(x)=(x, \s(x), \cdots, \s^k(x), \cdots), $$ then if $X$ is compact, $\f$ can be verified to be a topological conjugacy from $\S(X)$ to $\f(\S(X))\subseteq \S^2(X)$. So $(\S(X), \s)\hookrightarrow (\S^2(X), \s)$. In general, for a compact metric space $X$, we have the following embedding sequence: \begin{eqnarray} (X, f)\hookrightarrow (\S(X), \s)\hookrightarrow (\S^2(X), \s)\hookrightarrow \cdots \hookrightarrow (\S^k(X), \s)\hookrightarrow \cdots \label{3.1} \end{eqnarray} That's why we discuss the higher order representations. And the topic is also motivated by Nasu (\cite{Nasu}) and is helpful to study maps in symbolic dynamics discussed in \cite{Nasu}, as well. %If there exists $k>1$ such that $(\S^{k-1}(X), \s)\sim (\S^k(X), \s)$, then % the embedding sequence~(\ref{3.1}) will be finite, because of the following % result. % %\begin{thm} \label{th_high-order} %Suppose $X$ is a compact metric space. If there exists $k>1$ such that %$(\S^{k-1}(X), \s)\sim (\S^k(X), \s)$, then $(\S^n(X), \s)\sim (\S^{n+1}(X), %\s), \forall n \ge k-1.$ %\end{thm} %\proof %With the above conditions, there exists a homeomorphism $\f: %\S^{k-1}(X)\rightarrow \S^k(X)$ that satisfies %$ %\f \s_{k-1}=\s_{k}\f. %$ %Define $\p: \S^k(X)\to \S^{k+1}(X)$ as %$$ %\p((x_0, x_1, \cdots, x_i, \cdots))=(\f(x_0), \f(x_1), \cdots, \f(x_i), %\cdots),\ \ x_i\in \S^{k-1}(X), \ \ i=0, 1, \cdots, %$$ %then $\p: \S^k(X)\rightarrow \S^{k+1}(X)$ is one-to-one, onto, and continuous, %and therefore is a homeomorphism. % %It is obvious that $\p\s_{k}=\s_{k+1}\p$. So $\s|_{\S^k(X)}\sim %\s|_{\S^{k+1}(X)}.$ And thus $(\S^n(X), \s)\sim (\S^{n+1}(X), \s), \forall n %\ge k-1.$ %\qed As we discussed earlier that $(X, f)\hookrightarrow (\S(X), \s)$ shows a transformation between dynamics on $X$ and subshifts structure in $(\S(X), \s), (\S^k(X), \s)\hookrightarrow (\S^{k+1}(X), \s)$ indicates that the subshifts structure in $(\S^k(X), \s)$ can be transformed to the subshifts structure in $(\S^{k+1}(X), \s)$. In other words, the symbolic dynamics system $(\S^k(X), \s)$, and its subshifts, can be further represented by the one order higher symbolic dynamics system $(\S^{k+1}(X), \s)$. If the embedding sequence (\ref{3.1}) is finite, then the above transformation or representations will not go on without limit. This means that the piling up of symbol sequence spaces $\S^k(X)$ will not cause an unlimited increase of the complexity of the corresponding shift systems. In particular, if we have $(\S(X), \s)\sim (\S^2(X), \s)$, then $(\S(X), \s)$ is an ultimate (or final) representation. We may ask under what conditions does $(\S(X), \s)\sim (\S^2(X), \s)$ hold? We have the following theorems. \begin{thm} \label{th_iff} $(\S^2(X), \s)$ is topologically conjugate to $(\S(X), \s)$ if and only if $\S(X)$ is homeomorphic to $X$. In general, for $k\ge 1,~(\S^{k+1}(X), \s)\sim (\S^k(X), \s)$ if and only if $\S^k(X)$ is homeomorphic to $\S^{k-1}(X)$. \end{thm} \proof Suppose $\a: \S(X)\to X$ is a homeomorphism. Define $\f: \S^2(X)\to \S(X)$ as: $$ \f(\x)=(\a(\x_0),\a(\x_1),\cdots,\a(\x_k),\cdots), ~ \x=(\x_0,\x_1,\cdots,\x_k,\cdots) \in \S^2(X), $$ then $\f$ is a homeomorphism, and $\f \s_2 =\s \f$. Therefore $(\S^2(X), \s)\sim (\S(X), \s)$. Conversely, let $\f: \S^2(X)\to \S(X)$ is a topological conjugacy. $\forall ~ x \in \S(X)$, denote $\tilde x = (x,x,\cdots,x,\cdots)$, then $\tilde x$ is a fixed point of $\s_2$ in $\S^2(X)$. Since $\s_2 \sim \s$, $\f(\tilde x)$ is also a fixed point of $\s$ in $\S(X)$. So $\exists ~ x^* \in X$, such that $\f(\tilde x)=(x^*,\cdots, x^*, \cdots)$. Define $\a: \S(X)\to X$ as: $\a(x)=x^*$. Then $\a$ is a homeomorphism. Similarly, we can prove the general case of the Theorem. \qed {}From Theorems~\ref{th_homeo}~and~\ref{th_iff}, the following corollary is immediate: \begin{cor} \label{cor_3-rep} Suppose $(X, d)$ is a metric space, then we always have $$ (\S^k(X), \s)\sim (\S^2(X), \s),~\forall ~ k \ge 3. $$ \hfill $\Box$ \end{cor} So the embedding sequence~(\ref{3.1}) is finite, and the third or higher order representations are therefore not necessary. The following results show that we further have $(\S(X), \s)\sim (\S^2(X), \s)$ when $X=I_1$. \begin{thm} \label{th_high-order2} $(\S(I_1), \s)$ is topologically conjugate to $(\S^2(I_1), \s)$, i.e., $(\S(I_1), \s)\sim (\S^2(I_1), \s)$. \end{thm} \proof $\forall (x_0, x_1, \cdots, x_k, \cdots)\in \S^2([0, 1])$, where $$ x_i\in \S([0, 1]), \ x_i=(a_0^{(i)},a_1^{(i)}, \cdots, a_k^{(i)}, \cdots), \ a_k^{(i)} \in [0, 1], \ i\ge 0,\ k\ge 0. $$ Rewrite $a_k^{(i)}$ by $$ a_k^{(i)}=r_2(a_k^{(i)})=\sum^{+\infty}_{j=0}2^{-(j+1)}a_{kj}^{(i)} \ , \ \ i,k\ge 0, $$ then define $\a: \S([0, 1])\rightarrow [0, 1]$ as: $$ \a(x_i)=\sum^{+\infty}_{l=0}\displaystyle\sum^l_{{j=0 \atop k+j=l}\atop k\ge 0}2^{-(\frac{1}{2}l(l+1)+j+1)}a^{(i)}_{kj} \ , \ \ i\ge 0, $$ So $\a(x_i)$ is also a binary fraction. Further, $\a: \S([0, 1])\rightarrow [0, 1]$ is a one-to-one and onto mapping. Choose $d_1$ as the metric on $[0, 1]$, and correspondingly $\r_1$ as the metric on $\S([0, 1])$. Then $\forall x_i, y_i \in \S(I_1)$, \begin{eqnarray*} x_i = (a^{(i)}_0, a^{(i)}_1, \cdots, a^{(i)}_k, \cdots), \ \ y_i = (b^{(i)}_0, b^{(i)}_1, \cdots, b^{(i)}_k, \cdots), \end{eqnarray*} rewrite $a^{(i)}_k$ and $b^{(i)}_k$ as \begin{eqnarray*} a^{(i)}_k &=& r_2(a_k^{(i)}) = \sum^{+\infty}_{j=0}2^{-(j+1)}a_{kj}^{(i)} \ ,\\ b^{(i)}_k &=& r_2(b_k^{(i)}) = \sum^{+\infty}_{j=0}2^{-(j+1)}b_{kj}^{(i)} \ . \end{eqnarray*} Whenever $$ \r_1(x_i, y_i)< \frac{1}{2^{2N+1}}, $$ we have $$ d_1(a^{(i)}_k, b^{(i)}_k)< \frac{1}{2^N}, \ \ k\le N, $$ therefore $$ a_{kj}^{(i)}=b_{kj}^{(i)}, \ \ k\le N, \ j\le N-1. $$ So we have $$ d_1(\a(x_i), \a(y_i))\le 2^{1-\frac{1}{2}N(N+1)}, $$ namely, $\a: \S(I_1)\rightarrow I_1$ is continuous. Similarly, we can check that $\a^{-1}: I_1 \to \S(I_1)$ is also continuous. Hence $\S([0, 1])$ is homeomorphic to $[0, 1]$. From Theorem~\ref{th_iff} we have $$ (\S(I_1), \s)\sim (\S^2(I_1), \s). $$ The Theorem is proved. \qed We may ask if we also have $(\S(I_0), \s)\sim (\S^2(I_0), \s)$? We guess this is not true but only have: \begin{pro} $(\S(I_1), \s)$ is a faithful representation for both $(\S(I_0), \s)$ and \\ $(\S^2(I_0), \s)$. \end{pro} \proof {}From Lemma \ref{lem_factor}, $(\S(I_1), \s)$ is a faithful representation of $(\S(I_0), \s)$. Since $d_0(\a, \b)\le \frac{1}{2}d_1(\a, \b), \ \ \forall \a, \b \in [0, 1]$, we have \begin{eqnarray*} \r_0(a, b)& \le & \r_1(a, b), \ \ \forall a, b \in \S([0, 1]),\\ \r^{(2)}_0(x, y)& \le & \r^{(2)}_1(x, y), \ \ \forall x, y \in \S^2([0, 1]). \end{eqnarray*} Similar to the proof of Lemma \ref{lem_factor}, we can prove that $(\S^2(I_1), \s)$ is topologically semi-conjugate to $(\S^2(I_0), \s)$ under the identity mapping $i: \S^2(I_1)\rightarrow \S^2(I_0)$. Therefore $(\S^2(I_1), \s)$ is a faithful representation of $(\S^2(I_0), \s)$. So $(\S(I_1), \s)$ is a faithful representation for both $(\S(I_0), \s)$ and $(\S^2(I_0), \s)$. \qed Note that from Theorem~\ref{th_iff}, $$ (\S^2(N), \s) \nsim (\S(N), \s). $$ We suspect that $$(\S^2(I_0), \s) \nsim (\S(I_0), \s). $$ And we also suspect in most circumstances $$ (\S^2(X), \s) \nsim (\S(X), \s). $$ So it is very necessary to study the second order representations. $(\S^2(N), \s) \nsim (\S(N), \s)$ also means that shift maps with a finite or countable alphabet is not sufficient for the study of symbolic representations of dynamical systems, and so it is necessary to study symbolic dynamics with an uncountable alphabet. \section{Quasi-Representations} \label{quasi} While we have shown the existence of the topological conjugacy between a one-dimensional map and a subshift of a symbolic dynamics system, in practice it is often difficult to construct such conjugacy for applications. Instead, it may be easier to find a topological semi-conjugacy, which sometimes is sufficient for the problems under investigation. In this section we discuss quasi-representations of one-dimensional dynamical systems. The symbolic dynamics system $(\S(I), \s)$ is an extension of the usual symbolic dynamics system $(\S(N), \s)$. Equip $\S(N)$ with a metric $\r$ as follows: $$ \r(x, y)=\sum^{+\infty}_{i=0} \frac{1}{2^i} \frac{|x_i-y_i|}{1+|x_i-y_i|}. $$ Take from $I_1$ a convergent sequence $\{a_k\}$ with the limit $a \in I_1$, where $a_i \ne a_j,~ \forall~ i\ne j$. Let \begin{eqnarray*} S_{\infty} & = & \{a_1,a_2, \cdots, a\}, \\ \S_{\infty} & = & \{(x_0, x_1, \cdots) \in \S(I_1): x_i \in S_{\infty}, i \ge 0\}, \end{eqnarray*} then $\S_{\infty}$ is compact in $\S(I_1)$, and $(\S_{\infty}, \s)\le (\S(I_0), \s)$. From Theorem \ref{th_symb_rep}, $\exists f \in C(I_0)$ and $\L \subseteq I_0, \L $ is compact and invariant for $f$, such that $f|_{\L} \sim \s|_{\S_{\infty}}$. $\forall (\S, \s) \le (\S(N), \s)$, we have $$ {h_{\rm top}}(\s|_{\S}) \le {h_{\rm top}}(\s|_{\S(N)})=\log N \ne{h_{\rm top}}(\s|_{\S_{\infty}})=+\infty, $$ So $\s|_{\S} \not\sim \s|_{\S_{\infty}}$, and $f|_{\L} \not\sim \s|_{\S}$. Therefore the following result is obvious: \begin{thm} \label{th_not_conj} There exists an $f \in C(I_0)$, such that $\forall (\S, \s) \le (\S(N), \s), f|_{\L} \not\sim \s|_{\S}$, where $\L \subseteq I_0$ is a closed invariant subset for $f$. \hfill $\Box$ \end{thm} Theorem \ref{th_not_conj} indicates once again that the scope of application for $(\S(N), \s)$ is quite limited. So it is necessary to study its extensions, such as $(\S(I_0), \s)$, etc. Nevertheless, the system $(\S(N), \s)$ still has its special significance. For example, $(\S(N), \s)$ can be used effectively to characterize the dynamics of multimodal one-dimensional maps (see \cite{Hao89} and the references therein). The significance of $(\S(N), \s)$ can also be shown by the following theorem. \begin{thm} \label{th_quasi} $\forall f \in C(I_0), \exists (\S, \s) \le (\S(N), \s), N \ge 2,$ such that $(\S, \s)$ is a quasi-representation of $(I_0, f)$. \end{thm} \proof First, we prove $(\S(I_0), \s)$ is topologically semi-conjugate to $(\S(N), \s)$. Let $$ [0, 1]=\bigcup^{N-1}_{k=0}A_k, \ \ \mbox{where}\ A_0=[0, \frac{1}{N}], A_k=(\frac{k}{N}, \frac{k+1}{N}], \ k=1, 2, \cdots, N-1. $$ Define $\a: [0, 1]\rightarrow \{0, 1, \cdots, N-1\}$ as $\a(a)=k, \ a\in A_k.$ And define $\f: \S(I_0) \to \S(N)$ as: $$ \f((x_0, x_1, \cdots, x_k, \cdots))=(\a(x_0), \a(x_1), \cdots, \a(x_k), \cdots). $$ Then $$ |\a(x_i)-\a(y_i)|=|k-l|, \ \ x_i \in A_k, \ y_i\in A_l. $$ If $k\ne l$, we have $$ \frac{1}{N}\le |x_i-y_i|\le 1, \ \ 1\le |\a(x_i)-\a(y_i)|\le N-1, $$ therefore $$ \frac{|\a(x_i)-\a(y_i)|}{1+|\a(x_i)-\a(y_i)|} < N^2 \frac{|x_i-y_i|}{1+|x_i-y_i|}. $$ If $k=l$, it is obvious that $$ \frac{|\a(x_i)-\a(y_i)|}{1+|\a(x_i)-\a(y_i)|}\le N^2 \frac{|x_i-y_i|}{1+|x_i-y_i|}. $$ So $\r(\f(x), \f(y))\le N^2\r_0(x, y)$, thus $\f$ is continuous. $\f$ is also surjective. And the following diagram commutes: $$ \begin{array}{ccc} \S(I_0) & \mathop{\longrightarrow}\limits^{\s} & \S(I_0) \\ \f \downarrow & & \downarrow \f \\ \S(N) & \mathop{\longrightarrow}\limits^{\s} & \S(N) \end{array} $$ So we have proved that $(\S(I_0), \s)$ is topologically semi-conjugate to $(\S(N), \s)$. $\forall f\in C(I_0)$, there exists $(\S^*, \s)\le (\S(I_0), \s)$ such that $f|_{I_0}\sim \s|_{\S^*}$. Denote the topological conjugacy by $\p$. Then we can define $\l: I_0 \rightarrow \f(\S^*)$ as $\l=\f\p$, $$ \begin{array}{rcccc} I_0 &\mathop{\longrightarrow}\limits^{\p}& \S^* & \mathop{\longrightarrow}\limits^{\f} & \f(\S^*) \\ f\downarrow & & \downarrow \s& & \downarrow \s\\ I_0 & \mathop{\longrightarrow}\limits^{\p} & \S^*& \mathop{\longrightarrow}\limits^{\f}& \f(\S^*) \end{array} $$ So $\l$ is a continuous and onto map, and $\l f=\s \l.$ Since $\s(\S^*)\subseteq \S^*, \s(\f(\S^*))\subseteq \f(\S^*)$. So $\f(\S^*)$ is invariant for $\s.$ $\S^*$ is closed, $\S(I_0)$ is compact, so $\f(\S^*)$ is closed. So $(\f(\S^*), \s) \le (\S(N), \s)$. Take $\S=\f(\S^*)$, then $f|_{I_0}$ is topologically semi-conjugate to $\s|_{\S}.$ \qed {}From the above discussions, we have the following remarks. \vspace{0.3cm} \begin{rem} $\exists (\S^*, \s)\le (\S(I_0), \s)$, such that $\forall (\S, \s)\le (\S(N), \s), \s|_{\S}\not\sim \s|_{\S^*}$. \end{rem} \begin{rem} $(\S(N), \s)$ is a factor of $(\S(M), \s)$ when $M>N$. And $(\S(N), \s)$ is a factor of $(\S(I_0), \s)$. \end{rem} \begin{rem} \label{rem_embed} $(\S(N), \s)$ can be embedded in $(\S(I_0), \s)$, i.e., $\exists (\S, \s)\le (\S(I_0), \s)$, such that $\s|_{\S(N)}\sim \s|_{\S}$ \ , where $N \ge 2.$ \end{rem} In fact, the subshift $\S$ may be chosen as: $\S=R_N(\S(N))$, where \begin{eqnarray*} R_N(x) & = & (r_N(x), r_N(\s(x)), \cdots, r_N(\s^k(x)), \cdots),\\ r_N(x)& = & \sum^{+\infty}_{i=0} \frac{x_i}{N^{i+1}}, \ \forall x=(x_0, x_1, \cdots)\in \S(N). \end{eqnarray*} Then if $R_N(x)=R_N(y)$, we have $\forall k \ge 0,$ \begin{eqnarray*} r_N(\s^k(x))&=&r_N(\s^k(y)),\\ r_N(\s^{k+1}(x))&=&r_N(\s^{k+1}(y)), \end{eqnarray*} These imply $x_k=y_k, \forall k \ge 0.$ So $x=y$, and $R_N: \S(N)\rightarrow \S$ is a one-to-one mapping. When $x, y \in \S(N)$ and $\r(x, y)<1/2^{M+1}$, we have $x_i=y_i, \ i=0, 1, \cdots, M.$ So $$ |r_N(\s^k(x))-r_N(\s^k(y))|\le \sum^{+\infty}_{i=M-k+1} \frac{|x_{k+i}-y_{k+i}|}{N^{i+1}}<\frac{1}{N^{M-k}}, \ 0\le k\le M. $$ Therefore $$ \r_0(R_N(x), R_N(y))\le \sum^{M}_{k=0}\frac{1}{2^k}\frac{1}{N^{M-k}+1}+\sum^{+\infty}_{k=M+1} \frac{1}{2^k}. $$ Since $N\ge 2, \ \ 1/N\le 1/2$, $$ \r_0(R_N(x), R_N(y))<\frac{M+2}{2^M}. $$ So $R_N$ is continuous, and therefore is a homeomorphism. It is obvious that $R_N\s|_{\S(N)}=\s|_{\S}R_N.$ So $\s|_{\S(N)}\sim \s|_{\S}$. So we have the result in Remark~\ref{rem_embed} \section{Partitions and Representations} \label{partition} In Section~\ref{quasi} quasi-representations of one-dimensional dynamical systems are discussed. From the proof of Theorem~\ref{th_quasi}, when the whole interval (phase space) is divided into some smaller pieces, and code each piece with a symbol, then we get a quasi-representation of the original system. This shows a direct connection between partitions and representations. Partitions are natural ways to associate a symbolic sequence with an orbit by tracking its history. As pointed out in \cite{Adler}, in order to get a useful symbolism, one needs to construct a partition with special properties. For example, when a partition is Markov, the sysytem can be represented by a subshift of finite type. Some hyperbolic systems, such as Anosov systems, axiom A systems, psuedo-Anosov systems, and hyperbolic automorphisms on $n$-tori, $n \ge 2$, admit Markov partitions. However, for non-hyperbolic systems, there may be no Markov partitions. Therefore other than Markov partitions, some more general partitions for these systems need to be used, so that if a certain kind of partition exists for a non-hyperbolic system, the system then can be represented by a subshift of infinite type. In this section we generalize some concepts and main results discussed in \cite{Adler}. The discussion below are for dynamical systems $(X, \f)$, where $X$ is a compact metric space with metric $ d ( \cdot \, , \cdot ) $ and $\f $ is a homeomorphism of $X$ onto itself. \begin{defn} \label{defn_top_part} A finite or countable family of subsets $\MR = \{ R_{i}, i \in \MI \}$ is called a {\em topological partition} for a dynamical system $(X, \f)$ if: {\rm (1)} each $R_{i}$ is open; {\rm (2)} $R_{i} \cap R_{j} = \varnothing , i \ne j $; {\rm (3)} $X = \bigcup_{i \in \MI}\overline{R_{i}}$; {\rm (4)} $\forall i \in \MI, \card \{k \in \MI, \f R_i \cap R_k \ne \varnothing\}< + \infty$. \end{defn} \begin{rem} Other authors have taken the sets $R_i$ to be closed sets with the property that each is the closure of its interior. The variation introduced by Adler here is slightly more general, just enough to make some notation and certain arguments simpler. In fact, there is a example of partition whose elements are not the interiors of their closures {\rm (\cite{Adler})}. \end{rem} \begin{rem} When $\card~\MI <+\infty$, then Definition~\ref{defn_top_part} coincides with the definition of topological partitions in {\rm \cite{Adler}}. \end{rem} Given two topological partitions $$ \MR = \{ R_{i}, i \in \MI_1 \} ~ \mbox{and}~ \MS = \{ S_{j}, j \in \MI_2 \}, $$ we define their {\em common topological refinement} $\MR \vee \MS $ as $$ \MR \vee \MS = \{ {R_{i} \cap S_{j}} , i \in \MI_1, \ j \in \MI_2 \} . $$ \begin{lem} For dynamical system $(X , \f )$ with topological partition $\MR$, the set $\f ^{n} \MR $ defined by $$ \f ^{n} \MR = \{ \f ^{n} R_{i}, i \in \MI \} $$ is also a topological partition; and $\forall m \le n, \bigvee _{k=m}^{n} \f ^{k} \MR$ is again a topological partition. \end{lem} A topological partition is called a {\em generator} for a dynamical system $(X , \f)$ if $$\lim _{n \to \infty } D \left ( \bigvee _{-n}^{n} \f ^{k} \MR \right ) = 0 . $$ Where $D (\MR)$ denotes the {\em diameter} of a partition $\MR$, $$D(\MR) = \max _{R_{i} \in \MR} D( R_{i}) $$ where $D (R_{i}) \equiv \sup _{x,y \in R_{i}} d (x , y).$ We say that a topological partition $\MR$ for a dynamical system $(X , \f)$ satisfies {\em the $n$-fold intersection property} for a positive integer $n \ge 3$ if $$ R_{s_{k}} \cap \f ^{-1} R_{s_{k+1}} \ne \varnothing , \ 1 \le k \le n-1 \Rightarrow \bigcap _{k=1}^{n} \f ^{-k} R_{s_{k}} \ne \varnothing . $$ Furthermore, we call a topological partition {\em Markov} if it satisfies the $n$-fold intersection property for all $n \ge 3 .$ A homeomorphism $\f$ is said to be {\em expansive} if there exists a real number $c>0$ such that if $ d (\f ^{n} (x) , \f^{n} (y) ) < c$ for all $n \in \Z$, then $x = y$. Suppose a dynamical system $(X, \f)$ has a Markov generator $\MR\!=\!\{ R_{i}, i \in \MI \} $. We define an associated subshift of finite type $(\S_{\MR}, \s)$ over a finite or countable alphabet by $$\S_{\MR} = \{ s = (s_{n})_{n \in \Z} : R_{s_{n-1}} \cap \f ^{-1} R_{s_{n}} \ne \varnothing , s_{n}\in \MI, n \in \Z \} . $$ Similar to Theorems 6.5 and 6.13 in \cite{Adler}, we have the following result. \begin{thm} If the dynamical system $(X , \f)$ is expansive and has a Markov generator $\MR = \{ R_{i} , i \in \MI \}$, then the map $\pi : \S_{\MR} \to X$ defined by $$ \pi (s) = \bigcap _{ n = 0}^{\infty } \overline{\f^{n} R_{s_{-n}} \cap \f ^{n-1} R_{s_{-n+1}} \cap \dots \cap \f^{-n} R_{s_{n}}} $$ gives a regular representation $(\S_{\MR}, \s)$ of $(X, \f)$. Moreover, a subshift of finite type is a semi-conjugate representation of an expansive dynamical system $(X, \f )$ if and only if $(X, \f)$ has a Markov partition. \qed \end{thm} % \section{Distillations and Partial Representations} \label{distillation} \section{Partial Representations} \label{distillation} It would be better, under certain conditions, to symbolize a dynamical system by a conjugate representation and using a finite or countable alphabet. This section will show that if there exists a distillation, then we can achieve this target, although we have to abandon the quest of representing all points in the phase space, instead, only represent an invariant subset, that is, we obtain a partial representation. In contrast with partitions, if there exist pairwise disjoint non-empty closed or compact subsets $A_0, A_1, \cdots, A_{N-1}$ of the phase space $X$ (here the union of all $A_i$'s need not to cover $X$), satisfying certain conditions, then the restriction of the system to a invariant subset of $X$ can be represented by the full shift on $N$ symbols. When the number of such closed (compact) subsets need to be countably infinite, then a subsystem can be represented by the full shift with a countable alphabet (\cite{Fu96}). The family of such closed (compact) subsets with certain conditions is called a distillation. More precisely, we give the following definitions. \begin{defn} If for an $f \in M(X)$, there exists an invariant subset $\L \subseteq X$ and a subshift $(\S, \s)$ of a certain symbolic dynamical system such that $(\S, \s)$ is a symbolic representation of $(\L, f)$, then we call the subshift $(\S, \s)$ a {\rm partial representation} of $(X, f)$. \end{defn} A partial representation is also helpful to our understanding of the original system, especially when $\L$ is a maximal invariant subset or a global attractor of $(X, f)$. In these cases, apart from some transient states in $X \setminus \L$, all significant dynamical behaviour will asymptotically take place in $\L$. \begin{defn} \label{def_disti} Let $X$ be a topological space, $f \in M(X)$. We call a finite family of subsets $\MA = \{A_0, A_1, \cdots, A_{N-1} \}$ a {\rm quasi-distillation of order N} for the system $(X, f)$ if: \\ {\rm (1)} each $A_i$ is compact and non-empty; \\ {\rm (2)} $A_i \cap A_j = \varnothing,~ \forall i \ne j$;\\ {\rm (3)} $f(A_i)\supseteq \bigcup _{j \in a(i)}A_j,~ \forall 0\le i \le N-1$.\\ Where $a(i)\subseteq \{0, 1, \cdots, N-1\}$, and each $a(i)$ is non-empty and is maximal in the sense that $\forall j \notin a(i), ~ f(A_i)\cap A_j = \varnothing$. We call $\MA$ a {\rm distillation of order N} for $(X, f)$ if it satisfies a further condition: \\ {\rm (4)} $\card\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})\le 1,~ \forall~ (i_0i_1\cdots i_s \cdots) \in \S(N)$.\\ Where $\card(\cdot)$ denotes the cardinal number of a set. \end{defn} \begin{defn} \label{def_distil} Let $X$ and $f$ be as above. We call a countable family of subsets $\MA = \{A_0, A_1, \cdots, A_k, \cdots \}$ a {\rm quasi-distillation of order infinity} for the system $(X, f)$ if:\\ {\rm (1)} each $A_i$ is closed and non-empty;\\ {\rm (2)} there are open subsets $O_i \subseteq X, ~ i \in \Z_+$, such that $$ \forall~ i \in \Z_+ , ~ A_i \subseteq O_i ~~\mbox{and}~~ O_i \cap (\bigcup_{i\ne j}A_j)= \varnothing; $$ {\rm (3)} $f(A_i)\supseteq \bigcup_{j\in a(i)}A_j,~ \forall i \in \Z_+$.\\ Where $a(i)\subseteq \Z_+$, and each $a(i)$ is non-empty and is maximal in the same sense as in Definition~\ref{def_disti}. We call $\MA$ a {\rm distillation of order infinity} for a self-map on a metric space $(X, d)$ if it satisfies a further condition:\\ {\rm (4)} $\lim_{n \to + \infty}D(\bigcap_{s=0}^{n} f^{-s}(A_{i_s}))=0,~ \forall~ (i_0i_1\cdots i_s \cdots) \in \S(\Z_+)$.\\ Where $D(S)$ denotes the diameter of a subset $S$, i.e., $D(S)=\sup_{a,b \in S} d(a, b)$. \end{defn} At first we give a general lemma. \begin{lem} \label{lem_equal} For a finite or countable family of subsets $\{ A_i, i\in \MI\}$ of a topological space $X$ and a map $f: X \to X$, if $f(A_j)\supseteq \bigcup _{i \in \MI}A_i,~ \forall j \in \MI$, then $\forall l \ge 1, \forall i_k \in \MI, k=0,1, \cdots,$ $$ f^l (\bigcap_{s=0}^{l} f^{-s}(A_{i_s}))= A_{i_l}. $$ \end{lem} \proof {}From $$ f(A_j)\supseteq \bigcup _{i \in \MI}A_i,~ \forall j \in \MI, $$ we have $$ f(A_i)\bigcap A_j=A_j, ~ \forall i, j \in \MI. $$ So when $l=1$, we have $$ f(A_{i_0}\bigcap f^{-1}(A_{i_1}))\subseteq f(A_{i_0})\bigcap A_{i_1}=A_{i_1}. $$ $\forall x \in A_{i_1}$, since $f(A_{i_0})\supseteq A_{i_1}, \exists y \in A_{i_0}$ such that $f(y)=x$. Therefore $y \in f^{-1}(A_{i_1})$, and hence $y \in A_{i_0}\cap f^{-1}(A_{i_1})$, and $x=f(y)\in f(A_{i_0}\cap f^{-1}(A_{i_1}))$. That is, $$ A_{i_1}\subseteq f(A_{i_0}\bigcap f^{-1}(A_{i_1})). $$ So we get $$ f(A_{i_0}\bigcap f^{-1}(A_{i_1}))=A_{i_1}. $$ By the similar arguement the Lemma can be proven inductively. \qed Some known results about distillations and symbolic representations are Smale's horseshoe theorem (\cite{Smale}), higher dimensional versions of horseshoes (\cite{Wiggins88}) and some generalizations to horseshoe-like invariant sets (\cite{Fu96, Zhang}), and etc. Below we give some more general results about distillations and representations. The following theorem gives results on partial representations over a finite alphabet. \begin{thm} \label{th_part_quasi} Suppose $X$ is a Hausdorff space and $f \in C(X)$, and $(X, f)$ has a quasi-distillation of order $N$. Then there exists a subshift of finite type $(\S, \s)\le (\S(N), \s)$ such that $(\S, \s)$ is a partial quasi-representation of $(X, f)$. If $(X, f)$ has a distillation of order $N$, then there exists a subshift of finite type $(\S, \s)\le (\S(N), \s)$ such that $(\S, \s)$ is a partial conjugate representation of $(X, f)$. \end{thm} \proof Let $\S_A=\{x\in \S(N): x=(x_0x_1 \cdots x_k \cdots),~a_{x_kx_{k+1}}=1, \forall ~ k \ge 0\}$, where $A$ is the transition matrix, $$ A=(a_{ij})_{N\times N}, ~~ a_{ij}=\left\{\begin{array}{ll} 1, \;\;\;\; j\in a(i) \\ 0, \;\;\;\; \mbox{otherwise} \end{array} \right. . $$ {}From Lemma~\ref{lem_equal}, $\forall l \ge 1$, $$ f^l (\bigcap_{s=0}^{l} f^{-s}(A_{i_s}))= A_{i_l}, \ \ \forall (i_0i_1 \cdots) \in \S_A. $$ So $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})\ne \varnothing$, since $X$ is a Hausdorff space. Let $$ \L=\bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{N-1}A_i) =\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}), $$ then $\L$ is an invariant compact subset for $f$. Define a coding $\f: \L \to \S_A$ as: $$ \f(x)= (i_0i_1 \cdots i_k \cdots),~~ \forall~ x \in \bigcap_{s=0}^{+\infty}f^{-s}(A_{i_s}). $$ Then $\f$ is surjective. $\forall x \in \L$, suppose $x \in A_{i_0}, f^s (x)\in A_{i_s}, s=0, 1, \cdots, K$. Then $$ \f (x)\in \bigcap_{s=0}^{K}\f f^{-s}(A_{i_s}). $$ {}From the continuity of $f^s$,there exists a neighborhood $V_s (x)$ of $x$ such that $$ f^s (V_s (x)\cap \L) \subseteq A_{i_s},\ s=0, 1, \cdots, K. $$ Let $V(x)=\bigcap_{s=0}^K V_s(x)$, then $V(x)\cap\L \subseteq \bigcap_{s=0}^{K}f^{-s}(A_{i_s})$. So $\forall y \in V(x)\cap\L$, we have $\f (y) \in \bigcap_{s=0}^{K}\f f^{-s}(A_{i_s})$. Thus the first $K$ entries of $\f (y)$ and $\f (x)$ agree, therefore $$ \r (\f (x), \f (y))\le \frac{1}{2^K}. $$ So $\f$ is continuous. The commutativity $\f f|_{\L}=\s|_{\S_A} \f$ is obvious. So $(\S_A, \s)$ is a partial quasi-representation of $(X, f)$. When $(X, f)$ has a distillation of order $N$, then $\f$ is also one-to-one. Note that $X$ is a Hausdorff space, $\f$ is therefore a homeomorphism, and hence $(\S_A, \s)$ is a partial conjugate representation of $(X, f)$. \qed The following two theorems give results on partial representations over a countable alphabet. \begin{thm} \label{th_quasi_distil} Let $X$ be a sequentially compact $T_1$ space and $f \in C(X)$. If $(X, f)$ has a quasi-distillation of order infinity, then there exists a countable state Markov subshift $(\S, \s)\le (\S(\Z_+), \s)$ such that $(\S, \s)$ is a partial quasi-representation of $(X, f)$. \end{thm} \proof $\forall (s_0, s_1, \cdots) \in \S_A$, where $\S_A$ is defined similarly as in the proof of Theorem~\ref{th_part_quasi}, but here $A$ is a matrix of infinite order. From $$ \bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})= \bigcap_{l=0}^{+\infty} \bigcap_{s=0}^{l}f^{-s}(A_{i_s}), $$ $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is the intersection of a decreasing sequence of nonempty closed subsets in a sequentially compact $T_1$ space, so it is nonempty. Define a coding $\f: \L \to \S_A$ as: $$ \f(x)= (i_0i_1 \cdots i_k \cdots),~~ \forall~ x \in \L := \bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{+\infty}A_i) =\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}), $$ then $\f$ is onto. Let $N>0$ satisfy $\ep > \sum_{n=N}^{+\infty}\frac{1}{2^n}$. Suppose $x \in A_{i_0}$ and $f^s(x) \in f^s (x)\in A_{i_s}$, then $ x\in f^{-s}(A_{i_s})$ and $ \f (x)\in \f f^{-s}(A_{i_s}), s=0, 1, \cdots, N$. From the continuity of $f^s$, there exists a neighborhood $V_s (x)$ of $x$ such that $f^s (V_s (x)) \subseteq O_{i_s},\ s=0, 1, \cdots, N.$ Let $V(x)=\bigcap_{s=0}^N V_s(x)$, then $f^s (V(x))\subseteq O_{i_s}$, therefore $f^s (V (x)\cap \L) \subseteq A_{i_s},\ s=0, 1, \cdots, N,$ and $V (x)\cap \L \subseteq \bigcap_{s=0}^N f^{-s}(A_{i_s})$. So $y \in V(x)\cap\L$ implies $\f (y)\in \f \bigcap_{s=0}^N f^{-s}(A_{i_s}) \subseteq \bigcap_{s=0}^N \f f^{-s}(A_{i_s})$. Thus the first $N$ entries of $\f (y)$ and $\f (x)$ agree, hence $\r (\f (x), \f (y)) < \ep$. This proves the continuity of $\f$. Therefore $(\S_A, \s)$ is a partial quasi-representation of $(X, f)$. \qed \begin{thm} Let $(X, d)$ be a complete metric space and $f \in C(X)$. If $(X, f)$ has a distillation of order infinity, then there exists a countable state Markov subshift $(\S, \s)\le (\S(\Z_+), \s)$ such that $(\S, \s)$ is a partial conjugate representation of $(X, f)$. \end{thm} \proof As being shown in the proofs of Theorems~\ref{th_part_quasi}~and~\ref{th_quasi_distil}, $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is a nonempty set for all $(i_0i_1 \cdots i_k \cdots)\in \S_A$. From the condition (4) in Definition~\ref{def_distil}, $\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s})$ is a one-point set. Define a coding $\f: \L \to \S_A$ as: $$ \f (\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}))=(i_0i_1 \cdots i_s \cdots), $$ where $\L=\bigcap_{s=0}^{+\infty} f^{-s}(\bigcup_{i=0}^{+\infty}A_i) =\bigcup_{(i_0i_1 \cdots)\in \S_A}\bigcap_{s=0}^{+\infty} f^{-s}(A_{i_s}).$ Then as shown in the proof of Theorem~\ref{th_quasi_distil}, $\f$ is continuous. For $x=(x_0x_1 \cdots) \in \S_A, \ \ \forall \ \ep >0, \ \ \exists \ N >0, $ whenever $n \ge N$, we have $$ D(\bigcap_{s=0}^{n}f^{-s}(A_{a_s})) < \ep. $$ $\forall \ y \in \S_A,$ when $\r (x, y)< 1/2^N$, the first $N+1$ entries of $x$ and $y$ agree. Thus $$ d(\f ^{-1}(x), \f ^{-1}(y))\le D(\bigcap_{s=0}^{N}f^{-s}(A_{x_s})) < \ep, $$ hence $\f ^{-1}$ is continuous. This shows that $\f$ is a homeomorphism. Therefore $(\S_A, \s)$ is a partial conjugate representation of $(X, f)$. \qed \section{Representations for Discontinuous Maps} \label{discontinuous} This section will discuss some specific examples and show that it is possible to use symbolic dynamics as a tool for further studies of dynamics of a class of discontinuous maps: piecewise continuous maps. %%% \subsection{Representations of Piecewise %%%% Continuous Maps} \label{piecewise} Let $X \subseteq \R^n$, and $\MP= \{ P_0, P_1, \cdots, P_{N-1}\}$ be a finite family of subsets of $X$, satisfying $\bigcup_{i=0}^{N-1}P_i = X$, and $P_i \cap P_j=\varnothing$ for $i\ne j$. A piecewise continuous map is a map $f: X \to X$ whose restriction to each $P_i,~ 0\le i \le N-1$, is continuous, and $\MP$ is minimal in the sense that $f$ is not continuous on $P_i \cup P_j$ for $i \ne j$. A partition $\MP = \{ P_0, \cdots, P_{N-1}\}$ associated to a piecewise continuous map provides a natural coding $\f: X \to \S(N)$ by $\f(x) = (i_0 i_1 \cdots i_k \cdots)$ where $f^k(x)\in P_{i_k}$. Let $G=\{ (x, \f(x)),~ x \in X\}$ be the graph of $\f: X \to \S(N)$ endowed with the metric $$ d_G((x, \f(x)), (y, \f(y))) = \max \{ d(x,y), \r(\f(x), \f(y))\}, $$ where $d$ is the metric on $X$. Then the extension map $f_G: G \to G, ~ f_G(x, \f(x))=(f(x), \f(f(x)))$, is continuous (\cite{Goetz}). This result may be useful since sometimes it is a bridge between discontinuous and continuous maps. Here we give a definition of partitions for piecewise continuous maps. \begin{defn} For $X \subseteq \R^n,~f \in M(X)$. We call a finite family of subsets $\MP = \{ P_0, P_1, \cdots, P_{N-1}\}$ a {\rm partition} of $(X, f)$ if: {\rm (1)} each $P_i$ is open and convex; {\rm (2)} $P_i \cap P_j = \varnothing$ for $i \ne j$; {\rm (3)} $X= \bigcup_{i=0}^{N-1}\overline{P_i}$; {\rm (4)} $\forall ~ 0\le i \le N-1,~ f|_{P_i}$ is continuous and can be extended to a continuous map on $\overline{P_i}$. We call a partition {\rm minimal} if $f$ is not continuous on $\overline{P_i} \cup \overline{P_j}$ for $i \ne j$. A {\rm cell}, denoted by $C(x)$, is a set of points in $X$ encoded by the same symbolic sequence $\f(x)$, i.e., $C(x)= \{ y\in X: \f(y)=\f(x)\}$, where $\f$ is called the {\rm coding} associated with the partition $\MP$, $\f: X \to \S(N)$ is defined by $\f(x) = (i_0i_1\cdots i_k\cdots)$ where $f^k(x)\in P_{i_k}$. \end{defn} \begin{eg} \label{eg_gauss} Symbolic representation for the Gauss map. \end{eg} Let $ ( I , g )$ be the iterated system of the Gauss map (\cite{Adler91}) $ g : x \rightarrow x^{-1} ~(\bmod ~1)$ for $0< x \le 1$, and $g(0)=0$. Let a sequence $s = ( s_{n})_{n \in \Z_+} \in \S(\N)$ correspond to the continued fraction expansion $[s_{0}s_{1}s_{2}\cdots]$. This defines the map $\pi $ from $\S(\N)$ to $I=[0, 1]$: $$ \pi ( s_{0} \,, s_{1} \,, \cdots )=[s_{0}s_{1}s_{2}\cdots]. $$ It can be verified that \begin{itemize} \item[{(i)}] $g \pi = \pi \s $, \item[{(ii)}] $\pi $ is continuous, \item[{(iii)}] $\pi $ is onto, \item[{(iv)}] there is a bound on the number of pre-images (in this case two), \end{itemize}and \begin{itemize} \item[{(v)}] there is a unique pre-image of ``most" numbers in $I$ (here those with infinite continued fraction expansions). \end{itemize} So $(\S(\N), \s)$ is a regular representation of $(I, g)$. The map $\pi $ is not a homeomorphism, but we do have a satisfactory representation of the dynamical system by a one-sided full shift over a countable alphabet in the sense of Adler \cite{Adler}, i.e., \begin{itemize} \item orbits are preserved; \item every point has at least one symbolic representative; \item there is a finite upper limit to the number of representatives of any point; \item and every symbolic sequence represents some point. \end{itemize} There is an alternate definition of $\pi $ in terms of a countable partition of $I$: $$ \MR = \{ R_{i}, i \in \N \}, \ \ R_i = (\frac{1}{i+1}, \frac{1}{i}). $$ $$ \pi ( s_{0} , s_{1} , \cdots ) = \bigcap _{ n = 0}^{\infty }\overline{ R_{s_{0}} \cap g^{-1} ( R_{s_{1}}) \cap \cdots \cap g^{-n} (R_{s_{n}})}. $$ Note that in a suitable torus topology the Gauss map becomes continuous everywhere except at $x=0$. Below we give another example where the map is ``more discontinuous'' but is still easy to symbolize. \begin{eg} \label{eg_interval} Symbolic representations for interval exchange transformations. \end{eg} An interval exchange transformation $f: I \to I, I=[0, 1]$, over a partition $\MP=\{I_0, I_1, \cdots, I_{N-1}\}$ is a one-dimensional piecewise isometry, so we can follow the arguements in \cite{Ashwinf, Ashwinft, Goetz00} to discuss symbolic representation for $f$. By naturally coding orbits of $f$ using the partition $\MP, \f: I \to \S(N)$, $$ \f(x)=(\cdots i_{-1} i_0 i_1 \cdots), $$ where $f^k(x)\in I_{i_k}, k \in \Z$, we obtain a subset $\S \subseteq \S(N)$ of bi-infinite symbolic sequences, $\S=\{ \f(x)\in \S(N), x \in I\}$. $\S$ is closed and shift invariant, so $(\S, \s)\le (\S(N), \s)$. Note that if a subinterval $S \subseteq I$ is invariant under $f^m$, then $f^m |_S$ is either the identity or the reflection in the midpoint of $S$ (in this case $f^{2m} |_S$ is the identity). So the disk/polygon packing discussed in \cite{Ashwinf, Ashwinft, Goetz00} now reduce to rigid interval (\cite{Katok}) packing, i.e., the set $$ J=\overline{I\setminus \bigcap_{n \in \Z}f^n (\hat{I})},~ \hat{I}= \bigcup_{k=0}^{N-1} {\rm int} I_k $$ of points that never hit or approach the discontinuity can be decomposed into finite (\cite{Katok}:Lemma 14.5.4) cells, or rigid intervals $J_k$, $$ J=\bigcup_{k=1}^K J_k,~ K\le 2(N-1), $$ all points in $J$ have periodic codings, and $f$ is periodic on each $J_k$. As discussed in \cite{Katok}, when $f$ is generic (i.e., $J=\varnothing$), we can define a map $h: \S \to I$, $$ h((\cdots i_{-1} i_0 i_1 \cdots))=\bigcap_{k\in \Z}f^{-k}(I_{i_k}). $$ $h$ satisfies: \begin{itemize} \item[{(1)}] $f h = h \s $, \item[{(2)}] $h $ is continuous, \item[{(3)}] $h $ is onto, \item[{(4)}] there is a bound on the number of pre-images (in this case $2^N$), \end{itemize}and \begin{itemize} \item[{(5)}] there is a unique pre-image of ``most" points in $I$ (here those no image or pre-image of them are discontinuity points). \end{itemize} So $(\S, \s)$ is a regular representation of $(I, f)$. Although the map $h$ is not a homeomorphism, we do have a satisfactory representation of the dynamical system by a two-sided subshift over a finite alphabet with the properties listed near the end of Example~\ref{eg_gauss}. If $(\S, \s)$ is topologically transitive, then $(\S, \s)$ is a subshift of {\em infinite} type, because otherwise the periodic points of $\s|_{\S}$ would be dense in $\S$. %%%%% \subsection{Foliations and %%%%%% Representations} \label{foliation} % % In this section we will discuss ... \cite{Hao_Zheng98} % % \vspace{1cm}{\bf TO FINISH...}\vspace{1cm} \section{Final Remarks} When we consider the symbolic representation of an iterated map, one may hope to find one of the following: \begin{itemize} \item[{(A)}] a full representation (i.e., all points in the phase space are symbolically represented); \item[{(B)}] a conjugate representation; \item[{(C)}] a representation via a subshift of finite type over a finite or countable alphabet. \end{itemize} Unfortunately, it is very rare to get a symbolic representation satisfying all of (A), (B) and (C). Usually, if we'd like to get a symbolic representation satisfying (A) and (B), we may need to pay the price of giving up (C), i.e., we need to use an uncountable alphabet, as discussed in Sections~\ref{conjugate} and \ref{sec_second}; if we'd like to obtain a representation with properties (A) and (C), we may have to give up (B), as discussed in Sections~\ref{quasi} and \ref{partition}; if we'd like to find a representation with (B) and (C), we may have to give up (A), i.e., we only get a partial representation, as discussed in Section~\ref{distillation}. When we consider a symbolic representation of a discontinuous map, we at least have to give up (B), as discussed in Section~\ref{discontinuous} using special cases of piecewise continuous maps. Symbolic representations provide a powerful method to investigate general discrete dynamical systems through shifts or subshifts. This is similar to the situation for the study of finite groups in algebra, where all finite groups can be represented by subgroups of symmetric groups $S_n$, which are better understood. We can view $S_n$ as `symbolic' groups. There is a large body of theory that describes the dynamics of continuous smooth dynamical systems. However, if there are discontinuities in the system such as those caused by collisions (impacting) or switching there is still comparatively little in the way of general theory to describe such systems. In Section~\ref{discontinuous} we have shown through specific examples that it is helpful to use symbolic dynamics to develop the general theory of dynamics of a class of discontinuous maps: piecewise continuous maps. Most results in this paper are proven constructively. This makes our results potentially useful for applications. Finally, we conjecture that some results in Sections~\ref{conjugate}, \ref{sec_second}, \ref{quasi} and \ref{discontinuous} about representations for one dimensional maps may be extended to higher dimensional cases. Higher dimensional binary expansions and higher dimensional continued fractions (\cite{Arnold}) may be useful in the extension. We hope to discuss this topic in a separate paper. \vspace{0.5cm} \noindent {\bf Acknowledgments.} {\small X. Fu and P. Ashwin thank the EPSRC for support via grant GR/M36335, and they are grateful to Surrey University where earlier versions of this paper were written. The authors would like to thank Prof. Robert Harrison for his helpful comments and advice. While an earlier version of this paper was written, X. Fu was supported jointly by a scholarship from the Nonlinear Dynamics Group in Physics Department of Heriot-Watt University and a grant (No. 19572075) from China National Natural Science Foundation.} \begin{thebibliography}{20} \bibitem{Adler91} R. L. Adler, Geodesic flows, interval maps, and symbolic dynamics, in {\em Ergodic Theory, Symbolic Dynamics, and Hyperbolic Spaces} (eds. T. Bedford, M. Keane, C. Series), Oxford Univ. Press, 1991. \bibitem{Adler} R. L. Adler, {\em Symbolic Dynamics and Markov Partitions}, {\em MSRI} Publications, {\bf 53}, 1996. Also in {\em Bull. Amer. Math. Soc. (New Series)}, {\bf 35}(1998)1-56. \bibitem{Adler2} R. L. Adler, and B. Weiss, Similarity of automorphisms of the torus, {\em Memor. Amer. Math. Soc.}, {\bf 98}(1970)ii+43pp. \bibitem{Alekseev} V. M. Alekseev, and M. V. Yakobson, Symbolic dynamics and hyperbolic dynamic systems, {\em Phys. Reports}, {\bf 75}(1981)287-325. \bibitem{Arnold} V. I. Arnold, Higher dimensional continued fractions, {\em Regular and Chaotic Dynamics}, {\bf 3}(1998)10-17. \bibitem{Ashwinf} P. Ashwin and X. Fu, On the geometry and dynamics of planar piecewise isometries, (in preparation, 2000) \bibitem{Ashwinft} P. Ashwin, X. Fu and J. Terry, Riddling of invariant sets for some discontinuous maps preserving Lebesgue measure, (submitted, 2000) \bibitem{Berg} K. Berg, {\em On the Conjugacy Problem for K-Systems}, PhD Thesis, University of Minnesota, 1967. \bibitem{Fu96} X.-C. Fu, Criteria for a general continuous self-map to have chaotic sets, {\em Nonlinear Analysis TMA}, {\bf 26}(1996)329-334. \bibitem{Fu92} X.-C. Fu, and H.-W. Chou, Chaotic behavior of the general symbolic dynamics, {\em Applied Math. and Mech.} {\bf 13}(1992)117-123. \bibitem{Fu98} X.-C. Fu, and J. Duan, Infinite-dimensional linear dynamical systems with chaoticity, {\em J. of Nonlinear Sci.}, {\bf 9}(1999)197-211. \bibitem{Goetz} A. Goetz, Dynamics of a piecewise rotation, {\em Contin. Discrete Dyn. Sys.}, {\bf 4}(1998)593-608. \bibitem{Goetz00} A. Goetz, Dynamics of piecewise isometries, {\em Illinois J. Math.}, {\bf 44}(2000)465-478. \bibitem{GH83} J. Guckenheimer, and P. Holmes, {\em Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields}, Springer-Verlag, 1983 (3rd printing, 1990). \bibitem{Hao89} B.-L. Hao, {\em Elementary Symbolic Dynamics and Chaos in Dissipative Systems}, World Scientific, 1989. \bibitem{Hao_Zheng98} B.-L. Hao, and W.-M. Zheng, {\em Applied Symbolic Dynamics and Chaos}, World Scientific, 1998. \bibitem{Katok} A. Katok and B. Hasselblatt, {\em Introduction to the Modern Theory of Dynamical Systems}, Cambridge Univ. Press, 1995. \bibitem{Kitchens} B. P. Kitchens, {\em Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts}, Springer-Verlag Berlin, 1998. \bibitem{Lind} D. Lind, and B. Marcus, {\em An Introduction to Symbolic Dynamics and Coding}, Cambridge Univ. Press, 1995. \bibitem{May} R. M. May, Simple mathematical models with very complicated dynamics, {\em Nature}, {\bf 261}(1976)459-467. \bibitem{Nasu} M. Nasu, Maps in symbolic dynamics, {\em Lecture Notes of the Tenth KAIST Mathematics Workshop} (G. H. Choe ed.), Korea Advanced Institute of Science and Technology, 1996. \bibitem{Smale} S. Smale, Differentiable dynamical systems, {\em Bull. Amer. Math. Soc.}, {\bf 73} (1967) 747-817. \bibitem{Wiggins88} S. Wiggins, {\em Global Bifurcations and Chaos: Analytical Methods}, Springer-Verlag, 1988. \bibitem{Zhang} Z.-S. Zhang, On the shift-invariant sets of endomorphisms, {\em Acta Math. Sinica}, {\bf 27}(1984)564-576. \end{thebibliography} \end{document} ---------------0012051554166--