Autor Tema: Demostración de un teorema (Carlos Ivorra)

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

29 Diciembre, 2011, 11:27 am
Respuesta #10

Dani

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • Karma: +0/-0
  • Sexo: Masculino
    • danielmbcn.wordpress.com

P.D: También he visto que en las demostraciones utilizas clausuras universales, pero no sé si me convence mucho (por aquello del teorema de la deducción y de generalizar sobre variables libres...).

No es cuestión de que te convenza o no te convenza, sino de si está bien o está mal. Dime un ejemplo concreto que no te convenza y razonaremos si es correcto o no.

Pues consideremos el mismo ejercicio que viene a continuación del teorema 3.12. Dice así:

Mostrar que el teorema anterior (el 3.12) es falso si \( \alpha \) es una sentencia. (Considerar, por ejemplo, \( \Gamma = \left\{{\bigvee xy \neg x = y}\right\}, \alpha \equiv{x = y} \))

Yo en su momento comprobé que efectivamente el teorema 3.12 es falso si tomamos por ejemplo esa \( \alpha \) en particular. Tú dices que podemos hacer IG a \( \alpha \) y transformarla en una sentencia, es decir, tomando \( \alpha \equiv{} \bigwedge xy (x = y) \), con lo que supuestamente tendríamos una teoría (de axiomas \( \Gamma \cup{\left\{{\alpha}\right\}} \)) equivalente a la original que propones en el ejercicio. Pero a mí esto me parece raro por dos motivos:

1) Si es una teoría equivalente, por qué la de tu ejercicio no satisface el teorema 3.12 y la segunda, que obtenemos tomando la clausura universal de \( \alpha \), sí lo satisface?

2) Para tomar la clausura universal de \( x=y \) generalizamos sobre dos variables libres, y de ahí ¿deducimos? la teoría equivalente que solo tiene sentencias. ¿Qué pasa aquí con el teorema de la deducción?

29 Diciembre, 2011, 12:49 pm
Respuesta #11

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues consideremos el mismo ejercicio que viene a continuación del teorema 3.12. Dice así:

Mostrar que el teorema anterior (el 3.12) es falso si \( \alpha \) es una sentencia. (Considerar, por ejemplo, \( \Gamma = \left\{{\bigvee xy \neg x = y}\right\}, \alpha \equiv{x = y} \))

Yo en su momento comprobé que efectivamente el teorema 3.12 es falso si tomamos por ejemplo esa \( \alpha \) en particular. Tú dices que podemos hacer IG a \( \alpha \) y transformarla en una sentencia, es decir, tomando \( \alpha \equiv{} \bigwedge xy (x = y) \), con lo que supuestamente tendríamos una teoría (de axiomas \( \Gamma \cup{\left\{{\alpha}\right\}} \)) equivalente a la original que propones en el ejercicio.

En efecto, digo que la teoría \( T_1 \) que tiene por axiomas \( \bigvee xy \neg x = y \) y \( x=y \) es equivalente a la teoría \( T_2 \) que tiene por axiomas \( \bigvee xy \neg x = y \) y \( \bigwedge xy (x = y) \), en el sentido de que ambas tienen los mismos teoremas, pero no sólo lo "digo", sino que te lo demuestro:

Supón que \( \alpha \) es un teorema de \( T_1 \). Entonces también es un teorema de \( T_2 \). Para probarlo basta tener en cuenta que una demostración de \( \alpha \) en \( T_1 \) no es más que una sucesión de fórmulas cada una de las cuales sea uno de los dos axiomas de \( T_1 \), o un axioma lógico, o una consecuencia inmediata de fórmulas anteriores. En principio, si aparece \( x=y \) entre los axiomas usados, no se trata de una demostración en \( T_2 \), porque esa fórmula no es un axioma de \( T_2 \), pero eso se puede arreglar. Razonando \( T_2 \) puedes escribir \( \bigwedge xy (x = y) \) (porque es un axioma), a continuación aplicar dos veces EG y ya tienes \( x=y \). A partir de ahí enlazas con la demostración de \( \alpha \) en \( T_1 \) y ya tienes una demostración de \( \alpha \) en \( T_2 \).

Recíprocamente, para convertir una demostración de \( \alpha \) en \( T_2 \) en una demostración en \( T_1 \), en el caso no trivial en que se use \( \bigwedge xy (x = y) \) como axioma, sólo tienes que empezar a razonar en \( T_1 \) escribiendo \( x=y \), aplicando dos veces IG para obtener \( \bigwedge xy (x = y) \), y a partir de ahí enlazar con la demostración en \( T_2 \).

Así pues, las dos teorías tienen exactamente los mismos teoremas. Eso es lo que afirmo y ésta es la demostración.

La prueba que te he dado se generaliza directamente a cualquier otro caso de sustitución de una o varias fórmulas por sus clausuras universales, aunque en este caso había un argumento más directo: probar que ambas teorías son contradictorias, con lo que tienen los mismos teoremas porque cualquier fórmula es un teorema de cualquiera de las dos.

Pero a mí esto me parece raro por dos motivos:

1) Si es una teoría equivalente, por qué la de tu ejercicio no satisface el teorema 3.12 y la segunda, que obtenemos tomando la clausura universal de \( \alpha \), sí lo satisface?

La teoría \( T_2 \) satisface el teorema 3.12 porque, por una parte, es contradictoria y, por otra parte, a partir de \( \Gamma \) (que es consistente) se puede demostrar \( \lnot\bigwedge xy (x = y)  \).

La teoría \( T_1 \) no satisface el teorema 3.12 porque, por una parte, es contradictoria pero, por otra parte, a partir de \( \Gamma \) no se puede demostrar \( \lnot(x=y) \).

¿Cuál es el problema? ¿Contradice esto en algo mi afirmación de que \( T_1 \) y \( T_2 \) tienen los mismos teoremas? Los tienen, porque ambas son contradictorias. En cambio la teoría \( T_0 \) cuyo único axioma es  \( \bigvee xy \neg x = y \) es consistente y sucede que \( \lnot\bigwedge xy (x = y)  \) es uno de sus teoremas mientras que \( \lnot(x=y) \) no lo es.

Lo que sucede en el fondo es que \( x=y \) significa lo mismo que \( \bigwedge xy (x = y)  \) (y por eso da igual tomar una u otra como axioma), mientras que \( \lnot(x=y) \) no significa lo mismo que \( \lnot\bigwedge xy (x = y)  \), por lo que no tiene nada de raro que la segunda sea un teorema de \( T_0 \) y la primera no.

2) Para tomar la clausura universal de \( x=y \) generalizamos sobre dos variables libres, y de ahí ¿deducimos? la teoría equivalente que solo tiene sentencias. ¿Qué pasa aquí con el teorema de la deducción?

Al principio del mensaje te he justificado la equivalencia entre ambas teorías. Como verás, no he usado en ningún momento el teorema de deducción, así que no hay ningún problema con él.

Creo que lo que te confunde es que no eres consciente de que la definición de deducción es la que és: "una deducción es una sucesión de fórmulas tales que cada una es un axioma, un axioma lógico o una consecuencia por MP o IG a partir de fórmulas anteriores", y no hay absolutamente ninguna restricción sobre el uso de IG. Y nada de lo que viene después modifica en nada esta definición original de deducción.

El teorema de deducción, al igual que otros teoremas que imponen restricciones al uso de IG, simplemente es un criterio que te asegura que si una deducción cumple unos criterios adicionales, a partir de ella es posible construir otra deducción de otra cosa, pero cuando usas el teorema de deducción para demostrar algo (cumpliendo obviamente sus restricciones), lo que te prueba el teorema de deducción es precisamente que existe una deducción (según la definición original, sin restricción alguna sobre IG) que te demuestra la conclusión que has obtenido.

Así pues, al razonar en teoría sobre qué se puede demostrar y qué no, puedes olvidarte por completo del teorema de deducción y de las restricciones que impone. Sólo has de preocuparte de él cuando analizas una demostración en concreto que lo use en un punto concreto. Si es así, tendrás que garantizar que su uso es correcto, comprobando que se cumplen las restricciones pertinentes sobre el uso de IG.