Saturday, June 11, 2016

Simple Chaotic System

Define a function $d:\left\{0,1\right\}^\mathbb{N}\times\left\{0,1\right\}^\mathbb{N}\to\left[0,\infty\right)$ as follows:

If $x=\left(x_1,x_2,\dots\right)$ and $y=\left(y_1,y_2,\dots\right)$, then$$d\left(x,y\right)=\frac{1}{2^n}\text{, where }n=\min\left\{i\in\mathbb{N}:x_i\neq y_i\right\},$$and $d\left(x,y\right)=0$ if and only if $x=y$.

Claim: $d$ is a metric on $\left\{0,1\right\}^\mathbb{N}$.
Proof: Let $x=\left(x_1,x_2,\dots\right)$, $y=\left(y_1,y_2,\dots\right)$, and $z=\left(z_1,z_2,\dots\right)$ be elements of $\left\{0,1\right\}^\mathbb{N}$.
It follows by definition that $d\left(x,y\right)=0$ if and only if $x=y$. On the other hand, suppose that $x\neq y$. Then there exists an $n\in\mathbb{N}$ such that $d\left(x,y\right)=1/2^n>0$. Therefore, $d\left(x,y\right)\geqslant0$ for all $x,y\in\left\{0,1\right\}^\mathbb{N}$.
Suppose that $x=y$. Then $d\left(x,y\right)=0=d\left(y,x\right)$. On the other hand, suppose that $x\neq y$. Then there exists an $n\in\mathbb{N}$ such that $d\left(x,y\right)=1/2^n$. Since $\min\left\{i\in\mathbb{N}:x_i\neq y_i\right\}=n=\min\left\{i\in\mathbb{N}:y_i\neq x_i\right\}$, it follows that $d\left(x,y\right)=d\left(y,x\right)$. Therefore, $d\left(x,y\right)=d\left(y,x\right)$ for all $x,y\in\left\{0,1\right\}^\mathbb{N}$.
Suppose that $x=z$. Then $d\left(x,z\right)=0\leqslant d\left(x,y\right)+d\left(y,z\right)$ since $d$ maps to nonnegative values. On the other hand, suppose that $x\neq z$. Then there exists an $n\in\mathbb{N}$ such that $d\left(x,z\right)=1/2^n$. Suppose that $x=y$. Then $d\left(x,z\right)=d\left(y,z\right)\leqslant d\left(x,y\right)+d\left(y,z\right)$. On the other hand, suppose that $x\neq y$. Then there exists an $m\in\mathbb{N}$ such that $d\left(x,y\right)=1/2^m$. Suppose that $m\leqslant n$. Then $d\left(x,z\right)=1/2^n\leqslant1/2^m=d\left(x,y\right)\leqslant d\left(x,y\right)+d\left(y,z\right)$. On the other hand, suppose that $m>n$. Then $\min\left\{i\in\mathbb{N}:y_i\neq z_i\right\}=n$, which implies that $d\left(x,z\right)=d\left(y,z\right)\leqslant d\left(x,y\right)+d\left(y,z\right)$. Therefore, $d\left(x,z\right)\leqslant d\left(x,y\right)+d\left(y,z\right)$ for all $x,y,z\in\left\{0,1\right\}^\mathbb{N}$.
Hence, $d$ is a metric on $\left\{0,1\right\}^\mathbb{N}$. $\square$

Claim: The topology induced by $d$ is the same as the product topology on $\left\{0,1\right\}^\mathbb{N}$.
Proof: Let $x=\left(x_1,x_2,\dots\right)\in\left\{0,1\right\}^\mathbb{N}$, let $\varepsilon>0$, and let $B=B_d\left(x,\varepsilon\right)$. Then $x\in B$. Let $N$ be the smallest positive integer such that $1/2^N<\varepsilon$, and let $B'=\left\{x_1\right\}\times\left\{x_2\right\}\times\cdots\times\left\{x_{N-1}\right\}\times\left\{0,1\right\}\times\left\{0,1\right\}\times\cdots$. Then $x\in B'$. Let $y\in B'$. Then $d\left(x,y\right)\leqslant1/2^N<\varepsilon$, which implies that $y\in B$, which in turn implies that $B'\subseteq B$.
Conversely, let $N$ be a positive integer greater than $1$, and let $B'=\left\{x_1\right\}\times\left\{x_2\right\}\times\cdots\times\left\{x_{N-1}\right\}\times\left\{0,1\right\}\times\left\{0,1\right\}\times\cdots$. Then $x\in B'$. Let $\varepsilon=1/2^{N-1}$, and let $B=B_d\left(x,\varepsilon\right)$. Then $x\in B$. Let $y\in B$. Then $d\left(x,y\right)<\varepsilon=1/2^N$, which implies that $y\in B'$, which in turn implies that $B\subseteq B'$.
Therefore, since each $B$ is a basis element of the topology induced by $d$, and since each $B'$ is a basis element of the product topology on $\left\{0,1\right\}^\mathbb{N}$, it follows from Lemma $13.3$ of Munkres that the topologies generated by their respective bases are the same. $\square$

Claim: $\left(\left\{0,1\right\}^\mathbb{N},d\right)$ is complete.
Proof: Let $\left\{x_i\right\}_{i=1}^\infty$ be a Cauchy sequence of elements $x_i=\left(x_{i,1},x_{i,2},\cdots\right)\in\left\{0,1\right\}^\mathbb{N}$ and let $\varepsilon>0$. Then there exists an $N\in\mathbb{N}$ such that for all integers $m,n\geqslant N$, it is the case that $d\left(x_m,x_n\right)\leqslant1/2^k<\min\left\{1/2,\varepsilon\right\}$, where $k$ is the smallest positive integer for which this inequality holds. This implies that $x_{m,j}=x_{n,j}$ for all positive integers $j<k$ and all integers $m,n\geqslant N$. Therefore, $\left\{x_{i,j}\right\}_{i=1}^\infty$ converges because it is eventually constant. Let $\lim_{i\to\infty}x_{i,j}=y_j$. Since $k$ approaches infinity as $\varepsilon$ approaches zero, it is the case that for any $j\in\mathbb{N}$, one can find an $\varepsilon>0$ such that $j<k$, which implies that $y_j$ exists for all $j\in\mathbb{N}$. Therefore, $y=\left(y_1,y_2,\cdots\right)\in\left\{0,1\right\}^\mathbb{N}$.
It suffices to show that $\left\{x_i\right\}_{i=1}^\infty$ converges to $y$: Let $\varepsilon>0$. If $\varepsilon>1/2$, then $d\left(x_i,y\right)\leqslant1/2<\varepsilon$ for all $i\in\mathbb{N}$. Therefore, suppose that $0<\varepsilon\leqslant1/2$ and let $k$ be the smallest positive integer such that $1/2^k<\varepsilon$. Then for all positive integers $j<k$, there exists an $N_j\in\mathbb{N}$ such that $\left\{x_{i,j}\right\}_{i=N_j}^\infty$ is constant—with this constant value being equal to $y_j$. Let $N=\max\left\{N_1,N_2,\dots,N_{k-1}\right\}$. Then $d\left(x_i,y\right)\leqslant1/2^k<\varepsilon$ for all $i\geqslant N$, which implies that $\left\{x_i\right\}_{i=1}^\infty$ converges to $y$. Hence, $\left(\left\{0,1\right\}^\mathbb{N},d\right)$ is complete. $\square$

The shift map is the function $\sigma:\left\{0,1\right\}^\mathbb{N}\to\left\{0,1\right\}^\mathbb{N}$ defined by $\sigma\left(\left(x_1,x_2,x_3,\dots\right)\right)=\left(x_2,x_3,x_4,\dots\right)$.

Claim: The shift map is uniformly continuous.
Proof: Let $\varepsilon>0$, let $k$ be the smallest positive integer such that $1/2^k<\varepsilon$, let $\delta=1/2^{k}$, and let $x,y\in\left\{0,1\right\}^\mathbb{N}$ such that $d\left(x,y\right)<\delta$. This implies that $d\left(x,y\right)\leqslant1/2^{k+1}$, which in turn implies that $x_i=y_i$ for all positive integers $i\leqslant k$. It follows that $\sigma\left(x\right)_i=\sigma\left(y\right)_i$ for all positive integers $i<k$, which implies that $d\left(\sigma\left(x\right),\sigma\left(y\right)\right)\leqslant1/2^k<\varepsilon$. Therefore, the shift map is uniformly continuous. $\square$

Claim: If $\sigma^n\left(x\right)=x$ for some $n\in\mathbb{N}$, then $\sigma^{kn}\left(x\right)=x$ for all $k\in\mathbb{N}$.
Proof: Let $k=1$. Then $\sigma^{kn}\left(x\right)=\sigma^n\left(x\right)=x$. Assume that $\sigma^{kn}\left(x\right)=x$ for some $k\in\mathbb{N}$. Then $\sigma^{kn}\left(x\right)=\sigma^{kn}\left(\sigma^n\left(x\right)\right)=\sigma^{kn+n}\left(x\right)=\sigma^{\left(k+1\right)n}\left(x\right)=x$. Therefore, by the principle of mathematical induction, it is the case that $\sigma^{kn}\left(x\right)=x$ for all $k\in\mathbb{N}$. $\square$

Claim: A point $x\in\left\{0,1\right\}^\mathbb{N}$ has period $n\in\mathbb{N}$ if and only if $x$ is a repeating sequence of length $n$.
Proof: Assume that $x$ is a repeating sequence of length $n\in\mathbb{N}$. Then $x=\left(x_1,x_2,\dots,x_n,x_1,x_2,\dots,x_n,\dots\right)$. Observe that $\sigma^n\left(x\right)=\left(x_1,x_2,\dots,x_n,x_1,x_2,\dots,x_n,\dots\right)=x$. Therefore, $x$ has period $n$.
Conversely, assume that $x=\left(x_1,x_2,\dots\right)$ has period $n\in\mathbb{N}$. Then $\sigma^n\left(x\right)=x$, which implies that $x_i=x_{n+i}$ for all positive integers $i\leqslant n$. By the previous claim, it is the case that $x_i=x_{kn+i}$ for all $k\in\mathbb{N}$. Therefore, $x$ has the following form:$$\begin{align*}x&=\left(x_1,x_2,\dots,x_n,x_{n+1},x_{n+2},\dots,x_{n+n},\dots,x_{kn+1},x_{kn+2},\dots,k_{kn+n},\dots\right)\\&=\left(x_1,x_2,\dots,x_n,x_1,x_2,\dots,x_n,\dots\right),\end{align*}$$which implies that $x$ is a repeating sequence of length $n$. $\square$

Claim: The set $S$ of periodic points in $\left\{0,1\right\}^\mathbb{N}$ is countable.
Proof: Let $S_n$ be the set of elements of $S$ having period $n\in\mathbb{N}$. Then $\left|S_n\right|=2^n$ and$$S=\bigcup_{n=1}^\infty S_n,$$which is a countable union of finite sets, which implies that $S$ is countable. $\square$

Claim: The set $S$ of periodic points in $\left\{0,1\right\}^\mathbb{N}$ is dense in $\left\{0,1\right\}^\mathbb{N}$.
Proof: Clearly, $\overline{S}\subseteq\left\{0,1\right\}^\mathbb{N}$ since $S\subseteq\left\{0,1\right\}^\mathbb{N}$ and $\left\{0,1\right\}^\mathbb{N}$ is complete. On the other hand, let $x\in\left\{0,1\right\}^\mathbb{N}$. If $x$ is periodic, then $x\in S\subseteq\overline{S}$. Otherwise, let $U=U_1\times U_2\times\cdots\times U_n\times\left\{0,1\right\}\times\left\{0,1\right\}\times\cdots$ be a neighborhood of $x$ and define $y=\left(y_1,y_2,\dots,y_n,y_1,y_2,\dots,y_n,\dots\right)$, where $y_i\in U_i$ for all positive integers $i\leqslant n$. Then $y\neq x$ and $y\in U\cap S$, which implies that $x$ is a limit point of $S$. Therefore, $x\in\overline{S}$, which implies that $\left\{0,1\right\}^\mathbb{N}\subseteq\overline{S}$. Hence, $\overline{S}=\left\{0,1\right\}^\mathbb{N}$, which implies that $S$ is dense in $\left\{0,1\right\}^\mathbb{N}$. $\square$

Claim: The shift map has sensitive dependence on initial conditions.
Proof: Let $\beta=1/2$, let $x\in\left\{0,1\right\}^\mathbb{N}$, let $\varepsilon>0$, let $n$ be the smallest positive integer such that $1/2^n<\varepsilon$, and let $y\in B_d\left(x,\varepsilon\right)$. Then $d\left(x,y\right)\leqslant1/2^n<\varepsilon$, which implies that $x=y$ or $m=\min\left\{i\in\mathbb{N}:x_i\neq y_i\right\}\geqslant n$. Let $y$ be such that $m=n+1$. Then $d\left(\sigma^n\left(x\right),\sigma^n\left(y\right)\right)=1/2=\beta$. Therefore, $\sigma$ has sensitive dependence on initial conditions. $\square$