Autor Tema: Fórmulas $$\Delta_0$$ en el modelo booleano.

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

11 Enero, 2025, 05:21 pm
Leído 1544 veces

franma

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

En mis apuntes (página 51) se prueba que para todo \( u\in V^\mathbb{B} \) se tiene:
\( \displaystyle [\![ On(u) ]\!] = \bigvee_{\alpha \in On} [\![ u=\check{\alpha} ]\!] \)

La prueba comienza diciendo para todo \( \alpha\in On \) se tiene que:
\( [\![ On(\check{\alpha}) ]\!] =  [\![ On^{\check{V}}(\check{\alpha}) ]\!] = 1 \)

Ahora, que \( [\![ On^{\check{V}}(\check{\alpha}) ]\!] = 1 \) es consecuencia de un lema anterior que dice que \( \phi(\vec{x}) \Leftrightarrow V^\mathbb{B} \models \phi^{\check{V}}(\check{\vec{x}}) \). Lo que no termino de entender es como deducir que:
\( [\![ On(\check{\alpha}) ]\!] =  [\![ On^{\check{V}}(\check{\alpha}) ]\!] \)
en las notas dice que es consecuencia de que \( On \) sea una fórmula \( \Delta_0 \). Mi problema es que \( \check{V} \) no es una clase transitiva per se, sino que es una clase transitiva a los ojos de \( V^\mathbb{B} \), o sea, \( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \).
Lo que si sabemos es que:
\( (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
luego aplicando el lema tendríamos que:
\( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
y como \( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \) deducimos que:
\( V^\mathbb{B} \models \forall x\in \check{V}\,(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
¿Esta bien este razonamiento?

Agrego: Creo que esta mal porque al relativizar la fórmula debería ser:
\( \cancel{V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On^{\check{V}}(x) \Leftrightarrow On^{\check{V}}(x))} \)
¿no? Directamente puedo usar que si \( \mathsf{ZF} \vdash \phi \) entonces \( V^\mathbb{B} \models \phi \), ¿no?

Por otro lado, en un momento de la prueba se utiliza que:
\( [\![ On(u) ]\!] \leq [\![ u\in \check{\beta} ]\!] \lor [\![ u=\check{\beta} ]\!] \lor [\![ \check{\beta}\in u ]\!] \)
Esto no termino de entender como deducirlo :-[

Saludos,
Franco.

11 Enero, 2025, 07:16 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vaya por delante que no tengo una idea clara de qué cosas puedes suponer conocidas y cuáles tienen que ser demostradas, simplemente porque nunca me he puesto a trabajar tan a fondo con modelos booleanos, ya que todas estas cosas se demuestran mucho más fácilmente usando extensiones genéricas. Por ejemplo, lo que quieres probar aquí es consecuencia inmediata de que una extensión genérica tiene los mismos ordinales que el modelo base, y eso se demuestra fácilmente sin necesidad de nada de todo esto.

Lo que si sabemos es que:
\( (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
luego aplicando el lema tendríamos que:
\( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
y como \( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \) deducimos que:
\( V^\mathbb{B} \models \forall x\in \check{V}\,(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
¿Esta bien este razonamiento?

Todo lo que dices ahí es cierto. Lo que no sé es si cuando dices "sabemos esto", realmente es así. Por ejemplo, esto:

\( (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)

es demostrable, no en ZF, sino en la extensión de ZF con un predicado \( x\in \check V \). Si en esas condiciones puedes concluir igualmente que el valor booleano de esa sentencia es 1, pues bien (eso es cierto, lo que no sé es si lo tienes demostrado).

Directamente puedo usar que si \( \mathsf{ZF} \vdash \phi \) entonces \( V^\mathbb{B} \models \phi \), ¿no?

Pues no es exactamente ZF, pero casi (porque en ZF no está el predicado \( x\in \check V \)). El hecho es cierto. Vamos, quiero decir que todo suena bien, pero no sé si no habrá algún tecnicismo que se me escape, porque no es la forma habitual de trabajar.

Por otro lado, en un momento de la prueba se utiliza que:
\( [\![ On(u) ]\!] \leq [\![ u\in \check{\beta} ]\!] \lor [\![ u=\check{\beta} ]\!] \lor [\![ \check{\beta}\in u ]\!] \)
Esto no termino de entender como deducirlo :-[

Ahí sólo tienes que usar que en ZF se demuestra:

\( \forall uv(u\in \mbox{On}\land v\in \mbox{On}\rightarrow u\in v\lor u = v\lor v\in u) \)

y luego usar que  \( [\![\mbox{On}(\check{\beta}) ]\!]=1 \).

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

Vaya por delante que no tengo una idea clara de qué cosas puedes suponer conocidas y cuáles tienen que ser demostradas, simplemente porque nunca me he puesto a trabajar tan a fondo con modelos booleanos (...)

Te enuncio los principales resultados que creo nos pueden servir:

Proposición 1 (regla de Leibniz): Sea \( \phi(x,\vec{z}) \) una fórmula. Para todos \( u,v,\vec{w}\in V^\mathbb{B} \) se tiene que: \( [\![ u=v ]\!] \land [\![ \phi(v,\vec{w})]\!] \leq [\![ \phi(u,\vec{w}) ]\!] \)



Dado un contexto \( \Gamma(\vec{x}) \equiv \phi_1(\vec{x}),...,\phi_n(\vec{x}) \) definimos \( [\![\Gamma(\vec{u})]\!] := [\![\phi_1(\vec{u})]\!]\land \cdots \land [\![\phi_n(\vec{u})]\!]
 \)
Teorema 2 (correción): Si un secuente \( \Gamma(\vec{x})\vdash \phi(\vec{x}) \) es derivable en el sistema \( \mathsf{NK} \) (o \( \mathsf{LK} \)), entonces \( \mathsf{ZF}\vdash (\forall \vec{u}\in V^\mathbb{B})\,[\![\Gamma(\vec{u})]\!] \leq [\![\phi(\vec{u})]\!] \)



Teorema 3: \( V^\mathbb{B}\models \phi \) para todo \( \phi \) axioma de \( \mathsf{ZF} \)



Proposición 4: \( \phi(x_1,...,x_n) \Leftrightarrow V^\mathbb{B}\models \phi^{\check{V}}(\check{x}_1,...,\check{x}_n) \) para toda fórmula \( \phi \) de \( \mathsf{ZF} \) y \( x_1,...,x_n\in V \)



Todo lo que dices ahí es cierto. Lo que no sé es si cuando dices "sabemos esto", realmente es así. Por ejemplo, esto:

\( (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)

es demostrable, no en ZF, sino en la extensión de ZF con un predicado \( x\in \check V \). Si en esas condiciones puedes concluir igualmente que el valor booleano de esa sentencia es 1, pues bien (eso es cierto, lo que no sé es si lo tienes demostrado).

Creo que tienes razón y así tal cual como dices no lo tengo demostrado... yo lo estaba pensando con el \( \check{V} = \{\check{x} : x\in V\} \) pero claro, ahí ya habría que entrar a calcular \( \check{V}^{\check{V}} \) y me pierdo.

Pues no es exactamente ZF, pero casi (porque en ZF no está el predicado \( x\in \check V \)). El hecho es cierto. Vamos, quiero decir que todo suena bien, pero no sé si no habrá algún tecnicismo que se me escape, porque no es la forma habitual de trabajar.

De nuevo, tienes razón. El teorema 4 tiene una generalización para extensiones de \( \mathsf{ZF} \) pero deben de tener el mismo lenguaje... así que tampoco nos sirve.

Ahí sólo tienes que usar que en ZF se demuestra:

\( \forall uv(u\in \mbox{On}\land v\in \mbox{On}\rightarrow u\in v\lor u = v\lor v\in u) \)

y luego usar que  \( [\![\mbox{On}(\check{\beta}) ]\!]=1 \).

Entendido.

La verdad estuve pensando y sigo sin poder probarlo :-[

Saludos,
Franco.

11 Enero, 2025, 11:40 pm
Respuesta #3

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
(Espero terminar este mensaje antes que tú publiques otro >:D)

Encontré en el Jech:
Lema 14.21: Si \( \phi(x_1,...,x_n) \) es una fórmula \( \Delta_0 \) entonces \( \phi(x_1,...,x_n) \) si y sólo si \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]=1 \)
Demostración: Por inducción en la complejidad de \( \phi \)

Vamos a ello:
Caso \( x\in y \): Es un lema previo de mis notas.
Caso \( x = y \): Es un lema previo de mis notas.
Caso conectivas: inmediato por la hipótesis de inducción (si no me dejo nada).
Caso \( \exists \): No me esta saliendo :banghead:

Agrego Tiene olor a que vamos a tener que usar el principio del máximo (cosa que se prueba después en mis notas, pero se puede arreglar)

Pero vamos por buen camino supongo...

Saludos,
Franco.

11 Enero, 2025, 11:47 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahí sólo tienes que usar que en ZF se demuestra:

\( \forall uv(u\in \mbox{On}\land v\in \mbox{On}\rightarrow u\in v\lor u = v\lor v\in u) \)

y luego usar que  \( [\![\mbox{On}(\check{\beta}) ]\!]=1 \).

Entendido.

La verdad estuve pensando y sigo sin poder probarlo :-[

¿Te refieres a esto último o a lo anterior?

En cuanto a lo anterior, los resultados que me pones ya los había visto en tus apuntes, pero lo que hacen falta son resultados sobre el uso del nombre \( \check V \). El problema que tengo es que no sabría cómo demostrarte lo que necesitas porque para eso tendría que ponerme a desarrollar toda la teoría de modelos booleanos y ver qué hace falta para llegar hasta ahí, cosa que nunca he hecho porque, una vez demostrado el teorema fundamental, trabajar con modelos booleanos sólo es complicar las cosas para nada. Yo puedo decirte si algo es cierto o falso interpretándolo en términos de extensiones genéricas y viendo si es cierto o falso.

Por ejemplo, para tratar con \( \check V \) lo más práctico es tener en cuenta que \( (p\Vdash \sigma\in \check V)^M \) es equivalente a que \( \sigma_G\in M \) siempre que \( p\in G \).

pero no sabría argumentar estrictamente en términos de modelos booleanos porque nunca me he puesto a hacerlo y no tengo en la cabeza el esquema de qué cosas se pueden probar a partir de cuáles otras. Para ello tendría que sentarme a escribir todas las pruebas y ver qué hay que probar antes para probar cada cosa. En otros casos te puedo decir: para probar esto puedes hacerlo así y así, pero en este caso no estoy familiarizado con esta forma de probar estos resultados (sin hacer referencia a extensiones genéricas, sólo con modelos booleanos).

(Espero terminar este mensaje antes que tú publiques otro >:D)

Sí, aunque no te estaba diciendo gran cosa de provecho.   :(

Encontré en el Jech:
Lema 14.21: Si \( \phi(x_1,...,x_n) \) es una fórmula \( \Delta_0 \) entonces \( \phi(x_1,...,x_n) \) si y sólo si \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]=1 \)
Demostración: Por inducción en la complejidad de \( \phi \)

Vamos a ello:
Caso \( x\in y \): Es un lema previo de mis notas.
Caso \( x = y \): Es un lema previo de mis notas.
Caso conectivas: inmediato por la hipótesis de inducción (si no me dejo nada).
Caso \( \exists \): No me esta saliendo :banghead:

Agrego Tiene olor a que vamos a tener que usar el principio del máximo (cosa que se prueba después en mis notas, pero se puede arreglar)

Pero vamos por buen camino supongo...

Pero ten presente que en una fórmula \( \Delta_0 \) no es simplemente \( \exists x\beta \), sino que tiene que ser \( \exists x\in y\beta \).

11 Enero, 2025, 11:59 pm
Respuesta #5

franma

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

¿Te refieres a esto último o a lo anterior?

Lo anterior.

En cuanto a lo anterior, los resultados que me pones ya los había visto en tus apuntes, pero lo que hacen falta son resultados sobre el uso del nombre \( \check V \). El problema que tengo es que no sabría cómo demostrarte lo que necesitas porque para eso tendría que ponerme a desarrollar toda la teoría de modelos booleanos y ver qué hace falta para llegar hasta ahí, cosa que nunca he hecho porque, una vez demostrado el teorema fundamental, trabajar con modelos booleanos sólo es complicar las cosas para nada. Yo puedo decirte si algo es cierto o falso interpretándolo en términos de extensiones genéricas y viendo si es cierto o falso.

Por ejemplo, para tratar con \( \check V \) lo más práctico es tener en cuenta que \( (p\Vdash \sigma\in \check V)^M \) es equivalente a que \( \sigma_G\in M \) siempre que \( p\in G \).

pero no sabría argumentar estrictamente en términos de modelos booleanos porque nunca me he puesto a hacerlo y no tengo en la cabeza el esquema de qué cosas se pueden probar a partir de cuáles otras. Para ello tendría que sentarme a escribir todas las pruebas y ver qué hay que probar antes para probar cada cosa. En otros casos te puedo decir: para probar esto puedes hacerlo así y así, pero en este caso no estoy familiarizado con esta forma de probar estos resultados (sin hacer referencia a extensiones genéricas, sólo con modelos booleanos).

Entiendo lo que me dices, la verdad desconozco como deducir resultados sobre el modelo booleano a partir de las extensiones genéricas (y aunque suena interesante) no me serviría mucho en este caso ya que estoy estudiando para el examen, y cambiar tan radicalmente el enfoque del curso me puede complicar las cosas.

Sí, aunque no te estaba diciendo gran cosa de provecho.   :(

Todas las cosas que tu me dices me sirven. En este caso me sirve mucho tu lectura de mis pruebas y mis razonamientos.

Pero ten presente que en una fórmula \( \Delta_0 \) no es simplemente \( \exists x\beta \), sino que tiene que ser \( \exists x\in y\beta \).

De acuerdo, tenemos por ejemplo \( \phi(x_1,...,x_n) \equiv (\exists x\in y)\, \phi_0(x,x_1,...,x_n) \). Pero al momento de intentar probar la implicación (\( \Rightarrow \)), tenemos como hipótesis \( (\exists x\in y)\, \phi_0(x,x_1,...,x_n) \) y aquí no se ni como usar la hipótesis de inducción ni como relacionarlo con \( [\![ \quad  ]\!] \)

Agrego: También nos bastaría con probar el caso de \( \forall \), ¿no? Ya que de todos modos tendríamos un conjunto completo de conectivas y demás. Ese caso creo que es más sencillo (para mí) porque trabajamos con un ínfimo.
Bien, supongamos que \( \phi(x_1,...,x_n) \equiv (\forall x\in y)\,\phi_0(x,x_1,...,x_n) \), entonces tenemos que:
\( \begin{align*}
[\![ (\forall x\in \check{y})\,\phi_0(x,\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow \bigwedge_{ v\in \text{dom}(\check{y})}( \check{y}(v) \land [\![ \phi_0(v,\check{x}_1,...,\check{x}_n) ]\!]) = 1\\
&\Leftrightarrow \bigwedge_{ x\in y}( \check{y}(\check{x}) \land [\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!]) = 1 \\
&\Leftrightarrow \bigwedge_{ x\in y}[\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1 \\
&\Leftrightarrow (\forall x\in y)\, ([\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1) \\
&\Leftrightarrow (\forall x\in y)\, \phi_0(x,x_1,...,x_n) \tag{por H.I}
\end{align*} \)

¿Es correcto?

De todas formas buscando en internet vi que se puede hacer similarmente el \( \exists \), solamente que he leído que la hipotesis de inducción implica que \( [\![ \phi(\check{x}_1,...,\check{x}_n ]\!] \in \{0,1\} \) y esto no logro verlo...

Saludos,
Franco.

12 Enero, 2025, 12:13 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Agrego: También nos bastaría con probar el caso de \( \forall \), ¿no? Ya que de todos modos tendríamos un conjunto completo de conectivas y demás. Ese caso creo que es más sencillo (para mí) porque trabajamos con un ínfimo.
Bien, supongamos que \( \phi(x_1,...,x_n) \equiv (\forall x\in y)\,\phi_0(x,x_1,...,x_n) \), entonces tenemos que:
\( \begin{align*}
[\![ (\forall x\in \check{y})\,\phi_0(x,\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow \bigwedge_{ v\in \text{dom}(\check{y})}( \check{y}(v) \land [\![ \phi_0(v,\check{x}_1,...,\check{x}_n) ]\!]) = 1\\
&\Leftrightarrow \bigwedge_{ x\in y}( \check{y}(\check{x}) \land [\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!]) = 1 \\
&\Leftrightarrow \bigwedge_{ x\in y}[\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1 \\
&\Leftrightarrow (\forall x\in y)\, ([\![ \phi_0(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1) \\
&\Leftrightarrow (\forall x\in y)\, \phi_0(x,x_1,...,x_n) \tag{por H.I}
\end{align*} \)

¿Es correcto?

Es correcto, pero hay un problema en todo el argumento y está aquí:

Caso conectivas: inmediato por la hipótesis de inducción (si no me dejo nada).

¿Cómo razonas el caso \( \phi \equiv \lnot \psi \), por ejemplo?

De todas formas buscando en internet vi que se puede hacer similarmente el \( \exists \), solamente que he leído que la hipotesis de inducción implica que \( [\![ \phi(\check{x}_1,...,\check{x}_n ]\!] \in \{0,1\} \) y esto no logro verlo...

Eso tiene que ver con el problema que aparece al tener que probar el resultado para las conectivas. Creo que es mejor analizar ese caso primero, antes de pasar a los cuantificadores. En realidad es necesario demostrarlo para los dos cuantificadores.

13 Enero, 2025, 03:04 am
Respuesta #7

franma

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

Recién tengo un momento libre para usar el ordenador, así que aprovecho a responderte:

Es correcto, pero hay un problema en todo el argumento y está aquí:

Caso conectivas: inmediato por la hipótesis de inducción (si no me dejo nada).

¿Cómo razonas el caso \( \phi \equiv \lnot \psi \), por ejemplo?

Bien (siempre que digo "si no me dejo nada" parece que me dejo todo ::)), veo el problema que mencionas, a ver si puedo solucionarlo, cambiemos el enunciado que queremos probar por:
Si \( \phi(x_1,...,x_n) \) es una fórmula \( \Delta_0 \) entonces \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] \in \{0,1\} \) y además \( \phi(x_1,...,x_n) \) si y sólo si \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]=1 \)

La demostración nuevamente la hacemos por inducción en la complejidad de \( \phi \):
  • Caso \( x\in y \): página 31 de mis apuntes
  • Caso \( x = y \): página 31 de mis apuntes
  • Caso \( \phi(x_1,...,x_n) \equiv \phi_1(x_1,...,x_n)\land \phi_2(x_1,...,x_n) \): Tenemos que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \land [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] \) luego usando la hipótesis de inducción es claro que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow  [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \land [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] = 1 \\
    &\Leftrightarrow ([\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 1) \land ([\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] = 1) \\
    &\Leftrightarrow \phi_1(x_1,...,x_n) \land \phi_2(x_1,...,x_n) \equiv \phi(x_1,...,x_n)
    \end{align*} \)
  • Caso \( \phi(x_1,...,x_n) \equiv \phi_1(x_1,...,x_n)\lor \phi_2(x_1,...,x_n) \): Tenemos que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \lor [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] \) luego usando la hipótesis de inducción es claro que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow  [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \lor [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] = 1 \\
    &\Leftrightarrow ([\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 1) \lor ([\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] = 1) \\
    &\Leftrightarrow \phi_1(x_1,...,x_n) \lor \phi_2(x_1,...,x_n) \equiv \phi(x_1,...,x_n)
    \end{align*} \)
  • Caso \( \phi(x_1,...,x_n) \equiv \phi_1(x_1,...,x_n)\Rightarrow \phi_2(x_1,...,x_n) \): Tenemos que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \rightarrow [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] \) luego recordando que \( a\rightarrow b := \neg a \lor b \) y usando la hipótesis de inducción es claro que \( [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ \phi(\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow  [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \rightarrow [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] = 1 \\
    &\Leftrightarrow [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] \leq [\![ \phi_2(\check{x}_1,...,\check{x}_n)]\!] \\
    &\Leftrightarrow ([\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 1 \land [\![ \phi_2(\check{x}_1,...,\check{x}_n) ]\!] = 1) \lor ([\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 0) \\
    &\Leftrightarrow (\phi_1(x_1,...,x_n) \land  \phi_2(x_1,...,x_n) ) \lor \neg \phi_1(x_1,...,x_n) \\
    &\Leftrightarrow \neg \phi_1(x_1,...,x_n)\lor \phi_2(x_1,...,x_n) \equiv \phi(x_1,...,x_n)
    \end{align*} \)
    donde en el penúltimo paso usamos que \( [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 0 \) si y sólo si \( \neg \phi(x_1,...,x_n) \), esto se deduce de la hipótesis de inducción ya que:
    (\( \Rightarrow \)) Si \( [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 0 \) y \( \phi(x_1,...,x_n) \) entonces \( [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 1 \) por inducción lo cual es absurdo, luego deducimos \( \neg \phi(x_1,...,x_n) \)
    (\( \Leftarrow \)) Si \( \neg \phi(x_1,...,x_n) \) entonces por inducción no puede ser \( [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 1 \) luego como esta en \( \{0,1\} \) debe ser \( [\![ \phi_1(\check{x}_1,...,\check{x}_n) ]\!] = 0 \)
  • Caso \( \phi(x_1,...,x_n) \equiv \neg \phi_1(x_1,...,x_n) \): Tenemos que \( [\![ \phi(x_1,...,x_n) ]\!] = \neg [\![ \phi_1(x_1,...,x_n) ]\!]  \) luego usando la hipótesis de inducción es claro que \( [\![ \phi(x_1,...,x_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ \phi(x_1,...,x_n) ]\!] = 1 &\Leftrightarrow  \neg [\![ \phi_1(x_1,...,x_n) ]\!] = 1 \\
    &\Leftrightarrow  [\![ \phi_1(x_1,...,x_n) ]\!] = 0 \\
    &\Leftrightarrow \neg \phi_1(x_1,...,x_n) \equiv \phi(x_1,...,x_n) \tag{mismo razonamiento que en el item anterior}
    \end{align*} \)
  • Caso \( \phi(x_1,...,x_n) \equiv (\forall x\in y)\,\phi_1(x,x_1,...,x_n) \): Tenemos que \( [\![ \phi(x_1,...,x_n) ]\!] = \cdots = \bigwedge_{ x\in y}[\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] \) luego usando la hipótesis de inducción es claro que \( [\![ \phi(x_1,...,x_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ (\forall x\in \check{y})\,\phi_1(x,\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow \bigwedge_{ v\in \text{dom}(\check{y})}( \check{y}(v) \land [\![ \phi_0(v,\check{x}_1,...,\check{x}_n) ]\!]) = 1\\
    &\Leftrightarrow \bigwedge_{ x\in y}( \check{y}(\check{x}) \land [\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!]) = 1 \\
    &\Leftrightarrow \bigwedge_{ x\in y}[\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1 \\
    &\Leftrightarrow (\forall x\in y)\, ([\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1) \\
    &\Leftrightarrow (\forall x\in y)\, \phi_1(x,x_1,...,x_n)
    \end{align*} \)
  • Caso \( \phi(x_1,...,x_n) \equiv (\exists x\in y)\,\phi_1(x,x_1,...,x_n) \): Tenemos que \( [\![ \phi(x_1,...,x_n) ]\!] = \cdots = \bigvee_{ x\in y}[\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] \) luego usando la hipótesis de inducción es claro que \( [\![ \phi(x_1,...,x_n) ]\!]\in \{0,1\} \), además:
    \( \begin{align*}
    [\![ (\exists x\in \check{y})\,\phi_1(x,\check{x}_1,...,\check{x}_n) ]\!] = 1 &\Leftrightarrow \bigvee_{ v\in \text{dom}(\check{y})}( \check{y}(v) \rightarrow [\![ \phi_0(v,\check{x}_1,...,\check{x}_n) ]\!]) = 1\\
    &\Leftrightarrow \bigvee_{ x\in y}( \check{y}(\check{x}) \rightarrow [\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!]) = 1 \\
    &\Leftrightarrow \bigvee_{ x\in y}[\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1 \\
    &\Leftrightarrow (\exists x\in y)\, ([\![ \phi_1(\check{x},\check{x}_1,...,\check{x}_n) ]\!] = 1) \tag{ya que el supremo se toma sobre valores 0 y 1} \\
    &\Leftrightarrow (\exists x\in y)\, \phi_1(x,x_1,...,x_n)
    \end{align*} \)

¿Ahora si esta completa y correcta?

De todas maneras, aunque esta prueba (si esta bien) justifica la igualdad de mis notas, siento que no estoy viendo algo... ya que en mis apuntes en la página 55 vuelve a usar un resultado (esta vez ascensión para fórmulas \( \Sigma_1 \) aplicado a \( \check{V} \)) y no término de entenderlo :-[
¿No tendrá algo que ver con lo que se dice en la página 57 aquí?

Saludos,
Franco.

13 Enero, 2025, 03:26 pm
Respuesta #8

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora está bien, aunque debería bastarte con probarlo para el negador y otro conector (el implicador o el disyuntor, por ejemplo) y uno de los cuantificadores.

En cuanto a lo último, una vez lo tienes probado para fórmulas \( \Delta_0 \), si tienes una fórmula \( \phi(x_1,\ldots, x_n)\equiv \exists x\,\psi(x,x_1,\ldots, x_n) \) de tipo \( \Sigma_1 \) y se cumple \( \phi(x_1,\ldots, x_n) \), entonces tomamos un \( x \) que cumpla \( \psi(x,x_1,\ldots, x_n) \), por lo que ya has probado \( [\![\psi(\check x,\check x_1,\ldots, \check x_n)]\!]=1 \), luego \( [\![\exists x\psi(\check x_1,\ldots, \check x_n)]\!]=1 \), es decir, \( [\![\phi(\check x_1,\ldots, \check x_n)]\!]=1 \).

13 Enero, 2025, 06:45 pm
Respuesta #9

franma

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

Ahora está bien, aunque debería bastarte con probarlo para el negador y otro conector (el implicador o el disyuntor, por ejemplo) y uno de los cuantificadores.

Perfecto.

En cuanto a lo último, una vez lo tienes probado para fórmulas \( \Delta_0 \), si tienes una fórmula \( \phi(x_1,\ldots, x_n)\equiv \exists x\,\psi(x,x_1,\ldots, x_n) \) de tipo \( \Sigma_1 \) y se cumple \( \phi(x_1,\ldots, x_n) \), entonces tomamos un \( x \) que cumpla \( \psi(x,x_1,\ldots, x_n) \), por lo que ya has probado \( [\![\psi(\check x,\check x_1,\ldots, \check x_n)]\!]=1 \), luego \( [\![\exists x\psi(\check x_1,\ldots, \check x_n)]\!]=1 \), es decir, \( [\![\phi(\check x_1,\ldots, \check x_n)]\!]=1 \).

Entendido.



Aunque con toda esta discusión ya tenga arreglado el "problema" de los apuntes. Me quede pensando sobre como razonar en \( V^\mathbb{B} \), ya que tal vez se pueda hacer todo sin acudir a este lema (si no, no hay problema). A ver si lo que digo esta bien, tenemos el resultado que dice:

Si un secuente \( \Gamma(\vec{x})\vdash \phi(\vec{x}) \) es derivable en el sistema \( \mathsf{NK} \) (o \( \mathsf{LK} \)), entonces para todos \( \vec{u}\in V^\mathbb{B} \) se tiene:
\( V^\mathbb{B} \models \Gamma(\vec{u}) \Rightarrow \phi(\vec{u}) \)

Este resultado se prueba por inducción sobre la derivación (no escribí la prueba) pero daría igual usar fórmulas de \( \mathscr{L}_{\mathsf{ZF}} \) (lenguaje de ZF) que usar fórmulas de \( \mathscr{L}_{\mathsf{ZF}_{\check{V}}} \) (lenguaje de ZF + el predicado \( \cdot \in \check{V} \)), ¿no?. Al menos pensándolo en el aire no veo que cambiaría en la prueba (creo que lo único que precisamos es tener definido \( [\![ u\in\check{V}]\!] \)) ¿Hasta aquí bien?

Agrego: De hecho, lo único que cambia es que para la regla de \( = \)-elim precisamos usar la regla de Leibniz que vale también para el predicado \( \cdot\in \check{V} \) porque es un lema anterior. Así que si no me equivoco como digo más abajo, tenemos que \( V^\mathbb{B} \) se "porta bien" con razonamientos en \( \mathsf{ZF}_{\check{V}} \)
Creo que mi confusión nació de que al principio de la sección sobre interpretación de fórmulas se dice que se trabajará directamente en el lenguaje \( \mathscr{L}_{\mathsf{ZF}_{\check{V}}} \) y me había saltado eso por completo (así que todas las fórmulas en esa sección incluyen al nuevo predicado a no ser que se especifique lo contrario).


Además, cuando probamos que \( V^\mathbb{B} \models \phi \) para toda \( \phi \) axioma de \( \mathsf{ZF} \) en realidad lo hicimos para toda \( \phi \) axioma de \( \mathsf{ZF}_{\check{V}} \) (con los esquemas admitiendo fórmulas de \( \mathscr{L}_{\mathsf{ZF}_{\check{V}}} \))

¿Estas dos cosas juntas no nos permiten hacer razonamientos "de toda la vida" en \( \mathsf{ZF}_{\check{V}} \) y luego utilizar esas deducciones en el modelo booleano?
Porque en ese caso si sería inmediato que al ser \( On \) una fórmula \( \Delta_0 \) entonces:
\( \mathsf{ZF}_{\check{V}} \vdash (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
luego por corrección:
\( V^\mathbb{B} \models (\forall x\in \check{V})\ x\subseteq \check{V} \Rightarrow \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)
Pero como el antecedente es un teorema de \( V^\mathbb{B} \) tenemos que:
\( V^\mathbb{B} \models \forall x\in \check{V}(On(x) \Leftrightarrow On^{\check{V}}(x)) \)

¿Esto esta bien?

Saludos,
Franco.