17
$\begingroup$

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

$\endgroup$
12
$\begingroup$

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

$\endgroup$
  • 5
    $\begingroup$ By $|\mathbb R|^{|\mathbb N|}=|\mathbb R|$ don't you mean $|\mathbb N|\cdot|\mathbb R|=|\mathbb R|$? $\endgroup$ – bof Sep 14 at 19:24
  • 1
    $\begingroup$ Also, the finite set should have $T_1^{-1}$, rather than $T_1$. $\endgroup$ – Eric Wofsey Sep 15 at 1:19
  • $\begingroup$ 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? $\endgroup$ – user3338098 Sep 19 at 19:42
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.