Is an infinite composition of bijections always a bijection?

Question

Main Question

Suppose I have a sequence of real valued functions $f_1:X_0\rightarrow X_1,...,f_n:X_{n-1} \rightarrow X_n,...,$ and I then, with $\circ$ denoting function composition, define

$$g_n : X_0 \rightarrow X_n\;\text{by}\;g_n(x_0) = (f_n \circ ... \circ f_1)(x_0).$$

For the sake of having a notation available in case things get complicated, I declare

$$\bigcirc_{i=1}^n f_i := (f_n \circ ... \circ f_1),$$

and also

$$\left[\bigcirc_{i=1}^n f_i := (f_n \circ ... \circ f_1)\right] (x_0) := (f_n \circ ... \circ f_1)(x_0).$$

For whatever subset $X \subseteq X_0$ it is such that $g:X \rightarrow \mathbb{R}$ can be defined by $g(x) = \lim_{n\rightarrow \infty} g_n(x),$ is $g$ guaranteed to be a bijection?

Side Question

Does anyone have knowledge (and references) for people working with applying a non-constant sequence of maps as we do here? If the sequence $f_i$ is equal to some particular $f$ for all $i \in [1..],$ then $\bigcirc_{i=1}^n$ is just written $f^{i},$ the common notation for function iteration. It seems less common to apply a sequence of maps, but I've been able to do some cool stuff with this idea.

Answer 1

We shouldn't expect limits (of any sequence of functions) to preserve injectivity, since limits can change strict inequalities into nonstrict inequalities.

For a concrete counterexample, consider each $f_j\colon \Bbb R\to\Bbb R$ to be $f_j(x) = \frac x2$. Then the $n$-fold composition is just $x\mapsto \frac x{2^n}$, but the limit of this sequence is the very non-injective constant function $0$.

(Surjectivity is probably a problem also, because surjectivity is a property of a function and its codomain and it's not even clear what the codomain of the general sequence is supposed to be.)

Answer 2

There's a very simple example, actually.

Take $f_i (x) = \sqrt{x} = x^{1/2}.$ Over $X = (0, \infty),$ for each $i \in [1..]$, $f_i$ is bijective, meeting the requirements of the question.

With this choice of $f_i,$ we get $g_n (x)= x^{1/2^n}.$ We can easily take the limit of this. Fix an $x \in X;$ now, by exponentiating the logarithm inside the limit, then exchanging the limit and exponential, then factoring terms not varying with $n$ out of the limit, we get the following.

$$\lim_{n \rightarrow \infty} x^{1/2^n} = \exp\left[\ln(x)\lim_{n \rightarrow \infty} 2^{-n} \right] = \exp\left[0\right] = 1.$$

This means that $g : (0, \infty) \rightarrow \{1\}$ such that $g((0, \infty)) = \{1\}.$ $g$ maps an uncountable set to a finite set, so it cannot be bijective.

Answer 3

Here is a countable counterexample. Consider the one-point compactification $X = \mathbb{N} \cup \{ \infty \}$ of $\mathbb{N}$ and the sequence of bijections $f_i : X \to X$ given by the transpositions $i \leftrightarrow i+1$. Then the $n$-fold composition $\bigcirc_{i=1}^n f_i$ is the $(n+1)$-cycle

$$1 \to n+1 \to n \to n-1 \to \dots \to 2 \to 1$$

so the limit exists and satisfies $f(1) = f(\infty) = \infty$ and $f(n) = n - 1$ for $2 \le n < \infty$ and is no longer injective. These compositions can be visualized in a fairly direct way by seeing what they do to the numbers $1, 2, 3, \dots, \infty$ in order: we just repeatedly transpose $1$ with the number to the right, getting

$$2, \color{red}{1}, 3, 4, 5, 6, \dots, \infty$$ $$2, 3, \color{red}{1}, 4, 5, 6, \dots, \infty$$ $$2, 3, 4, \color{red}{1}, 5, 6, \dots, \infty$$ $$2, 3, 4, 5, \color{red}{1}, 6, \dots, \infty$$

so we are just gradually transposing $1$ towards infinity. More extreme examples are also possible, e.g. the constant function with constant value $\infty$ can also occur as a limit.

Answer 4

Regarding notation, I'm fond of a modified Einstein index contraction notation: $f^0_n : X_0 \to X_n$ where $f^0_n = f_n \circ \cdots \circ f_1$. It's nice because then you also have notation for partial compositions $f^m_n : X_m \to X_n$.

Now choose any sequence of bijections that you wish $$h_n : X_0 \to X_n $$ In your setting, taking $X_n$ for all $n$ to be a fixed subset of $\mathbb R$ such as $X_n = \mathbb R$ or $X_n = \mathbb N$, I'm sure you can conjure up such sequences with rather arbitrary asymptotic behavior, in particular ones which do not have any limit at all, let alone a bijection in the limit.

Define $$f_n = h_n h_{n-1}^{-1}: X_{n-1} \to X_n $$ It follows that $f^0_n=h_n$.

To summarize: your problem on the limiting behavior of "infinite compositions of bijections" is no different from the problem on limiting behavior of sequences of bijections.

Answer 5

If you'll forgive me for the digression, here is an answer for the question in your title rather than the one in your body. "Infinite composition", in my experience, tends to refer to the categorical phenomenon of taking the colimit of a tower of maps. So in our case, "$g_\infty$" would rather refer to the map $X_0\to\varinjlim(X_0\to X_1\to X_2\to X_3\to\cdots)$.

In this formulation of the problem, $g_\infty$ is indeed a bijection (if we take colimits of sets). This holds in any category in fact, so long as the $X_i\to X_{i+1}$ are understood to be isomorphisms.

One possible way to see that: consider the constant tower $\Delta X_0:X_0=X_0=X_0=\cdots$ and that the maps $g_n:X_0\cong X_n$ induce an isomorphism of towers $\Delta X_0\cong(X_0\to X_1\to\cdots)$, hence an isomorphism $X_0\cong\varinjlim(X_0\to X_1\to\cdots)$ of colimits; this isomorphism is clearly the canonical (co)leg of the cocone, the canonical map $X_0\to\varinjlim(X_0\to X_1\to\cdots)$, so truly $g_\infty$ is an isomorphism.