# Is an infinite composition of bijections always a bijection?

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.

• Maybe the side question can be its own question or this one can link to it? Commented Aug 11 at 0:49
• @ТymaGaidash Okay, that's a good idea. Commented Aug 11 at 3:44
• In my opinion this is really just one question - I don't think the reference request really needs to be separate. But the title implied it was two questions, which will tend to get it closed, so I've edited it to remove that. Commented Aug 11 at 13:51
• I daresay it is rather harder to come up with a nontrivial example (i.e. not just permutations) where the infinite composition is a bijection, than with counterexamples. Commented Aug 12 at 16:49

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.)

• The codomain of a composite is the codomain of the last function in the composite. Thus $\operatorname{cod} (f_n \circ \ldots \circ f_1) = \operatorname{cod} f_n$. A natural way to define the codomain of the infinite sequence is $\lim_{n \to \infty} \operatorname{cod} (f_n \circ \ldots \circ f_1) = \lim_{n \to \infty} \operatorname{cod} f_n$, a set-theoretic limit. Commented Aug 12 at 4:52
• ...or simply assume that all the $f_j$ are endomorphisms, which seems reasonable enough in the context of this question. Commented Aug 12 at 16:44

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.

• Another example would be $f_i : [0,1]\to [0,1]$, with $f_i(x) =x^2$ for all $i$. Then the pointwise limit does exist, and is neither injective nor continuous (as its range has exactly two elements). Commented Aug 11 at 19:04

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.

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.

• Shouldn't it be $f_n=h_n\circ h_{n-1}^{-1}$? Commented Aug 13 at 4:42
• Ah, right! thanks. Commented Aug 13 at 14:45

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.

• I've never had much caregory theory before, but I feel like your answer is connected to Lee Mosher's. Am I correct on this hunch? Commented Aug 15 at 5:26
• @AidanO'Keeffe I suppose, since $g_\infty$ can be expressed as $\varinjlim_n h_n$ Commented Aug 15 at 7:23