Some Philosophy and Definitions

How much hope do we mortals have to achieve true understanding and mastery of nature? Doubtlessly our own strengths and limitations are what primarily determine the answer to this question. That, essentially, is why I'm a psychology major. But while I have my math-major hat on, I'd like to approach this issue from the other end and ask: how tractable is the universe?

The outlook is actually quite good. After millennia of sluggish progress, humans have made great strides since the seventeenth century in physics, technology, medicine, and biology. Science is finally catching up with mathematics. Mathematics played a large role in making all this possible, of course. We mustn't neglect to be grateful to the universe for being so wonderfully mathematical, for accomplishing all its dizzying complexity with a bunch of unyieldingly consistent and hence eminently knowable rules. Even in the nastiest cases, when a natural process is nondeterministic down to the participating elementary particles, the process remains governed by laws of probability.

Yet actually, there is no guarantee that mathematics is always tractable. The existence of unprovable true statements, undecidable formal languages, and undefinable real numbers demonstrates how any formal system strong enough to be useful is also strong enough to formulate questions that it's too weak to answer. This may be understood as an intractable characteristic of mathematical entities in theory. My concern in these pages is with an intractable characteristic of mathematical entities in practice, a way in which the properties of certain systems interact with the unavoidable shortcomings of applied mathematics to royally screw us over. We're going to talk about chaotic functions, functions concerning which, in a particular but important sense, approximation is useless.

Okay, Can We Do Some Actual Mathematics Now?

If you insist.

Defintion
Given $f:X\to X$, ${f}^{n}$ is defined as $f\circ f\circ \cdots \circ f$ for $n$ instances of $f$; that is, $f$ composed with itself $n-1$ times. ${f}^{0}$ is defined to be the identity function.
Defintion
Given $f:X\to X$, the dynamical system defined by $f$ is the sequence ${\left({f}^{n}\right)}_{n=0}^{\infty }$.

Why is it called "dynamical"? Because we imagine that the successive images of $X$ under $f$ show how $X$ changes over time. Indeed, many real-world applications of dynamical systems are models of how things actually do change over time. For example, the doubling function on $\left[0,\infty \right)$ defines a dynamical system that models unconstrained population growth. Each application of $f$ represents the passage of a certain amount of time in the model. In the population-growth example, this amount is equal to the doubling time of the population.

Given that a dynamical system is defined recursively, some can be expressed in a simple closed form and others can't. The dynamical system on $ℝ$ defined by $f\left(x\right)={x}^{2}$ is just ${f}^{n}\left(x\right)={x}^{{2}^{n}}$. But given $f\left(x\right)=3{x}^{2}+sinx$,

${f}^{0}\left(x\right)=x,$
${f}^{1}\left(x\right)=3{x}^{2}+sinx,$
${f}^{2}\left(x\right)=27{x}^{4}+18{x}^{2}sinx+3{\left(sinx\right)}^{2}+sin\left(sinx+3{x}^{2}\right),$
$\text{etc.}$

We can learn about the global behavior of a dynamical system by examining what happens to individual points as $f$ is repeatedly applied to them.

Defintion
Given $f:X\to X$ and $x\in X$, the orbit of $x$ under $f$, denoted $O\left(x\right)$, is the sequence ${\left({f}^{n}\left(x\right)\right)}_{n=0}^{\infty }$. We call $x$ a periodic point if ${f}^{m}\left(x\right)=x$ for some $m\in ℕ$. The least such $m$ is called the period of $x$.

For example, under the function $f:ℝ\to ℝ$ defined by $f\left(x\right)=-\frac{3}{2}{x}^{2}+\frac{5}{2}x+1$, $0$ is a periodic point with period $3$, since $f\left(0\right)=1$, $f\left(1\right)=2$, and $f\left(2\right)=0$.

Periodicity is a nice property. If we know a point is periodic, we can predict its entire orbit from finitely many of its successive images. You might think, then, that if the set of periodic points $P$ is dense in $X$—that is, if $X$ is just the closure of $P$—and if $f$ is continuous, then $f$ must be exceptionally well behaved. However, you would be dead wrong.

Consider the tent function, which is the function $T:\left[0,1\right]\to \left[0,1\right]$ defined by $T\left(x\right)=2x$ for $x\le \frac{1}{2}$ and $T\left(x\right)=2-2x$ for $x\ge \frac{1}{2}$. (This example is from Adams and Franzosa, 2008.) I hope you agree that $T$ is continuous. You can think of $T$'s effect on $\left[0,1\right]$ as stretching the interval out to twice its length and then folding it back onto itself.

Here's a graph of $T$:

Here's a graph of ${T}^{3}$:

You get the idea: for each $n$, ${T}^{n}$ has ${2}^{n-1}$ peaks. As $n$ increases, ${T}^{n}$ gets more and more crowded. And yet, periodic points of this dynamical system are dense in $\left[0,1\right]$. A theorem I won't prove here says that any number whose binary representation is of the form $0.\overline{{a}_{1}{a}_{2}\dots {a}_{n}0}$ is a periodic point. The idea is that for any repeating binary $x$, the effect of $T$ on $x$ is as follows:

• If the first bit after the binary point is $0$, $T$ does a left shift.
• If the first bit after the binary point is $1$, $T$ does a left shift and flips all the bits.

For example, $0.\overline{10110}=\frac{22}{31}$ is a periodic point:

${T}^{0}\left(0.\overline{10110}\right)=0.\overline{10110};$
${T}^{1}\left(0.\overline{10110}\right)=0.\overline{10010};$
${T}^{2}\left(0.\overline{10110}\right)=0.\overline{11010};$
${T}^{3}\left(0.\overline{10110}\right)=0.\overline{01010};$
${T}^{4}\left(0.\overline{10110}\right)=0.\overline{10100};$
${T}^{5}\left(0.\overline{10110}\right)=0.\overline{10110}.$

It's easy to show that numbers of the form $0.\overline{{a}_{1}{a}_{2}\dots {a}_{n}0}$ are dense in $\left[0,1\right]$.

The graphs of $T$ make plain another important property of $T$: topological transitivity. This means that, given any open $U,V\subseteq \left[0,1\right]$, there are some $x\in U$ and $n\in ℕ$ such that ${T}^{n}\left(x\right)\in V$. Essentially, the image of any open set, no matter how small, is eventually the entire space. We'd show this for $T$ by picking an $n$ large enough that an interval for which ${T}^{n}$ is surjective is a subset of $U$.

This dynamical system has predictable aspects everywhere you look, and it's certainly deterministic, but its images are all over the place: no two open sets can be reliably distinguished. In a nutshell, it's chaotic.

Defintion
A function $f:X\to X$ is chaotic if its periodic points are dense in $X$ and it's topologically transitive.

There are many competing definitions of topological chaos, but I like this one because it makes explicit the strange duality of a chaotic function. Also, the requirements it places on $f$ aren't too strong. Consider the following property.

Defintion
Suppose $\left(X,d\right)$ is a metric space. A function $f:X\to X$ sensitively depends on initial conditions if there exists $\delta >0$ such that for any $x\in X$ and $\epsilon >0$, there exists $y\in {B}_{\epsilon }\left(x\right)$ and $n\in ℕ$ with $d\left({f}^{n}\left(x\right),{f}^{n}\left(y\right)\right)>\delta$.

Sensitive dependence on initial conditions is what I was referring to when I spoke earlier of approximation being useless. You can think of $\delta$ as a kind of minimum error of approximating a point in $X$: no matter how good your approximation is, so long as it isn't exact, $f$ may eventually bring $x$ and your approximation more than $\delta$ units apart. Look how widely $T$ scatters a few numbers in the narrow interval $\left[0.29997,0.30003\right]$:

 T0 T1 T2 T3 T4 T5 T6 0.29997 0.29998 0.29999 0.3 0.30001 0.30002 0.30003 0.59994 0.59996 0.59998 0.6 0.60002 0.60004 0.60006 0.80012 0.80008 0.80004 0.8 0.79996 0.79992 0.79988 0.39976 0.39984 0.39992 0.4 0.40008 0.40016 0.40024 0.79952 0.79968 0.79984 0.8 0.80016 0.80032 0.80048 0.40096 0.40064 0.40032 0.4 0.39968 0.39936 0.39904 0.80192 0.80128 0.80064 0.8 0.79936 0.79872 0.79808 0.39616 0.39744 0.39872 0.4 0.40128 0.40256 0.40384 0.79232 0.79488 0.79744 0.8 0.80256 0.80512 0.80768 0.41536 0.41024 0.40512 0.4 0.39488 0.38976 0.38464 0.83072 0.82048 0.81024 0.8 0.78976 0.77952 0.76928 0.33856 0.35904 0.37952 0.4 0.42048 0.44096 0.46144 0.67712 0.71808 0.75904 0.8 0.84096 0.88192 0.92288 0.64576 0.56384 0.48192 0.4 0.31808 0.23616 0.15424 0.70848 0.87232 0.96384 0.8 0.63616 0.47232 0.30848 0.58304 0.25536 0.07232 0.4 0.72768 0.94464 0.61696 0.83392 0.51072 0.14464 0.8 0.54464 0.11072 0.76608 0.33216 0.97856 0.28928 0.4 0.91072 0.22144 0.46784 0.66432 0.04288 0.57856 0.8 0.17856 0.44288 0.93568 0.67136 0.08576 0.84288 0.4 0.35712 0.88576 0.12864 0.65728 0.17152 0.31424 0.8 0.71424 0.22848 0.25728

It turns out that for continuous functions, chaos implies sensitivity. But I won't ask you to take my word for it this time. We'll prove it.