Autor Tema: Teorema de Gödel

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

09 Junio, 2009, 05:37 am
Respuesta #30

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í)
Gracias Gustavo por las aclaraciones.
Lo de los infinitos potenciales y actuales me es conocido, y ya me daba cuenta que el infinito que se procura usar es el ''potencial''.
Pero la cuestión es que, en tal caso, cuando se usa una expresión del metalenguaje como por ejemplo 'n|' para indicar que se deben repetir n palotes |||||||||, ese n es un número natural, y no me queda muy claro qué clase de aritmética hay que usar ahí. Ya empiezo a dudar acerca de si puedo usar expresiones como m+n palotes, o dado un número n de palotes, descomponer n en sus factores primos y luego por cada factor primo armar alguna expresión lógica que bla bla...
La aparición del infinito ''actual'' estaría en expresiones como ''P implica Q'' donde P y Q pueden ser fórmulas cualesquiera.
El número total de expresiones que puedo poner en los lugares de P y Q son infinitas.
También puede ser que tenga una fobia exagerada contra el infinito.

Otro lugar donde veo el infinito actual es en la ''memoria de la computadora que escribe sentencias''.
Si yo puedo escribir una sentencia de tamaño tan grande como yo quiera, es que tengo memoria suficiente en algún lugar para ''almacenar'' todos esos signos que las forman. Esos lugares quizá ya están presentes intuitivamente en la mente, así como lo está la secuencia de números naturales. Aunque ahora también podría pensar, si quiero, que la ''memoria'' no es algo con una cantidad ''fija'' de ''celdas'', sino que es algo ''ampliable según la necesidad''. En fin...

Pero no quiero cansar más con esto.

Ya que has definido los términos, fórmulas, y todos los elementos del teorema, sería bueno comenzar a discutir la prueba.
Encontré algo así como un ejercicio sobre consistencia de la lógica, en un libro sobre Godel, y que quizá exponga en un próximo post.

09 Junio, 2009, 07:31 pm
Respuesta #31

Gustavo Piñeiro

  • Visitante
Lo de los infinitos potenciales y actuales me es conocido, y ya me daba cuenta que el infinito que se procura usar es el ''potencial''.
Pero la cuestión es que, en tal caso, cuando se usa una expresión del metalenguaje como por ejemplo 'n|' para indicar que se deben repetir n palotes |||||||||, ese n es un número natural, y no me queda muy claro qué clase de aritmética hay que usar ahí. Ya empiezo a dudar acerca de si puedo usar expresiones como m+n palotes, o dado un número n de palotes, descomponer n en sus factores primos y luego por cada factor primo armar alguna expresión lógica que bla bla...
La aparición del infinito ''actual'' estaría en expresiones como ''P implica Q'' donde P y Q pueden ser fórmulas cualesquiera.
El número total de expresiones que puedo poner en los lugares de P y Q son infinitas.

Hola,

En realidad, en la definición del lenguaje formal nunca se habla de "n palotes" de modo que no se necesita ninguna aritmética previa. Por otra parte, la definición de fórmula debe entenderse como una construcción jerarquizada: en ''P implica Q'', P y Q no son cualesquiera, sino fórmulas construidas en pasos previos.

Acerca de la memoria de la computadora, en efecto se va ampliando según sea necesario. Nunca se supone (ni es necesario suponer) que sea infinta en acto. En general eso sucede con todos los elementos del lenguaje formal: por ejemplo, la variables se agregan a medida que son necesarias, nunca es necesario suponer que todas las variables existen "en acto" a la vez.

Saludos!

09 Junio, 2009, 09:59 pm
Respuesta #32

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
LauLuna, espero no haberte hecho enojar.

¡En absoluto!

10 Junio, 2009, 05:01 pm
Respuesta #33

Gustavo Piñeiro

  • Visitante
Hola,

Algunas cuestiones más acerca de la definición del lenguaje formal. En primer lugar, para que la lectura de las fórmulas no se haga humanamente imposible aceptaremos algunas abreviaturas. Ya mencioné antes que usaremos sólo los paréntesis necesarios. Por ejemplo, si siguiéramos al pie de la letra las definiciones deberíamos escribir:

((S(0) + S(S(0))) + S(0))

En lugar de eso escribiremos simplemente:

(S0 + S0) + S0

Usaremos también las siguientes abreviaturas, usuales en lógica:
 
Si \( F \) es una fórmula entonces \( \forall{x_i}F \) será la abreviatura de \( -\exists{x_i}-F \).
Si \( F \) y \( G \) son fórmulas entonces \( F\wedge G \) será una abreviatura de \( -(F\Rightarrow{} -G) \).
Si \( F \) y \( G \) son fórmulas entonces \( F\vee G \) será una abreviatura de \( (-F\Rightarrow{} G) \).

Muchas veces a las variables, en lugar de llamarlas \( x_1 \), \( x_2 \), etc. las llamaremos \( x \), \( y \), etc.

Finalmente, agregamos al lenguaje un símbolo especial, digamos \( \otimes{}  \), que servirá para escribir sucesiones de fórmulas. Formalmente definimos:

1. Si \( F \) es una fórmula entonces \( \otimes{}  \)F\( \otimes{}  \) es una sucesión de fórmulas.
2. Si \( S \) es una sucesión de fórmulas y \( G \) es una fórmula entonces \( SG\otimes{} \) es una fórmula.
3. Toda sucesión de fórmulas se obtiene por aplicaciones sucesivas de las reglas anteriores.

Axiomas lógicos:

Por definición, un axioma lógico es cualquier fórmula que se obtenga de los esquemas siguientes. (Como ya dije en otro mensaje, estos esquemas definen en realidad un algoritmo que permite reconocer, dada una fórmula, si ésta es, o no, un axioma lógico.)

1. \( F\Rightarrow{}(G\Rightarrow{}F) \), donde \( F \) y \( G \) son fórmuas cualesquiera.

2. \( F\Rightarrow{}(G\Rightarrow{}H)\Rightarrow{}((F\Rightarrow{}G)\Rightarrow{}(F\Rightarrow{}H)) \), donde \( F \), \( G \) y \( H \) son fórmuas cualesquiera.

3. \( (-F\Rightarrow{}-G)\Rightarrow{}(G\Rightarrow{}F) \), donde \( F \) y \( G \) son fórmuas cualesquiera.

4. \( \forall{x}F(x)\Rightarrow{}F(x/t) \).
Una explicación aquí: \( x \) respresenta una variable cualquiera y cuando escribimos \( F(x) \) entendemos que \( x \) es una variable libre en F, \( t \) es un término y \( F(x/t) \) es la fómrula que se obtiene reemplazando toda aparición de la variable \( x \) por el término \( t \). Una restricción: si \( t \) tiene variables, ninguna de éstas puede aparecer afectada por un cuantificador al efectuarse el reemplazo.

5. \( \forall{x}(F\Rightarrow{}G)\Rightarrow{}(F\Rightarrow{}\forall{x}G) \) siempre que \( x \) no aparezca libre en \( F \).

6. \( x = x \), donde \( x \) es una variable cualquiera.

7. \( x = y \Rightarrow{} y = x \), donde \( x \) e \( y \) son variables cualesquiera.

8. \( x = y \Rightarrow{} (y = z\Rightarrow{} x = z) \)

9. \( x = y \Rightarrow{} t(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) = t(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \), donde \( t \) es un término cualquiera.

10. \( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \), donde \( F \) es una fórmula cualquiera.

Los axiomas 9 y 10 dicen esencialmente que si \( x=y \) entonces podemos reemplazar libremente \( x \) por \( y \).

Los esquemas del 1 al 5 son los axiomas de la lógica primer orden, al agregar los otros se obtiene la lógica de primer orden con igualdad. Éste es el sistema de axiomas que se usa en Gödel \( \forall{} \), hay otros sistemas posibles. De hecho, para facilitar ciertas demostraciones, en el sistema hemos puesto más axiomas de los que realmente son necesarios. Por ejemplo, las fórmulas que corresponden al esquema 8 pueden deducirse de las demás y por lo tanto no es necesario (aunque tampoco es erróneo) incluirlos.

En otro mensaje tocará hablar de las reglas de inferencia.

Saludos!

<<                >>

10 Junio, 2009, 09:33 pm
Respuesta #34

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Gustavo,

me pregunto si en los axiomas lógicos para la igualdad 6-10 en lugar de usar metavariables para variables no deberíamos usar metavariables para términos cualesquiera.

Un saludo.

11 Junio, 2009, 12:44 am
Respuesta #35

Gustavo Piñeiro

  • Visitante
me pregunto si en los axiomas lógicos para la igualdad 6-10 en lugar de usar metavariables para variables no deberíamos usar metavariables para términos cualesquiera.

Hola,

Sí, podrían usarse metavriables para términos cualesquiera. Puede probarse (gracias al esquema 9) que si el esquema 10 vale para variables entonces vale también para términos. Pero todo es cuestión de gustos y conveniencia, así como pusimos el esquema 8 (que en realidad es innecesario ya que se deduce de los otros), de la misma forma podríamos haber puesto metavariables que fueran términos.

Saludos,

Gustavo

<<                >>

11 Junio, 2009, 03:03 pm
Respuesta #36

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Sí, podrían usarse metavriables para términos cualesquiera. Puede probarse (gracias al esquema 9) que si el esquema 10 vale para variables entonces vale también para términos. Pero todo es cuestión de gustos y conveniencia, así como pusimos el esquema 8 (que en realidad es innecesario ya que se deduce de los otros), de la misma forma podríamos haber puesto metavariables que fueran términos.

En realidad es que depende de la reglas de inferencia. Si vas a incluir la de la Generalización (como es usual), entonces esa regla te permite pasar de las variables a otros términos. Por ejemplo, desde

'x=x'

a

'(para todo x) x=x'

y de ahí a

'0=0'

'S0=S0'

etc.

Lo cierto es que yo estoy más acostumbrado a trabajar con sistemas que sólo usan fórmulas cerradas y por eso no me había dado cuenta de que, probablemente, en el sistema que estás proponiendo bastan las metavariables de variable.

Un saludo.

12 Junio, 2009, 03:55 am
Respuesta #37

Gustavo Piñeiro

  • Visitante
En realidad es que depende de la reglas de inferencia. Si vas a incluir la de la Generalización (como es usual), entonces esa regla te permite pasar de las variables a otros términos.

En efecto, es exactamente así, todo depende de las reglas de inferencia. En nuestro sistema formal usaremos dos reglas de inferencia: (En todo lo que sigue \( P \) y \( Q \) son fórmulas.)

a) Modus ponens: De \( P \) y de \( P\Rightarrow Q \) se deduce \( Q \).
b) Generalización: De \( P \) se deduce \( \forall{x}P \), donde \( x \) es una variable cualquiera.

Una pregunta que puede surgir es: ¿Por qué las reglas de inferencia se toman aparte de los axiomas? ¿No son axiomas acaso? ¿La regla de generalización no puede escribirse como \( P\Rightarrow \forall{x}P \)?   

En principio, la diferencia es que:
a) Un axioma es una fórmula.
b) Una regla de inferencia puede verse como una operación que, dadas ciertas fórmulas, permite generar una fórmula nueva.

Una demostración (veremos en breve) es una sucesión de fórmulas en la que cada una de ellas es, o bien un axioma, o bien es generada por fórmulas anteriores por aplicación de estas operaciones llamadas "reglas de inferencia".

La posible confusión entre axiomas y reglas de inferencia puede provenir de leer las fórmulas apegándose a la interpretación de los símbolos. Cuando leemos \( P\Rightarrow (Q\Rightarrow P) \) (axioma 1), solemos entender que el axioma dice: "De \( P \) puede deducirse \( Q\Rightarrow P \)" o "Si \( P \) es verdadera entonces \( Q\Rightarrow P \) también lo es". En efecto ésa lectura es la que nos permite entender qué dice el axioma y la que nos convence de que es correcto, pero, en el contexto del programa de Hilbert (que es el contexto en el que se da la definición de demostración que mencioné más arriba) la lectura "correcta" de \( P\Rightarrow (Q\Rightarrow P) \) es:

"P flecha paréntesis Q flecha P paréntesis"

Solamente se trabaja a nivel sintáctico, sin interpretar los símbolos. Las reglas de inferencia nos dicen cómo combinar los símbolos para generar nuevas fórmulas.

Creo que sería más claro si en los axiomas en lugar de \( \Rightarrow  \) se usara, por ejemplo, el símbolo \( * \).

De este modo el axioma 1 sería: \( P*(Q*P) \)
Otro axioma sería \( (-P*-Q)*(Q*P) \)

Y el modus ponens diría que si en una demostración aparece \( P \) y \( P*Q \) entonces podemos agregar más adelante la fórmula \( Q \).

Dicho sea de paso, si se agregan como axiomas todas las fórmulas del tipo \( P\Rightarrow \forall{x}P \), donde \( P \) es una fórmula cualquiera y \( x \) es una variable cualquiera, entonces puede usarse el modus ponens como única regla de inferencia.

<<                >>

12 Junio, 2009, 01:05 pm
Respuesta #38

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Gustavo, permíteme que plantee una cuestión sobre la regla de Generalización.

Así a primera vista parece un tanto arbitraria porque da la impresión de que permite afirmar de todo x lo que antes no habíamos podido afirmar más que de algún término concreto. Por ejemplo, imagina que yo llego a la fórmula

(1)   '0+x = SSS0'

No parece lógico que de ahí pueda pasar a

(2)   '(para todo x) 0+x = SSS0'

De hecho, (2) es falsa en la interpretación estándar de este lenguaje, y desde luego no es un teorema de la aritmética de Peano. Se deduce en seguida que (1) no es un teorema de la aritmética, pero uno se queda pensando cómo garantizan los axiomas y las reglas de inferencia que nunca se vaya a obtener un teorema como (1), es decir, un teorema que junto con Generalización echaría por tierra la consistencia o la corrección de nuestro sistema.

Otra forma de plantear esto es la siguiente. En la lógica pura de primer orden hay una regla semejante a Generalización. La podemos llamar 'introducción del cuantificador universal' (IU), que permite pasar de

'P(t)'

a

'(para todo x) P(x)'.

Pero IU está sometida a restricciones que nos garantizan que 't' representa a un objeto cualquiera o a un objeto arbitrario, de modo que podemos afirmar de todos los objetos aquello que podemos afirmar del objeto designado por 't'. En el sistema que propones, en cambio, Generalización no está sometida a restricción alguna. ¿Qué hay en el sistema que nos garantice que esas restricciones no son necesarias?

Un saludo.
 

12 Junio, 2009, 01:34 pm
Respuesta #39

Gustavo Piñeiro

  • Visitante
Gustavo, permíteme que plantee una cuestión sobre la regla de Generalización.

Así a primera vista parece un tanto arbitraria porque da la impresión de que permite afirmar de todo x lo que antes no habíamos podido afirmar más que de algún término concreto. Por ejemplo, imagina que yo llego a la fórmula

(1)   '0+x = SSS0'

Hola,

Es que nunca llegarías a demostrar la fórmula '0+x = SSS0' (si como axiomas tomas fórmulas que sean verdaderas para la interpretación usual). Cuando definamos la noción de "verdad" veremos que esta definición se aplica tanto a enunciados como a fórmulas con variables libres y que en este último caso dice que \( P(x) \) es verdadera si y sólo si \( \forall{x}P(x) \) es verdadera.

Esta definición está en línea con el uso habitual del lenguaje matemático. Cuando queremos decir en lenguaje simbólico que la suma es conmutativa habitualmente escribimos \( x + y = y + x \) y muy rara vez \( \forall{x}\forall{y}(x + y = y + x) \).

De hecho, en el esquema lógico 6 puse \( x = x \) y quedó sobreentendido que esto equivalía a \( \forall{x}(x = x) \).

Saludos,

Gustavo

<<                >>