For an infinite sequence of functions $\Bbb{R}\to\Bbb{R}$, each function is a composition of a certain finite set of functions $\Bbb{R}\to\Bbb{R}$.

Question

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.

Answer 1

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

Answer 2

Copying my answer from another question, which is closed and threatened with deletion:

More generally:

Theorem. For any infinite set $S$ and any countable set $F$ of functions $f:S\to S$, there are two functions $g,h:S\to S$ such that $F$ is contained in the semigroup generated by $\{g,h\}$ under composition. (On the other hand, if $S$ is a finite set with more than two elements, then three selfmaps of $S$ are needed in order to generate them all.)

Proof. Let $F=\{f_n:n\in\omega\}$. We may assume that $S=X\times\omega\times2$ for some infinite set $X$. Construct a bijection $g:S\to\{(x,n,i)\in S:n=0\text{ or }i=1\}$ such that $g(x,n,0)=(x,n-1,1)$ for $n\gt0$; thus $g^2[S]=X\times\{0\}\times\{0\}$. Define $h:S\to S$ so that $h(x,n,0)=(x,n+1,0)$ and $h(x,n,1)=f_ng^{-2}(x,0,0)$. Then $f_n=hgh^{n+1}g^2$.

The theorem is due to Sierpiński:

W. Sierpiński, Sur les suites infinies de fonctions définies dans les ensembles quelconques, Fund. Math. 24 (1935) 209–212.

A simpler proof of Sierpiński's theorem was given by Banach:

Stefan Banach, Sur un théorème de M. Sierpiński, Fund Math. 25 (1935) 5–6.

(By the way, if the given functions are bijections, then the functions $g,h$ can also be taken to be bijections; see Theorem 3.5 of Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995) 230–242.)

Sierpiński's theorem resurfaced in Monthly problem 6244, proposed by John Myhill; the solution appeared in Amer. Math. Monthly 87 (1980) 676–678.

Since every semigroup is isomorphic to a semigroup of mappings, as a corollary to Sierpiński's theorem we have:

Corollary. Every countable semigroup is embeddable in a $2$-generator semigroup.

This was proved in a different way by Trevor Evans, Embedding theorems for multiplicative systems and projective geometries, Proc. Amer. Math. Soc. 3 (1952) 614–620.