Mostrar que las composiciones de funciones son asociativas

Question

Mi intención es mostrar que una composición de biyecciones también es una biyección mostrando la existencia de una inversa. Pero mi enfoque requiere la asociatividad de la composición de funciones.

Sean $f: X \rightarrow Y, g: Y \rightarrow Z, h: Z \rightarrow W$ funciones.
$((f \circ g) \circ h)(x) = h((f \circ g)(x)) = h(g(f(x)))$, y $(f \circ (g \circ h))(x) = (g \circ h)(f(x)) = h(g(f(x)))$.

Sin embargo, tengo problemas justificando que las dos composiciones, $(f \circ g) \circ h$ y $f \circ (g \circ h)$, tienen el mismo dominio y rango. Cuando consulté ProofWiki, cuyo enlace está al final, me confundí aún más. Específicamente, para que $(f \circ g) \circ h = f \circ (g \circ h)$ esté definido, ProofWiki requiere que dom$g =$ codom$f$ y dom$h =$ codom$g$.

En primer lugar, creo que debería ser dom$g =$ range$f$.... Además, como se puede ver en el ejemplo a continuación, realmente hay que ajustar los dominios y rangos de $f, g, h$ para que el requisito sea verdadero.
Sean $f: \mathbb R \rightarrow \mathbb R$ tal que $f(x) = 2x$, $g: \mathbb R^+ \rightarrow \mathbb R$ tal que $g(y) = ln(y)$, $h: \mathbb R \rightarrow \mathbb R$ tal que $h(z) = z - 10$.
Entonces $((f \circ g) \circ h)(x) = ln(2x) - 10 = (f \circ (g \circ h))(x)$, con dom$((f \circ g) \circ h) = \mathbb R^+$ = dom$(f \circ (g \circ h))$. Como resultado, necesitamos establecer dom$f = \mathbb R^+$, range$f = \mathbb R^+$; dom$g$, range$g$, dom$h$ y range$h$ permanecen iguales. ¿Se me permite hacer eso?

Este ajuste implica que cuando decimos dom$f = X$, $f$ debe estar definido para todos los elementos en $X$, pero $X$ puede no ser el conjunto entero de elementos para los que $f$ está definido.

http://www.proofwiki.org/wiki/Composition_of_Mappings_is_Associative

Answer 1

Por lo general, cuando $f\colon X\to Y$ y $g\colon Y\to Z$ son mapas, su composición se escribe $g\circ f$, en lugar de $f\circ g$: de esta manera se escribe $$ g\circ f(x)=g(f(x)) $$ por definición.

Parece que estás confundiendo el codominio con el rango. El rango, o imagen, de $f$ es el subconjunto del codominio $Y$ que consiste en los elementos $f(x)$, para $x\in X$. El rango no tiene ningún papel cuando se considera la composición de mapas. Al menos, cuando se supone que los mapas están definidos en todo el dominio, como es el caso al hablar de suryectividad o biyectividad.

La asociatividad es casi obvia. Si tienes otra función $h\colon Z\to W$, tienes, por definición, que $g\circ f\colon X\to Z$ y $h\circ g\colon Y\to W$. Por lo tanto, también se pueden considerar las composiciones $$ h\circ(g\circ f) \qquad\text{y}\qquad (h\circ g)\circ f $$ y ambas son mapas de $X\to W$, por lo que tiene sentido preguntarse si son iguales. Lo son, porque para cada $x\in X$ tenemos $$ h\circ(g\circ f)(x)=h(g\circ f(x))= h(g(f(x))=h\circ g(f(x))=(h\circ g)\circ f(x). $$ Si no puedes entender esto, simplemente define $y=f(x)$, $z=g(y)$, $F=g\circ f$ y $G=h\circ g$, de manera que $F(x)=g(f(x))=g(y)=z$. Entonces $$ h\circ(g\circ f)(x)=h\circ F(x)=h(F(x))=h(z) $$ y $$ (h\circ g)\circ f(x)=G\circ f(x)=G(y)=h\circ g(y)=h(g(y))=h(z) $$ así que los dos elementos son iguales.

Answer 2

Tienes $$ (f \circ g) \circ h(x) = f \circ g(h(x)) = f(g(h(x)),$$ y $$ f \circ (g \circ h(x)) = f(g \circ h(x)) = f(g(h(x)).$$ Ahora sigue la asociatividad que buscas.

Answer 3

Me resultó más fácil razonar sobre la composición utilizando la siguiente notación y definiciones.

Notación infija para funciones

$$(x,y)\in f \leftrightarrow x \space \boldsymbol f \space y $$ y dejemos $$(x,b)\in f \wedge (b,y) \in g \leftrightarrow x \space \boldsymbol f \space b \space \boldsymbol g \space y$$ entonces

Definición de $(g \circ f)$

Si $f,g$ son funciones, entonces $(g \circ f)$ es la relación $$(x,y)\in(g\circ f)\leftrightarrow \exists b: x \space \boldsymbol f \space b \space \boldsymbol g \space y$$

---

La composición ($\circ$) es asociativa

Si $h,g,f$ son funciones, entonces $$(h \circ g) \circ f = h \circ (g \circ f)$$ Prueba. $(x,y)\in(h \circ g) \circ f \leftrightarrow \exists b:x\space\boldsymbol f\space b\space\boldsymbol (\boldsymbol h \boldsymbol\circ \boldsymbol g \boldsymbol )\space y$. Donde $b\space\boldsymbol (\boldsymbol h \boldsymbol\circ \boldsymbol g \boldsymbol )\space y \leftrightarrow (b,y)\in (h \circ g)\leftrightarrow \exists b': b\space\boldsymbol g \space b' \space\boldsymbol h \space y.$ Luego la regla de membresía se convierte en $$(x,y)\in(h \circ g) \circ f \leftrightarrow \exists b,b': x\space\boldsymbol f\space b\space\boldsymbol g \space b' \space\boldsymbol h \space y$$ La otra dirección es nuevamente dos aplicaciones de la definición de composición. $(x,y)\in h\circ (g \circ f) \leftrightarrow \exists b:x\space\boldsymbol (\boldsymbol g \boldsymbol \circ \boldsymbol f \boldsymbol) \space b \space \boldsymbol h \space y$. Pero $x\space\boldsymbol (\boldsymbol g \boldsymbol \circ \boldsymbol f \boldsymbol) \space b \leftrightarrow (x,b) \in (g \circ f) \leftrightarrow \exists b': x\space\boldsymbol f \space b' \space\boldsymbol g \space b$. Por lo tanto, $$(x,y)\in h \circ (g \circ f) \leftrightarrow \exists b,b': x\space\boldsymbol f\space b'\space\boldsymbol g \space b \space\boldsymbol h \space y$$ Y así, $$(x,y) \in (h \circ g) \circ f \leftrightarrow (x,y)\in h \circ ( g \circ f)$$ Lo cual implica $$(h \circ g) \circ f=h \circ ( g \circ f)$$

Answer 4

Tal vez sea INCLUSO más fácil (¿más claro?) razonar sobre una construcción más general (con una gran inspiración tanto de la definición de una categoría, la excelente respuesta de mcg256, y el comentario útil de Milan)?

Podemos ver una relación R(A,B) como una colección de caminos de manera que cada camino tenga un punto inicial único en el conjunto A y un punto terminal único en el conjunto B.

En el caso especial de una relación, un camino está determinado por sus puntos finales, pero esta NO es una suposición necesaria.

Por lo tanto, para definir la composición de manera más general, podemos ver los datos iniciales como dos colecciones de flechas M(A,B) y M(B,C), cada flecha en M(X,Y) tiene origen en X y destino en Y, y podemos confeccionar una tercera colección de flechas M(A,B)*M(B,C)=M(A,B,C) a través de la concatenación, podemos combinar dos flechas precisamente si el destino de la primera es el origen de la segunda.

Para comprobar la asociatividad, dado los datos iniciales M(A,B) M(B,C) y M(C,D), debemos mostrar que M(A,B,C)*M(C,D) ``='' M(A,B)*M(B,C,D). Estamos en riesgo de tener un isomorfismo canónico en lugar de igualdad, y por lo tanto las comillas alrededor del símbolo =.

Exactamente se necesita la misma entrada para producir una flecha típica en cada lado de la ecuación anterior.

Las imágenes que se podrían dibujar para ilustrar una flecha típica en los cálculos respectivos son

(A->B-->C)--->D y A->(B-->C--->D).

Por lo tanto, si definimos M(A,B,C,D) como la colección de todos los diagramas A->B-->C--->D, (de manera que el destino de -> es el origen de --> etc..) entonces las 3 colecciones a mano son todas canónicamente isomorfas.

¿Hemos demostrado que la composición es asociativa?

Tal vez al menos hemos llegado al meollo del asunto, y establecido un sentido preciso en el cual 3 cosas formalmente diferentes son lo mismo.

Es tentador decir que en el caso especial de funciones y relaciones, las 3 cosas formalmente diferentes son precisamente las mismas, pero incluso aquí quizás deberíamos ser cuidadosos, ya que tal vez estamos confiando en isomorfismos canónicos entre productos de conjuntos finitos:

(AxB)xC es canónicamente isomorfo a Ax(BxC) que a su vez es canónicamente isomorfo a la colección de todos los tríos ordenados (a,b,c) de los factores respectivos.

También es tentador decir que en la práctica, no surge confusión, si nuestro mayor error es mezclar cosas canónicamente isomorfas.

Sin embargo, el vector (a,b,c) me recuerda una supuesta demostración de una conjectura MUY famosa en teoría de números, que según mi entendimiento extremadamente pedestre de la opinión de los expertos, es quizás problemática, debido en parte a la confusión de: cosa versus cosa hasta el isomorfismo o quizás copia isomorfa de cosa.

Resumen del intento del post presente: El isomorfismo candidato de los tipos (x_y)z y x(y_z de hecho es un isomorfismo, dando un sentido en el cual x_y_z es ambiguo.

Pero, al igual que el autor de este post, https://explainingmaths.wordpress.com/2012/04/01/is-composition-of-functions-associative/,

Estoy insatisfecho con el post presente. Es obvio que la composición de funciones es/(debe ser) asociativa, pero los intentos de generalización modesta, me dejan cuestionando dónde, si acaso, podría haber un poco de truco.

Sería divertido tener una discusión larga y reflexiva que conduzca al acuerdo de que de hecho todos los asuntos son trivialmente obvios, obviamente triviales, y que en ningún lugar ha habido ningún tipo de truco después de todo.