Autor Tema: Prueba del teorema de colapso de Mostowski.

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

03 Enero, 2025, 06:26 am
Leído 640 veces

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Buenas a todos,

Tengo una prueba "esquemática" del teorema de colapso de Mostowski y estoy intentando rellenar los detalles. Primero el enunciado:
Si \( E(y,x) \) es una relación binaria extensional y bien fundada sobre una clase \( U \), entonces existe una clase transitiva \( M \) y una biyección \( \Phi: U\to M \) que realiza un isomorfismo entre \( (U,E) \) y \( (M,\in) \), es decir:
\( E(y,x) \Leftrightarrow \Phi(y)\in \Phi(x) \) (para todos \( x,y\in U \))
Además, la clase transitiva \( M \) y la biyección \( \Phi : U\to M \) son únicas.

Para la demostración definimos una funcional \( \Phi : U\to V \) por E-recursión de la siguiente manera:
\( \Phi(x) := \{\Phi(y) : y\in E^{-1}(x) \} \)
(se corresponde al caso donde \( F = id \) en el post anterior).

Lo primero que podemos hacer es probar que \( M := \text{img}\ \Phi \) es transitivo:
Supongamos que \( y\in x\in M \), como \( x\in M \) existe \( u\in U \) tal que \( \Phi(u) = x \) y por lo tanto \( y\in x = \Phi(u) = \{\Phi(v) : v\in E^{-1}(u)\} \) luego \( y=\Phi(v) \) para algún \( v\in E^{-1}(u) \) y por lo tanto \( y\in M \).

Ahora en mis notas dice, "se prueba por \( E \)-inducción que \( \Phi \) es inyectiva (utilizando el hecho que \( E \) es extensional)". Yo aquí no logro ver como hacer esto :-[ ¿Qué enunciado debemos usar para la \( E \)-inducción? ¿Debemos fijar una variable y hacer algo del estilo "fijado \( u_0 \in U \) probar que para todo \( v\in U \) si \( \Phi(u_0)=\Phi(v) \) entonces \( u_0=v \)?

Saludos,
Franco.

PD: Perdón que publique dos mensajes tan juntos. Es que están bastante relacionados y estoy aprovechando que tengo tiempo de escribirlos ahora.

03 Enero, 2025, 12:23 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora en mis notas dice, "se prueba por \( E \)-inducción que \( \Phi \) es inyectiva (utilizando el hecho que \( E \) es extensional)". Yo aquí no logro ver como hacer esto :-[ ¿Qué enunciado debemos usar para la \( E \)-inducción? ¿Debemos fijar una variable y hacer algo del estilo "fijado \( u_0 \in U \) probar que para todo \( v\in U \) si \( \Phi(u_0)=\Phi(v) \) entonces \( u_0=v \)?

Eso mismo. ¿Cuál es el problema? Supones que eso es cierto para todo \( u\,E\,u_0 \) y quieres probar que es cierto para \( u_0 \). En caso contrario existe un \( v\in U \), \( v\neq u \) tal que \( \Phi(u_0)=\Phi(v) \).

Ahora vamos a probar que \( u_0=v \) probando que, para todo \( z\in U \) si \( z\,E\,u_0 \), entonces \( z\,E\,v \) y viceversa. La extensionalidad de la relación significa precisamente que, si pasa esto, es que \( u_0=v \).

Ahora bien, si \( z\,E\,u_0 \), entonces \( \Phi(z)\in \Phi(u_0)=\Phi(v) \), luego existe un \( z'\in U \) tal que \( z'\,E\,v \) y \( \Phi(z)=\Phi(z') \), y ahora usas que \( z \) cumple la hipótesis de inducción para concluir que \( z = z' \), luego \( z\,E\,v \).

La implicación contraria se prueba igual.

03 Enero, 2025, 10:11 pm
Respuesta #2

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Hola Carlos :)

Eso mismo. ¿Cuál es el problema?

Intenté eso durante mucho tiempo y no me salía la prueba :-[

Supones que eso es cierto para todo \( u\,E\,u_0 \) y quieres probar que es cierto para \( u_0 \). En caso contrario existe un \( v\in U \), \( v\neq u \) tal que \( \Phi(u_0)=\Phi(v) \).

Ahora vamos a probar que \( u_0=v \) probando que, para todo \( z\in U \) si \( z\,E\,u_0 \), entonces \( z\,E\,v \) y viceversa. La extensionalidad de la relación significa precisamente que, si pasa esto, es que \( u_0=v \).

De acuerdo.

Ahora bien, si \( z\,E\,u_0 \), entonces \( \Phi(z)\in \Phi(u_0)=\Phi(v) \), luego existe un \( z'\in U \) tal que \( z'\,E\,v \) y \( \Phi(z)=\Phi(z') \), y ahora usas que \( z \) cumple la hipótesis de inducción para concluir que \( z = z' \), luego \( z\,E\,v \).

Aquí no veo como usar la hipótesis de inducción, ya que, es verdad que tenemos \( z\,E\,u_0 \) luego \( z \) cumple la hipótesis de inducción y por lo tanto si \( \Phi(z)= \Phi(u_0) \) entonces \( z=u_0 \). Pero no veo como usar esto :-[

Tal vez entendí mal la inducción. Yo interpreto que estamos usando el enunciado:
\( \psi(v) \equiv \Phi(v)=\Phi(u_0) \Rightarrow v=u_0 \)

Ahora que lo pienso, tal vez el el enunciado correcto sea:
\( \psi(v) \equiv (\forall u\in U)(\Phi(v)=\Phi(u) \Rightarrow v=u) \)
en cuyo caso si entiendo tu prueba por inducción y de hecho, tal vez este sea el motivo por el cual no me salía la prueba...

Saludos,
Franco.

03 Enero, 2025, 10:33 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Aquí no veo como usar la hipótesis de inducción, ya que, es verdad que tenemos \( z\,E\,u_0 \) luego \( z \) cumple la hipótesis de inducción y por lo tanto si \( \Phi(z)= \Phi(u_0) \) entonces \( z=u_0 \). Pero no veo como usar esto :-[

Tal vez entendí mal la inducción. Yo interpreto que estamos usando el enunciado:
\( \psi(v) \equiv \Phi(v)=\Phi(u_0) \Rightarrow v=u_0 \)

Ahora que lo pienso, tal vez el el enunciado correcto sea:
\( \psi(v) \equiv (\forall u\in U)(\Phi(v)=\Phi(u) \Rightarrow v=u) \)
en cuyo caso si entiendo tu prueba por inducción y de hecho, tal vez este sea el motivo por el cual no me salía la prueba...

La hipótesis de inducción es la que has dicho en tu mensaje anterior, no la (primera) que dices ahora, es decir:

¿Debemos fijar una variable y hacer algo del estilo "fijado \( u_0 \in U \) probar que para todo \( v\in U \) si \( \Phi(u_0)=\Phi(v) \) entonces \( u_0=v \)?

Justo eso: la fórmula a la que le aplicas la inducción es

\( \psi(u_0)\equiv \forall v(v\in U\land \Phi(u_0)=\Phi(v)\rightarrow u_0 = v) \).

Como \( z\,E\,u_0 \), tenemos que \( z \) cumple la hipótesis de inducción, es decir, que \( \forall v(v\in U\land \Phi(z)=\Phi(v)\rightarrow z = v) \) y aplicamos esto a \( v = z' \).

03 Enero, 2025, 10:40 pm
Respuesta #4

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
La hipótesis de inducción es la que has dicho en tu mensaje anterior, no la (primera) que dices ahora, es decir:

Es que en mi anterior mensaje me quise referir a la primer formula que ponía ahora :-[ Pero todo entendido.

Saludos,
Franco.