Autor Tema: Algunas dudas más sobre la prueba del teorema de extensión genérica.

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

17 Enero, 2025, 05:35 am
Leído 1352 veces

franma

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

Perdón por abrir otro hilo sobre el tema, pero creía que entendía casi todo de la prueba del teorema de extensión genérica que se da aquí (página 29) pero me han surgido varias dudas que comento a continuación:
  • Primero algo no muy relacionado, cuando se trabaja con modelos booleanos por ejemplo y se dice que una prueba es por inducción mutua (digamos que el predicado es \( P(u,v) \)) y se supone válida la hipotesis para todos \( u'\in dom(u) \) y \( v'\in dom(v) \) para luego probar que vale para \( u \) y \( v \). Esto se consigue considerando \( P'(u)=\forall v\in V^\mathbb{B}\, P(u,v) \) y luego haciendo inducción en \( u \) con predicado \( P'(u) \), ¿no?. Si no, no entiendo como llegar a esa hipotesis para la inducción
  • Ahora si, respecto a la prueba, en la página 31 se enuncia un lema y se dice que se probará por inducción mutua en \( u \) y \( v \) (de ahí la duda anterior). Pero ahora mi duda es, ¿donde ocurre esta inducción? ¿es en \( M \)? Supongo que podemos probar cosas por inducción en \( M^\mathbb{B} \) relativizando el teorema de inducción en \( V^\mathbb{B} \), pero me genera dudas que en el enunciado de inducción aparezca \( \tilde{G} \) que a priori no esta en \( M \) (y la mayoría de veces no lo está) ¿luego relativizando no aparecerían problemas? ¿O acaso hay que entender que \( b\in \tilde{G} \) quiere decir \( b\cap G\neq \emptyset \)? Aunque así fuera en la prueba por inducción se usan por ejemplo la propiedad de \( M \)-genericidad del ultrafiltro genérico, lo que me da a pensar que la prueba esta siendo razonada "en \( V \)" pero no se si es correcto esto. Entonces mi pregunta es, ¿donde y cómo se hace esta inducción?

Espero me puedan ayudar.

Saludos,
Franco.

17 Enero, 2025, 11:47 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Primero algo no muy relacionado, cuando se trabaja con modelos booleanos por ejemplo y se dice que una prueba es por inducción mutua (digamos que el predicado es \( P(u,v) \)) y se supone válida la hipotesis para todos \( u'\in dom(u) \) y \( v'\in dom(v) \) para luego probar que vale para \( u \) y \( v \). Esto se consigue considerando \( P'(u)=\forall v\in V^\mathbb{B}\, P(u,v) \) y luego haciendo inducción en \( u \) con predicado \( P'(u) \), ¿no?. Si no, no entiendo como llegar a esa hipotesis para la inducción.

Sí, es una forma de verlo. Si has probado lo que requiere la inducción mutua, puedes concluir que todo \( u \) cumple \( P'(u) \), porque, si lo supones cierto para todo \( u'\in \mbox{dom}(u) \), dado cualquier \( v \), tienes que si \( u'\in \mbox{dom}(u) \) y \( v'\in \mbox{dom}(v) \), se cumple \( P'(u') \), luego se cumple \( P(u', v') \) y por la inducción mutua, también se cumple \( P(u, v) \), luego se cumple \( P'(u) \).

Ahora si, respecto a la prueba, en la página 31 se enuncia un lema y se dice que se probará por inducción mutua en \( u \) y \( v \) (de ahí la duda anterior). Pero ahora mi duda es, ¿donde ocurre esta inducción? ¿es en \( M \)? Supongo que podemos probar cosas por inducción en \( M^\mathbb{B} \) relativizando el teorema de inducción en \( V^\mathbb{B} \), pero me genera dudas que en el enunciado de inducción aparezca \( \tilde{G} \) que a priori no esta en \( M \) (y la mayoría de veces no lo está) ¿luego relativizando no aparecerían problemas? ¿O acaso hay que entender que \( b\in \tilde{G} \) quiere decir \( b\cap G\neq \emptyset \)? Aunque así fuera en la prueba por inducción se usan por ejemplo la propiedad de \( M \)-genericidad del ultrafiltro genérico, lo que me da a pensar que la prueba esta siendo razonada "en \( V \)" pero no se si es correcto esto. Entonces mi pregunta es, ¿donde y cómo se hace esta inducción?

Sí, la inducción es en \( V \), y es sobre la propiedad

\( P(u, v)\equiv u\in M^{\mathbb B}\land v\in M^{\mathbb B}\rightarrow (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \).

17 Enero, 2025, 11:19 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 :)

Sí, es una forma de verlo. Si has probado lo que requiere la inducción mutua, puedes concluir que todo \( u \) cumple \( P'(u) \), porque, si lo supones cierto para todo \( u'\in \mbox{dom}(u) \), dado cualquier \( v \), tienes que si \( u'\in \mbox{dom}(u) \) y \( v'\in \mbox{dom}(v) \), se cumple \( P'(u') \), luego se cumple \( P(u', v') \) y por la inducción mutua, también se cumple \( P(u, v) \), luego se cumple \( P'(u) \).

Bien, entendido. Entonces a partir de ahora, si quiero probar predicados en "varias variables" por induccion directamente puedo suponer que vale para todos \( u_1'\in dom(u_1),...,u_n'\in dom(u_n) \) y si pruebo que eso implica que vale para \( u_1,...,u_n \) ya tendria que \( P(u_1,...,u_n) \) vale para todos. Me parece interesante comentar esto porque hasta el momento yo cuando tenía que hacer estas pruebas por inducción hacía el esquema de inducción usual con \( P' \) y esto es un poco más comodo.

Sí, la inducción es en \( V \), y es sobre la propiedad

\( P(u, v)\equiv u\in M^{\mathbb B}\land v\in M^{\mathbb B}\rightarrow (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \).

No termino de entender :-[. Tenemos el principio de inducción en \( V^\mathbb{B} \) (que es un teorema de ZF), luego lo podemos relativizar a \( M \), pero esto NO es lo que estamos haciendo, ¿cierto?

Entonces, ¿que esquema de inducción estamos usando? Lo único que se me ocurre es que la relación \( uRv \equiv u\in \text{dom}(v) \) vista como relación sobre \( M^\mathbb{B} \) siga siendo bien fundada (externamente, y con esto me refiero a en \( V \)) y luego apliquemos inducción respecto a esta relación, ¿es eso?

Saludos,
Franco.

18 Enero, 2025, 12:25 am
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No termino de entender :-[. Tenemos el principio de inducción en \( V^\mathbb{B} \) (que es un teorema de ZF), luego lo podemos relativizar a \( M \), pero esto NO es lo que estamos haciendo, ¿cierto?

No relativizamos nada.

Entonces, ¿que esquema de inducción estamos usando?

Lo que has llamado inducción mutua en \( V \).

Lo único que se me ocurre es que la relación \( uRv \equiv u\in \text{dom}(v) \) vista como relación sobre \( M^\mathbb{B} \) siga siendo bien fundada (externamente, y con esto me refiero a en \( V \)) y luego apliquemos inducción respecto a esta relación, ¿es eso?

Ciertamente es una relación bien fundada, porque cualquier relación bien fundada en una clase se restringe a una relación bien fundada en cualquier otra clase, pero eso no tiene nada que ver. Usamos lo que has llamado inducción mutua en \( V \) aplicada a la propiedad \( P(u, v) \) que te he indicado antes. En ella aparece \( M \), pero eso no significa que se tenga que relativizar nada a \( M \). ¿Cuál es el problema?

18 Enero, 2025, 12:32 am
Respuesta #4

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
(...) ¿Cuál es el problema?

El problema es que no se que es la "inducción mutua". Yo solo conozco el teorema de inducción para \( V^\mathbb{B} \) que dice: Sea \( \phi(u) \) una fórmula entonces se tiene que:
\( (\forall u\in V^\mathbb{B})\,((\forall v\in dom(u))\,\phi(v)\Rightarrow \phi(u)) \Rightarrow (\forall u\in V^\mathbb{B})\,\phi(u) \)

Lo que quise expresar en mi primer mensaje es esto, que no sabía que es la "inducción mutua" y que para las pruebas donde se usaba yo suelo consierar la fórmula \( P'(u) \) y hacer como explique en el primer mensaje.

Siento que estoy un poco confundido porque se habla muchas veces de inducción en la prueba y no se que esquema de inducción estamos usando.

Saludos,
Franco.

18 Enero, 2025, 12:43 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El problema es que no se que es la "inducción mutua". Yo solo conozco el teorema de inducción para \( V^\mathbb{B} \) que dice: Sea \( \phi(u) \) una fórmula entonces se tiene que:
\( (\forall u\in V^\mathbb{B})\,((\forall v\in dom(u))\,\phi(v)\Rightarrow \phi(u)) \Rightarrow (\forall u\in V^\mathbb{B})\,\phi(u) \)

Lo que quise expresar en mi primer mensaje es esto, que no sabía que es la "inducción mutua" y que para las pruebas donde se usaba yo suelo consierar la fórmula \( P'(u) \) y hacer como explique en el primer mensaje.

Pero creía que eso era lo que habíamos aclarado en los mensajes precedentes. Tú mismo has dicho:

Bien, entendido. Entonces a partir de ahora, si quiero probar predicados en "varias variables" por induccion directamente puedo suponer que vale para todos \( u_1'\in dom(u_1),...,u_n'\in dom(u_n) \) y si pruebo que eso implica que vale para \( u_1,...,u_n \) ya tendria que \( P(u_1,...,u_n) \) vale para todos. Me parece interesante comentar esto porque hasta el momento yo cuando tenía que hacer estas pruebas por inducción hacía el esquema de inducción usual con \( P' \) y esto es un poco más comodo.

Pues justo eso es lo que estamos haciendo (para n = 2) con la propiedad \( P(u, v) \) que he indicado más arriba. Eso es lo que has llamado inducción mutua.

18 Enero, 2025, 12:49 am
Respuesta #6

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Perdona que este tan espeso hoy. Pero no logro entenderlo :-[

Pues justo eso es lo que estamos haciendo (para n = 2) con la propiedad \( P(u, v) \) que he indicado más arriba. Eso es lo que has llamado inducción mutua.

De acuerdo, entonces "inducción mutua" es suponer que vale para todos los \( u'\in dom(u) \) y \( v'\in dom(v) \). Ahora, la válidez de este esquema de inducción se puede probar por ejemplo consideando la fórmula \( P'(u) \) y utilizando tu argumento que utiliza el teorema de inducción ya conocida. Hasta ahí creo que todo bien.

Ahora mi problema actual es: digamos que este esquema de inducción mutua vale en \( V^\mathbb{B} \) pero yo quiero hacer una prueba que razona sobre elementos \( u\in M^\mathbb{B} \). ¿Cómo conecto ambas cosas? Ni siquiera podemos considerar \( V^\mathbb{B} \) ya que \( \mathbb{B} \) es solamente \( M \) completa. Espero que se entienda mi duda.

Saludos,
Franco.

18 Enero, 2025, 01:08 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De acuerdo, entonces "inducción mutua" es suponer que vale para todos los \( u'\in dom(u) \) y \( v'\in dom(v) \). Ahora, la válidez de este esquema de inducción se puede probar por ejemplo consideando la fórmula \( P'(u) \) y utilizando tu argumento que utiliza el teorema de inducción ya conocida. Hasta ahí creo que todo bien.

Yo nunca había visto la expresión "inducción mutua". Entiendo, por lo que has dicho, que es a eso a lo que llamas inducción mutua y, en cualquier caso, mi primer párrafo en la respuesta #1 prueba que esa forma de razonamiento (la llamemos como la llamemos) es correcta.

Ahora mi problema actual es: digamos que este esquema de inducción mutua vale en \( V^\mathbb{B} \) pero yo quiero hacer una prueba que razona sobre elementos \( u\in M^\mathbb{B} \). ¿Cómo conecto ambas cosas? Ni siquiera podemos considerar \( V^\mathbb{B} \) ya que \( \mathbb{B} \) es solamente \( M \) completa. Espero que se entienda mi duda.

Tenemos un modelo transitivo \( M \) de ZF, un álgebra de boole \( \mathbb B\in M \) completa en \( M \) y un ultrafiltro genérico \( G \), y ahora razonamos por inducción mutua en \( V \) aplicada a la propiedad

\( P(u, v)\equiv u\in M^{\mathbb B}\land v\in M^{\mathbb B}\rightarrow (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \)

No hay nada que relativizar ni nada que conectar. Se trata de probar que para todo \( u, v\in V^{\mathbb B} \) se cumple \( P(u, v) \), para lo cual suponemos \( P(u', v') \) para todo \( u'\in \mbox{dom}(u), v'\in \mbox{dom}(v) \) y tenemos que demostrar \( P(u, v) \). Para ello suponemos que \( u, v\in M^{\mathbb B} \) y tenemos que probar que \( (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \), y eso es lo que se hace en tus apuntes.

La clase \( V^{\mathbb B} \) está definida para cualquier conjunto parcialmente ordenado. No hace falta que sea un álgebra de Boole, ni mucho menos que sea completa. El hecho de que \( \mathbb B \) sea completa en \( M \) es necesario para que esté definido \( [\![u=v]\!] \) (que en realidad es \( [\![u=v]\!]^M \)) y, en efecto, sólo estamos considerando esto para \( u, v\in M^{\mathbb B} \).

18 Enero, 2025, 01:25 am
Respuesta #8

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Tenemos un modelo transitivo \( M \) de ZF, un álgebra de boole \( \mathbb B\in M \) completa en \( M \) y un ultrafiltro genérico \( G \), y ahora razonamos por inducción mutua en \( V \) aplicada a la propiedad

\( P(u, v)\equiv u\in M^{\mathbb B}\land v\in M^{\mathbb B}\rightarrow (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \)

No hay nada que relativizar ni nada que conectar. Se trata de probar que para todo \( u, v\in V^{\mathbb B} \) se cumple \( P(u, v) \), para lo cual suponemos \( P(u', v') \) para todo \( u'\in \mbox{dom}(u), v'\in \mbox{dom}(v) \) y tenemos que demostrar \( P(u, v) \). Para ello suponemos que \( u, v\in M^{\mathbb B} \) y tenemos que probar que \( (u^G = v^G\leftrightarrow [\![u=v]\!]\in G) \), y eso es lo que se hace en tus apuntes.

La clase \( V^{\mathbb B} \) está definida para cualquier conjunto parcialmente ordenado. No hace falta que sea un álgebra de Boole, ni mucho menos que sea completa. El hecho de que \( \mathbb B \) sea completa en \( M \) es necesario para que esté definido \( [\![u=v]\!] \) (que en realidad es \( [\![u=v]\!]^M \)) y, en efecto, sólo estamos considerando esto para \( u, v\in M^{\mathbb B} \).

Ahora con esta explicación creo que lo entiendo. Pero me deja sintiendome un tanto raro. Me parece un poco abrumador detrás frase tan inocente como "se prueba por inducción mutua sobre \( u,v\in M^\mathbb{B} \)" hubiese tanta tela que cortar (al menos para mí). No creo que me hubiera podido salir solo, y claro, ahora que lo leo parece bastante razonable, pero no creo ser capaz de poder deducirlo por mi mismo.

Muchas gracias por toda la ayuda.

Saludos,
Franco.

18 Enero, 2025, 01:29 am
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora con esta explicación creo que lo entiendo. Pero me deja sintiendome un tanto raro. Me parece un poco abrumador detrás frase tan inocente como "se prueba por inducción mutua sobre \( u,v\in M^\mathbb{B} \)" hubiese tanta tela que cortar (al menos para mí). No creo que me hubiera podido salir solo, y claro, ahora que lo leo parece bastante razonable, pero no creo ser capaz de poder deducirlo por mi mismo.

Bueno, alternativamente, la justificación de la inducción mutua vale también si la restringimos directamente a \( M^{\mathbb B} \), si te gusta más verlo así. Quiero decir que (razonando en \( V \), sin relativizar a nada), si quieres probar que se cumple \( P(u, v) \) para todos los \( u, v\in M^{\mathbb B} \), puedes suponer como hipótesis de inducción \( P(u', v') \) para todo \( u'\in \mbox{dom}(u) \) y todo \( v'\in \mbox{dom}(v) \) y probar \( P(u, v) \).