Autor Tema: Esquema de recursión primitiva para PROP

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

05 Abril, 2012, 06:41 am
Leído 5394 veces

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Primero que nada, voy a exponer un breve resumen de algunos conceptos y definiciones que se manejan en el libro Logic and Structure de Dirk van Dalen, para que todo el que lea este post sea capaz de entender la notación y saber cuál es concretamente mi duda. Si algo figura en inglés es porque lo he transcrito directamente del libro.

El lenguaje de la lógica proposicional se basa en un alfabeto que consiste de:

i) símbolos de proposición: \( p_0,\ p_1,\ p_2,\dots, \)
ii) conectivos: \( \wedge,\ \vee,\ \rightarrow,\ \lnot,\ \leftrightarrow,\ \bot, \)
iii) símbolos auxiliares: \( (\ ,\ ). \)

Definición 1
Se define el lenguaje de la lógica proposicional (\( \mbox{PROP} \)) como el menor conjunto \( X \) que satisface las siguientes reglas:

\( \begin{array}{ll} \mbox{ I } & p_i\in X(i\in \mathbb{N}),\ \bot\in X, \\ \mbox{ II }& \mbox{Si $\varphi,\psi\in X$, entonces (\varphi\wedge \psi),\ (\varphi\vee \psi),\ (\varphi\rightarrow \psi),\ (\varphi\leftrightarrow \psi)\in X$}\\ \mbox{ III }& \mbox{Si $\varphi \in X$, entonces $(\lnot \varphi)\in X$} \end{array} \)

Con la finalidad de simplificar la cláusula \( \mbox{II} \) se escribirá \( \varphi,\psi\in X\Rightarrow \varphi\square \psi\in X \) donde \( \square \) es uno de los conectivos \( \wedge,\ \vee,\ \rightarrow,\ \leftrightarrow \). A modo de ejemplo, \( (p_7\rightarrow p_0),\ ((\bot \vee p_{32})\wedge (\lnot p_2))\in \mbox{PROP} \) pero \( p_1\leftrightarrow p_7,\ \lnot\lnot\bot\not\in \mbox{PROP} \).

Como en toda definición inductiva, a partir de ella podemos inferir dos teoremas que son el principio de inducción primitiva y el esquema de recursión primitiva.

Principio de inducción primitiva

Sea \( A \) una propiedad. Luego, \( A(\varphi) \) es cierta para toda fórmula proposicional \( \varphi\in\mbox{PROP} \) si:

1) \( A(p_i) \) para todo \( i \), y \( A(\bot) \),
2) \( A(\varphi),\ A(\psi)\Rightarrow A((\varphi\square \psi)) \)
3) \( A(\varphi),\ A(\psi)\Rightarrow A((\lnot\varphi)) \)

Demostración
Sea \( X=\{\varphi\in \mbox{PROP}|A(\varphi)\} \). Luego \( X \) satisface \( \mbox{I} \), \( \mbox{II} \) y \( \mbox{III} \) de la definición 1. Por lo tanto, como \( \mbox{PROP} \) es el menor conjunto que cumple con las reglas, \( \mbox{PROP}\subseteq X \) y en consecuencia, para toda \( \varphi\in \mbox{PROP} \), \( A(\varphi) \) es verdadera.
[cerrar]

Esquema de recursión primitiva

Let mappings \( H_{\square}:B^2\rightarrow B \) and \( H_{\lnot}:B\rightarrow B \) be given and let \( H_{at} \) be a mapping from the set of atoms into \( B \), then there exists exactly one mapping \( F:\mbox{PROP}\rightarrow B \) such that

\( \left\{\begin{array}{lll}{ F(\varphi)}&=& \mbox{ $H_{at}(\varphi)$ for $\varphi$ atomic }\\F((\varphi\square\psi))} &=& \mbox{ $H_{\square}(F(\varphi), F(\psi))$ }\\F((\lnot\varphi))} &=& \mbox{ $H_{\lnot}(F(\varphi))$ } \end{array}\right. \)

Un ejemplo de aplicación puede ser el siguiente. Supongamos que queremos definir una función \( \mbox{brackets}:\mbox{PROP}\rightarrow \mathbb{N} \) que, dada una fórmula proposicional \( \varphi \), me devuelva la cantidad de paréntesis de dicha fórmula. La podemos definir recursivamente como:

\( \left\{\begin{array}{lll} \mbox{brackets}(\varphi)} &=& \mbox{$0$ for all $\varphi$ atomic}\\ \mbox{brackets}((\varphi\square\psi))} &=& \mbox{brackets}(\varphi)+\mbox{brackets}(\psi)+2 }\\\mbox{brackets}((\lnot\varphi))} &=& \mbox{brackets}(\varphi)+2 \end{array}\right. \)

Mi duda está en la demostración del esquema de recursión primitiva. El libro dice lo siguiente:

Demostración
The proof is left as an excersice for the reader. Hint:

(a) Give an inductive definition of the function \( F \), defined by recursion on \( \mbox{PROP} \) from the functions \( H_{at} \), \( H_{\square} \), \( H_{\lnot} \), as a set \( F^* \) of pairs.
(b) Formulate and prove for \( F^* \) the induction principle.
(c) Prove that \( F^* \) is indeed a function on \( \mbox{PROP} \).
(d) Prove that it is the unique function on \( \mbox{PROP} \) satisfying the recursion equations.
[cerrar]

Sé hacer el apartado (a) y el apartado (b) pero no me doy cuenta de cómo usar el principio de inducción para probar que es función. Agradezco cualquier ayuda.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Abril, 2012, 02:27 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Por lo que creo entender, en el apartado a) has demostrado la existencia de un conjunto \( F^*\subset \text{PROP}\times B \) de pares ordenados, y en el apartado c) quieres probar que es una función \( F=F^*: \text{PROP}\longrightarrow B \).

Esto significa que tienes que probar que si \( \phi\in \text{PROP} \) y \( b,b'\in B \) cumplen que \( (\phi,b),(\phi,b')\in F^* \), entonces \( b=b' \). Y se trata de razonarlo por inducción sobre \( \phi \), es decir, tomando como propiedad \( A(\phi) \) la dada por

\( \forall bb'\in B ((\phi,b)\in F^*\land (\phi, b')\in F^*\Rightarrow b=b') \).

Para continuar es necesario hacer referencia a la forma concreta en que hayas construido el conjunto \( F^* \) en el apartado a).

05 Abril, 2012, 04:04 pm
Respuesta #2

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Gracias Carlos.

Para continuar es necesario hacer referencia a la forma concreta en que hayas construido el conjunto \( F^* \) en el apartado a).

Yo había pensado en definir \( F^*\subset \mbox{PROP}\times B \) de la siguiente manera:

\( \begin{array}{ll} \mbox{ I } & \mbox{Si $\varphi=p_i$ o $\varphi=\bot$, entonces $(\varphi,H_{at}(\varphi))\in F^*$} \\ \mbox{ II }& \mbox{Si $(\varphi,b)\in F^*$ y $(\psi,b')\in F^*$, entonces $((\varphi\square \psi),H_{\square}(b,b'))\in F^*$}\\ \mbox{ III }& \mbox{Si $(\varphi,b) \in F^*$, entonces $((\lnot \varphi),H_{\lnot}(b))\in F^*$} \end{array} \)

¿Está bien así? Porque si tengo mal la definición del conjunto, también tendré mal el principio de inducción que se pide en el apartado (b). Con lo que has dicho, me quedó claro la propiedad que hay que probar. Es porque una función \( f:A\rightarrow B \) se puede ver como una relación \( f^*\subset A\times B \) donde cada elemento \( a\in A \) aparece una y sólo una vez como primer componente de un par ordenado. Por lo tanto, si \( (a,b)\in f^* \) y \( (a,b')\in f^* \) han de ser el mismo par, o sea que \( b=b' \).

Gracias de nuevo.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Abril, 2012, 04:17 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tu definición es correcta, en el sentido de que determina correctamente el conjunto \( F^* \) y a partir de ella no deberías tener dificultades para probar que F es una función. Sólo hay un punto que me resulta confuso, y es que en las instrucciones del libro dice que definas F "by recursion on PROP". Lo que no sé es qué principio de recursión estás suponiendo exactamente, pero no insinúo con ello que haya nada que no cuadre en tu planteamiento. Sólo digo que no acabo de hacerme una idea del enfoque que está siguiendo tu libro.

05 Abril, 2012, 05:07 pm
Respuesta #4

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Sólo hay un punto que me resulta confuso, y es que en las instrucciones del libro dice que definas F "by recursion on PROP".

Creo que lo que dice en realidad es "dar una definición inductiva de la función \( F \) (la cual satisface la propiedad de estar definida por recursión sobre \( \mbox{PROP} \) a partir de las funciones \( H_{at} \), \( H_{\square} \) y \( H_{\lnot} \)), como un conjunto \( F^* \) de pares". Es decir, para mi lo que está entre paréntesis (en el texto original entre dos comas), es sólo una propiedad que cumple la función \( F \) pero no significa que debamos definirla por recursión; ya está definida así por hipótesis desde el momento que escribimos:

\( \left\{\begin{array}{lll}{ F(\varphi)}&=& \mbox{ $H_{at}(\varphi)$ for $\varphi$ atomic }\\F((\varphi\square\psi))} &=& \mbox{ $H_{\square}(F(\varphi), F(\psi))$ }\\F((\lnot\varphi))} &=& \mbox{ $H_{\lnot}(F(\varphi))$ } \end{array}\right. \)

Al menos ésa es mi interpretación.

Para el apartado (b):

Principio de inducción primitiva para \( F^* \)

Sea \( A \) una propiedad sobre los elementos de \( F^* \). Si se cumple:

\( \begin{array}{ll} \mbox{ i } & \mbox{$A(\varphi, H_{at}(\varphi))$ si $\varphi=p_i$ o $\varphi=\bot$} \\ \mbox{ ii }& \mbox{Si $A(\varphi,b)$ y $A(\psi,b')$, entonces $A((\varphi\square \psi),H_{\square}(b,b'))$}\\ \mbox{ iii }& \mbox{Si $A(\varphi,b)$, entonces $A((\lnot \varphi),H_{\lnot}(b))$} \end{array} \)

Entonces es cierto \( A(\varphi, b) \) para cualquier \( (\varphi, b)\in F^* \).

La demostración es un calco de la de mi primer post. Pero ahora me surge una duda. ¿Cuál sería la propiedad que hay que probar? Para usar el principio de inducción enunciado anteriormente tiene que ser una propiedad referida a un par \( (\varphi,{\red b})\in F^* \) pero lo lógico sería lo que has dicho tú antes:

Y se trata de razonarlo por inducción sobre \( \phi \), es decir, tomando como propiedad \( A(\phi) \) la dada por

\( \forall bb'\in B ((\phi,b)\in F^*\land (\phi, b')\in F^*\Rightarrow b=b') \).

Ahí estás tomando una propiedad que depende de un sólo parámetro que es \( \varphi \). En tal caso habría que usar, no el principio de inducción de \( F^* \) (que fue el que enuncié recién), sino el de \( \mbox{PROP} \) que está arriba de todo en este hilo. Pero si fuera así, no entiendo la necesidad de los apartados (a) y (b). ¿Para qué entonces definir el conjunto \( F^* \)?  :-\
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

05 Abril, 2012, 06:04 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La demostración es un calco de la de mi primer post. Pero ahora me surge una duda. ¿Cuál sería la propiedad que hay que probar? Para usar el principio de inducción enunciado anteriormente tiene que ser una propiedad referida a un par \( (\varphi,a)\in F^* \) pero lo lógico sería lo que has dicho tú antes:

Y se trata de razonarlo por inducción sobre \( \phi \), es decir, tomando como propiedad \( A(\phi) \) la dada por

\( \forall bb'\in B ((\phi,b)\in F^*\land (\phi, b')\in F^*\Rightarrow b=b') \).

Ahí estás tomando una propiedad que depende de un sólo parámetro que es \( \varphi \). En tal caso habría que usar, no el principio de inducción de \( F^* \) (que fue el que enuncié recién), sino el de \( \mbox{PROP} \) que está arriba de todo en este hilo.

Ah, es que yo no había hecho ningún caso al apartado b), pero teniéndolo en cuenta, la propiedad \( A(\phi,b) \) podría enunciarse así:

\( \forall b'\in B ((\phi,b')\in F^*\Rightarrow b=b') \).

Pero si fuera así, no entiendo la necesidad de los apartados (a) y (b). ¿Para qué entonces definir el conjunto \( F^* \)?  :-\

Yo tengo la sensación, desde tu primer hilo sobre este tema, cuando aclaraste que había técnicas que no valía usar, de que tu libro lo hace todo muchísimo más complicado de lo necesario. Mi impresión es que todos los principios de inducción y recursión que usas podrían reducirse trivialmente a los usuales para números naturales (razonando por inducción o recursión sobre la longitud de las fórmulas), pero como no conozco el propósito concreto del libro, ni si supone ciertas limitaciones por alguna razón técnica que en principio no sea evidente, no puedo decir nada al respecto con seguridad.

06 Abril, 2012, 12:53 am
Respuesta #6

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias Carlos. Voy a ver si lo paso en limpio.

Yo tengo la sensación, desde tu primer hilo sobre este tema, cuando aclaraste que había técnicas que no valía usar, de que tu libro lo hace todo muchísimo más complicado de lo necesario. Mi impresión es que todos los principios de inducción y recursión que usas podrían reducirse trivialmente a los usuales para números naturales (razonando por inducción o recursión sobre la longitud de las fórmulas), pero como no conozco el propósito concreto del libro, ni si supone ciertas limitaciones por alguna razón técnica que en principio no sea evidente, no puedo decir nada al respecto con seguridad.

La verdad que no tengo idea. No conozco otros libros de lógica como para comparar. Estudio de ahí porque es el libro del curso y los profesores se basan en él. Puede ser que esté un poco rebuscado, esta materia me está costando entenderla. Se me plantean mucho más dudas que en otras.

Volviendo al tema, ¿cómo se probaría la unicidad? Lo que vendría a ser el apartado (d).

Saludos, y muchas gracias.           
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

06 Abril, 2012, 12:58 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Volviendo al tema, ¿cómo se probaría la unicidad? Lo que vendría a ser el apartado (d).

Pues supones otra función G que cumpla las mismas condiciones de la definición recursiva de F y tienes que probar la fórmula \( A(\phi) \) dada por \( F(\phi)=G(\phi) \) para toda fórmula \( \phi \).

06 Abril, 2012, 07:47 am
Respuesta #8

pierrot

  • pabloN
  • Moderador Global
  • Mensajes: 3,447
  • País: uy
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, reúno todo lo dicho anteriormente en este post.

Esquema de recursión primitiva para \( \mbox{PROP} \)

Dado un conjunto \( B \) arbitrario y ciertas funciones \( H_{\square}:B^2\rightarrow B \), \( H_{\lnot}:B\rightarrow B \) y \( H_{at} \) que va del conjunto de átomos en \( B \), existe una única función \( F:\mbox{PROP}\rightarrow B \) tal que:

\( \left\{\begin{array}{lll}{ F(\varphi)}&=& \mbox{ $H_{at}(\varphi)$ si $\varphi=p_i$ o $\varphi=\bot$}\\F((\varphi\square\psi))} &=& \mbox{ $H_{\square}(F(\varphi), F(\psi))$ }\\F((\lnot\varphi))} &=& \mbox{ $H_{\lnot}(F(\varphi))$ } \end{array}\right. \)

Prueba
Existencia
Definamos el conjunto \( F^*\subset \text{PROP}\times B \) de pares ordenados como el menor conjunto que satisface con las reglas:

\( \begin{array}{ll} \mbox{ I } & \mbox{Si $\varphi=p_i$ o $\varphi=\bot$, entonces $(\varphi,H_{at}(\varphi))\in F^*$} \\ \mbox{ II }& \mbox{Si $(\varphi,b)\in F^*$ y $(\psi,b')\in F^*$, entonces $((\varphi\square \psi),H_{\square}(b,b'))\in F^*$}\\ \mbox{ III }& \mbox{Si $(\varphi,b) \in F^*$, entonces $((\lnot \varphi),H_{\lnot}(b))\in F^*$} \end{array} \)

Veamos ahora que este subconjunto del producto cartesiano \( \text{PROP}\times B \) es una función \( F=F^*:\text{PROP}\rightarrow B \). Para ello debemos mostrar que toda fórmula \( \varphi\in \text{PROP} \) aparece una y sólo una vez como primer componente de un par ordenado de \( F^* \). O dicho de otra manera, si \( \varphi\in \text{PROP} \) y \( b,b'\in B \) cumplen que \( (\varphi,b)\in F^* \) y \( (\varphi,b')\in F^* \) entonces \( b=b' \). La prueba la haré directamente por inducción sobre \( \varphi \) como sugeriste al principio porque me parece más fácil. Entonces la propiedad a probar estaría referida a los elementos de \( \text{PROP} \) y sería la siguiente \( A(\varphi):=\mbox{`` dados $b,b'\in B$, si $(\varphi,b)\in F^*$ y $(\varphi,b')\in F^*$ entonces $b=b'$ ''} \).

PASO BASE
Hay que probar que se cumple \( A(\varphi) \) para toda \( \varphi \) atómica. Supongamos que \( (\varphi,b)\in F^* \) y que \( (\varphi,b')\in F^* \). Como \( \varphi=p_i \) para algún \( i\in \mathbb{N} \), o \( \varphi=\bot \), por la regla \( \text{I} \) de construcción de \( F^* \) se tiene que \( b=H_{at}(\varphi) \) y que \( b'=H_{at}(\varphi) \). Como \( H_{at} \) es función, la imagen de \( \varphi \) por \( H_{at} \) es única y por lo tanto, \( b=b' \).

PASO INDUCTIVO 1
Supongamos que son ciertas \( A(\varphi) \) y \( A(\psi) \). Hay que probar \( A((\varphi\square \psi)) \), o sea, que si \( ((\varphi\square \psi),r)\in F^* \) y \( ((\varphi\square \psi),r')\in F^* \) entonces \( r=r' \). Por un lado sabemos que \( (\varphi,b_1)\in F^*\wedge (\varphi,b_2)\in F^* \) implica \( b_1=b_2=b \). Es decir, \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente. Por otra parte, sabemos que \( (\psi,b_1')\in F^*\wedge (\psi,b_2')\in F^* \) implica \( b_1'=b_2'=b' \). Es decir, \( (\psi,b') \) es el único par ordenado en \( F^* \) que tiene a \( \psi \) como primer componente. Por la regla \( \text{II} \) de construcción de \( F^* \), como \( (\varphi,b)\in F^* \) y \( (\psi,b')\in F^* \) sabemos que \( ((\varphi\square \psi),H_{\square}(b,b'))\in F^* \). Como \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente, y \( (\psi,b') \) es el único par ordenado en \( F^* \) que tiene a \( \psi \) como primer componente, todo par en \( F^* \) que tenga a \( (\varphi\square \psi) \) como primer componente, deberá tener a \( H_{\square}(b,b') \) como segunda componente. Por lo tanto, si \( ((\varphi\square \psi),r)\in F^* \) entonces \( r=H_{\square}(b,b') \). Análogamente, \( r'=H_{\square}(b,b') \). Finalmente, como \( H_{\square} \) es función, la imagen de \( (b,b') \) por \( H_{\square} \) es única y por lo tanto, \( r=r' \).

PASO INDUCTIVO 2
Supongamos que es cierta \( A(\varphi) \). Hay que probar \( A((\lnot \varphi)) \), o sea, que si \( ((\lnot \varphi),s)\in F^* \) y \( ((\lnot \varphi),s')\in F^* \) entonces \( s=s' \). Por hipótesis de inducción sabemos que \( (\varphi,b_1)\in F^*\wedge (\varphi,b_2)\in F^* \) implica \( b_1=b_2=b' \). Es decir, \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente. Por la regla \( \text{III} \) de construcción de \( F^* \), como \( (\varphi,b)\in F^* \) sabemos que \( ((\lnot \varphi),H_{\lnot}(b))\in F^* \). De nuevo, como \( (\varphi,b) \) es el único par ordenado en \( F^* \) que tiene a \( \varphi \) como primer componente, todo par en \( F^* \) que tenga a \( (\lnot \varphi) \) como primer componente, deberá tener a \( H_{\lnot}(b) \) como segunda componente. Por lo tanto, si \( ((\lnot \varphi),s)\in F^* \) entonces \( s=H_{\lnot}(b) \). Análogamente, \( s'=H_{\lnot}(b) \). Finalmente, como \( H_{\lnot} \) es función, la imagen de \( b \) por \( H_{\lnot} \) es única y por lo tanto, \( s=s' \).

Unicidad
Es inmediato a partir de ésto:
Pues supones otra función G que cumpla las mismas condiciones de la definición recursiva de F y tienes que probar la fórmula \( A(\phi) \) dada por \( F(\phi)=G(\phi) \) para toda fórmula \( \phi \).
Se trata de otra inducción en \( \text{PROP} \), mucho más directa que la anterior.
[cerrar]

Muchas gracias por tu ayuda, Carlos.

Saludos
$_="loe  hnachaPkr erttes,urJ";$j=0;for($i=0;s/(.)(.{$j})$//;$i++){$_=$2.$_,$j+=1-$i%2,print$1}print

06 Abril, 2012, 12:45 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Falta una cosa. De hecho, fui yo quien te lo dijo mal: para probar que \( F^* \) es una función tienes que demostrar lo que dices que hay que demostrar, que no es lo que demuestras (que es lo que yo te dije que tenías que demostrar). Me refiero a que falta probar que para cada \( \phi \) existe un \( b \) tal que \( (\phi,b)\in F^* \). Sólo has probado la unicidad, pero no la existencia.