Why any countable subset of $\mathbb{R}→\mathbb{R}$ is generated by a finite set under composition?

Given a sequence of functions $\{g_k\}$, where $g_k: \Bbb R\to\Bbb R$ for all $n\in \mathbb N$. Prove that there exists a finite set of functions $$f_1,f_2,\ldots,f_n$$ such that any function $g_k$ can be expressed as a composition $$f_{k_1}\circ f_{k_2}\circ\cdots\circ f_{k_m}.$$

The main ingredient in my answer is the following fact:

$|\mathbb{R}^{\mathbb N}| = |\mathbb{R}|$.

Its proof isn't directly related to this question so I won't put it right here. But you can find it in the answer to this question. Due to this fact we can talk about the $\mathbb R$ as about the disjoint union $\coprod\limits_{i=1}^\infty R_i$ where all of the $R_i$'s are the copies of $\mathbb{R}$.

Now we can define two functions $\mathbb{R} \to \mathbb{R}$: $F$ and $G$. $F$ sends $R_i$ due to the map $g_i$ (namely, $F|_{R_i} = g_i \circ T_i$, where $T_i$ is an arbitrary bijection from $R_i$ to $\mathbb R$) and $G$ works by the following rule: it's defined as a function $\coprod\limits_{i=1}^\infty R_i \to \coprod\limits_{i=1}^\infty R_i$ which sends $T_{i-1}^{-1}(a)$ to $T_i^{-1}(a)$ for all $a$ in $\mathbb R$. It's a well-defined map since all $T_i$'s are bijections.

The rest of the proof is quite elementary: you can easily check that $g_i = F \circ G^{i-1} \circ {T_1}^{-1}$. So your finite set of functions $f_i$ is just $\{F, G, T_1\}$.

Let $b:{\Bbb R}\to [0,1)$ be a bijection and $u:x\mapsto x+1$ be a unit shift. We can define $G:[1,\infty)\to{\Bbb R}$ as $$ G(x)=g_{[x]}\left(b^{-1}\left(\{x\}\right)\right) $$ where $[x]$ and $\{x\}=x-[x]$ are integer and fractional parts of $x$ respectively. Now we can write the $n$-th function in the original sequence as

$$ g_n(x) = G\left(n+b(x)\right)\quad\mbox{for $n\in{\Bbb N}$.} $$

In other words, each $g$ can be expressed as a composition of $f_1=b$, $f_2=G$ and some number of $f_3=u$'s:

\begin{equation} \qquad g_n = G\circ u^{(n)}\circ b\qquad ∎ \end{equation}

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.