Autor Tema: Teorema 2.14 en "Lógica matemática" de Carlos Ivorra

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

10 Septiembre, 2021, 01:57 pm
Leído 2208 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, en la página 104 del libro Lógica matemática de Carlos Ivorra se enuncia un teorema (Teorema 2.14) que se deja como ejercicio al lector.

He conseguido demostrar (al menos creo que lo he hecho...) todas los teorema lógicos que se exponen salvo el de la segunda línea, es decir,

\( \vdash (\alpha \rightarrow \exists x \beta) \leftrightarrow \exists x (\alpha \leftrightarrow \beta) \) si \( x \) no está libre en \( \alpha \)

Si he conseguido demostrar la implicación de derecha a izquierda, pero no veo como hacer la otra implicación. ¿Alguna idea?

Un saludo y muchas gracias por las respuestas.

10 Septiembre, 2021, 02:21 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He conseguido demostrar (al menos creo que lo he hecho...) todas los teorema lógicos que se exponen salvo el de la segunda línea, es decir,

\( \vdash (\alpha \rightarrow \exists x \beta) \leftrightarrow \exists x (\alpha {\color{red}\rightarrow} \beta) \) si \( x \) no está libre en \( \alpha \)

Si he conseguido demostrar la implicación de derecha a izquierda, pero no veo como hacer la otra implicación. ¿Alguna idea?

Te he marcado en rojo una errata de tu mensaje. ¿Qué problema has encontrado?

Supones \( \alpha \rightarrow \exists x \beta \)

Luego supones \( \alpha \)

Obtienes \( \exists x \beta \) por MP

Pasas a \( \beta \) por EP  (observa que, como \( x \) no está libre en \( \alpha \), no tenemos prohibido generalizar respecto de \( x \), por lo que podemos usarla para eliminar el particularizador).

Pasas a \( \alpha\rightarrow \beta \) por el teorema de deducción.

Pasas a \( \exists x(\alpha\rightarrow \beta) \) por IP.

Y ya lo tienes.

10 Septiembre, 2021, 03:27 pm
Respuesta #2

Eparoh

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

Te he marcado en rojo una errata de tu mensaje. ¿Qué problema has encontrado?

Si, eso ha sido una errata.

Supones \( \alpha \rightarrow \exists x \beta \)

Luego supones \( \alpha \)

Obtienes \( \exists x \beta \) por MP

Pasas a \( \beta \) por EP  (observa que, como \( x \) no está libre en \( \alpha \), no tenemos prohibido generalizar respecto de \( x \), por lo que podemos usarla para eliminar el particularizador).

Pasas a \( \alpha\rightarrow \beta \) por el teorema de deducción.

Pasas a \( \exists x(\alpha\rightarrow \beta) \) por IP.

Y ya lo tienes.

Pensé en algo de ese estilo pero le veo algo raro.

Estamos eliminando el particularizador dentro del alcance de la suposición de \( \alpha \), pero no concluyes en una fórmula que no tenga libre a \( x \) antes de aplicar el teorema de deducción, por tanto, la línea \( \alpha \rightarrow \beta \) no veo como se deduce del teorema de deducción.

Quiero decir, por lo que pones, no veo que sea cierto que \( \alpha \rightarrow \exists \beta, \alpha \vdash \beta \) para poder aplicar el teorema de deducción, pues \( \beta \) es algo que has introducido "artificialmente", ¿no?

Un saludo y gracias.

EDITADO: La fórmula en rojo la había escrito mal.

10 Septiembre, 2021, 04:06 pm
Respuesta #3

Carlos Ivorra

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

\( \alpha\rightarrow \exists x\beta, \alpha, \beta\rightarrow \beta \)

y no generalizamos respecto de nada, luego el teorema de deducción nos permite concluir que

\( \alpha\rightarrow \exists x\beta, \beta \vdash \alpha\rightarrow \beta \)

luego, usando IP, tenemos también que

\( \alpha\rightarrow \exists x\beta, \beta \vdash \exists x(\alpha\rightarrow \beta) \)

Además, en esta deducción no se generaliza respecto de variables libres en \( \beta \) y la conclusión no tiene libre la variable \( x \), luego la regla ED nos permite concluir que

\( \alpha\rightarrow \exists x\beta \vdash \exists x(\alpha\rightarrow \beta) \)

Y en la deducción no se generaliza respecto a variables libres en \( \alpha \) (sólo se generaliza respecto de \( x \)), luego puedes aplicar el teorema de deducción para concluir que

\(  \vdash (\alpha\rightarrow \exists x\beta)\rightarrow \exists x(\alpha\rightarrow \beta) \)

Pero en la práctica, sólo tienes que tener presente que cuando elimines un particularizador la variable que dejes tiene que ser una variable respecto a la que esté permitido generalizar. Si es así, puedes seguir razonando normalmente, (sin generalizar respecto de variables libres en la fórmula que has dejado) aplicando el teorema de deducción siempre que quieras y, si al final llegas a una fórmula en la que no esté libre ninguna variable de la fórmula que has dejado al eliminar el particularizador, la deducción será correcta.

10 Septiembre, 2021, 04:35 pm
Respuesta #4

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, gracias por responder tan rápido pero esta vez no he entendido lo que me quieres decir  :'(

Entiendo que esto es cierto: \( \alpha\rightarrow \exists x\beta, \beta \vdash \exists x(\alpha\rightarrow \beta) \)

Pero, lo que no entiendo es como puedes aplicar EP a partir de este razonamiento pues, para poder aplicar EP, ¿una de tus líneas anteriores a \( \beta \) no tendría que ser también \( \exists x \beta \)?

Y en el razonamiento para ver que  \( \alpha\rightarrow \exists x\beta, \beta \vdash \exists x(\alpha\rightarrow \beta) \) es cierto, no veo como podría ser este el caso.

Un saludo.

10 Septiembre, 2021, 05:16 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tienes razón. Ahora voy con prisa y quiero pensarlo un poco más, porque algo se me escapa, pero una prueba sería así:

\( \alpha\rightarrow \exists x\,\beta,\alpha, \exists x\,\beta,\beta\vdash \beta \)

luego

\( \alpha\rightarrow \exists x\,\beta,\alpha, \exists x\,\beta,\beta\vdash \alpha\rightarrow \beta \)

donde podría quitar \( \alpha \) de la lista de premisas, pero la dejo, porque siempre puedo añadir una premisa aunque no haga falta. Por IP

\( \alpha\rightarrow \exists x\,\beta,\alpha, \exists x\,\beta,\beta\vdash \exists x(\alpha\rightarrow \beta) \)

Por EP

\( \alpha\rightarrow \exists x\,\beta,\alpha, \exists x\,\beta\vdash \exists x(\alpha\rightarrow \beta) \)

Pero la última premisa es redundante, luego

\( \alpha\rightarrow \exists x\,\beta, \alpha\vdash \exists x\,(\alpha\rightarrow \beta) \)

Por otro lado,

\( \alpha\rightarrow \exists x\,\beta, \lnot \alpha\vdash \alpha\rightarrow \beta \)

luego

\( \alpha\rightarrow \exists x\,\beta, \lnot \alpha\vdash \exists x(\alpha\rightarrow \beta) \)

Y usando \( \alpha\lor \lnot\alpha \) podemos concluir

\( \alpha\rightarrow \exists x\,\beta\vdash \exists x(\alpha\rightarrow \beta) \)

Esto prueba que el resultado es cierto, pero quiero pensar más sobre esto.

10 Septiembre, 2021, 06:35 pm
Respuesta #6

Eparoh

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

Mientras piensas más sobre ello como comentas, he escrito la prueba que has dado en lo que creo que sería la versión en forma de deducción. La adjunto en pdf.

Un saludo y muchas gracias como siempre.

Pd. Con la raya punteada yo señalo el uso de EP, para recordarme de no generalizar, pero distinguirlo del teorema de deducción.

10 Septiembre, 2021, 08:34 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Mientras piensas más sobre ello como comentas, he escrito la prueba que has dado en lo que creo que sería la versión en forma de deducción. La adjunto en pdf.

Sí, en efecto, la prueba que adjuntas es la de mi último mensaje "pasada a limpio".

Lo que me mosqueaba es que yo habría dado por válida la demostración de mi primer mensaje, pero tienes razón en que no está justificada a partir de los resultados probados en mi libro. Pero que no esté justificada no significa que no sea justificable.

Supón que tenemos unas premisas \( \alpha_1,\ldots, \alpha_n \) y en una deducción a partir de ellas, en un momento suponemos \( \gamma \) para aplicar el teorema de deducción (y a partir de ahí no generalizamos respecto de variables libres en \( \gamma \)). Luego llegamos a \( \exists x\,\alpha \), más adelante eliminamos el particularizador con \( S_x^y\alpha \), donde \( y \) es una variable que no está libre en \( \gamma \) y a partir de ahí no generalizamos respecto de variables libres en \( S_x^y\alpha \), luego llegamos a una fórmula \( \beta \) que puede tener libre la variable \( y \), pero aplicamos sin complejos el teorema de deducción para concluir \( \gamma\rightarrow \beta \) y seguimos deduciendo hasta una fórmula \( \delta \) que no tiene libre la variable \( y \). Afirmo que \( \delta \) es consecuencia de las premisas.

Esto justifica la validez de la prueba de mi primer mensaje.

Para probarlo, observamos que las hipótesis son:

\( \alpha_1,\ldots, \alpha_n, \gamma\vdash \exists x\, \alpha \)

\( \alpha_1,\ldots, \alpha_n, \gamma, S_x^y\alpha\vdash \beta \)

\( \alpha_1,\ldots, \alpha_n, \gamma\rightarrow \beta\vdash \delta \)

Entonces, suponiendo  \( \alpha_1,\ldots, \alpha_n, \gamma \), podemos deducir \( \exists x\,\alpha \), luego aplicamos la forma demostrada de EP para introducir \( S_x^y\alpha \), lo que nos permite deducir \( \beta \), pero \( \beta\vdash \gamma\rightarrow \beta \) y esto nos permite deducir \( \delta \). Como \( \delta \) no tiene libre la variable \( y \), EP nos permite concluir que \( \alpha_1,\ldots, \alpha_n, \gamma \vdash \delta \). (Observa que aquí NO he aplicado el teorema de deducción a \( \gamma \), sino que \( \gamma \) permanece como premisa en todo momento.)

Por otro lado, como \( \lnot \gamma\vdash \gamma\rightarrow \beta \), también tenemos que \( \alpha_1,\ldots, \alpha_n, \lnot\gamma\vdash \delta \), y por consiguiente, por el tercio excluso, también \( \alpha_1,\ldots, \alpha_n\vdash \delta \).

Obviamente, puestos a probar lo que preguntabas, es más sencilla la otra demostración. Sólo pongo esto para ilustrar una vez más el principio de que si te encuentras una restricción técnica que no se corresponda con una objeción "conceptual", es decir, semántica, es que la restricción tiene que poder eliminarse. Lo que me mosqueaba era que no veía ninguna objeción conceptual a la primera prueba, y por eso quería encontrar la justificación de que la restricción era eliminable (sólo para "desmosquearme").

12 Septiembre, 2021, 05:22 pm
Respuesta #8

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, muy interesante esto último que comentas y que, por lo que veo, es principalmente generalizar la prueba anterior para unas fórmulas cualesquiera (cumpliendo las restricciones necesarias para que todo funcione, claro).

Como siempre, muy agradecido por todo lo que aprendo de ti  ;D

Un saludo.