# Infinite composition of functions

Does the concept of an infinite composition of functions makes sense? In both cases of an countable infinite composition of functions and an uncountable infinite composition.

I don't know how to define it or if even makes sense.

-
–  Cameron Buie Jul 10 '13 at 10:31

At least for the case of self-composition, aka "function iteration" there is a wide discussion about functions with and without fixpoints; attractive and repelling ones - where "fixpoint" means, that if $t$ is the fixpoint $f(t)=t$ . If you consider $f(x) = b^x$ where $b = \sqrt 2$ then if you begin at, say $x_0=3$ you approach with infinitely many self-compositions/iterations $x_{k+1} = b^ {x_k}$the value $x_\infty =2$ - which also means, that fixpoint $t=2$ is an attracting one.

-

This can be problematic. Consider the case where $f(x)=x+1$ defined on the natural numbers. Then $f^n(x)=x+n$, but now there is a problem to compose this function infinitely many times on itself, because its range would have to be empty.

So one has to impose further conditions on the chain of functions, and possibly on the domain (e.g. some topology, or something like that). Then you can require, for example, $f_\infty(x)=\lim_{n\to\infty} f_n\circ\ldots\circ f_1(x)$, if it exists.

-
I don't see how the range of $f^{n}(x)$ tends to the empty set as $n \to \infty$ –  Jorge Jul 10 '13 at 12:18
@Nivalth: The range of $f^n$ is $\{k\in\Bbb N\mid k\geq n\}$. What is the intersection of these sets? –  Asaf Karagila Jul 10 '13 at 12:19
Thank you for your fast comment. So your question is, if the range of $f_{n}=R_{n}$ then what is $\displaystyle \bigcap_{i \in \mathbb{N}}R_{i}$? I see more or less naively now that it should be the empty set, but I don't see how to formalize it. –  Jorge Jul 10 '13 at 12:21
@Nivalth: Note that for every $k$ we have $k\notin R_{k+1}$. –  Asaf Karagila Jul 10 '13 at 12:26
@Nivalth: You're welcome. Don't feel bad for accepting a good answer. –  Asaf Karagila Jul 10 '13 at 12:30
show 1 more comment

We can in fact make some sense of the notion of infinite composition, but the infinite composition will not exactly unique, just unique enough to work well (I will explain what this means). Suppose that we have a sequence of maps, $$X_0\to X_1\to X_2\to \cdots.$$ Where we denote the map $f_i:X_i\to X_{i+1}$. One issue with defining an infinite composition is that we do not have a target for this composition, namely an $X_{\infty}$. So we must find a way to specify one. In other words, we need a limit of these spaces (actually it is a colimit). This limit will not be unique, BUT given any two their will be a unique isomorphism between them (some more data must be specified to force uniqueness). So we will define $X_{\infty}$ as the solution to a problem. The problem will be to find a set $Y$, along with a batch of maps, $$\phi_i:X_i\to Y$$ such that $\phi_i\circ f_i=\phi_{i+1}$. SO we may find a whole bunch of these SO we will add another condition on this $Y$ (which you may think of a minimality condition). We want our $Y$ to satisfy the condition that if their is another $Z$ and another batch of maps, $\theta_i:X_i\to Z$ such that $\theta_i\circ f_i=\theta_{i+1}$, then their is a unique map, $Y\to Z$ such that the composites $X_i\to Y\to Z$ is equal to $\theta_i$. This is a part of category theory, which is a vast subject and has very wide applicability. For more on this type of limit see here.

-
–  Baby Dragon Jul 10 '13 at 13:25