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

elementary-set-theoryfinitely-generatedfunction-and-relation-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}.$$

Best Answer

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