Hay una secuencia infinita de funciones $g_1,g_2,\ldots$, cada uno de ellos es $\Bbb R\to\Bbb R$. Demostrar que existe un conjunto finito de funciones $f_1,f_2,\ldots,f_n$ tal que cualquier función de $g_k$ puede ser expresado como una composición en $f_{k_1}\circ f_{k_2}\circ\cdots\circ f_{k_m}$.
Respuestas
¿Demasiados anuncios?
El ingrediente principal de mi respuesta es el siguiente hecho:
$|\mathbb{R}^{\mathbb N}| = |\mathbb{R}|$ .
Su prueba no está directamente relacionada con esta pregunta, así que no la pondré aquí. Pero puedes encontrarla en la respuesta a este pregunta. Debido a este hecho podemos hablar de la $\mathbb R$ como sobre la unión disjunta $\coprod\limits_{i=1}^\infty R_i$ donde todos los $R_i$ son las copias de $\mathbb{R}$ .
Ahora podemos definir dos funciones $\mathbb{R} \to \mathbb{R}$ : $F$ y $G$ . $F$ envía $R_i$ debido al mapa $g_i$ (A saber, $F|_{R_i} = g_i \circ T_i$ , donde $T_i$ es una biyección arbitraria desde $R_i$ a $\mathbb R$ ) y $G$ funciona con la siguiente regla: se define como una función $\coprod\limits_{i=1}^\infty R_i \to \coprod\limits_{i=1}^\infty R_i$ que envía $T_{i-1}^{-1}(a)$ a $T_i^{-1}(a)$ para todos $a$ en $\mathbb R$ . Es un mapa bien definido ya que todos $T_i$ son biyecciones.
El resto de la prueba es bastante elemental: se puede comprobar fácilmente que $g_i = F \circ G^{i-1} \circ {T_1}^{-1}$ . Así que su conjunto finito de funciones $f_i$ es sólo $\{F, G, T_1\}$ .
Alexander Belopolsky
Puntos
309
Dejemos que $b:{\Bbb R}\to [0,1)$ sea una biyección y $u:x\mapsto x+1$ sea un desplazamiento unitario. Podemos definir $G:[1,\infty)\to{\Bbb R}$ como $$ G(x)=g_{[x]}\left(b^{-1}\left(\{x\}\right)\right) $$ donde $[x]$ y $\{x\}=x-[x]$ son partes enteras y fraccionarias de $x$ respectivamente. Ahora podemos escribir el $n$ -La función número uno de la secuencia original es la siguiente
$$ g_n(x) = G\left(n+b(x)\right)\quad\mbox{for $ n \in { \Bbb N} $.} $$
En otras palabras, cada $g$ puede expresarse como una composición de $f_1=b$ , $f_2=G$ y algún número de $f_3=u$ 's:
\begin {Ecuación} \qquad g_n = G \circ u^{(n)} \circ b \qquad ∎ \end {Ecuación}
bof
Puntos
19273
De manera más general:
Teorema. Para cualquier conjunto infinito $S$ y cualquier conjunto contable $F$ de las funciones $f:S\to S$ hay dos funciones $g,h:S\to S$ tal que $F$ está contenido en el semigrupo generado por $\{g,h\}$ en la composición. (Por otro lado, si $S$ es un conjunto finito con más de dos elementos, entonces tres automapas de $S$ para generarlas todas).
Como ya has aceptado una respuesta, no me molestaré en dar una prueba, pero sí daré referencias. El teorema se debe a Sierpiński:
Una prueba más sencilla del teorema de Sierpiński fue dada por Banach:
Stefan Banach, Sobre un teorema del señor Sierpiński, Fund Math. 25 (1935) 5-6.
(Por cierto, si las funciones dadas son biyecciones, entonces las funciones $g,h$ también pueden tomarse como biyecciones; véase el teorema 3.5 de Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995) 230-252.)
El teorema de Sierpiński resurgió en Mensualmente problema 6244, propuesto por John Myhill; la solución apareció en Amer. Math. Monthly 87 (1980) 676-678.
Como todo semigrupo es isomorfo a un semigrupo de mapeos, como corolario del teorema de Sierpiński tenemos:
Corolario. Todo semigrupo contable es incrustable en un $2$ -generador de semigrupo.
Esto fue demostrado de manera diferente por Trevor Evans, Embedding theorems for multiplicative systems and projective geometries, Proc. Amer. Math. Soc. 3 (1952) 614-620.
