Autor Tema: Regla de equiv. entre términos idénticos (Lógica matemática de Carlos Ivorra)

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

05 Septiembre, 2021, 02:01 pm
Leído 3083 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, tengo algunas dudas relacionadas con la regla de equivalencia entre términos idénticos expuesta en el libro Lógica matemática de Carlos Ivorra (página 70), más concretamente con la sustitución empleada en la demostración de dicha regla.

En el pie de nota está escrito que las equivalencias se cumplen si en el caso de existir variables auxiliares en las sustituciones, se toman acordes en ambos miembros de las identidades (como ya se había comentado en la nota de la página 34), por lo que antes de plantear la duda sobre la regla en sí, quiero ver que entiendo bien lo que significa esto.

Entiendo que cuando tenemos una expresión de la forma \( S_x^t \theta \) nos referimos a cualquier expresión calculada mediante la definición de sustitución, pero en la que no exigimos que las posibles variables auxiliares \( x_j \) se tomen con índice mínimo, si no que pueden tomarse elecciones arbitrarias (siempre que respeten las condiciones de, por ejemplo si \( \theta \equiv \forall x_i \alpha \) en el caso en que \( x \) está libre en \( \theta \) y \( x_i \) está libre en \( t \), entonces la variable auxiliar no puede estar ni en \( \theta \) ni en \( t \)).

Al tener esta ambigüedad, entiendo que en cualquier demostración que se haga sobre sustituciones, como por ejemplo las del Teorema 1.13, tenemos que asegurarnos que son ciertas al elegir una variable auxiliar arbitraria en el caso correspondiente, ¿verdad?

Más aún, está ambigüedad también obliga a establecer que cuando se establezca una identidad entre sustituciones, esta se dará siempre que se tomen las variables auxiliares de forma arbitraria también, pero consistentes en ambos miembros de la identidad.

Para entender esto, he probado las identidades que se proponen en la demostración de la regla ETI, en general he probado lo siguiente:

Si \( y \) no está en \( \theta \), entonces \( S_y^t S_x^y \theta \equiv S_x^t \theta \).

La demostración la he hecho por inducción, y en el caso en el que \( \theta \equiv \forall x_i \alpha \) siendo \( x \) libre en \( \theta \) y \( x_i \) libre en \( t \) obtengo lo siguiente:

\( S_y^t s_x^y \theta \equiv \forall z S_y^t S_{x_i}^z S_x^y \alpha \)

siendo \( z \) una variable que no está en \( \forall x_i S_x^y \alpha \) ni en \( t \); y

\( S_x^t \theta \equiv \forall w S_x^t S_{x_i}^w \alpha \)

siendo \( w \) una variable que no está en \( \forall x_i \alpha \) ni en \( t \).

Entonces, si he entendido correctamente, probar en este contexto que \( S_y^t s_x^y \theta \equiv S_x^t \theta \) significa probar que para cualquier variable \( u \) que no está en \( \forall x_i \alpha \), ni en \( \forall x_i S_x^y \alpha \), ni en \( t \) se cumple que

\( \forall u S_y^t S_{x_i}^u S_x^y \alpha \equiv \forall u S_x^t S_{x_i}^u \alpha \)

¿Es esto lo que significa que las variables auxiliares se tomen de forma consistente en ambos miembros de la identidad?

Ahora, respecto a la duda sobre la regla ETI en particular, es la siguiente.

En la regla, se hace uso de este último resultado, por ejemplo en la primera de ellas se toma como premisa directamente \( S_y^{t_2}S_x^y \alpha \) suponiendo que es la misma expresión que \( S_x^{t_2} \alpha \), pero mi duda es que por lo que he dicho anteriormente, si partimos de \( S_x^{t_2} \alpha \), en la sustitución hemos necesitado tomar variables auxiliares (supongamos que \( \alpha \equiv \forall x_i \beta \)) y la que hemos tomado está precisamente en \( \forall x_i S_x^y \beta \), entonces no podemos decir que las dos expresiones sean iguales, ¿no?.

Supongo que esto en la práctica no supone ningún problema pues, siempre podemos tomar las variables de forma que esto no suceda pero, ¿podría arreglarse de alguna forma para que, aunque suceda, la regla siga siendo cierta?

Un saludo y muchas gracias por las respuestas.

05 Septiembre, 2021, 04:56 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Empezando por el final:

¿podría arreglarse de alguna forma para que, aunque suceda, la regla siga siendo cierta?

Es que la regla es cierta siempre. La definición de sustitución requiere en ocasiones introducir variables auxiliares y en ella se elige una con un criterio arbitrario, pero cualquier otra serviría igual. El hecho fundamental es que si en una fórmula sustituyes una variable ligada por otra distinta que no aparezca en ella, el resultado es una fórmula equivalente. Por eso, en cualquier caso es cierto que \( S_x^{t_2}\alpha \leftrightarrow S_y^{t_2}S_x^y\alpha \) es un teorema lógico, y lo mismo con las demás identidades, y la prueba de la regla se puede adaptar sustituyendo cada fórmula cuando conviene por su equivalente aunque no sea exactamente la misma.

En lugar de esforzarte por encontrar condiciones para que se den las identidades, es mejor que veas que las identidades no son necesarias en absoluto. Por ejemplo, en la primera prueba, toma como hipótesis \( S_x^{t_2}\alpha \) y luego usa (pruébalo) que eso es equivalente a \( S_y^{t_2}S_x^y\alpha \) (no necesariamente idéntico, pero siempre equivalente), por lo que puedes escribir como segunda línea lo que en la prueba está como primera línea, y a partir de ahí vale todo igual.

La nota al pie está porque alguien me señaló en una ocasión que las identidades no tenían por qué ser ciertas debido que la elección de las variables auxiliares podría hacer que hubiera diferencias, pero detallar los cambios en la prueba que eso requería me hubiera obligado a alterar un tanto la estructura del capítulo, y no me pareció que mereciera la pena por un mero tecnicismo, por lo que me limité a añadir la nota para que el detalle no pasara inadvertido.

05 Septiembre, 2021, 07:18 pm
Respuesta #2

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, gracias por la respuesta.

Justo había pensado en probar esa equivalencia mientras le daba vueltas esta mañana, pero he estado intentándolo un buen rato y no veo como hacerlo. Siempre llego a un punto en el que parece que deba usar justo la regla ETI.
Y, para el segundo caso con términos en lugar de fórmulas, no se ni por donde empezar ya que en los axiomas de \( K_\mathcal{L} \) no aparecen sustituciones en términos.

¿Podrías darme alguna pista de como avanzar un poco en cada caso?

Pd. De todas formas, aunque para este caso concreto sea mejor simplemente probar las equivalencias que propones, ¿las sustituciones e identidades entre estas hay que entenderlas como puse en el primer post, o he entendido alguna cosa mal?

Un saludo.

05 Septiembre, 2021, 09:12 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Veamos, me temo que te he llevado en mala dirección con mi mensaje anterior. Empecemos por aquí:

Pd. De todas formas, aunque para este caso concreto sea mejor simplemente probar las equivalencias que propones, ¿las sustituciones e identidades entre estas hay que entenderlas como puse en el primer post, o he entendido alguna cosa mal?

Pon que vas a calcular \( S_y^{t_2}S_x^y\alpha \). Como la variable \( y \) no está en \( \alpha \), la sustitución \( S_x^y\alpha \) se limita a cambiar cada \( x \) libre por una \( y \), sin más alteraciones. Si ahora calculas \( S_x^{t_2}\alpha \), es posible que alguna variable libre en \( t_2 \) esté ligada en \( S_x^y\alpha \) y haya que cambiar la por otra. Según la definición de sustitución la cambias por la mínima variable posible, pero ésta podría no ser la variable que elegirías si calculas \( S_x^{t_2}\alpha \). Lo que digo es que si en lugar de elegir "la variable que toca" en cada caso eliges la misma en los dos casos, por ejemplo, eliges siempre la mínima variable que no esté en \( \alpha, t, t_1, t_2, y \), entonces obtendrás una identidad y toda la prueba de la regla vale tal cual.

Al tener esta ambigüedad, entiendo que en cualquier demostración que se haga sobre sustituciones, como por ejemplo las del Teorema 1.13, tenemos que asegurarnos que son ciertas al elegir una variable auxiliar arbitraria en el caso correspondiente, ¿verdad?

No sé si te entiendo. Las identidades del teorema 1.13 serán ciertas si calculas las sustituciones con el mismo criterio. Por ejemplo, te vale el de elegir la mínima variable posible. Pero si usas criterios distintos, puedes obtener fórmulas lógicamente equivalentes, pero no idénticas.

Más aún, está ambigüedad también obliga a establecer que cuando se establezca una identidad entre sustituciones, esta se dará siempre que se tomen las variables auxiliares de forma arbitraria también, pero consistentes en ambos miembros de la identidad.

Es que rara vez vas a necesitar establecer identidades entre sustituciones. La equivalencia lógica es más que suficiente. Salvo situaciones muy peculiares, es irrelevante si dos fórmulas son o no idénticas. Lo único que importa, como máximo, es si son lógicamente equivalentes.

¿Es esto lo que significa que las variables auxiliares se tomen de forma consistente en ambos miembros de la identidad?

Significa lo que he explicado al principio de este mensaje. No sé si queda claro.

Ahora vamos al grueso del asunto:

Sucede que si en una fórmula cambias unas variables ligadas por otras (sin que las nuevas coincidan con otras variables libres) obtienes una fórmula equivalente. Probar eso es algo farragoso y yo evité meterme en eso en mi libro porque pensé que no me hacía falta. En particular, en la definición de sustitución opté por fijar un criterio arbitrario para elegir las variables adicionales —a decir verdad, seguí el criterio de Mosterín—, lo cual es peligroso, porque pensé que no afectaba en nada y simplificaba las cosas. Y casi acerté, porque parece que el único punto donde eso da problemas es en la prueba de la regla ETI, no recuerdo ahora mismo si se da otro caso en el libro. Cuango alguien me señaló el problema opté por la solución más simple (cosa que no tenía en la cabeza al escribir el mensaje anterior, y por eso digo que te he llevado en mala dirección).

La solución más simple es admitir sustituciones en las que las variables que es necesario introducir puedan ser arbitrarias, siempre que cumplan las condiciones que realmente son necesarias, es decir, sólo se trata de cambiar "la variable de mínimo índice tal que..." por "cualquier variable que..." en la definición. Y, para no alterar sustancialmente la estructura de los primeros capítulos, expliqué el cambio en la nota de la página 34 que mencionas e introduje la nota al pie en la prueba de ETI. Si hubiera escrito el libro teniendo en cuenta este cambio, habría presentado la sustitución de forma distinta, sin hacer tanto énfasis en un criterio de elección en concreto, y posiblemente habría añadido explicaciones sobre el uso de las sustituciones en las que la diferencia de criterio fuera relevante, pero así están las cosas.

El caso es que lo que no tenía yo en la cabeza al escribir el mensaje anterior es que en realidad no hay problema alguno, no hay nada que demostrar, si admitimos que los axiomas lógicos se definen admitiendo sustituciones con cualquier criterio para elegir las variables adicionales, es decir, considerando que, por ejemplo, cualquier fórmula que siga el esquema K4 es un axioma cualesquiera que sean las variables adicionales que se hayan usado para calcular la sustitución, si es que se ha dado el caso.

Si lo entendemos así, y esto es un convenio totalmente satisfactorio desde un punto de vista teórico (los axiomas así definidos son igualmente manejables que si sólo admitimos sustituciones con un criterio fijo), entonces no hay problema.

Si tomamos todas esas fórmulas como axiomas, entonces la demostración de la regla ETI vale tal cual, sin necesidad de modificar nada en ella, sin más que elegir adecuadamente el modo en que se calculan las sustituciones. Los usos de II que aparecen en ella (que son esencialmente usos del axioma K6) son válidos tal cual porque K6 incluye las fórmulas calculadas con sustituciones cualesquiera.

Lo que te decía de probar la equivalencia de las sustituciones realizadas con criterios distintos sólo es necesario si consideramos que los axiomas sólo incluyen las sustituciones con un criterio fijo, pues entonces cualquier otra sustitución tiene que reducirse a "la de verdad", pero si no, ya está.

En resumen: ¿Ves que considerar que los axiomas incluyen fórmulas con sustituciones arbitrarias resuelve el problema o sigues viendo alguna dificultad?

Si ves alguna dificultad, la podemos discutir. Si ves que funciona, pero le has tomado cariño a los axiomas con la sustitución restringida, deberías plantearte que en realidad no es una buena elección. Estaba claro que era una elección arriesgada introducir un criterio arbitrario (no "lógico") en la definición de los axiomas lógicos, un riesgo que acepté porque creí que me permitía llegar hasta el teorema de completitud (luego ya todo da igual, pues fórmulas semánticamente equivalentes son lógicamente equivalentes y todo es trivial) sin necesidad de meterme en el fárrago de probar las equivalencias entre fórmulas que se diferencian sólo en sus variables ligadas, pero me equivoqué por la prueba de ETI.

Lo sensato —a mi juicio— ante este tropiezo anunciado (introducir arbitrariedades suele salir caro) no es emperrarse en seguir el criterio a toda costa (cosa que es posible, pero muy farragoso) sino eliminar la arbitrariedad en la definición de los axiomas lógicos que nunca habría tenido que estar ahí.

Justo había pensado en probar esa equivalencia mientras le daba vueltas esta mañana, pero he estado intentándolo un buen rato y no veo como hacerlo. Siempre llego a un punto en el que parece que deba usar justo la regla ETI.
Y, para el segundo caso con términos en lugar de fórmulas, no se ni por donde empezar ya que en los axiomas de \( K_\mathcal{L} \) no aparecen sustituciones en términos.

¿Podrías darme alguna pista de como avanzar un poco en cada caso?

Pues si quieres nos ponemos a ello, pero antes de meterme, preferiría saber si realmente estás interesado o prefieres ensanchar los axiomas.

05 Septiembre, 2021, 10:10 pm
Respuesta #4

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos.

Al tener esta ambigüedad, entiendo que en cualquier demostración que se haga sobre sustituciones, como por ejemplo las del Teorema 1.13, tenemos que asegurarnos que son ciertas al elegir una variable auxiliar arbitraria en el caso correspondiente, ¿verdad?

No sé si te entiendo. Las identidades del teorema 1.13 serán ciertas si calculas las sustituciones con el mismo criterio. Por ejemplo, te vale el de elegir la mínima variable posible. Pero si usas criterios distintos, puedes obtener fórmulas lógicamente equivalentes, pero no idénticas.

Aquí me refería a lo siguiente. Admitamos que \( S_x^t \theta \) no es una expresión fijada por el criterio arbitrario que se marca en la definición, sino que representa cualquier expresión que se calcule por las reglas dadas para las sustituciones, pero tal que si es necesario introducir variables auxiliares estas puedan ser arbitrarias (cumpliendo lo que deben claro) y no las de mínimo índice. Entonces al probar, por ejemplo el Teorema 1.13 c), tenemos que tener en cuenta que \( S_x^t \theta \) aun para un \( \theta \) concreto puede no ser una expresión fija, luego en la prueba debe reflejarse que si es necesario añadir una variable auxiliar, esta puede ser arbitraria y todo funciona igual para cubrir todas las posibles expresiones que puede ser \( S_x^t \theta \). Es como lo que comentas tras la demostración del Teorema 1.12 sobre que realmente la variable auxiliar que se toma podría ser cualquiera y no la de mínimo índice necesariamente.

¿Es esto lo que significa que las variables auxiliares se tomen de forma consistente en ambos miembros de la identidad?

Significa lo que he explicado al principio de este mensaje. No sé si queda claro.

Creo que si que me ha quedado claro, y creo que si es lo mismo que yo estaba diciendo antes.

Lo que quería decir en el primer mensaje es lo siguiente.

Cuando me puse a la tarea de demostrar que "Si \( y \) no está en \( \theta \) entonces \( S_y^t S_x^y \theta \equiv S_x^t \theta \)", como ya has comentado al principio del mensaje anterior, esta identidad no tiene porque ser cierta bajo el criterio de "tomar las variables auxiliares con el mínimo índice", pero si bajo el criterio de tomar las variables de forma consistente en ambos miembros de la identidad.

Por eso, lo que quería decir en mi primer mensaje es que, en la demostración por inducción del hecho anterior, cuando llego al caso en que \( \theta \equiv \forall x_i \alpha \) siendo \( x \) libre en \( \theta \) y \( x_i \) libre en \( t \) (es decir, el caso donde se introducen variables auxiliares), el cálculo para \( S_y^t s_x^y \theta \) es

\( S_y^t s_x^y \theta \equiv \forall z S_y^t S_{x_i}^z S_x^y \alpha \)

donde (como hemos tomado el criterio de que \( S_y^t s_x^y \theta \) representa cualquier expresión siguiendo las reglas pero con variables auxiliares arbitrarias) \( z \) es una variable que no está en \( \forall x_i S_x^y \alpha \) ni en \( t \).

Por otra parte, el cálculo de \( S_x^t \theta \) es

\( S_x^t \theta \equiv \forall w S_x^t S_{x_i}^w \alpha \)

donde de nuevo, \( w \) es una variable cualquiera que no está en \( \forall x_i \alpha \) ni en \( t \).

Por tanto, para probar que la identidad es cierta en este caso, entendiendo que elegimos las variables de forma consistente en ambos miembros de la identidad, es ver que si \( u \) es cualquier variable tal que no está en \( \forall x_i S_x^y \alpha \), ni en \( \forall x_i \alpha \), ni en \( t \), entonces se cumple que

\( \forall u S_y^t S_{x_i}^u S_x^y \alpha \equiv \forall u S_x^t S_{x_i}^u \alpha \)

¿Me he explicado ahora mejor?

En resumen: ¿Ves que considerar que los axiomas incluyen fórmulas con sustituciones arbitrarias resuelve el problema o sigues viendo alguna dificultad?

Pues, creo que si entiendo lo que dices. Lo que te refieres, creo, es que partimos de las premisas \( t_1=t_2 \) y \( S_x^{t_2} \alpha \), y queremos deducir \( S_x^{t_1} \alpha \). Entonces, fijamos antes de nada el criterio de a que expresión en concreto vamos a llamar a \( S_x^{t_1} \alpha \) y \( S_x^{t_2} \alpha \), y las tomamos de modo que en caso de precisar el uso de variables auxiliares, se cumplan igualmente las identidades descritas al comienzo de la prueba. Y a partir de ahí, pues ya todo tal cual está escrito en el libro.

Si no te refieres a esto, y me estás diciendo que independientemente de como sean estas expresiones (aunque las identidades no se den como identidades reales) aun se puede hacer la prueba tan solo aumentando los axiomas, entonces no te lo he entendido :/

Justo había pensado en probar esa equivalencia mientras le daba vueltas esta mañana, pero he estado intentándolo un buen rato y no veo como hacerlo. Siempre llego a un punto en el que parece que deba usar justo la regla ETI.
Y, para el segundo caso con términos en lugar de fórmulas, no se ni por donde empezar ya que en los axiomas de \( K_\mathcal{L} \) no aparecen sustituciones en términos.

¿Podrías darme alguna pista de como avanzar un poco en cada caso?

Pues si quieres nos ponemos a ello, pero antes de meterme, preferiría saber si realmente estás interesado o prefieres ensanchar los axiomas.

Pues la verdad si que estoy interesado. Me gustaría tener completo el punto de vista de fijar una definición precisa (aunque arbitraria) de las sustituciones y ver que podemos llegar al mismo sitio. Porque, por lo que entiendo de lo que me has comentado, después de conseguir probar ETI por este camino ya no es necesaria ninguna prueba más de este estilo para las sustituciones hasta llegar al teorema que nos muestre que toda fórmula lógicamente valida es un teorema lógico, y ya todo sea más sencillo, ¿no?

Un saludo y como siempre, te estoy muy agradecido por todo lo que aprendo de ti.

06 Septiembre, 2021, 12:18 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Aquí me refería a lo siguiente. Admitamos que \( S_x^t \theta \) no es una expresión fijada por el criterio arbitrario que se marca en la definición, sino que representa cualquier expresión que se calcule por las reglas dadas para las sustituciones, pero tal que si es necesario introducir variables auxiliares estas puedan ser arbitrarias (cumpliendo lo que deben claro) y no las de mínimo índice. Entonces al probar, por ejemplo el Teorema 1.13 c), tenemos que tener en cuenta que \( S_x^t \theta \) aun para un \( \theta \) concreto puede no ser una expresión fija, luego en la prueba debe reflejarse que si es necesario añadir una variable auxiliar, esta puede ser arbitraria y todo funciona igual para cubrir todas las posibles expresiones que puede ser \( S_x^t \theta \). Es como lo que comentas tras la demostración del Teorema 1.12 sobre que realmente la variable auxiliar que se toma podría ser cualquiera y no la de mínimo índice necesariamente.

Sí, pero es que si no fijamos un criterio para la introducción de var¡ables auxiliares, el hecho de que el teorema 1.12 dé identidades no tiene gran valor y costaría más precisar cómo deben ajustarse unas sustituciones a otras para obtener identidades que probar que las fórmulas obtenidas son equivalentes (y los términos demostrablemente iguales).

Por tanto, para probar que la identidad es cierta en este caso, entendiendo que elegimos las variables de forma consistente en ambos miembros de la identidad, es ver que si \( u \) es cualquier variable tal que no está en \( \forall x_i S_x^y \alpha \), ni en \( \forall x_i \alpha \), ni en \( t \), entonces se cumple que

\( \forall u S_y^t S_{x_i}^u S_x^y \alpha \equiv \forall u S_x^t S_{x_i}^u \alpha \)

¿Me he explicado ahora mejor?

El problema que veo es que si \( S_x^t \) puede suponer cualquier criterio para la elección de variables auxiliares, la identidad que escribes estará sujeta a que \( S_x^t \) se calcule "coherentemente", pues no sabes en cuántos sitios dentro de \( \alpha \) habrá hecho falta introducir variables nuevas para no ligar variables libres de \( t \). Por eso no veo que lo que propones concrete nada.

No lo he pensado con detalle, pero creo que para garantizar la identidad bastaría el criterio que te he dicho antes: realizar las sustituciones eligiendo en cada momento, no la menor variable que valga para la sustitución que estás calculando, sino la menor variable distinta de todas las que aparecen en \( \alpha, t, t_1, t_2, y \). El único problema real es que en ciertas sustituciones \( y \) pueda servir como variable auxiliar y en otras no, lo que haga que los criterios no cuadren.

Pues, creo que si entiendo lo que dices. Lo que te refieres, creo, es que partimos de las premisas \( t_1=t_2 \) y \( S_x^{t_2} \alpha \), y queremos deducir \( S_x^{t_1} \alpha \). Entonces, fijamos antes de nada el criterio de a que expresión en concreto vamos a llamar a \( S_x^{t_1} \alpha \) y \( S_x^{t_2} \alpha \), y las tomamos de modo que en caso de precisar el uso de variables auxiliares, se cumplan igualmente las identidades descritas al comienzo de la prueba. Y a partir de ahí, pues ya todo tal cual está escrito en el libro.

Si no te refieres a esto, y me estás diciendo que independientemente de como sean estas expresiones (aunque las identidades no se den como identidades reales) aun se puede hacer la prueba tan solo aumentando los axiomas, entonces no te lo he entendido :/

Sí, me refiero a eso, y creo que para garantizar las identidades basta seguir el criterio que te digo: introducir en cada caso la menor variable distinta de todas las que aparecen en \( \alpha, t, t_1, t_2, y \), aunque algunas de estas expresiones no intervengan en la sustitución concreta que estés calculando.

Pues la verdad si que estoy interesado. Me gustaría tener completo el punto de vista de fijar una definición precisa (aunque arbitraria) de las sustituciones y ver que podemos llegar al mismo sitio. Porque, por lo que entiendo de lo que me has comentado, después de conseguir probar ETI por este camino ya no es necesaria ninguna prueba más de este estilo para las sustituciones hasta llegar al teorema que nos muestre que toda fórmula lógicamente valida es un teorema lógico, y ya todo sea más sencillo, ¿no?

Si puede hacer falta alguna más no sabría decirte ahora mismo. Lo que estamos discutiendo son cosas muy técnicas, y no sabría decirte si hay otro punto similar.

El teorema de completitud te asegura que si dos fórmulas son verdaderas en los mismos modelos entonces son lógicamente equivalentes, por lo que ya es trivial que si dos fórmulas se diferencian sólo en sus variables ligadas, entonces son lógicamente equivalentes y no hay ninguna necesidad de preocuparse de qué variable hay en cada sitio.

Bien, pensaré cómo desarrollar lo necesario para probar ETI con las sustituciones definidas con un criterio fijo, pero eso será largo y ahora es tarde. Mañana no sé si podré ponerme a ello. En cuanto tenga un rato me ocupo.

06 Septiembre, 2021, 10:37 am
Respuesta #6

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos.

Aquí me refería a lo siguiente. Admitamos que \( S_x^t \theta \) no es una expresión fijada por el criterio arbitrario que se marca en la definición, sino que representa cualquier expresión que se calcule por las reglas dadas para las sustituciones, pero tal que si es necesario introducir variables auxiliares estas puedan ser arbitrarias (cumpliendo lo que deben claro) y no las de mínimo índice. Entonces al probar, por ejemplo el Teorema 1.13 c), tenemos que tener en cuenta que \( S_x^t \theta \) aun para un \( \theta \) concreto puede no ser una expresión fija, luego en la prueba debe reflejarse que si es necesario añadir una variable auxiliar, esta puede ser arbitraria y todo funciona igual para cubrir todas las posibles expresiones que puede ser \( S_x^t \theta \). Es como lo que comentas tras la demostración del Teorema 1.12 sobre que realmente la variable auxiliar que se toma podría ser cualquiera y no la de mínimo índice necesariamente.

Sí, pero es que si no fijamos un criterio para la introducción de var¡ables auxiliares, el hecho de que el teorema 1.12 dé identidades no tiene gran valor y costaría más precisar cómo deben ajustarse unas sustituciones a otras para obtener identidades que probar que las fórmulas obtenidas son equivalentes (y los términos demostrablemente iguales).

Vale, creo que por fin he entendido a que te referías en el libro con poder utilizar un criterio arbitrario para las variables auxiliares.

Te refieres que, antes de comenzar a calcular con sustituciones, fijamos un criterio para las variables auxiliares y entonces trabajamos con ese criterio, y ya demostramos lo que deseemos demostrar, sabiendo que estamos siguiendo dicho criterio. ¿He entendido ya bien los matices a los que te estabas refiriendo?

Por tanto, para probar que la identidad es cierta en este caso, entendiendo que elegimos las variables de forma consistente en ambos miembros de la identidad, es ver que si \( u \) es cualquier variable tal que no está en \( \forall x_i S_x^y \alpha \), ni en \( \forall x_i \alpha \), ni en \( t \), entonces se cumple que

\( \forall u S_y^t S_{x_i}^u S_x^y \alpha \equiv \forall u S_x^t S_{x_i}^u \alpha \)

¿Me he explicado ahora mejor?

El problema que veo es que si \( S_x^t \) puede suponer cualquier criterio para la elección de variables auxiliares, la identidad que escribes estará sujeta a que \( S_x^t \) se calcule "coherentemente", pues no sabes en cuántos sitios dentro de \( \alpha \) habrá hecho falta introducir variables nuevas para no ligar variables libres de \( t \). Por eso no veo que lo que propones concrete nada.

Completamente de acuerdo, tienes toda la razón en eso. Lo había pensado, pero como tampoco había entendido del todo bien aún a lo que te referías al decir "criterio arbitrario para las variables auxiliares", estaba ofuscado en querer que lo que yo había pensado funcionara.

Si puede hacer falta alguna más no sabría decirte ahora mismo. Lo que estamos discutiendo son cosas muy técnicas, y no sabría decirte si hay otro punto similar.

Dada mi obsesión por tenerlo todo bien atado, seguro que si lo hay antes de llegar al teorema de completitud (y no es tan sumamente sutil que no me doy cuenta) lo encontraré :P

El teorema de completitud te asegura que si dos fórmulas son verdaderas en los mismos modelos entonces son lógicamente equivalentes, por lo que ya es trivial que si dos fórmulas se diferencian sólo en sus variables ligadas, entonces son lógicamente equivalentes y no hay ninguna necesidad de preocuparse de qué variable hay en cada sitio.

Claro, a eso me refería, que si tras probar ETI por este camino más largo, ya no aparece más nada parecido hasta llegar al teorema de completitud, entonces ya todo lo discutido irrelevante, pues probar que este tipo de equivalencias donde solamente cambiamos de nombre a las variables ligadas son lógicamente válidas es mucho más sencillo que probar que son teoremas lógicos.

Bien, pensaré cómo desarrollar lo necesario para probar ETI con las sustituciones definidas con un criterio fijo, pero eso será largo y ahora es tarde. Mañana no sé si podré ponerme a ello. En cuanto tenga un rato me ocupo.

Te lo agradezco muchísimo, y obviamente sin prisa ninguna, faltaría más.

Muchas gracias por toda la ayuda y un saludo.

06 Septiembre, 2021, 02:15 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Al final ha quedado muchísimo más simple de lo que esperaba.

Como el LaTeX del foro no entiende \multicolumn (que es lo que uso para hacer las rayas verticales), adjunto la prueba en pdf.

He cambiado el pdf para añadir la prueba para términos, que estaba sin arreglar.


06 Septiembre, 2021, 07:46 pm
Respuesta #8

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos.

Ciertamente, no ha quedado tan "monstruoso" como pensaba que quedaría cuando lo dijiste en las respuestas anteriores  ;D

Por curiosidad, ¿has conseguido obtener la deducción por práctica en estas cosas y e ir tanteando, o has seguido algún razonamiento que te ha llevado hasta la deducción?

Lo pregunto porque estuve dándole vueltas durante al menos un par de horas, y al verlo ahora parece "sencillo", pero no se si se me habría ocurrido  nunca :'(

Lo último, solo comentar de la prueba que adjuntas que creo que la variable \( y \) tampoco tiene que estar en \( t \) para poder aplicar el segundo teorema lógico en la línea 7 de la segunda parte de ETI, ¿no?

Un saludo y de nuevo, muchas gracias por toda la ayuda en esta pequeña odisea  ;)

06 Septiembre, 2021, 10:25 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ciertamente, no ha quedado tan "monstruoso" como pensaba que quedaría cuando lo dijiste en las respuestas anteriores  ;D

Por curiosidad, ¿has conseguido obtener la deducción por práctica en estas cosas y e ir tanteando, o has seguido algún razonamiento que te ha llevado hasta la deducción?

Pues la idea que yo tenía inicialmente era probarlo por inducción sobre la longitud de una expresión, pero al llegar al caso del cuantificador caía en un círculo vicioso, y al tratar de resolverlo me di cuenta de que lo que necesitaba para ello (la línea (14) de la primera demostración) en realidad resolvía el problema sin inducción ni nada y, por otra parte, es una fórmula donde no está el problema del término \( t \) con la variable \( x \) libre que molesta, por lo que no tendría que haber problema en demostrarla de forma "relativamente natural", y así era.

Lo pregunto porque estuve dándole vueltas durante al menos un par de horas, y al verlo ahora parece "sencillo", pero no se si se me habría ocurrido  nunca :'(

Pues el camino fue ése: intenté probarlo por inducción, y quedaba larguísimo, pero al llegar al caso del cuantificador vi que necesitaba (14) para que me cuadrara todo, y de ahí vi que (14) implicaba de hecho (19). Luego, probar (14) ya era algo más o menos rutinario.

Lo último, solo comentar de la prueba que adjuntas que creo que la variable \( y \) tampoco tiene que estar en \( t \) para poder aplicar el segundo teorema lógico en la línea 7 de la segunda parte de ETI, ¿no?

Ah, sí, por supuesto, a la variable \( y \) no la tiene que conocer ni su madre. Si falta decir que no está en algún sitio, hay que añadirlo.

Los mensajes anteriores los he leído esta mañana con prisas, porque estamos en septiembre y tenía que hacer cosas de esas que tiene uno que hacer para que le paguen un sueldo a fin de mes. Supongo que algunas cosas ahora ya han quedado desfasadas, pero si hay algo pendiente recuérdamelo.