1 Introduction
A topological dynamical system is a pair
$(X,f)$
where X is a compact metric space and
$f\in C(X,X)$
is a continuous map of X to itself. Limit sets and backward limit sets provide some of the most important tools in understanding the behavior of a topological dynamical system, since they provide information about the long-term behavior of the orbits of the system. One notion, in particular, of a backward limit set is the notion of a special
$\alpha $
-limit set, which has played an important role in one-dimensional dynamics (the notion is defined and discussed below).
Descriptive set theory provides a means for calibrating the complexity of sets in Polish spaces, and this in turn is important for understanding the impact of possible theorems about the objects under consideration. To give an example of this phenomenon, consider the case of normal numbers for some base
$b \geq 2$
. Let
$\mathcal {N}_b$
denote the set of real numbers which have a normal base-b expansion. Let
$\mathcal {N}^{\perp }_b$
denote the set of real numbers
$\gamma $
such that
$\gamma +N_b \subseteq \mathcal {N}_b$
, that is, they preserve base-b normality under addition. By its definition, this set does not at first even appear to be a Borel set as it involves a universal quantification over
$\mathcal {N}_b$
(the definition shows it to be a coanalytic or
${\boldsymbol{\Pi}}^1_1$
set; see [Reference Kechris18] for the definition). However, a deep theorem of Rauzy characterizes the normality-preserving numbers as those with zero upper noise [Reference Rauzy20]. Since the upper noise of
$\gamma $
is defined by taking limits (and lim sups) of sequences of continuous functions of
$\gamma $
, it follows immediately that
$\mathcal {N}_b^{\perp }$
is Borel, in fact a
${\boldsymbol{\Pi}}^0_3$
set. In fact, in [Reference Airey, Jackson and Mance3] it was shown that
$\mathcal {N}^{\perp }_b$
is a
${\boldsymbol{\Pi}}^0_3$
-complete set, which shows that it is no simpler than this.
The present paper shows that the special
$\alpha $
-limit set of a point in a topological dynamical system, in fact even for the case of the unit square in
$\mathbb {R}^2$
, can be a
${\boldsymbol{\Sigma}}^1_1$
-complete set, and thus not Borel. The significance of this is that it tells us that there are no such ‘hidden theorems’ for special
$\alpha $
-limit sets, even in compact metric spaces. Thus, the definition involving an existential quantification over all backward orbits cannot be simplified.
We remark that it is unusual in our experience for a dynamically defined set to be non-Borel. In fact, most of the important sets studied in a topological dynamical system occur at the lowest few levels of the Borel hierarchy. Examples we can think of include the basin of an attracting cycle (an open set), the non-wandering set (a closed set), the set of periodic points (an
$F_{\sigma }$
set), and the set of points with a dense orbit (a
$G_{\delta }$
set). The reader can surely think of many more examples. On the other hand, a result of Foreman, Rudolph, and Weiss [Reference Foreman, Rudolph and Weiss10] says that the set of invertible, ergodic, measure-preserving transformations (on the unit interval with Lebesgue measure) which are isomorphic to their inverses is a complete analytic set. In particular, the isomorphism relation between invertible, ergodic, measure-preserving transformations is not Borel. Hjorth [Reference Hjorth16] had previously shown that the isomorphism relation is not Borel for the larger class of invertible measure-preserving transformations.
The authors have recently shown that special
$\alpha $
-limit sets can in fact occur at any level in the Borel hierarchy, but this will be part of a forthcoming paper.
We now discuss these notions more precisely. Throughout this paper
$\mathbb {N}=\{ 0,1,\ldots \}$
will denote the set of natural numbers. The
$\omega $
-limit set of a point
$x\in X$
under a map f, denoted
$\omega (x)$
or
$\omega (x,f)$
, consists of all accumulation points of the forward orbit
$(f^n(x))_{n\in \mathbb {N}}$
of the point x. These sets are always closed, and their topological properties are well understood; see, for example, [Reference Agronsky, Bruckner, Ceder and Pearson1, Reference Agronsky and Ceder2, Reference Block and Coppel5, Reference Bruckner and Smítal6, Reference Jiménez López and Smítal17, Reference Sharkovsky and Verotskaya21].
The backward limit sets of a point x play a dual role to the
$\omega $
-limit set. The idea is that to describe the ‘source’ of a trajectory, we should reverse the direction of time. For invertible dynamical systems (homeomorphisms) this leads to a well-defined
$\alpha $
-limit set
$\alpha (x)=\omega (x,f^{-1})$
. This idea came into discrete dynamics from the study of flows, where
$\alpha $
-limit sets are fundamental in defining such objects as unstable manifolds, homoclinic and heteroclinic trajectories, and the Morse decompositions at the heart of Conley theory [Reference Conley7, Reference Guckenheimer and Holmes12].
For non-invertible mappings
$f:X\to X$
, the situation is more complicated, since a point may have several preimages (or none at all). There are several ways to define backward limit sets in this setting.
(1) The
$\alpha $
-limit set of a point, denoted
$\alpha (x)$
, consists of all accumulation points of all preimage sequences
$(x_n)_{n\in \mathbb {N}}$
, where
$x_n\in f^{-n}(\{x\})$
for all n. These sets are especially useful in dimension one. Coven and Nitecki proved that a point is non-wandering for an interval map if and only if it belongs to its own
$\alpha $
-limit set [Reference Coven and Nitecki8], and Cui and Ding related the
$\alpha $
-limit sets of a unimodal interval map to its renormalizations [Reference Cui and Ding9].
(2) The
$\alpha $
-limit set of a backward orbit, denoted
$\alpha ((x_n)_{n=0}^{\infty })$
, consists of all accumulation points of a single backward orbit, that is, a sequence
$(x_n)_{n\in \mathbb {N}}$
, where
$f(x_{n+1})=x_n$
for all n. Hirsch, Smith and Zhao showed that the
$\alpha $
-limit set of a backward orbit is always internally chain transitive [Reference Hirsch, Smith and Zhao15]. A converse result holds when f is expansive and has the shadowing property [Reference Good, Meddaugh and Mitchell11]. For maps on the interval, the
$\alpha $
-limit set of a backward orbit satisfies a local transportation condition which makes it simultaneously an
$\omega $
-limit set of f [Reference Balibrea, Dvorníková, Lampart and Oprocha4].
(3) The special
$\alpha $
-limit set of a point, denoted
$s\alpha (x)$
, is the union
$\bigcup \alpha ((x_n)_{n=0}^{\infty })$
taken over all backward orbits of x, that is, sequences
$(x_n)_{n\in \mathbb {N}}$
such that
$f(x_{n+1})=x_n$
for all n and
$x_0=x$
. These sets were defined by Hero, who showed that for interval maps, a point is in the attracting center if and only if it belongs to its own special
$\alpha $
-limit set [Reference Hero14]. Generalizations of this result to other one-dimensional spaces were given in [Reference Sun, Xi, Chen and Zhang22, Reference Sun, Xi and Liang23].
Kolyada, Misiurewicz and Snoha pointed out that special
$\alpha $
-limit sets need not be closed, and asked whether they are necessarily Borel or at least analytic [Reference Kolyada, Misiurewicz and Snoha19]. The difficulty arises when x has uncountably many backward orbit branches, since we are then taking an uncountable union of their (closed) accumulation sets.
The complexity of special
$\alpha $
-limit sets (or
$s\alpha $
-limit sets, for short) for maps of the interval
$I=[0,1]$
will be addressed in a forthcoming paper, where it will be shown that
$s\alpha (x)$
is always Borel, and in fact both
$F_{\sigma }$
and
$G_{\delta }$
[Reference Hantáková and Roth13].
This paper is concerned with the complexity of
$s\alpha $
-limit sets in other compact metric spaces. We start in §2 by showing that
$s\alpha $
-limit sets are always analytic. The proof is short and uses the fact that backward orbits occur in a well-known compact metric space related to
$(X,f)$
, namely, the natural extension.
The main construction in this paper gives a map on the unit square
$I^2=[0,1]^2$
with a
$s\alpha $
-limit set which is
${\boldsymbol{\Sigma}}^1_1$
-complete, that is, analytic but not Borel. Our construction starts in §3 at the symbolic level with a one-sided shift space
$X\subset \{0,1,2,3,4\}^{\mathbb {N}}$
, in which the set of all ill-founded trees on a countable set has been suitably encoded into the backward orbit branches of a given point x. We show that
$s\alpha (x)\subset X$
is not Borel. Then in §4 we embed this shift space as a totally invariant subsystem for a map on the square
$F:I^2\to I^2$
, and show that the
$s\alpha $
-limit set of the corresponding point is not a Borel subset of
$I^2$
. We remark that the map F in our counterexample is surjective, piecewise monotone, and triangular, that is, a skew product map of the form
$F(x,y) = (f(x),g_x(y))$
.
2 Special
$\alpha $
-limit sets are analytic
A Polish space is any separable, completely metrizable topological space. A subset B of a Polish space Y is called analytic (or a
${\boldsymbol{\Sigma}}^1_1$
set) if there exist a Polish space X, a Borel subset
$A\subseteq X$
, and a continuous map
$f:X\to Y$
such that
$B=f(A)$
. The class of analytic sets in an uncountable Polish space strictly contains the class of Borel sets. A set is called
${\boldsymbol{\Sigma}^1_1}$
-
complete if it is analytic but not Borel, or equivalently, if it is analytic but its complement is not.
Recall that a topological dynamical system is a pair
$(X,f)$
where X is a compact metric space and
$f:X\to X$
is continuous. In this section we show that
$s\alpha $
-limit sets of topological dynamical systems are always analytic.
Theorem 2.1. Every
$s\alpha $
-limit set of a topological dynamical system
$(X,f)$
is analytic.
Proof Give
$X^{\mathbb {N}}$
the product topology. It is compact and metrizable. For example, if d is the metric on X, then
$\widehat {d}(x_0x_1\cdots{\kern-1pt},y_0y_1\cdots{\kern-1pt}) = \sum _{n} 2^{-n} \min (1,d(x_n,y_n))$
is one compatible metric on
$X^{\mathbb {N}}$
. Now let
$\widehat {X}\subseteq X^{\mathbb {N}}$
be the closed subspace
$$ \begin{align*} \widehat{X} = \{ x_0 x_1 \cdots ~|~ f(x_{n+1})=x_n \text{ for all } n\in\mathbb{N}\}. \end{align*} $$
$\widehat {X}$
is a topological space whose points are the backward orbits of
$(X,f)$
. We remark that the space
$\widehat {X}$
equipped with the map
$x_0x_1\cdots \mapsto f(x_0)x_0x_1\cdots $
is a well-known object in topological dynamics called the natural extension of
$(X,f)$
.
Consider the relation
$R\subseteq \widehat {X}\times X$
given by
$$ \begin{align*} R &= \{ (x_0x_1\cdots{\kern-1pt}, y) ~|~ x_{n_i} \to y \text{ along some subsequence } n_i\to\infty \} \\ &= \bigcap_{j=1\vphantom{N}}^{\infty} \bigcap_{N=0}^{\infty} \bigcup_{n=N}^{\infty} \bigg\{ (x_0x_1\cdots{\kern-1pt}, y) ~|~ d(x_n,y) < \frac{1}{j} \bigg\}. \end{align*} $$
Then R is a countable intersection of open sets, so it is Borel.
Let
$\pi _0:\widehat {X} \to X$
be the projection on the zeroth coordinate,
$x_0x_1\cdots \mapsto x_0$
. Now fix an arbitrary point
$x\in X$
and let
$A=\pi _0^{-1}(\{x\})$
. Then A is closed in
$\widehat {X}$
. Finally, let
$\pi :\widehat {X}\times X \to X$
be the map
$(x_0x_1\cdots{\kern-1pt},y)\mapsto y$
. By the definition of
$s\alpha $
-limit sets we have
$$ \begin{align*} s\alpha(x)=\pi(R\cap(A\times X)). \end{align*} $$
Thus we have expressed
$s\alpha (x)$
as the continuous image of a Borel subset of the compact metric space
$\widehat {X}\times X$
. It follows that
$s\alpha (x)$
is analytic.
3 A non-Borel
$s\alpha $
-limit set in a shift space
In order to show that a set B in a Polish space Y is not Borel, it suffices to start with a known non-Borel set A in a Polish space X and find a reduction of A to B, that is, a continuous function
$f:X\to Y$
such that
$A=f^{-1}(B)$
. We follow this strategy using the well-known example of the ill-founded trees as a non-Borel subset of the Cantor space.
To describe those trees let
$\mathbb {N}^{<\mathbb {N}}$
denote the set of all finite words in the countable alphabet
$\mathbb {N}=\{0,1,2,\ldots \}$
. Then a tree is any subset
$T\subseteq \mathbb {N}^{<\mathbb {N}}$
which contains along with any word all of its initial segments. The nodes of the tree are just the individual words
$v\in T$
, and if v has length
$n\geq 1$
, then its parent node is its initial segment of length
$n-1$
. By passing to shorter and shorter initial segments we traverse the branch which connects the node v back to the empty word
$\emptyset $
, which forms the root of the whole tree.
A tree T is said to be ill-founded if it has an infinite branch, that is, an infinite word
$v\in \mathbb {N}^{\mathbb {N}}$
such that every initial segment of v belongs to T. Let
$\mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
denote the power set, that is, the collection of all subsets
$A\subseteq \mathbb {N}^{<\mathbb {N}}$
. Let
$\mathcal {T}$
and
$\mathcal {T}_{\mathrm {IF}}$
denote the set of trees and the set of ill-founded trees, respectively.
$\mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
becomes the Cantor space when we identify it with the countable product
$\{0,1\}^{\mathbb {N}^{<\mathbb {N}}}$
by identifying each subset
$A\subseteq \mathbb {N}^{<\mathbb {N}}$
with its characteristic function
$\chi _A : \mathbb {N}^{<\mathbb {N}} \to \{0,1\}$
. A well-known result in descriptive set theory is that
$\mathcal {T}_{\mathrm {IF}} \subset \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
is analytic but not Borel, and in fact, this is regarded as the prototypical example of a
$\boldsymbol{\Sigma}^1_1$
-complete set; see [Reference Kechris18, Theorem 27.1].
The following notation will be useful. We write
$\mathrm {len}(w)\in \mathbb {N}\cup \{\infty \}$
for the length of a finite or infinite word, and we write
$w_i$
for the ith symbol of w for
$0\leq i < \mathrm {len}(w)$
. We write
$w|n = w_0 \ldots w_{n-1}$
for the initial segment of w of length n. We write
$v{}^{\smallfrown } w$
for the concatenation of the words v, w, provided
$\mathrm {len}(v)<\infty $
. We use exponents to indicate repetition of a symbol, so
$a^n$
is the symbol a repeated n times, while
$a^{\infty }$
is the infinite sequence
$aaa\cdots $
. If we write a word explicitly as a string of digits
$w=4530\cdots $
the reader may assume that each
$w_i$
is a single-digit number, otherwise we will use a longer notation such as
$w=(4,53,0,\ldots )$
to avoid confusion.
We recall a few facts from the standard proof that
$\mathcal {T}_{\mathrm {IF}}\subset \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
is analytic, as we will need them later on.
Lemma 3.1. The set of trees
$\mathcal {T}$
is closed in
$\mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
. The set
$$ \begin{align*} R=\{(T,y)\in\mathcal{P}(\mathbb{N}^{<\mathbb{N}})\times\mathbb{N}^{\mathbb{N}}~|~T\text{ is a tree and } y \text{ is an infinite branch of } T \} \end{align*} $$
is closed in
$\mathcal {P}(\mathbb {N}^{<\mathbb {N}}) \times \mathbb {N}^{\mathbb {N}}$
. In particular, this implies that
$\mathcal {T}_{\mathrm {IF}}\subset \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
is analytic.
Proof We include the proof for completeness. Suppose that
$A\subseteq \mathbb {N}^{<\mathbb {N}}$
is not a tree. Then there is a word v and an initial segment w of v such that
$v\in A$
but
$w\notin A$
. Consider the set
$\{A'\subseteq \mathbb {N}^{<\mathbb {N}}~|~v\in A', w\notin A'\}$
. Translating to characteristic functions, this is the set of
$\chi _{A'}\in \{0,1\}^{\mathbb {N}^{<\mathbb {N}}}$
which take the value
$1$
in position v and
$0$
in position w. But specifying values in finitely many positions clearly defines an open set in the product topology on
$\{0,1\}^{\mathbb {N}^{<\mathbb {N}}}$
(such sets are usually called cylinder sets). This shows that the complement of
$\mathcal {T}$
is open in
$\mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
, so
$\mathcal {T}$
is closed.
For the second statement of the lemma, since
$\mathcal {T}$
is closed it suffices to show that R is relatively closed in
$\mathcal {T}\times \mathbb {N}^{\mathbb {N}}$
. So suppose that
$(T,y)$
belongs to the complement of R in
$\mathcal {T} \times \mathbb {N}^{\mathbb {N}}$
. This means that y is not an infinite branch of the tree T, so there must be some n such that
$y|n\notin T$
. Consider the set of pairs
$(T',y')\in \mathcal {T} \times \mathbb {N}^{\mathbb {N}}$
such that
$y|n\notin T'$
and
$y_i=y^{\prime }_i$
for all
$i<n$
. Again, since we’ve specified the values of
$T', y'$
in only finitely many positions, we get a relatively open set in
$\mathcal {T} \times \mathbb {N}^{\mathbb {N}}$
. This shows that the complement of R is open, so R is closed.
Finally, note that
$\mathcal {T}_{\mathrm {IF}}$
is just the projection of R on the first coordinate, and the continuous image of a Borel subset in a Polish space is analytic by definition.
We wish to ‘encode’ the set
$\mathcal {T}_{\mathrm {IF}}$
into a
$s\alpha $
-limit set. Let
$2^{\mathbb {N}}$
be the standard Cantor space. Choose an enumeration
$(s_i)$
of
$\mathbb {N}^{<\mathbb {N}}$
and define a homeomorphism
$h:\mathcal {P}(\mathbb {N}^{<\mathbb {N}}) \to 2^{\mathbb {N}}$
by letting
$h(T)$
be the point x such that
$x_i=1$
whenever
$s_i\in T$
and
$x_i=0$
whenever
$s_i\not \in T$
. Let
$5^{\mathbb {N}}=\{0,1,2,3,4\}^{\mathbb {N}}$
be the one-sided shift space in five symbols (it is also a Cantor space) and let
$\sigma :5^{\mathbb {N}}\to 5^{\mathbb {N}}$
be the shift map defined by
$(\sigma x)_i=x_{i+1}$
. A subshift in
$5^{\mathbb {N}}$
is any closed subset
$X\subseteq 5^{\mathbb {N}}$
such that
$\sigma (X)\subseteq X$
. For T an ill-founded tree and y an infinite branch of T we define inductively points
$\omega _n(T,y)\in 5^{\mathbb {N}}$
by
$$ \begin{align} \begin{aligned} \omega_0(T,y)&=3{}^{\smallfrown} 4{}^{\smallfrown} 0^{\infty},\\ \omega_{n}(T,y)&=3{}^{\smallfrown} (x|n) {}^{\smallfrown} 2^{y_{n-1}} {}^{\smallfrown} \omega_{n-1}(T,y) \quad \text{for } n\geq 1, \text{ where } x=h(T). \end{aligned} \end{align} $$
Then define a subset
$X\subset 5^{\mathbb {N}}$
by
$$ \begin{align} X:=\{0,1,2,3\}^{\mathbb{N}} \cup \{\sigma^j(\omega_i(T,y))~|~(T,y)\in R, i,j\in\mathbb{N}\}, \end{align} $$
where we continue to use the set R from Lemma 3.1.
Example 3.2. Let T be the tree of strictly increasing finite words
$s\in \mathbb {N}^{<\mathbb {N}}$
and let
$y=(2,3,5,7,11,\ldots )\in \mathbb {N}^{\mathbb {N}}$
be an infinite word in the body of T. Let
$(s_i)$
be an enumeration of
$\mathbb {N}^{<\mathbb {N}}$
whose first few terms are
$s_0=\emptyset $
,
$s_1=0$
,
$s_2=00$
, so that
$s_0, s_1\in T$
but
$s_2\not \in T$
. Then
$$ \begin{align*} \omega_3(T,y)=3\;110\;{22222}\; 3\;11\;{222}\; 3\;1\;{22}\; 3\; 4\; 00000\cdots{\kern-1pt}. \end{align*} $$
Thus, from
$\omega _n(T,y)$
we can read off the first n symbols of
$x=h(T)$
and y. Each block of 2s encodes a digit of y. The blocks of 0s and 1s record the initial segments of x.
Lemma 3.3. The set
$X\subset 5^{\mathbb {N}}$
is a subshift and
$\sigma (X)=X$
.
Proof Invariance
$\sigma (X)\subseteq X$
is immediate from (2). Surjectivity of
$\sigma |_X$
follows from (1), (2), and the observation that
$\sigma ^{t_n}(\omega _n(T,y))=\omega _{n-1}(T,y)$
, where
$t_n=1+n+y_{n-1}$
.
Equations (1) and (2) implicitly determine a set of forbidden words F in the alphabet
$\{0,1,2,3,4\}$
. Any word with an initial 4 and a non-zero symbol occurring after it is forbidden. Any word which ends with a 4 is forbidden if it is not an initial segment of some
$\sigma ^j(\omega _i(T,y))$
,
$i,j\in \mathbb {N}$
,
$(T,y)\in R$
. A point
$x\in 5^{\mathbb {N}}$
is in X if and only if it contains none of those forbidden words. This shows that X is closed.
Now consider the dynamical system given by the subshift
$\sigma |_X : X \to X$
and fix the point
$\omega _0=3{}^{\smallfrown }4{}^{\smallfrown }0^{\infty }\in X$
. The backward orbit branches of
$\omega _0$
correspond to the ill-founded trees, allowing us to prove the following result.
Theorem 3.4. The set
$s\alpha (\omega _0)\subset X$
is
${\boldsymbol{\Sigma}}^1_1$
-complete.
Proof We know from Theorem 2.1 that
$s\alpha (\omega _0)$
is analytic. It remains to show that it is not Borel. Define a map
$f:\mathcal {P}(\mathbb {N}^{<\mathbb {N}}) \to X$
by
$f(T)=3{}^{\smallfrown } h(T)$
. The map is well defined since X contains
$\{0,1,2,3\}^{\mathbb {N}}$
. It is continuous since h is. We will show that
$T\in \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
is an ill-founded tree if and only if
$f(T)\in s\alpha (\omega _0)$
. This means
$\mathcal {T}_{\mathrm {IF}}=f^{-1}(s\alpha (\omega _0))$
, and since the preimage of a Borel set by a continuous map is always Borel, it follows that
$s\alpha (\omega _0)$
is not a Borel subset of X.
Suppose first that
$T\in \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
is an ill-founded tree. Let
$y\in \mathbb {N}^{\mathbb {N}}$
be an infinite branch of T. Continuing to use the notation from Lemma 3.1, we see that
$(T,y)\in R$
and so each of the points
$\omega _n(T,y)$
,
$n\in \mathbb {N}$
, belongs to X. Clearly there is a backward orbit branch of
$\omega _0$
with
$(\omega _n(T,y))_n$
as a subsequence. But
$\omega _n(T,y) \to 3{}^{\smallfrown } h(T) = f(T)$
as
$n\to \infty $
.
Conversely, choose any
$T\in \mathcal {P}(\mathbb {N}^{<\mathbb {N}})$
such that
$f(T)\in s\alpha (\omega _0)$
. Then we can choose a backward orbit branch of
$\omega _0$
with a subsequence converging to
$f(T)$
, so we get points
$\omega _i\in X$
and times
$t_i\geq 1$
,
$i\in \mathbb {N}$
, such that
$\omega _i\to 3{}^{\smallfrown } h(T)$
as
$i\to \infty $
and
$$ \begin{align} \sigma^{t_i}(\omega_{i+1})=\omega_i, \quad i\in\mathbb{N}. \end{align} $$
We may suppose without loss of generality that each
$\omega _i$
begins with the symbol 3. By the definition of X we may write
$\omega _i = \omega _{n_i}(T_i,y_i)$
for some
$(T_i,y_i)\in R$
,
$n_i\in \mathbb {N}$
. We warn the reader that
$y_i\in \mathbb {N}^{\mathbb {N}}$
is a whole infinite word; the subscript here does not refer to the symbol in position i, but to the ith infinite word in the sequence. Since
$n_i$
counts the number of 3s in
$\omega _i$
(except the last 3 before the 4), equations (1) and (3) imply that
$n_{i+1}> n_i$
. Thus the numbers
$n_i$
form an increasing sequence, and in particular
$n_i\geq i$
for all i. Write
$x_i=h(T_i)$
for all i. Again from (1) and (3) we get
$x_i|n_i=x_{i+1}|n_i$
and
$y_i|n_i=y_{i+1}|n_i$
for all i. Therefore we may pass to the limits
$x=\lim x_i$
,
$y=\lim y_i$
, and since
$\omega _i\to 3{}^{\smallfrown } h(T)$
we get
$x=h(T)$
. But h is a homeomorphism and therefore
$T=\lim T_i$
. Since each
$(T_i,y_i)\in R$
and R is closed, we conclude
$(T,y)\in R$
, that is, T is an ill-founded tree. This concludes the proof.
4 A non-Borel
$s\alpha $
-limit set in the square
The square is the Cartesian product
$I^2=[0,1]\times [0,1]$
with the usual Euclidean topology. For a mapping
$f:X\to X$
, a subset
$A\subseteq X$
is called invariant if
$f(A)\subseteq A$
and totally invariant if
$f^{-1}(A)=A$
. Two topological dynamical systems
$(X,f)$
,
$(Y,g)$
are called conjugate if there is a homeomorphism
$h:X\to Y$
such that
$h\circ f=g\circ h$
. The main goal of this section is to prove the following theorem.
Theorem 4.1. There is a continuous surjective map
$F : I^2 \to I^2$
and a point
$x_0\in I^2$
such that
$s\alpha (x_0)\subset I^2$
is
${\boldsymbol{\Sigma}}^1_1$
-complete.
The proof proceeds by constructing the map F. It has the form of a skew product
$F(x,y)=(f(x),g_x(y))$
. There is a closed subset S in the ‘x-axis’ of the square,
$S\subset I\times \{0\}\subset I^2$
, such that
$F^{-1}(S)=F(S)=S$
. The subsystem
$(S,F)$
is conjugate to the subshift
$(X,\sigma )$
constructed in the previous section.
Proposition 4.2. There is a surjective continuous map
$F:I^2\to I^2$
and a closed subset
$S\subset I^2$
such that
$F^{-1}(S)=F(S)=S$
and
$(S,F)$
is conjugate to
$(X,\sigma )$
.
Proof Start with the embedding
$e:5^{\mathbb {N}} \to I$
and the map
$f:I\to I$
given by
$$ \begin{align*}&\quad\quad \quad \quad \quad e(x_0x_1x_2\cdots{\kern-1pt})=\sum_{j=0}^{\infty} \frac{2x_j}{9^{j+1}}, \\f(x)&=\begin{cases}9x - 2i & \text{ for } x\in\bigg[\dfrac{2i}{9},\dfrac{2i+1}{9} \bigg], i\in\{0,1,2,3,4\}, \\[1em] (2i+2) - 9x & \text{ for } x\in\bigg[\dfrac{2i+1}{9},\dfrac{2i+2}{9} \bigg], i\in\{0,1,2,3\}.\end{cases}\end{align*} $$
Then f is the standard
$9$
-horseshoe with five increasing laps and four decreasing laps and
$C=e(5^{\mathbb {N}})\subset I$
is the Cantor set of points whose trajectories stay in the increasing laps; see Figure 1. Clearly
$f\circ e = e\circ \sigma $
, and so
$(C,f)$
is conjugate to
$(5^{\mathbb {N}},\sigma )$
. Henceforth we will write
$I_i=[{2i}/{9},({2i+1})/{9}]$
for the ith increasing lap of f.
By Lemma 3.3 we have
$\sigma (X)=X$
. That means we can write X as the following finite union of closed sets:
$$ \begin{align*} X=\bigcup_{i<5} X_i, \quad X_i:=\{x\in X~|~i{}^{\smallfrown} x \in X\}. \end{align*} $$
Here
$X_i$
is the ‘follower set’ of the symbol i in X, that is, the set of points in X which can be preceded by the symbol i and still belong to X.
Going through the embedding e, we get that the closed set
$A=e(X)\subset I$
is the union of the closed sets
$A_i=e(X_i)$
,
$i<5$
. Moreover, we have
$A\subset C$
and
$(A,f)$
is conjugate to
$(X,\sigma )$
. For any closed set
$Y\subseteq I$
, we write
$d(x,Y)=\min \{|x-y|~|~y\in Y\}$
for the distance from a point
$x\in I$
to Y. For
$i<5$
we define sets
$$ \begin{align*} B_i=\{x\in I ~|~ d(x,A_i) \leq d(x,A_j) \text{ for all }j<5\}. \end{align*} $$
Thus
$B_i$
represents the points
$x\in I$
for which
$A_i$
is as close or closer to x than any of the other sets
$A_j$
. Clearly the sets
$B_i$
are closed and their union is all of I. For points
$x\in A$
we have
$x\in B_i$
if and only if
$x\in A_i$
, because the distance to at least one of the sets
$A_i$
is zero. This shows that
$$ \begin{align} I=\bigcup_{i<5} B_i, \text{ and for all } i<5, B_i\cap A = A_i. \end{align} $$
Now we define a function
$\phi :I\to [0,\tfrac 12]$
. Let
$$ \begin{align} \phi(x)=\tfrac12 d(f(x),B_i) \quad \text{for } x\in I_i, i<5. \end{align} $$
This defines
$\phi $
on the increasing laps of f. On the decreasing laps of f we have already defined
$\phi $
at the endpoints, and we simply extend to any continuous function with
$0<\phi (x)\leq \tfrac 12$
whenever
$x\in I\setminus \bigcup _{i<5} I_i$
.
Now define a skew product mapping
$F:I^2\to I^2$
by
$$ \begin{align} F(x,y)=(f(x),g_x(y)) \quad \text{where } g_x(y)=\phi(x)+y\cdot(1-\phi(x)); \end{align} $$
The map
$F:I^2\to I^2$
applied to nine rectangular regions. Arrows indicate orientation. C is the full Cantor set
$5^{\mathbb {N}}$
embedded into I. A is the embedded copy of the shift space X. The sets
$B_i$
have gaps around the points that cannot be preceded by the symbol i. For example,
$B_0$
is missing the embedded image of
$40^{\infty }$
, since this point can only be preceded by a
$3$
, and
$B_4$
is a singleton, since only
$0^{\infty }$
can be preceded by a
$4$
. (Note: the gaps are not drawn to scale, and many smaller gaps are not visible at all.) The choice of
$\phi $
causes the image of each rectangle
$I_i\times I$
to meet the x-axis of the square only in the set
$B_i$
. The point a represents
$02^{\infty }$
, so
$a,f(a)\in A$
and
$\phi (a)=0$
. The point b represents
$42^{\infty }$
, so
$b\not \in A$
,
$f(b)\in A$
, and
$\phi (b)>0$
.
Let
$E:5^{\mathbb {N}}\to I^2$
be the embedding
$E(x)=(e(x),0)$
and let
$S=E(X)=A\times \{0\}$
. We claim that
$\phi $
has the following three properties:
-
(i)
$\phi (x)=0$
for all
$x\in A$
; -
(ii)
$\phi (x)>0$
if
$x\not \in A$
but
$f(x)\in A$
; -
(iii) for each
$y\in I$
there is a preimage
$x\in f^{-1}(y)$
with
$\phi (x)=0$
.
Property (i) gives
$F\circ E=E \circ \sigma $
, which implies that
$F(S)=S$
and
$(S,F)$
is conjugate to
$(X,\sigma )$
. Property (ii) implies that
$F^{-1}(S)=S$
. Property (iii) makes F surjective. This is everything we needed to show about the system
$(S,F)$
. It remains to establish properties (i)–(iii) of the function
$\phi $
.
To prove property (i) choose
$x\in A$
and write
$x=e(x_0x_1\cdots )$
with
$x_0x_1\cdots \in X$
. Let
$i=x_0$
so
$x\in I_i$
. Then
$x_1x_2\cdots \in X_i$
so
$f(x)\in A_i \subseteq B_i$
and therefore
$\phi (x)=0$
.
To prove property (ii) we choose a point
$x\not \in A$
such that
$f(x)\in A$
. There are two cases. First, suppose
$x\not \in C$
. If x is in an increasing lap of f then
$f(x)\not \in C$
either, contradicting
$f(x)\in A$
. But if x is not in an increasing lap of f then
$\phi (x)>0$
by the definition of
$\phi $
, so we are done. Second, suppose
$x\in C\setminus A$
. Then we can write
$x = e(x_0 x_1 \cdots )$
with
$x_0 x_1\cdots \in 5^{\mathbb {N}}\setminus X$
. Let
$i=x_0$
, so
$I_i$
is the lap containing x. Then
$x_1 x_2 \cdots \not \in X_i $
, so
$f(x)\not \in A_i$
. But we supposed
$f(x)\in A$
, so by (4) we have
$f(x)\not \in B_i$
. Therefore
$\phi (x)>0$
by the definition of
$\phi $
.
To prove property (iii) pick any point
$y\in I$
. Since the sets
$B_i$
cover I we can find i with
$y\in B_i$
. Then we take
$x=f|_{I_i}^{-1}(y)\in I_i$
. Then
$\phi (x)=0$
by the definition of
$\phi $
.
Proof of Theorem 4.1. By Theorem 3.4 the subshift
$(X,\sigma )$
has a point
$\omega _0$
such that
$s\alpha (\omega _0)\subset X$
is not Borel. By Proposition 4.2 there is a continuous surjection
${F:I^2\to I^2}$
and a closed subset
$S\subset I^2$
such that
$F^{-1}(S)=F(S)=S$
and
$(S,F)$
is conjugate to
$(X,\sigma )$
. Let
$E:X\to S \subset I^2$
denote the conjugacy and let
$x_0 = E(\omega _0)$
. The backward orbit branches of
$x_0$
in the system
$(I^2,F)$
are the same as the backward orbit branches in the subsystem
$(S,F)$
, and these correspond through the conjugacy to the backward orbit branches of
$\omega _0$
in
$(X,\sigma )$
. Therefore
$s\alpha (x_0)=E(s\alpha (\omega _0))$
. Since E is a topological embedding we conclude that
$s\alpha (x_0)\subset I^2$
is not Borel.
Remark 4.3. The only property of the subshift
$(X,\sigma )$
which was really needed in the proof of Proposition 4.2 was surjectivity
$\sigma (X)=X$
. Thus, the same proof technique leads to the following general embedding result.
Proposition 4.4. Any subshift
$X\subseteq \{0,\ldots, r-1\}^{\mathbb {N}}$
,
$r\geq 2$
, with
$\sigma (X)=X$
can be embedded as a totally invariant subsystem of a surjective map on the square.
Proof The proof is essentially the same as the proof of Proposition 4.2. To accommodate a shift space with r symbols we divide the square into
$2r-1$
vertical strips and use for the base map the full (
$2r-1$
)-horseshoe. No other significant changes are needed.
Remark 4.5. In dimension one, the
$s\alpha $
-limit sets of an interval map
$f:I\to I$
are always Borel and can only occur at or below the second level of the Borel hierarchy (they are simultaneously
$F_{\sigma }$
and
$G_{\delta }$
; see [Reference Hantáková and Roth13]). But the possibility to embed subshifts into the square without the restrictions imposed by the order structure of
$\mathbb {R}$
gives much more flexibility to dynamical systems in dimension two than in dimension one. This gives some explanation of why their special
$\alpha $
-limit sets can be more complex.
Acknowledgements
The first author was supported by NSF grant DMS-1800323. The second author was supported by grant 2019/34/E/ST1/00082 for the project ‘Set theoretic methods in dynamics and number theory,’ NCN (The National Science Centre of Poland). The third author was supported by RVO (Czech Republic) funding for IČ47813059.
