Autor Tema: Demostración formal de inyectividad de una función compuesta.

0 Usuarios y 1 Visitante están viendo este tema.

27 Noviembre, 2011, 05:34 pm
Leído 2031 veces

Fran Colegiales

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 18
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos:
Estoy haciendo el siguiente ejercicio:
Sean \( f:A\to B, g:B\to C. \)
Si \( f,g, \) son inyectivas, muestre que \( g \circ f \) es inyectiva.

Hice una demostración informal, pero quiero hacer una demostración formal y quedo trabado en el medio.

Uso las siguientes premisas:

\( \forall{x}\forall{y}\forall{z} [[ (y,x) \in{R_f}\wedge(z,x)\in{R_f}]\rightarrow{y=z}] \)
\( \forall{x}\forall{y}\forall{z} [[ (y,x) \in{R_g}\wedge(z,x)\in{R_g}]\rightarrow{y=z}] \)
\( \forall{x}\forall{y}[ (x,y) \in{R_{g \circ f}}\Leftrightarrow \exists{z}[(x,z)\in{R_f}\wedge (z,y) \in{R_g}]] \)

Donde \( R_f \) es la regla de asignación de la función \( f \),
\( R_g \) es la regla de asignación de la función \( g \),
y \( R_{g \circ f} \) es la regla de asignación de la función \( g \circ f \).

La primer premisa dice que \( f \) es inyectiva, la segunda que \( g \) es inyectiva, y la última es la definición de función compuesta.

Quiero llegar a la conclusión \( \forall{x}\forall{y}\forall{z} [[ (y,x) \in{R_{g \circ f}}\wedge(z,x)\in{R_{g \circ f}}]\rightarrow{y=z}] \)

¿Es posible hacer esta demostración sólo con esas premisas o necesito más premisas? En ese caso, ¿cuales?

Gracias por el tiempo.

29 Noviembre, 2011, 03:42 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tienes bastantes premisas.

Si supones que \( (y,x), (z,x)\in R_{g\circ f} \), entonces existen \( u, v \) tales que \( (y,u)\in R_f, (u,x)\in R_g, (z,v)\in R_f, (v,x)\in R_g \).

Por la inyectividad de \( g \) tienes que \( u=v \) y por la de \( f \) que \( y=z \).

01 Diciembre, 2011, 11:30 pm
Respuesta #2

Fran Colegiales

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 18
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos:

Gracias por responderme.

Lo estuve pensando y me parece que al sistema deductivo con el que estoy trabajando -el de Gentzen- le falta una regla de derivación para el símbolo "=". Una regla de eliminación para "=".
Si a partir de dos fórmulas:
1) a=b
2) \( \phi \)
(donde a y b son constantes de individuo)
Yo pudiera derivar:
3)
[a\b]\( \phi\Longleftrightarrow{\phi} \)

([a\b] \( \phi \) sería la fórmula que resulta de reemplazar todas las apariciones de "b" en la fórmula \( \phi \) por "a")

Entonces, podría hacer la demostración formalmente. Pero no sé si esa es una regla válida y no encuentro hasta el momento bibliografía que me ayude, así que por eso vuelvo a consultarte.

Saludos. Gracias.



01 Diciembre, 2011, 11:55 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En efecto, el sistema de Gentzen no tiene en principio reglas para tratar con el igualador, pero si quieres trabajar con el igualador tienes que añadírselas. En cualquier libro de lógica podrás encontrar formalizaciones del cálculo deductivo con igualador. Sólo tienes que elegir la que más te guste, pero necesitas una.