Autor Tema: Teorema de Gödel

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

12 Junio, 2009, 01:47 pm
Respuesta #40

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,370
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Añadir que las reglas de deducción en el sistema formal \( \mathcal{L} \) del cálculo de predicados son:

(1) Modus ponens: De \( \mathcal{A} \) y  \( (\mathcal{A}\rightarrow{\mathcal{B}}) \) se deduce \( \mathcal{B} \) siendo \( \mathcal{A} \) y \( \mathcal{B} \) fórmulas bien formadas cualesquiera de \( \mathcal{L} \).

(2) Generalización: De \( \mathcal{A} \) se deduce \( (\forall{x_i})\mathcal{A} \) siendo \( \mathcal{A} \) cualquier fórmula bien formada de \( \mathcal{L} \) y \( x_i \) cualquier variable.

Junto con los axiomas de \( \mathcal{L} \) hacen que todo teorema de \( \mathcal{L} \) sea fórmula lógicamente válida en cualquier interpretación (por el Teorema de corrección). También que si

\( \mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_k,\ldots\mathcal{A}_n \)

es una demostración de \( \mathcal{L} \), también lo es:

\( \mathcal{A}_1,\mathcal{A}_2,\ldots,\mathcal{A}_k \)

Dado que la fórmula \( \mathcal{A}_k \): \( (0+x=SSS0) \) no es verdadera (ni falsa), no puede ser un teorema de \( \mathcal{N} \) suponiendo que este tiene un modelo, con lo cual no existe la hipotética contradicción a la que se refiere Lauluna.

Saludos.

12 Junio, 2009, 01:51 pm
Respuesta #41

Gustavo Piñeiro

  • Visitante
Lo cierto es que yo estoy más acostumbrado a trabajar con sistemas que sólo usan fórmulas cerradas.

Releo esta frase y comprendo entonces tu "desconfianza" hacia la regla de generalización (que es útil solamente si se trabaja con fórmulas con variables libres). Como dije antes, todo es cuestión de gustos y de conveniencia, se pede trabajar todo el tiempo con enunciados (o fórmulas cerradas) e incluir reglas de sustitución de variables y de términos (o axiomas adecuados que las representen) que permitan pasar, por ejemplo, directamente de \( \forall{x}P(x) \) a \( \forall{y}P(y) \) o bien aceptar entre las fórmulas con valor de verdad a las fórmulas con variables libres (más la regla de generalización) y hacer:

\( \forall{x}P(x) \)
\( \forall{x}P(x)\Rightarrow P(y) \) (axioma lógico)
\( P(y) \) (modus ponens)
\( \forall{y}P(y) \) (generalización)

En realidad, la cuestión de si incluir, o no, a las fórmulas con variabes libres entre aquellas fórmulas que admiten valor de verdad fue tema de reflexión con Guillermo Martínez durante la escritura del libro. Y por el modo en que finalmente definimos la noción de verdad (lo comentaré después) llegamos a la conclusión de que necesitábamos incluir a las fórmulas con variables libres.

dado que la fórmula \( \mathcal{A}_k \): \( (0+x=SSS0) \) no es verdadera (ni falsa), no puede ser un teorema

Todo depende de la definición que se adopte. Según mi definición, la fórmula es falsa para la interpretación usual.

Gracias y saludos a ambos!

<<                >>

12 Junio, 2009, 02:06 pm
Respuesta #42

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,370
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Todo depende de la definición que se adopte. Según mi definición, la fórmula es falsa para la interpretación usual.

Cierto, lo que hace que \( \mathcal{A}_k:\;(0+x=SSS0) \) no sea un teorema de \( \mathcal{N} \) es que \( \mathcal{A}_k \) no sea verdadera para toda valoración \( v \) en su hipotético modelo \( \mathbb{N} \), independientemente de como se la llame.

Saludos.

13 Junio, 2009, 12:57 am
Respuesta #43

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,332
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

2. Si \( F \) es una fórmula y \( x_i \) es una variable entonces \( \exists{x_i}F \) es una fórmula.

Definición: decimos que la variable \( x_i \) tiene una aparición libre en la fórmula \( F \) si esa aparición no está afectada por el cuantificador \( \exists{} \) (es decir, si no está precedida por un \( \exists{x_i} \). En principio omito aquí la definición formal del concepto de variable libre.)


Definición: un enunciado es una fórmula en la que ninguna variable tiene apariciones libres (en particular esto sucede si la fórmula no tiene variables).


Pregunta sobre lo que marqué con rojo:
Voy a considerar a la variable \( x_1 \) por ejemplo, y voy a suponer que tengo una fórmula F.
Por la regla de construcción dada, resulta que \( \exists{x_1}F \) también es una fórmula, a la cual denoto con G.
Si aplico de nuevo la misma regla así como está escrita, con la misma variable \( x_1 \), resulta que \( \exists{x_1}G \) también es una fórmula, a la cual puedo llamar H.
Si ''desenrollo'' un poco la fórmula H, obtengo la fórmula \( \exists{x_1\exists{x_1}}F \).
¿Es lícito formar fórmulas en donde el/un cuanfiticador aparezca dos veces afectando a la misma variable?
¿Y si no, cuál es el modo más sencillo de evitarlo usando las formalidades del caso?


Pregunta sobre lo que marqué con verde:
Cuando una variable no está afectada por el cuantificador existencial, ¿cómo ''conviene'' ser interpretada? ¿Una constante quizás, o qué?
Además, las fórmulas tenemos que imaginarlas en un contexto interesante donde hay muchas otras fórmulas, relaciones entre ellas, inferencias, etc. No termino de comprender el papel que juegan las variables libres en un contexto como este, dentro de la metamatemática. ¿Hay algún riesgo o complicación, o se usan fórmulas con variables libres sin inconvenientes?

Creo que la duda tiene que ver con la última definición que está en púrpura, la de enunciado.
¿Por qué se destacan las fórmulas sin variables libres? ¿Son fórmulas deseables?
¿Las proposiciones lógicas que vamos a aceptar tienen que ser enunciados?

No sé en realidad precisar bien la duda, pero lo puedo resumir así: siento comezón en las fórmulas con variables libres, y no sé cuál es la mejor forma de rascarme.

13 Junio, 2009, 03:12 am
Respuesta #44

Gustavo Piñeiro

  • Visitante
Pregunta sobre lo que marqué con rojo:
¿Es lícito formar fórmulas en donde el/un cuanfiticador aparezca dos veces afectando a la misma variable?

Sí, es lícito.

Pregunta sobre lo que marqué con verde:
Cuando una variable no está afectada por el cuantificador existencial, ¿cómo ''conviene'' ser interpretada? ¿Una constante quizás, o qué?
Además, las fórmulas tenemos que imaginarlas en un contexto interesante donde hay muchas otras fórmulas, relaciones entre ellas, inferencias, etc. No termino de comprender el papel que juegan las variables libres en un contexto como este, dentro de la metamatemática. ¿Hay algún riesgo o complicación, o se usan fórmulas con variables libres sin inconvenientes?

Creo que la duda tiene que ver con la última definición que está en púrpura, la de enunciado.
¿Por qué se destacan las fórmulas sin variables libres? ¿Son fórmulas deseables?
¿Las proposiciones lógicas que vamos a aceptar tienen que ser enunciados?

No sé en realidad precisar bien la duda, pero lo puedo resumir así: siento comezón en las fórmulas con variables libres, y no sé cuál es la mejor forma de rascarme.

Las fórmulas con variables libres expresan "relaciones" o "propiedades" (más exactamente, expresan conjuntos). Las variables libres actúan como variables en el mismo sentido que se le da al término cuando se trabaja con funciones. De hecho, a las fórmulas con variables libres, Bertrand Russell las llamaba "funciones proposicionales", que tienen un cierto valor de verdad dependiendo de qué valores se asignen a las variables. Por ejemplo \( x + y = 5 \) expresa el conjunto de todos los pares \( (x,y) \) cuya suma es 5 o también la relación "la suma de \( x \) más \( y \) es 5". Una fórmula con variables libres no es verdadera ni falsa en sí misma, depende de qué valores adopten las variables.

Una fórmula sin variables libres (o fórmula cerrada) es en sí misma verdadera o falsa. Ejemplos son "2 + 4 = 10" o \( \exists{x}\exists{y}(x + y = 5) \).

A veces (contradiciendo un poco lo anterior, pero el contexto en cada caso debería servir para evitar confusiones) al escribir axiomas y demostraciones escribiremos fórmulas con variables libres a modo de abreviaturas de enunciados. Por ejemplo, muchas veces escribirermos \( x + y = y + x \) queriendo decir \( \forall{x}\forall{y}(x + y = y + x) \).  No todos adoptan esta práctica (LauLuna ha dicho que él no lo hace). Como ya dije, es cuestión de gustos y conveniencia.

Saludos!

<<                >>

13 Junio, 2009, 03:54 am
Respuesta #45

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,332
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
OK Gustavo, como siempre muy claro.

En cuanto a lo de las fórmulas ''cerradas'', me parece que si algo como x+y=y+x puede dar lugar a cierta ambigüedad (aunque has explicado que no habrá confusión en cada caso), entonces sería mejor evitarlo, y escribir todos los cuantificadores que realmente están presentes en la expresión, sin recurrir a abreviaturas.

Yo tiendo a ser redundante, y hay algunas personas allegadas que me lo critican.
Estoy entre los que prefieren escribir todo el tiempo \( \forall{x}\forall{y}(x + y = y + x) \), aunque resulte algo pesado, en vez de una abreviatura como \( x + y = y + x \).
Y no tanto por el fanatismo de ''lo correcto'', sino que este terreno de la metamatemática da pie para caer fácilmente en ambigüedades y confusiones, sobretodo para quienes estamos poco familiarizados con el tema.
A lo mejor estoy exigiendo lo que es una conveniencia para mí particularmente, porque como he manifestado, todos los pasos que se dan, y todas las construcciones que se hacen me generan dudas.
Como no tengo práctica en el tema, todavía ''siento'' que todo está en el aire, y prefiero la exactitud tanto como sea posible.

Pero está bueno que por lo menos se expliquen y se comenten todas las alternativas que hay dando vueltas por ahí.

Saludos.

P.D.: Lo de cuantificar dos veces la misma variable en una misma fórmula me sigue pareciendo extraño. Pero si está entre las posibilidades que uno puede construir, me la banco.

13 Junio, 2009, 01:32 pm
Respuesta #46

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Tal como Gustavo dice, yo, al igual que Argentinator, prefiero trabajar con fórmulas cerradas, es decir, con enunciados.

Las fórmulas abiertas no son enunciados o proposiciones en sentido estricto, por tanto, no tienen valor de verdad en sí mismas. Uno se pregunta entonces qué pintan en las deducciones, porque parece que las deducciones deberían partir de enunciados y llegar a enunciados a través de enunciados.

Sin embargo, es una práctica muy extendida la de admitir fórmulas abiertas (es decir, con variables libres) en los sistemas deductivos. Está así en Gödel, en Kleene, más recientemente en Mendelson y en muchísimos otros. Torkel Franzén ('Inexhaustibility. A Non Exhaustive Treatment' AK Peters 2004, un libro muy recomendable para quien desee profundizar en algunos aspectos de la incompletitud de Gödel y esté dispuesto a estudiar en serio) introduce la regla de Generalización de esta manera (p. 103, traduzco y sustituyo símbolos por lenguaje informal):

"Si la fórmula phi es deducible de un conjunto gamma de fórmulas y x no está libre en ninguna fórmula de gamma, entonces '(para todo x) phi(x)' es deducible de gamma."

Y añade:

"Esto está de nuevo de acuerdo con el razonamiento matemático usual. Si queremos deducir a partir de un conjunto M de premisas queparatodo número real x vale A(x), lo hacemos generalmente razonando para un número real r arbitrario que no especificamos y mostrando que A(r) vale. El paso final expresado en la regla de arriba: 'como r era un real arbitrario, se sigue que A(x) vale para todo real x', suele dejarse implícito [en el razonamiento matemático informal, nota de LauLuna]"

Entonces, la función de las variables libres en el curso de las derivaciones formales parece ser la de reproducir el razonamiento para objetos escogidos al azar, por así decirlo. Por eso las variables libres hacen estrecha pareja con la regla de Generalización, según yo lo veo.

De todas maneras, hay que tener en cuenta que los sistemas que permiten trabajar con fórmulas abiertas permiten probar como teoremas fórmulas abiertas (porque nada nos obliga a dar un paso más y aplicar Generalización) y esto parece una imperfección: deducimos fórmulas que no poseen en sí mismas un valor de verdad en la interpretación usual.

En la mayoría de los textos de Lógica Formal, por lo que yo sé, se evita hoy en día el trabajar con fórmulas abiertas. Para el razonamiento sobre objetos arbitrarios de cara a introducir el cuantificador universal se permite pasar de

'P(a)'

donde 'a' es una constante, a

'(para todo x) P(x)'

si 'a' no aparece en las premisas ni en ninguna suposición no cancelada, lo que garantiza que 'a' denota un objeto arbitrario.

Me pregunto si no sería también deseable introducir esta práctica en los sistemas formales matemáticos.

Un saludo.

13 Junio, 2009, 02:07 pm
Respuesta #47

Fernando Revilla

  • Es más fácil engañar a alguien que convencerle de que ha sido engañado.
  • Administrador
  • Mensajes: 11,370
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • Las matemáticas son demasiado humanas (Brouwer).
    • Fernando Revilla
Las fórmulas abiertas no son enunciados o proposiciones en sentido estricto, por tanto, no tienen valor de verdad en sí mismas.

Algunas formulas abiertas si lo son y otras no. Es precisamente por eso por lo que yo prefiero distinguir entre fórmulas verdaderas, falsas y ni verdaderas ni falsas. Esto es una distinción clara entre los lenguajes \( L \) del cálculo de enunciados y el \( \mathcal{L} \) del cálculo de predicados.

Por supuesto que son las fórmulas cerradas en las que tenemos que hacer especial hincapié pues si son verdaderas en todo modelo de un sistema de primer orden \( S \) son teoremas de \( S \).   

Saludos.

13 Junio, 2009, 03:13 pm
Respuesta #48

Gustavo Piñeiro

  • Visitante
Hola,

P.D.: Lo de cuantificar dos veces la misma variable en una misma fórmula me sigue pareciendo extraño. Pero si está entre las posibilidades que uno puede construir, me la banco.

En realidad, el único riesgo es el de ser redundante, ya que, por ejemplo, \( \exists{x}\exists{x}(x = 6) \) es equivalente \( \exists{x}(x = 6) \). Creo que no se ponen reglas especiales para evitar este uso para no complicar innecesariamente las reglas sintácticas del lenguaje, dado que, precisamente, no hay "peligro" en repetir cuantificadores. Sin embargo, no habría ningún cambio esencial en poner reglas que lo eviten.

Por otra parte, considerando el consenso favorable a evitar el uso de fórmulas abiertas para indicar enunciados, no tengo problemas en adoptar esa convención (que, admito, tiende a evitar confusiones). A partir de ahora, entonces, las fórmulas abiertas denotarán siempre relaciones (o funciones proposicionales, término que usaba Ruseell, hoy en desuso, pero que a mí me parece muy descriptivo) y las cerradas, enunciados.

Modificaremos entonces los esquemas lógicos 6, 7 y 8. El 6 ahora dirá: \( \forall{x}(x = x) \), análogamente se modifican el 7 y el 8. El esquema lógico 4 puede dar lugar a fórmulas no cerradas, pero esto no es problema (véanse las definiciones de más abajo).

Supongamos ahora que se propone un conjunto A de axiomas para la Aritmética, es decir, un conjunto de enunciados escritos en el lenguaje formal. (Normalmente, nos interesarán sólo los conjuntos recursivos de axiomas, los cuales están definidos a través de un programa. En la práctica, este programa, a su vez, suele tener la forma de un conjunto finito de esquemas, similar al que dimos para los axiomas lógicos.)

Tenemos así axiomas lógicos y axiomas propios de la teoría (estos últimos son los axiomas del conjunto A, la distinción es la misma que la que hacía Euclides entre nociones comunes y postulados). Podemos dar la siguiente definición:

Definición: una demostración es una sucesión finita de fórmulas en la que cada una de ellas es, o bien un axioma (propio o lógico), o bien se dedude de fórmulas anteriores por aplicación de las reglas de inferencia.

Definición: una fórmula es demostrable si es la última fórmula en una demostración.

Es cierto, como dice LauLuna, que el esquema lógico 4 permite que haya fórmulas abiertas demostrables (no estamos obligados a usar la regla de generalización para agregar los cuantificadores que faltan). Una forma de lograr que esta circunstancia no complique el desarrollo de las ideas es la siguiente:

Definición: una fórmula es demostrable si es la última fórmula en una demostración y es un teorema si es un enunciado demostrable.

Admito que es una definición que acabo de sacarme de la manga, no sé si esta distinción entre "fórmulas demostrables" y "teoremas" existe en la literatura (donde, normalmente, ambas expresiones se toman como sinónimos). Propongo la distinción como modo de compatibilizar las reglas que hasta ahora hemos venido consensuando con el hecho de que sólo los enunciados representen expresiones con valor de verdad.

Me parece que, en este caso, la distinción, lejos de crear confusiones, puede ser útil y, de paso, reserva la palabra "mágica" teorema sólo para los enunciados.

Saludos!

<<                >>

13 Junio, 2009, 05:02 pm
Respuesta #49

Gustavo Piñeiro

  • Visitante
Definición: Un conjunto A de axiomas es recursivo si existe un algoritmo (que trabaja a nivel sintáctico, es decir, solamente manipula signos sin tomar en cuenta su eventual significado) que, dada una secuencia finita símbolos del lenguaje, reconoce si esa secuencia constituye, o no, un axioma.

Los axiomas lógicos forman un conjunto recursivo.

Teorema: Si el conjunto A de axiomas propios es recursivo entonces existe un algoritmo que, dada una secuencia de símbolos del lenguaje, reconoce si esa secuencia constituye, o no, una demostración.

Este teorema es esencial en todo el desarrollo posterior. Es posible tomar un conjunto diferente de axiomas lógicos o diferentes reglas de inferencia, pero estas modificaciones no deben alterra la verdad de este teorema, que está en el corazón mismo del Programa de Hilbert.

Comenté antes que si se agregara la siguiente regla de inferencia:

De los infinitos enunciados \( P(0), P(1), P(2),... \) se deduce \( \forall{x}P(x) \).

Entonces el teorema anterior sería falso y también sería falso el teorema de Gödel.

<<                >>