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

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

16 Diciembre, 2011, 04:37 pm
Leído 4852 veces

Dani

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • Karma: +0/-0
  • Sexo: Masculino
    • danielmbcn.wordpress.com
Éste es el teorema 3.9 del libro Lógica y Teoría de Conjuntos de Carlos Ivorra, de la parte de Modelos. No viene la demostración, así que la he intentado yo (sin éxito, naturalmente).

Teorema: Sea \( M \) un modelo de un lenguaje formal \( \zeta \) y sea \( \Gamma \) una colección de fórmulas de \( \zeta \). Si \( M\models \Gamma \) y \( \Gamma \vdash \alpha \) entonces \( M \models \alpha \)

Demostración:

Sea \( \Gamma \) la colección de fórmulas \( \beta_1, ..., \beta_n \). Además, \( \beta_1, ..., \beta_n \vdash \alpha \) y \( M\models\beta_1, ..., \beta_n \). Por el teorema de la deducción tenemos \( \beta_1, ..., \beta_{n-1} \vdash \beta_n \rightarrow{\alpha} \). Aplicando el teorema de la deducción \( n \) veces llegamos a \( \vdash \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \)

\( M\models \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \) syss (\( M\models \beta_1 \) implica \(  M\models\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \). Como \( M\models \beta_1 \) es cierta, entonces \(  M\models\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...) \).

Repitiendo el mismo proceso \( n \) veces llegamos a \( M\models (\beta_n \rightarrow{\alpha} \)) syss \( M\models \beta_n \) implica \( M\models \alpha \).

Es decir, \( M\models \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \) syss (\( M\models \beta_n \) implica \( M\models \alpha \)).

Aquí es donde me encallo. Para que se cumpla la condición de la izquierda se ha de cumplir la de la derecha. Veamos la condición de la derecha: es claro que \( M \models \beta_n \), pero no veo evidente que \( M \models \alpha  \). Es decir, veo que \( \vdash \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \), pero no que \( M\models \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \).

¿Por qué es necesariamente cierto que \( M\models \alpha \)?

Edito: Ahora que lo pienso, no veo que tenga mucho sentido empezar a demostrar suponiendo \( M\models \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \). ¿Cómo puedo demostrar este teorema?

16 Diciembre, 2011, 08:29 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Considera una deducción de \( \alpha \) a partir de \( \Gamma \). Se trata de una sucesión finita de fórmulas \( \alpha_1,\ldots, \alpha_n \), cada una de las cuales, o bien es un axioma lógico (y ya sabemos entonces que es verdadero en \( M \)), o bien es una premisa (y entonces es verdadera en \( M \) por hipótesis) o bien es consecuencia inmediata de dos fórmulas precedentes, y sabemos que toda consecuencia lógica de fórmulas verdaderas en un modelo es verdadera en el modelo. Por inducción sobre \( i \) es claro entonces que cada \( \alpha_i \) es verdadera en \( M \) (es decir, supones que todas las fórmulas anteriores a la i-ésima son verdaderas en \( M \) y demuestras que lo mismo le sucede a \( \alpha_i \)). En particular, \( \alpha_n\equiv \alpha \) es verdadera en \( M \).

16 Diciembre, 2011, 08:39 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tal y como lo intentas tienes un problema técnico, y es que no puedes aplicar el teorema de deducción si la deducción de \( \alpha \) generaliza respecto de variables libres en alguna premisa. Eso se podría arreglar tomando clausuras universales de las premisas en el momento oportuno (o añadiendo como hipótesis que las premisas son sentencias). En tal caso, llegarías a que

\( \vdash \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \)

y eso implica

\( M\models \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \)

por el teorema de corrección: tienes un teorema lógico, luego es verdadero en cualquier modelo.

De ahí podrías llegar a que \( \alpha \) es verdadera en \( M \) aplicando \( n \) veces la definición de verdad en un modelo, concretamente la parte referente a las implicaciones. De todos modos, creo que es más sencillo el argumento que te propongo en el post anterior.


17 Diciembre, 2011, 09:56 am
Respuesta #3

Dani

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • Karma: +0/-0
  • Sexo: Masculino
    • danielmbcn.wordpress.com
Hola, Carlos. ¡Muchas gracias! Creo que mi principal error fue "olvidar" el teorema de la corrección, que dice que todos los teoremas lógicos son lógicamente válidos, esto es, verdaderos en cualquier modelo. Tenía \( \vdash \beta_1\rightarrow{}(\beta_2\rightarrow{}(...\rightarrow{}(\beta_{n-1}\rightarrow{}(\beta_n \rightarrow{\alpha}))...)) \) y también "olvidé" que esto también es un teorema lógico, de manera que es verdadero en M. Cumpliéndose esto y teniendo por hipótesis que \( M\models \beta_n \), entonces \( M\models\alpha \).

Y sí, definitivamente me quedo con tu primer argumento. No tuve en cuenta que el teorema de deducción también exige que en ningún momento de la deducción se puede generalizar respecto a variables libres de \( \alpha \). Lo de tomar clausuras universales de las premisas sobre la marcha, restringir la demostración solo para el caso en que las premisas son sentencias, y otros apaños, me suena un poco feo :P

Gracias por tu ayuda. Seguiré pregutando mis dudas por aquí :)

25 Diciembre, 2011, 02:00 pm
Respuesta #4

Dani

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • Karma: +0/-0
  • Sexo: Masculino
    • danielmbcn.wordpress.com
Esta vez propongo una demostración alternativa al teorema 4.4. No sé si algún paso está mal, pero de lo contrario me parecería una prueba mucho más simple y directa.

Teorema: Toda teoría axiomática consistente tiene una extensión consistente y completa.

Demostración:

Sea \( T \) una teoría axiomática consistente. Sea \( S \) una teoría axiomática con los mismos axiomas y los mismos signos que \( T \). Si \( T \) es una teoría completa, entonces ya hemos acabado la demostración; si no, entonces existe un \( \alpha_1 \) tal que no \( \Gamma \vdash \neg \alpha_1 \). Luego, por el teorema 3.12, \( \Gamma \cup{\left\{{\alpha_1}\right\}} \) es consistente. Sea ahora \( \Gamma \cup{\left\{{\alpha_1}\right\}} \) la colección de axiomas de la teoría \( S' \). Si \( S' \) es completa, ya hemos terminado la demostración. Si no, volvemos a repetir el mismo proceso hasta que, para toda fórmula \( \alpha_{n+1} \), \( \Gamma \cup{\left\{{\alpha_1, ... , \alpha_n}\right\}} \vdash \alpha_{n+1} \), de lo que se deducirá que la teoría \( S^{(n)} \) formada por los axiomas \( \Gamma \cup{\left\{{\alpha_1, ... , \alpha_n}\right\}} \) es una extensión de \( T \) consistente y completa.

¿Está bien?

Edito: En la demostración hago referencia al "teorema 3.12". Dicho teorema dice lo siguiente: Sea \( \Gamma \) una colección de fórmulas y \( \alpha \) una sentencia. Entonces \( \Gamma \cup{\left\{{\alpha}\right\}} \) es consistente si y solo si no \( \Gamma \vdash \neg \alpha \)

25 Diciembre, 2011, 03:39 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El problema es que no puedes garantizar que, tras un número finito de pasos, llegues a una teoría completa. Si la teoría de partida es, por ejemplo, la aritmética de Peano, sucede que una extensión consistente y completa no puede ser recursiva, es decir, no puede haber un criterio que permita determinar qué fórmulas son axiomas y cuáles no. En particular, no puede obtenerse añadiendo un número finito de axiomas a los axiomas de Peano.

Por ello hay que contemplar la posibilidad de necesitar infinitos pasos, y más concretamente es necesario asegurarse de que al repetir el proceso infinitas veces tenemos en cuenta todas las posibles sentencias, y por ello es necesario partir de una enumeración de todas ellas. Estas consideraciones son las que hacen que la prueba del teorema 4.4 sea necesariamente algo más complicada que la que propones, aunque tampoco mucho más.

26 Diciembre, 2011, 02:25 pm
Respuesta #6

Dani

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

Tuve un despiste importante. Creo que cuando en la demostración pensé que toda teoría consistente tiene un modelo numerable, ese "numerable" lo interpreté (vaya usted a saber por qué) como "de universo finito", y de ahí la suposición (incorrecta) que hice.

Pero aun así... ¿una teoría con infinitos axiomas? :o ¿Cómo se concibe eso?

26 Diciembre, 2011, 02:54 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero aun así... ¿una teoría con infinitos axiomas? :o ¿Cómo se concibe eso?

Eso es el pan de cada día. El sistema \( K_{\mathcal L} \) cuyos teoremas son los teoremas lógicos tiene infinitos axiomas. Por ejemplo, para cada par de fórmulas \( \alpha \) y \( \beta \), la fórmula \( \alpha\rightarrow (\beta\rightarrow \alpha) \) es un axioma lógico, y como hay infinitos pares de fórmulas posibles, tienes infinitos axiomas lógicos. (Es verdad que se puede formalizar la lógica con cero axiomas y unas cuantas reglas de inferencia, pero es frecuente tomar infinitos axiomas lógicos.)

La aritmética de Peano (de primer orden) tiene infinitos axiomas: para cada fórmula \( \phi(x) \), un axioma de la aritmética de Peano es

\( \phi(0)\land \forall n(\phi(n)\rightarrow \phi(n+1))\rightarrow \forall n\ \phi(n) \),

y esta vez no puedes evitar los infinitos axiomas (salvo que consideres una teoría de segundo orden).

La teoría de conjuntos de Zermelo-Fraenkel tiene también infinitos axiomas, pues el esquema axiomático del reemplazo es una familia de infinitos axiomas, uno para cada fórmula del lenguaje de la teoría de conjuntos.

Todos estos son ejemplos de sistemas axiomáticos recursivos, es decir, hay infinitos axiomas, pero es fácil saber si una fórmula dada es o no un axioma. Cuando intentas completar un sistema axiomático consistente, lo normal es que acabes con un sistema axiomático no recursivo: hay infinitos axiomas y no hay modo de saber si una fórmula dada es o no un axioma. Tienes un procedimiento que especifica qué fórmulas son axiomas y cuáles no, pero no es constructivo, porque para saber cuáles tomas y cuáles dejas necesitarías ser capaz de decidir si determinados conjuntos de fórmulas son consistentes o contradictorios, y no hay un algoritmo para ello.

28 Diciembre, 2011, 03:32 pm
Respuesta #8

Dani

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 120
  • Karma: +0/-0
  • Sexo: Masculino
    • danielmbcn.wordpress.com
Hay algo que me inquieta, Carlos. Y es que en muchos de los teoremas de tu libro (al menos hasta donde he llegado (al teorema 4.6)), siempre hablas de sentencias, y no de fórmulas. (Una sentencia es una expresión sin variables libres, ¿no?)

¿Significa esto que si, por ejemplo, trabajo en una teoría axiomática que, además de sentencias, contenga fórmulas entre sus axiomas o teoremas, todos los teoremas que he visto hasta ahora sobre completitud sintáctica (más el teorema 3.12 y los que se deduzcan de él) dejan de cumplirse? Eso me da un poco de miedo, pues entonces habría una infinidad de teorías axiomáticas (con fórmulas) que "escaparían" del "control" de los susodichos teoremas, y no estoy seguro de que sin esos teoremas pudiéramos afirmar algo con seguridad sobre esas teorías.
 
En el ejemplo que pones de la Geometría de Euclides, el que viene a continuación del teorema 3.12, aplicas el teorema 3.12 al quinto postulado. Es decir, tomas el postulado

Por un punto exterior a una recta, se puede trazar una única paralela a la recta dada

como una sentencia. Aquí me surgen dos dudas:

1) ¿Qué pasa si consideras otra teoría axiomática, también de interés matemático, cuyos axiomas sean fórmulas y no sentencias? ¿Ya no puedes aplicar todos esos teoremas?

2) En la misma Geometría de Euclides, ¿por qué tomas el quinto postulado como una sentencia? A mí me parece una fórmula: representemos los puntos por letras del alfabeto latino y las rectas por letras griegas:

\( \bigwedge \alpha(Ep\alpha \rightarrow{T\beta\alpha}) \)

Lo leo así: "para toda recta alpha, si un punto p es exterior (E) a alpha, entonces se puede trazar (T) una recta paralela beta a alpha".

Yo veo que es una fórmula porque hay variables libres ahí (\( p, \beta \)). ¿Por qué lo tomas como sentencia? ¿Quizá lo he formalizado mal? Y si es así... ¿podemos transformar fórmulas en sentencias siempre en todos los casos (aplicando IG o IP, por ejemplo)?

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...).

28 Diciembre, 2011, 04:36 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hay algo que me inquieta, Carlos. Y es que en muchos de los teoremas de tu libro (al menos hasta donde he llegado (al teorema 4.6)), siempre hablas de sentencias, y no de fórmulas. (Una sentencia es una expresión sin variables libres, ¿no?)

Sí.

¿Significa esto que si, por ejemplo, trabajo en una teoría axiomática que, además de sentencias, contenga fórmulas entre sus axiomas o teoremas, todos los teoremas que he visto hasta ahora sobre completitud sintáctica (más el teorema 3.12 y los que se deduzcan de él) dejan de cumplirse? Eso me da un poco de miedo, pues entonces habría una infinidad de teorías axiomáticas (con fórmulas) que "escaparían" del "control" de los susodichos teoremas, y no estoy seguro de que sin esos teoremas pudiéramos afirmar algo con seguridad sobre esas teorías.

Puedes tomar como axioma una fórmula con variables libres, pero si tomas su clausura universal obtienes una teoría equivalente: todo teorema de una es un teorema de la otra y viceversa. Partiendo de dicha fórmula, puedes pasar a su clausura universal mediante IG, y partiendo de la clausura universal, puedes pasar a la fórmula con variables libres usando EG. Así pues, suponer que los axiomas son sentencias no supone ninguna pérdida de generalidad.


En el ejemplo que pones de la Geometría de Euclides, el que viene a continuación del teorema 3.12, aplicas el teorema 3.12 al quinto postulado. Es decir, tomas el postulado

Por un punto exterior a una recta, se puede trazar una única paralela a la recta dada

como una sentencia. Aquí me surgen dos dudas:

1) ¿Qué pasa si consideras otra teoría axiomática, también de interés matemático, cuyos axiomas sean fórmulas y no sentencias? ¿Ya no puedes aplicar todos esos teoremas?

Pasa lo que acabo de decir, que si cambias sus axiomas por las clausuras universales de sus axiomas tienes otra teoría con los mismos teoremas, luego a un matemático le dará igual una que otra.


2) En la misma Geometría de Euclides, ¿por qué tomas el quinto postulado como una sentencia? A mí me parece una fórmula: representemos los puntos por letras del alfabeto latino y las rectas por letras griegas:

\( \bigwedge \alpha(Ep\alpha \rightarrow{T\beta\alpha}) \)

Lo leo así: "para toda recta alpha, si un punto p es exterior (E) a alpha, entonces se puede trazar (T) una recta paralela beta a alpha".

Yo veo que es una fórmula porque hay variables libres ahí (\( p, \beta \)). ¿Por qué lo tomas como sentencia? ¿Quizá lo he formalizado mal? Y si es así... ¿podemos transformar fórmulas en sentencias siempre en todos los casos (aplicando IG o IP, por ejemplo)?

Está mal formalizado, porque \( \beta \) necesita un cuantificador existencial y \( p \) tiene que aparecer en la conclusión. Serviría

\( \bigwedge \alpha(Ep\alpha \rightarrow\bigvee \beta\ {T\beta\alpha p}) \)

Que se lee: para todo punto \( p \) y toda recta \( \alpha \), si \( p \) es exterior a \( \alpha \) existe una recta \( \beta \) que pasa por \( p \) y es paralela a \( \alpha \). Así valdría, porque, aunque el axioma valga "para todo punto \( p \)", no pasa nada si omites el \( \bigwedge p \) inicial, pero tampoco pasa nada si lo pones, y así tienes una sentencia. La que, desde luego, no puede quedar libre es \( \beta \).


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.