8 votos

¿Es cada función $f : \mathbb N \to \mathbb N$ una composición $f = g\circ g$?

Verdad o incorrecta: para cada función de $f: \mathbb N \rightarrow \mathbb N$ allí es una función $g: \mathbb N \rightarrow \mathbb N$ $f=g \circ g$.

9voto

azimut Puntos 13457

Considerar la asignación de $$f : \mathbb N\to\mathbb N, x\mapsto\begin{cases}1 & \text{if }x = 2 \\2 & \text{if }x = 1 \\ x & \text{ otherwise.}\end{cases}$$

Suponga $g : \mathbb N\to\mathbb N$ es una asignación con $f = g\circ g$.

Tenemos $g(1) \neq 1$, porque de lo contrario $f(1) = g(g(1)) = g(1) = 1$.

Además $g(1) \neq 2$, porque de lo contrario $g(2) = g(g(1)) = f(1) = 2$ e lo $f(2) = g(g(2)) = g(2) = 2$.

Por lo $y := g(1) \notin\{1,2\}$ y, por tanto,$f(y) = y$.

Continuamos con $g(y) = g(g(1)) = f(1) = 2$.

De ello se desprende que $g(2) = g(g(y)) = f(y) = y$, por lo que $$f(1) = g(g(1)) = g(y) = g(g(2)) = f(2).$$ Contradicción.

Comentario

Basado en el argumento anterior, obtenemos la siguiente generalización:

Deje $X$ ser un conjunto. Sostiene que la $\lvert X\rvert \leq 1$ si y sólo si para cada función de $f : X \to X$, hay una función de $g : X\to X$$f = g\circ g$.

6voto

phunehehe Puntos 570

No.

Por ejemplo, tomar $f:\mathbb{N}\to\mathbb{N}$ que $f (x) =\begin{cases} 2 & x=1\\ 1 & x=2\\ x & x>2\\ \end{casos} $.

Asumir que hay $g:\mathbb{N}\to\mathbb{N}$ tal que $f=g\circ g$.

Observe que $g(1)\neq1$ desde $g(1)=1\Rightarrow f(1)=g(g(1))=g(1)=1\neq f(1)$ y $g(2)\neq 2$. También $g(1)\neq 2$ desde $g(1)=2\Rightarrow f(1)=g(g(1))=g(2)\neq 2=f(1)$. De aquí se desprende que $f(g(1))=g(1)$ porque $g(1)\neq 1,2$.

También sabemos que $g(1)\neq g(2)$ porque $g(g(1))\neq g(g(2))$.

Pero también deducimos que $g(1)=f(g(1))=g(g(g(1)))=g(f(1))=g(2)$, que contradice la línea anterior.

3voto

QuentinUK Puntos 116

Shay y Azimut ha encontrado el perfecto contra-ejemplo, y sólo quiero decir una palabra acerca de cómo uno puede venir para arriba con un contra-ejemplo.

Deje $S_n$ ser el grupo simétrico de a $\{1, \dots, n\}$. Una condición necesaria para que una permutación $\sigma \in S_n$ a admitir una raíz cuadrada es que ser aún: de hecho, las plazas de las $S_n$ se encuentran en el núcleo de la señal $S_n \to \{\pm 1\}$.

Con esto en mente, la permutación de $\mathbf N$ que los interruptores $1$ $2$ es un candidato natural para una función que no tiene raíz cuadrada. De hecho, si uno puede hablar de su signo, debe ser negativa. Por desgracia, no se puede hablar de el signo de una permutación arbitraria de $\mathbf N$. Uno puede, sin embargo, hablan de la señal de una permutación que está casi en todas partes la identidad. Permutaciones de $\mathbf N$ que salen casi todos los elementos de forma fija en un subgrupo del grupo de todas las permutaciones de $\mathbf N$, que se identifica con la directa límite de $\mathbf S_{\infty}$ de los directos de sistema de $S_1 \to S_2 \to S_3 \to \dots$. El signo homomorphisms son compatibles con los mapas de sistema directo, y determinar un signo homomorphism $\mathbf S_{\infty} \to \{\pm 1\}$. Azimut y Shay mapa es "extraño" elemento de $\mathbf S_{\infty}$, y por lo tanto no puede admitir una raíz cuadrada en el interior de $\mathbf S_{\infty}$.

Por desgracia, esto no es suficiente para ver que su mapa no admite la raíz cuadrada, porque no son permutaciones de $\mathbf N$ que no están en $\mathbf S_{\infty}$, pero cuyo cuadrado es. Por lo tanto, aún es necesario argumentar (como lo hacen) que su mapa no puede admitir una raíz cuadrada en el grupo más grande $S_{\mathbf N}$. Pero tal vez, todavía es interesante disponer de esta fuente de la intuición!

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X