Fundemental Theorem of Dynamical Systems (Part 2)

Now we begin to prove the theorem.

4.Attractor-repeller pairs

Definition: A compact set $A \subseteq X$ is an attractor for $f$ if there exists $U$ open, $f(\bar U) \subseteq U$ and $\displaystyle \bigcup_{i=0}^\infty f^i(U) = A$. $U$ is called a basin of attraction.

For any attractor $A \subseteq X$, $U$ be a basin for $A$, let $U^\ast = X \backslash \bar U, \ U^\ast$ is open. By definition, $f(A) = A$ and $f(A^\ast) = A^\ast$. We also have

$f^{-1}(\overline{U^\ast}) = f^{-1}(\bar{X \backslash \bar U}) \subseteq X \backslash f^{-1}(U) \subseteq X \backslash U \subseteq \overline{U^\ast}$

Definition: A repeller for $f$ is an attractor for $f^{-1}$. A basin of repelling for $f$ is a basin of attracting for $f^{-1}$.

Hence $A^\ast$ is a repeller for $f$ with basin $U^\ast$.

It’s easy to see that $A^\ast$ is defined independent of the choice of basin for $A$. (Exercise)

We call such a pair $A, \ A^\ast$ an attracting-repelling pair.

The following two properties of attracting-repelling pairs are going to be important for our proof of the theorem.

Proposition 1: There are at most countably many different attractors for $f$.

Proof: Since $X$ is compact metric, there exists countable basis $\mathcal{U} = \{U_i\}_{i \in \mathbb{N}}$ that generates the topology.

For any attractor $A$, any attracting basin $\mathcal{B}$ of $A$ is a union of sets in $\mathcal{U}$, i.e. $\displaystyle \mathcal{B} = \bigcup_{i=1}^\infty U_{n_i}$latex for some subsequence $(n_i)$ of $\mathbb{N}$.

Since $A$ is compact, $U_{n_i}$ is an open cover of $A$, we have some $\{ m_1, \ m_2, \ \cdots \ m_k \} \subseteq \{n_i\}_{i \in \mathbb{N}}$ s.t. $\{ U_{m_1}, \ U_{m_2}, \ \cdots, \ U_{m_k} \}$ covers $A$.
Let $B' = U_{m_1} \cup U_{m_2} \cup \cdots \cup U_{m_k}$ hence $A \subseteq B' \subseteq B$. We have

$\displaystyle A \subseteq \bigcap_{n \in \mathbb{N}} f^n(B') \subseteq \bigcap_{n \in \mathbb{N}} f^n(B)$

Since $B$ is an attracting basin for $A$, all three sets are equal. Hence $A = \bigcap_{n \in \mathbb{N}} f^n(B')$. i.e. any attractor is intersection of foreward interates of come finite union of sets in $\mathcal{U}$. Since $\mathcal{U}$ is countable, the set of all finite subset of it is coubtable.

Hence there are at most countably many different attractors. This establishes the proposition.

By proposition 1, we let $(A_n)_{n \in \mathbb{N}}$ be a list of all attractors for $f$. Now we are going to relate the arrtactor-repeller pairs to the chain recurrent set and chain transitive components.

Proposition 2:

$\mathcal{R}(f) = \displaystyle \bigcap_{n \in \mathbb{N}}(A_n \cup A^\ast_n)$

Proof: i) $\mathcal{R}(f) \subseteq \bigcap_{n \in \mathbb{N}}(A_n \cup A^\ast_n)$

This is same as saying for any attractor $A$, $\mathcal{R}(f) \subseteq (A \cup A^\ast)$.

For all $x \notin (A \cup A^\ast)$, let $B$ be a basin of $A$, then there is $N \in \mathbb{N}$ for which $x \notin (f^N(B) \cup f^{-N}(B^\ast))$ (recall that $B^\ast$ is the dual basin of $B$ for $A^\ast$). Since $B^\ast = X \backslash \overline{B}$ and $f(\overline{B}) \subseteq B$ we conclude

$X \backslash f^{-N}(B^\ast) = f^{-N}(\overline{B}) \subseteq f^{-N-1}(f(\overline{B})) \subseteq f^{-N-1}(B)$

Hence $x \in f^{-N-1}(B)$. Let $M$ be the smallest integer for which $x \in f^{-M}(B)$. Hence $x \in f^{-M}(B) \backslash f^{-M+1}(B)$. Let $U = f^{-M}(B)$ is also a basin for $A$.

Now we show such $x$ cannot be chain recurrent: Since $X \backslash f(U)$ and $\overline{f^2(U)}$ are compact and disjoint, we may let

$\varepsilon_1 = \frac{1}{2} \min\{ d(a, b) \ | \ a \in X \backslash f(U), \ b \in \overline{f^2(U)} \}$

Since $f(x) \in f(U)$, there exists some $\varepsilon_2$ s.t.

$\overline{B(f(x), \varepsilon_2)} \subseteq f(U)$

$f(\overline{B(f(x), \varepsilon_2)}) \subseteq f^2(U)$ so there exists $\varepsilon_3$ s.t.

$N(f(\overline{B(f(x), \varepsilon_2)}), \varepsilon_3) \subseteq f^2(U)$

(Here $B(p, r)$ denotes the ball of radius $r$ around $p$ and $N(C, r)$ denotes the $r$-neignbourhood of compact set $C$)

Now set $\varepsilon = \min\{ \varepsilon_1, \ \varepsilon_2, \ \varepsilon_3\}$, for any $\varepsilon$-chain $x, x_1, x_2, \cdots$, we have: Since $\varepsilon < \varepsilon_2$ and $\varepsilon_3$, $x_1 \in B(f(x), \varepsilon_2)\subseteq f(U)$ and $x_2 \in B(f(x_1), \varepsilon_3) \subseteq N(f(\overline{B(f(x), \varepsilon_2)}), \varepsilon_3) \subseteq f^2(U)$. Hence the third term of any such chain must be in $f^2(U)$. Since $\varepsilon < \varepsilon_1$, no $\varepsilon$-chain starting at $x_2$ can reach $X \backslash f(U)$, in particular, the chain $x, x_1, x_2, \cdots$ does not come back to $x$. Hence we conclude that $x$ is not chain recurrent. ii) $\bigcap_{n \in \mathbb{N}}(A_n \cup A^\ast_n) \subseteq \mathcal{R}(f)$ Suppose not, there is $x \in \bigcap_{n \in \mathbb{N}}(A_n \cup A^\ast_n)$ and $x \notin \mathcal{R}(f)$. i.e. for some $\varepsilon > 0$ there is no $\varepsilon$-chain from $x$ to itself. Let $U$ be the open set consisting all points that can be connected from $x$ by an $\varepsilon$-chain.

We wish to generate an attractor by $V$, to do this all we need to check is $f(\overline{V}) \subseteq V$:
For any $y \in \overline{V}$ there exists $y' \in V$ with $d(f(y), f(y')) < \varepsilon$. Since $y' \in V$, there is $\varepsilon$-chain $x, x_1, \cdots, x_n, y'$ which gives rise to $\varepsilon$-chain $x, x_1, \cdots, x_n, y', f(y)$. Therefore $f(\overline{V}) \subseteq V$.

Hence $\displaystyle A = \bigcap_{n \in \mathbb{N}} f^n(V)$ is an attractor with $V$ as a basin.

By assumption, $x \in A \cup A^\ast$, since $A \in V$ and there is no $\varepsilon$-chain from $x$ to itself, $x$ cannot be in $A$. i.e. $x \in A^\ast$ Take any limit point $y$ of $(f^n(x))_{n\in \mathbb{N}}$, since $A^\ast$ is compact $f$-invariant we have $y \in A^\ast$. But since we can find $N$ where $d(f^N(x), y)<\varepsilon$, $x, f(x), \cdots, f^{N-1}(x), y$ gives an $\varepsilon$-chain from $x$ to $y$, hence $y \in V$.

Recall that $V$ is a basin of $A$ hence $A^\ast \cap V$ is empty. Contradiction. Establishes proposition 2.

This proposition says that to study the chain recurrent set is the same as studying each attractor-repeller pair of the system. But the dynamics is very simple for each such pair as all points not in the pair will move towards the attractor under foreward iterate. We can see that such property is goint to be of importantce for our purpose since the dynamical for each attractor-repeller pair is like the sourse-sink map.

5. Main ingredient

Here we are going to prove a lemma that’s going to produce for us the ‘building blocks’ of our final construction. Namely a function for each attracting-repelling pair that strickly decreases along the orbits not in the pair. In light of proposition $2$, we should expect to put those functions together to get our complete Lyapunov function.

Lemma1: For each attractor-repeller pair $A, A^\ast$ there exists continuous function $g: X \rightarrow [0,1]$ s.t. $g^{-1}(0)=A, \ g^{-1}(1)=A^\ast$ and $g(f(p)) < g(p)$ for all $p \notin (A\cup A^\ast)$.

Proof: First we define $\varphi: X \rightarrow [0,1]$ s.t.

$\varphi(x) = \frac{d(x,A)}{d(x, A)+d(x, A^\ast)}$

Note that $\phi$ takes value $0$ only on $A$ and $1$ only on $A^\ast$. However, $\phi$ can’t care less about orbits of $f$.

Define $\bar\varphi(x) = \sup\{\varphi(f^n(x)) \ | \ n\in\mathbb{N} \}$. Hence automatically for all $x$, $\bar \varphi(f(x)) \leq \bar \varphi(x)$. Since no points accumulates to $A^\ast$ under positive iterations, we still have the $\bar \varphi^{-1}(0)=A$ and $\bar \varphi^{-1}(1) = A^\ast$.

We now show that $\bar\varphi$ is continuous:

For $x \in A^\ast$ and $(x_i)\rightarrow x$, $\varphi(x_i) \leq \bar\varphi(x_i) \leq 1$ and $(\varphi(x_i)) \rightarrow 1$ hence $\bar\varphi(x_i)\rightarrow 1$ i.e. $\bar\varphi$ is continuous on $A^\ast$.

For $x \in A$ we use the fact that $A$ is attracting. Let $B$ be a basin of $A$. For all $(x_i) \rightarrow x$, for any $\varepsilon>0$, there is $N \in \mathbb{N}$ s.t. $f^N(B) \subseteq N(A, \varepsilon)$. Therefore for some $x_i \in f^N(B)$, all $f^n(x_i)$ are in $N(A, \varepsilon)$ i.e. $\varphi(f^n(x_i))\leq \frac{\varepsilon}{\varepsilon+C}$ hence $\bar\varphi(x_i)\leq \frac{\varepsilon}{\varepsilon+C}$. But for some $M \in \mathbb{N}$ and all $m>M$, $x_m \in B$. Therefore $\bar\varphi(x_i) \rightarrow 0$. $\bar\varphi$ is continuous on $A$.

Let $T = \overline{B} \backslash f(B)$, for any $\displaystyle x \in T, \ r=\inf_{x \in T} \varphi(x)$, since $f^n(T) \subseteq f^n(\overline{B})$, there exists $N>0$ s.t. for all $n>N$ $\varphi(f^n(T))\subseteq [0,r/2]$. i.e. $\displaystyle \bar\varphi9x) = \max_{0\leq n\leq N} \varphi(f^n(x))$ which is countinous. Since those ‘bands’ $T$ partitions the whole $X$ (by taking $B_n$ to be $f^n(B) \backslash f^{n+1}(B)$), hence we have proven $\bar\varphi$ is continuous on the whole $X$.

Finally, we define

$\displaystyle g(x) = \sum_{n=0}^\infty \frac{\bar\varphi(f^n(x))}{2^{n+1}}$

We check that $g$ is continuous since $\bar\varphi$ is. $g$ takes values $0$ and $1$ only on $A$ and $A^\ast$, respectively. For any $x \notin (A \cup A^\ast)$,

$\displaystyle g(f(x))-g(x) = \sum_{n=0}^\infty \frac{\bar\varphi(f^{n+1}(x))-g(f^n(x))}{2^{n+1}}$

therefore $g(f(x))-g(x) = 0$ iff $\bar\varphi(f^{n+1}(x)) = \bar\varphi(f^n(x))$ for all $n$ i.e. $\bar\varphi$ is constant on the orbit of $x$. But this cannot be since there is a subsequence of $(f^n(x))$ converging to some point in $A$, continuity of $\bar\varphi$ tells us this constant has to be $0$ hence $x \in A$.

Therefore $g$ is strictly decreasing along orbits of $f$ not in $(A \cup A^\ast)$.

Establishes lemma 1.

6.Proof of the main theorem

The proof of the main theorem now follows easily from what we have established so far.

First we restate the fundamental theorem of dynamical systems:

Theorem: Complete Lyapunov function exists for any homeomorphisms on compact metric spaces.

Proof: First we enumerate the countably many attractors as $(A_n)_{n \in \mathbb{N}}$. For each $A_n$, we have function $g_n: X \rightarrow R$ where $g_n$ is $0$ on $A_n$, $1$ on $A_n^\ast$ and is strictly decreasing on $X \backslash ( A_n \cup A_n^\ast)$.
Define $g: X \rightarrow \mathbb{R}$ by

$\displaystyle g(x) = 2 \cdot \sum_{n=1}^\infty \frac{g_n(x)}{3^n}$

Since each $g_n$ is bounded between $0$ and $1$, the sequence of partial sums converge uniformly. Hence the limit function $g$ is continuous.

For points $p \in \mathcal{R}(f)$, we have $p \in (A_n \cup A_n^\ast)$ for all $n \in \mathbb{N}$. i.e. $latex \ \forall n \in \N, \ g_n(p) = 0$ or $g_n(p) = 1$. Hence we have

$g(p) = \sum_{n=1}^\infty \frac{2 \cdot g_n(p)}{3^n} = \sum_{n=1}^\infty \frac{a_n}{3^n}$

where each $a_n$ is in $\{0, 2 \}$. This is same as saying the base-$3$ expansion of $g(p)$ only contains digits $0$ and $2$. We conclude $g(\mathcal{R}(f)) \subseteq \mathcal{C}$ where $\mathcal{C}$ is the standard middle-third Cantor set in $[0, 1]$. i.e. $g(\mathcal{R}(f))$ is compact and nowhere dense in $\mathbb{R}$.

For $p \notin \mathcal{R}(f)$, there exists $n \in \mathbb{N}$ such that $p \notin (A_n \cup A_n^\ast)$, hence $g_n(f(p)) < g_n(p)$. This implies $g(f(p)) < g(p)$ since $g_i(f(p)) \leq g_i(p)$ for all $i \in \mathbb{N}$. i.e. $g$ is strictly decreasing along orbits that are not chain recurrent.

To show $g$ is constant only on the chain-transitive components, we need the following lemma:

Claim: $p, \ q \in \mathcal{R}(f)$ are in the same chain-transitive component iff there is no attracting-repelling pair $A, \ A^\ast$ where one of $p, \ q$ is in $A$ while the other in $A^\ast$.

Proof (of claim):$\Rightarrow$” Suppose $x, y \in \mathcal{R}(f)$ and $x \sim y$, for any attractor $A$, if $x \notin A$ and $y \notin A$, then $x, y$ are both in $A^\ast$ and we are done. Hence suppose at least one of $x, y$ is in $A$. W.L.O.G. suppose $x \in A$. Let $B$ be a basin of $A$. Since $\overline{f(B)}, \ X\backslash B$ are closed and disjoint, we may choose $\varepsilon<\min\{ d(a, b) \ | \ a \in (X\backslash B), \ b \in \overline{f(B)} \}$. By the same arguement as in proposition $2$, there are no $\varepsilon/2$-chain (with length $>1$) from any point in $f{B}$ to any point in $X \backslash B$. Hence there is also no $\varepsilon/2$-chain from any point in $A$ to any point in $A^\ast$. Hence $y \notin A^\ast$ i.e. $y \in A$.

$\Leftarrow$” Suppose for any attractor $A$, $x \in A$ iff $y \in A$. For any $\varepsilon>0$, let $U$ be the set of all points $y$ for which there is an $\varepsilon$-chain from $x$ to $y$, as defined in proposition $2$. We have showed in proposition $2$ that $U$ is a basin of some attractor $A'$. Since $x \in \mathcal{R}(f) \subseteq (A' \cup {A'}^\ast)$ and $x \in U$, hence $x \in A'$. Hence by our assumption, $y$ must be also in $A'$. Hence $y \in U$ i.e. there is an $\varepsilon$-chain from $x$ to $y$. Since the construction is symetric, we may also show there is an $\varepsilon$-chain from $y$ to $x$. i.e. $x\sim y$.

Establishes the claim.

Finally, for $p, q \in \mathcal{R}(f)$, $g(p) = g(q)$ means $g(p)$ and $g(q)$ has the same base-$3$ expansion in the Cantor set. This is same as saying $\forall i \in \mathbb{N}, \ g_i(p) = g_i(q) \in \{0, 2\}$, which is to say there is no $i \in \mathbb{N}$ for which one of $p, \ q$ is in $A_i$ while the other in $A_i^\ast$. Hence by Lemma, we conclude that $g(p) = g(q)$ iff $p, \ q$ are in the same chain transitive component.

This establishes our theorem.

3 thoughts on “Fundemental Theorem of Dynamical Systems (Part 2)”

1. The proof of Proposition 2 is not clear to me how you concluded that the chain x, x_1, x_2, \ cdots does not come back to x

Like