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

There is an infinite sequence of functions $$g_1,g_2,\ldots$$, each of them is $$\Bbb R\to\Bbb R$$. 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\}$$.

• By $|\mathbb R|^{|\mathbb N|}=|\mathbb R|$ don't you mean $|\mathbb N|\cdot|\mathbb R|=|\mathbb R|$? – bof Sep 14 at 19:24
• Also, the finite set should have $T_1^{-1}$, rather than $T_1$. – Eric Wofsey Sep 15 at 1:19
• what does the syntax $F|_{R_i}$ represent? If it means $F$ for an input from $R_i$ then shouldn't $F$ be a set of functions? – user3338098 Sep 19 at 19:42

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

Since you already accepted an answer, I won't bother to give a proof, but I will give references. The theorem is due to Sierpiński:

W. Sierpiński, Sur les suites infinies de fonctions définies dans les ensembles quelconques, Fund. Math. 25 (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–252.)

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.

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:

$$$$\qquad g_n = G\circ u^{(n)}\circ b\qquad ∎$$$$