Given an infinite sequence of functions $\{g_1, g_2, \ldots, g_n, \ldots\}$ where $ g_n : \Bbb R \to \Bbb R$ prove there's a finite set of functions $ \{ f_1, f_2, \ldots, f_M \} $ such that any $ g_n $ can be represented as a composition of $ f_m $'s.
Honestly, not sure even how to approach this. The intuition is that if the infinite sequence of functions is not defined using finite set of functions and composition then the sequence definition would be infinite itself, but I don't know how to formalize that.
Best Answer
Fix a bijection $\varphi:\mathbb{R}\to [0,1)$ and define $\psi : \mathbb{R} \to \mathbb{R}$ by
$$ \psi(x) = \begin{cases} g_n(\varphi^{-1}(x-n)), & \text{if $x \in [n, n+1)$ for some $n \in \mathbb{N}_1$}; \\ 0, &\text{otherwise}; \end{cases} $$
where $\mathbb{N}_1 = \{1,2,3,\dots\}$. Finally, set $ f(x) = x+1 $. Then
$$ g_n = \psi \circ f^{\circ n} \circ \varphi $$
for any $n \in \mathbb{N}_1$.