Autor Tema: Definición del predicado de verdad.

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

04 Enero, 2025, 10:12 pm
Leído 945 veces

franma

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

Tengo una duda de los siguientes apuntes. Específicamente en la página 11 cuando se define el predicado de verdad. Ahí se dice que "esta definido por recursión bien fundada sobre el tamaño de \( f\in Form \)". Esta frase es la que no entiendo :-[ exactamente ¿cómo es esa "recursión"?

Dejo las definiciones necesarias aquí:
Spoiler
Las variables serán representadas por ordinales finitos, es decir, \( Var := \omega \), y adoptamos como notación de las variables \( {\tt x,\tt y,\tt z},... \). Ahora codificaremos las fórmulas construidas a partir de \( =,\in,\neg,\lor \) y \( \exists \) usando la codificación:
\( \begin{align*}
    \tt x \dot = \tt x' &:= (0,(\tt x,\tt x')) \\
    \tt x \dot\in \tt x' &:= (1,(\tt x,\tt x')) \\
    \dot\neg f &:= (2,f) \\
    f_1 \dot\lor f_2 &:= (3,(f_1,f_2)) \\
    (\dot\exists \tt{x}) f &:= (4,(\tt{x},f))
\end{align*} \)
(donde \( \dot{=},\dot{\in},\dot{\lor} \) y \( \dot{\exists} \) representan los símbolos internos).
El resto de construcciones se deducen por las leyes de De Morgan.

Consideramos la función \( \Phi : \mathfrak{P}(V_\omega) \to \mathfrak{P}(V_\omega) \) definida por:
\( \begin{align*}
    \Phi(X) := &\{0\} \times (Var\times Var)\ \cup \\
    & \{1\} \times (Var\times Var)\ \cup \\
    & \{2\} \times X\ \cup \\
    & \{3\}\times (X\times X)\ \cup \\
    & \{4\} \times (Var \times X)
\end{align*} \)

Definimos el conjunto \( Form \) de las fórmulas internas como el menor punto fijo de la función \( \Phi \):
$$Form := \bigcup_{n\in \omega} \Phi^n(\emptyset)$$
(donde \( \Phi^n(\emptyset) \) es el conjunto de fórmulas de altura \( \leq n \))

Se define la función de verdad \( Val_{(M,E)}:Form\to \mathfrak{P}(M^{Var}) \) por recursión bien fundada sobre el tamaño de \( f\in Form \), escribiendo:
\(     \begin{align*}
        Val_{(M,E)}(\tt x \dot{=} \tt y) &:= \{ \rho \in M^{Var} : \rho(\tt x) = \rho(\tt y) \} \\
        Val_{(M,E)}(\tt x \dot{\in} \tt y) &:= \{ \rho \in M^{Var} : E(\rho(\tt x),\rho(\tt y)) \} \\
        Val_{(M,E)}(\dot{\neg} f) &:= Val_{(M,E)}(f)^\complement \\
        Val_{(M,E)}(f_1 \dot{\lor} f_2) &:= Val_{(M,E)}(f_1) \cup Val_{(M,E)}(f_2) \\
        Val_{(M,E)}((\dot{\exists} \tt x) f) &:= \{\rho \in M^{Var} : (\exists a\in M)(\rho, \tt x \leftarrow a)\in Val_{(M,E)}(f) \}
    \end{align*} \)
[cerrar]

Saludos,
Franco.

04 Enero, 2025, 10:49 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Se puede entender de varias formas equivalentes. La más sencilla en este contexto creo que sería definir \( \mbox{Form}_N=\bigcup\limits_{n\leq N}\Phi^n(\emptyset) \) y considerar que estás definiendo aplicaciones \( \mbox{Val}_{(M, E)}^N: \mbox{Form}_N\longrightarrow \mathfrak P(M^{\rm Var}) \), de modo que defines \( \mbox{Val}_{(M, E)}^N \) suponiendo definidas las anteriores (y de modo que cada una extiende a las anteriores). Así aplicas el teorema de recursión usual para los números naturales.

Pero lo de "recursión bien fundada" sugiere otro enfoque equivalente:

Define en \( \rm Form \) la relación dada por \( f\,R\,g \) si y sólo si \( g = \lnot f \) o existe \( h\in \mbox{Form} \) tal que \( g = f\lor h \) o \( g = h\lor f \) o existe \( x\in \mbox{Var} \) tal que \( g = \exists x\,f \).

Equivalentemente, Observa que \( f\,R\,g \) si y sólo si implica que el mínimo \( n \) tal que \( f\in \Phi^n(\emptyset) \) es menor que el mínimo \( m \) tal que \( g\in \Phi^m(\emptyset) \). Visto así Teniendo esto en cuenta, es fácil concluir que se trata de una relación bien fundada en \( \mbox{Form} \).

Entonces \( \mbox{Val}_{(M, E)} \) puede verse como una función definida por recursión sobre \( R \). Por los pelos te basta con la versión débil que presentabas  aquí, porque se da la casualidad de que cada fórmula tiene a lo sumo una fórmula anterior excepto en el caso de \( f_1\lor f_2 \), que tiene dos fórmulas anteriores, pero en este caso, para definir \( \mbox{Val}_{(M, E)}(f_1\lor f_2) \) te basta suponer conocido el conjunto \( \{\mbox{Val}_{(M, E)}(f_1), \mbox{Val}_{(M, E)}(f_2)\} \), ya que sólo necesitas calcular su unión.

05 Enero, 2025, 07:10 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 :)

Se puede entender de varias formas equivalentes. La más sencilla en este contexto creo que sería definir \( \mbox{Form}_N=\bigcup\limits_{n\leq N}\Phi^n(\emptyset) \) y considerar que estás definiendo aplicaciones \( \mbox{Val}_{(M, E)}^N: \mbox{Form}_N\longrightarrow \mathfrak P(M^{\rm Var}) \), de modo que defines \( \mbox{Val}_{(M, E)}^N \) suponiendo definidas las anteriores (y de modo que cada una extiende a las anteriores). Así aplicas el teorema de recursión usual para los números naturales.

Bien, esto lo entiendo.

Define en \( \rm Form \) la relación dada por \( f\,R\,g \) si y sólo si \( g = \lnot f \) o existe \( h\in \mbox{Form} \) tal que \( g = f\lor h \) o \( g = h\lor f \) o existe \( x\in \mbox{Var} \) tal que \( g = \exists x\,f \).

Bien, esto me parece bastante intuitivo.

Equivalentemente, \( f\,R\,g \) si y sólo si el mínimo \( n \) tal que \( f\in \Phi^n(\emptyset) \) es menor que el mínimo \( m \) tal que \( g\in \Phi^m(\emptyset) \). Visto así es fácil concluir que se trata de una relación bien fundada en \( \mbox{Form} \).

Con esta equivalencia ya me pierdo un poco. Entiendo que si \( f R g \) entonces el mínimo \( n \) donde aparece \( f \) es menor que el de \( g \). Pero la vuelta no la veo. Otra cosa que no entiendo es como podemos estar tan seguros que todas las fórmulas tienen una sola fórmula anterior (menos el caso de la disyunción).

Entonces \( \mbox{Val}_{(M, E)} \) puede verse como una función definida por recursión sobre \( R \). Por los pelos te basta con la versión débil que presentabas  aquí, porque se da la casualidad de que cada fórmula tiene a lo sumo una fórmula anterior excepto en el caso de \( f_1\lor f_2 \), que tiene dos fórmulas anteriores, pero en este caso, para definir \( \mbox{Val}_{(M, E)}(f_1\lor f_2) \) te basta suponer conocido el conjunto \( \{\mbox{Val}_{(M, E)}(f_1), \mbox{Val}_{(M, E)}(f_2)\} \), ya que sólo necesitas calcular su unión.

Aquí lo que me cuesta ver es como estaría definida la \( F \) para lograr lo que queremos. No se como definirla :-[

Saludos,
Franco.

05 Enero, 2025, 10:40 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Con esta equivalencia ya me pierdo un poco. Entiendo que si \( f R g \) entonces el mínimo \( n \) donde aparece \( f \) es menor que el de \( g \). Pero la vuelta no la veo.

Ah, no, es que eso no es cierto. Disculpa. Eso define otra relación bien fundada que sirve también, pero es otra distinta. En cualquier caso, sí que es cierta la implicación que dices, y ésa basta para probar que la relación R está bien fundada.

Otra cosa que no entiendo es como podemos estar tan seguros que todas las fórmulas tienen una sola fórmula anterior (menos el caso de la disyunción).

Las fórmulas de tipo \( x=x' \) o \( x\in x' \) no tienen ninguna anterior (son minimales), una de la forma \( \lnot f \) tiene únicamente a \( f \) como fórmula anterior. Una de la forma \( f\lor g \) tiene dos anteriores, que son \( f \) y \( g \), mientras que una de la forma \( \exists x\,f \) tiene a \( f \) como única fórmula anterior, simplemente por la definición de R.

Entonces \( \mbox{Val}_{(M, E)} \) puede verse como una función definida por recursión sobre \( R \). Por los pelos te basta con la versión débil que presentabas  aquí, porque se da la casualidad de que cada fórmula tiene a lo sumo una fórmula anterior excepto en el caso de \( f_1\lor f_2 \), que tiene dos fórmulas anteriores, pero en este caso, para definir \( \mbox{Val}_{(M, E)}(f_1\lor f_2) \) te basta suponer conocido el conjunto \( \{\mbox{Val}_{(M, E)}(f_1), \mbox{Val}_{(M, E)}(f_2)\} \), ya que sólo necesitas calcular su unión.

Aquí lo que me cuesta ver es como estaría definida la \( F \) para lograr lo que queremos. No se como definirla :-[

Pues, mira, me acabo de dar cuenta de que las dos formas del teorema que discutimos en este hilo no son suficientemente generales para abarcar este caso. La forma más general sería definir

\( G(x)=F(x, G|_{R^{-1}(x)}) \),

y la validez del teorema de ese hilo se prueba sin más que el cambio obvio que te indicaba al final de la respuesta #1 en ese hilo.

Pero es necesario admitir al propio \( x \) como posible argumento en la definición de \( G(x) \), porque si no, a la hora de definir \( G \) sobre un elemento minimal, \( G|_{R^{-1}(x)} = \emptyset \) y no podemos usar \( x \) para definir \( G(x) \).

También serviría la forma más particular: \( G(x)=F(x,\{G(y)\mid y\,R\,x\}) \).

Voy a usar esta forma porque es la más próxima al enunciado que tú manejas, pero sería más natural usar la forma general.

Define \( F: V\longrightarrow V \) definiendo \( F(u) \) según los casos siguientes:

1) Si \( u = (x\dot =y, \emptyset) \), entonces \( F(u)=\{\rho\in M^{\rm Var}\mid \rho(x)=\rho(y)\} \).

2) Si \( u = (x\dot\in y, \emptyset) \), entonces \( F(u)=\{\rho\in M^{\rm Var}\mid \rho(x)\in \rho(y)\} \).

3) Si \( u = (\dot \lnot f, \{X\}) \), entonces \( F(u) = M^{\rm Var}\setminus X \).

4) Si \( u = (f\dot\lor g, X) \), entonces \( F(u) = \bigcup X \).

5) Si \( u = (\dot\exists x, f, \{X\}) \), entonces \( F(u) = \{\rho\in M^{\rm Var}\mid \exists a\in M(\rho x\leftarrow a)\in X\} \).

6) En cualquier otro caso \( F(u)=\emptyset \)

Pero estos tecnicismos no deberían importarte. Puedes aplicar el teorema de recursión simplemente porque la definición que has dado en el spoiler te dice cómo definir \( \mbox{Val}_{M, E}(f) \) supuesto que ya has definido \( \mbox{Val}_{M, E}(g) \) para toda fórmula \( g\,R\,f \). Convertir esa definición en una función \( F \) (que tiene que admitir a \( x \) como argumento) es pura rutina.

06 Enero, 2025, 12:58 am
Respuesta #4

franma

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

Ah, no, es que eso no es cierto. Disculpa. Eso define otra relación bien fundada que sirve también, pero es otra distinta. En cualquier caso, sí que es cierta la implicación que dices, y ésa basta para probar que la relación R está bien fundada.

Bien, me quedo con esa primera relación entonces.

Las fórmulas de tipo \( x=x' \) o \( x\in x' \) no tienen ninguna anterior (son minimales), una de la forma \( \lnot f \) tiene únicamente a \( f \) como fórmula anterior. Una de la forma \( f\lor g \) tiene dos anteriores, que son \( f \) y \( g \), mientras que una de la forma \( \exists x\,f \) tiene a \( f \) como única fórmula anterior, simplemente por la definición de R.

De acuerdo. Yo lo estaba pensando con la relación del "mínimo \( n \) donde aparece \( f \)" y no me salía. No sé si valdra tambien para esa.

Pues, mira, me acabo de dar cuenta de que las dos formas del teorema que discutimos en este hilo no son suficientemente generales para abarcar este caso. La forma más general sería definir

\( G(x)=F(x, G|_{R^{-1}(x)}) \),

y la validez del teorema de ese hilo se prueba sin más que el cambio obvio que te indicaba al final de la respuesta #1 en ese hilo.

De acuerdo.

Pero es necesario admitir al propio \( x \) como posible argumento en la definición de \( G(x) \), porque si no, a la hora de definir \( G \) sobre un elemento minimal, \( G|_{R^{-1}(x)} = \emptyset \) y no podemos usar \( x \) para definir \( G(x) \).

Si, tienes razón.

También serviría la forma más particular: \( G(x)=F(x,\{G(y)\mid y\,R\,x\}) \).

Voy a usar esta forma porque es la más próxima al enunciado que tú manejas, pero sería más natural usar la forma general.

Define \( F: V\longrightarrow V \) definiendo \( F(u) \) según los casos siguientes:

1) Si \( u = (x\dot =y, \emptyset) \), entonces \( F(u)=\{\rho\in M^{\rm Var}\mid \rho(x)=\rho(y)\} \).

2) Si \( u = (x\dot\in y, \emptyset) \), entonces \( F(u)=\{\rho\in M^{\rm Var}\mid \rho(x)\in \rho(y)\} \).

3) Si \( u = (\dot \lnot f, \{X\}) \), entonces \( F(u) = M^{\rm Var}\setminus X \).

4) Si \( u = (f\dot\lor g, X) \), entonces \( F(u) = \bigcup X \).

5) Si \( u = (\dot\exists x, f, \{X\}) \), entonces \( F(u) = \{\rho\in M^{\rm Var}\mid \exists a\in M(\rho x\leftarrow a)\in X\} \).

6) En cualquier otro caso \( F(u)=\emptyset \)

Pero estos tecnicismos no deberían importarte. Puedes aplicar el teorema de recursión simplemente porque la definición que has dado en el spoiler te dice cómo definir \( \mbox{Val}_{M, E}(f) \) supuesto que ya has definido \( \mbox{Val}_{M, E}(g) \) para toda fórmula \( g\,R\,f \). Convertir esa definición en una función \( F \) (que tiene que admitir a \( x \) como argumento) es pura rutina.

Muchas gracias por detallarlo. Y estoy de acuerdo que esto son tecnisismos y realmente no aportan demasiado, pero ahora que estoy estudiando (para el examen) me gusta saber que si es necesario se detallarlos, y justo aquí estaba un poco perdido.

Aprovecho para hacer una pregunta bastante relacionada, una vez que tenemos esta definición por R-recursión tambien podemos hacer pruebas sobre las formulas internas con \( R \)-inducción, ¿no? Y por como elegimos la relación \( R \) es "básicamente" lo mismo que la inducción para fórmulas externas, ¿no?
Pregunto porque en la página 12 se enuncia un lema y supuse que la prueba se hace utilizando esta inducción lo cual es bastante sencillo de hacer.

Gracias nuevamente.

Saludos,
Franco.

06 Enero, 2025, 01:57 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De acuerdo. Yo lo estaba pensando con la relación del "mínimo \( n \) donde aparece \( f \)" y no me salía. No sé si valdra tambien para esa.

No, para ésa no vale, pero es irrelevante. Sólo te comentaba eso de que cada fórmula tiene a lo sumo dos anteriores porque eso permitía usar la versión débil del teorema de recursión (salvo que es necesario añadir la \( x \) como argumento, según hemos visto), pero, por lo demás, ese hecho es irrelevante.

Por otro lado, insisto en que también puedes usar la relación \( R' \) definida como \( f\,R' g \) si y sólo si el mínimo \( m \) tal que \( f\in \Phi^m(\emptyset) \) es menor que el mínimo \( m \) tal que \( g\in \Phi^m(\emptyset) \).

También está bien fundada y se cumple \( f\,R\,g\rightarrow f\,R'\,g \).

Una definición por recursión respecto a \( R' \) (o un razonamiento por inducción) puede ser más cómodo o más fácil porque te permite suponer que la función \( G \) está definida (o que la hipótesis de inducción se cumple) no sólo para las fórmulas que forman una fórmula \( f \) (que son a lo sumo una o dos), sino para todas las fórmulas que aparecen en los conjuntos  \( \Phi^n(\emptyset) \) anteriores al primero en que aparece \( f \).

Pero si usas recursión respecto a \( R' \), ahí si que ya no tendrías más remedio que usar la forma general del teorema de recursión, con \( G(x)=F(x, G|_{R^{-1}(x)}) \).

Aprovecho para hacer una pregunta bastante relacionada, una vez que tenemos esta definición por R-recursión tambien podemos hacer pruebas sobre las formulas internas con \( R \)-inducción, ¿no? Y por como elegimos la relación \( R \) es "básicamente" lo mismo que la inducción para fórmulas externas, ¿no?

Sí, aunque también puedes plantear a inducción respecto a fórmulas externas de formas ligeramente distintas. Puedes suponer la hipótesis de inducción para las subfórmulas que componen una fórmula dada (lo que equivale a usar la relación \( R \)) o para todas las fórmulas con menos conectores lógicos/cuantificadores (lo que equivale a la relación \( R' \)), o bien para todas las fórmulas de longitud menor (que correspondería a una relación \( R'' \) que habría que definir adecuadamente), y aún habría alguna posibilidad más.

07 Enero, 2025, 06:59 am
Respuesta #6

franma

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

No, para ésa no vale, pero es irrelevante. Sólo te comentaba eso de que cada fórmula tiene a lo sumo dos anteriores porque eso permitía usar la versión débil del teorema de recursión (salvo que es necesario añadir la \( x \) como argumento, según hemos visto), pero, por lo demás, ese hecho es irrelevante.

De acuerdo.

Por otro lado, insisto en que también puedes usar la relación \( R' \) definida como \( f\,R' g \) si y sólo si el mínimo \( m \) tal que \( f\in \Phi^m(\emptyset) \) es menor que el mínimo \( m \) tal que \( g\in \Phi^m(\emptyset) \).

También está bien fundada y se cumple \( f\,R\,g\rightarrow f\,R'\,g \).

Esta bien, aunque (no sé realmente porqué) prefiero la otra relación.

Una definición por recursión respecto a \( R' \) (o un razonamiento por inducción) puede ser más cómodo o más fácil porque te permite suponer que la función \( G \) está definida (o que la hipótesis de inducción se cumple) no sólo para las fórmulas que forman una fórmula \( f \) (que son a lo sumo una o dos), sino para todas las fórmulas que aparecen en los conjuntos  \( \Phi^n(\emptyset) \) anteriores al primero en que aparece \( f \).

Pero si usas recursión respecto a \( R' \), ahí si que ya no tendrías más remedio que usar la forma general del teorema de recursión, con \( G(x)=F(x, G|_{R^{-1}(x)}) \).

Bien, de acuerdo.

Sí, aunque también puedes plantear a inducción respecto a fórmulas externas de formas ligeramente distintas. Puedes suponer la hipótesis de inducción para las subfórmulas que componen una fórmula dada (lo que equivale a usar la relación \( R \)) o para todas las fórmulas con menos conectores lógicos/cuantificadores (lo que equivale a la relación \( R' \)), o bien para todas las fórmulas de longitud menor (que correspondería a una relación \( R'' \) que habría que definir adecuadamente), y aún habría alguna posibilidad más.

Perfecto, de hecho me surgió una duda (tal vez un poco tonta) con respecto a la prueba de ese lema, mi duda es sobre el enunciado para la inducción: debe ser este
\( \psi(f) :\equiv (\forall \rho,\rho' \in M^{Var})(\rho|_{FV(f)} = \rho'|_{FV({\color{red}f})} \Rightarrow (\rho\in Val_{(M,E)}(f) \Leftrightarrow \rho'\in Val_{(M,E)}(f))) \)
¿no?

Corregido.

Saludos,
Franco.

07 Enero, 2025, 10:16 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Perfecto, de hecho me surgió una duda (tal vez un poco tonta) con respecto a la prueba de ese lema, mi duda es sobre el enunciado para la inducción: debe ser este
\( \psi(f) :\equiv (\forall \rho,\rho' \in M^{Var})(\rho|_{FV(f)} = \rho'|_{FV(f')} \Rightarrow (\rho\in Val_{(M,E)}(f) \Leftrightarrow \rho'\in Val_{(M,E)}(f))) \)
¿no?

Sí, eso es (salvo que has puesto una \( f' \) que en realidad es una \( f \)).

07 Enero, 2025, 10:04 pm
Respuesta #8

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Perfecto, de hecho me surgió una duda (tal vez un poco tonta) con respecto a la prueba de ese lema, mi duda es sobre el enunciado para la inducción: debe ser este
\( \psi(f) :\equiv (\forall \rho,\rho' \in M^{Var})(\rho|_{FV(f)} = \rho'|_{FV(f')} \Rightarrow (\rho\in Val_{(M,E)}(f) \Leftrightarrow \rho'\in Val_{(M,E)}(f))) \)
¿no?

Sí, eso es (salvo que has puesto una \( f' \) que en realidad es una \( f \)).

Perfecto, muchas gracias. Ya lo corregí.

Saludos,
Franco.