Autor Tema: Teorema de Gödel

0 Usuarios y 3 Visitantes están viendo este tema.

21 Junio, 2009, 01:31 pm
Respuesta #110

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Bueno, la lógica puede presentarse como un cálculo de deducción natural, esto es, sin axiomas, como un conjunto de reglas de inferencia.

Cuando una lógica es completa (como la de primer orden), esas reglas son capaces de derivar todas las consecuencias lógicas de cualquier conjunto de fórmulas (axiomas).

En general, esas  reglas revisten una forma inductiva: tienes un par de reglas por las que empezar, por ejemplo, la que te permite derivar los axiomas a partir de los axiomas y la que te permite derivar 't=t' para cualquier término t; después toman la forma del paso de inducción: si has derivado tal y tal de los axiomas, puedes derivar tal y tal.

Este proceso recursivo debe dar lugar a una enumeración recursiva de los teoremas.

21 Junio, 2009, 07:25 pm
Respuesta #111

Gustavo Piñeiro

  • Visitante
Comencemos con la demostración. Supongamos que se ha dado un sistema recursivo y omega-consistente de axiomas para la aritmética tal que todo enunciado finitario verdadero es demostrable. Debemos demostrar que el sistema es incompleto.

Cuando decimos "1 + 1 = 2" estamos haciendo una afirmación aritmética, una afirmación acerca de los números.

Cuando decimos "1 + 1 = 2 es demostrable" estamos haciendo una afirmación acerca de la afirmación 1 + 1 = 2. Es decir, estamos en otro nivel de lenguaje.

El lenguaje formal de la aritmética permite, en principio, hacer afirmaciones acerca de los núemros. "1 + 1 = 2", por ejemplo, se traduce como "S0 + S0 = SS0". Aparentemente, a primera vista, en este lenguaje no se podría afirmar que "1 + 1 = 2 es demostrable".

Nuestro primer objetivo es mostrar que esta primera impresión es errónea y que usando el lenguaje formal de la aritmética se puede afirmar que "1 + 1 = 2 es demostrable". ¿Cómo?

"1 + 1 = 2 es demostrable" habla de una afirmación y, en principio, el lenguaje formal sólo permite hablar de números. Para que el lenguaje formal pueda referirse a afirmaciones debemos transformar a las afirmaciones en números.

De aquí surge a idea de la "numeración de Gödel" o "codificación de Gödel": a cada enunciado (en realidad a cada enunciado y a cada sucesión finita de enunciados) le asignaremos un número (llamado su código o su número de Gödel) de tal modo que hablar del número equivaldrá a hablar del enunciado (o sucesión de enunciados).

En un próximo comentario veremos en detalle cómo se hace esta asignación de códigos, pero la idea general es ésta: si al enunciado "1 + 1 = 2" le correspondiera como código el número (por decir) 22.344 entonces "1 + 1 = 2 es demostrable" sería equivalente "22.344 es el código de un enunciado demostrable" y esta útlima afirmación habla ahora de un número, ya no de un enunciado.

Continuará...

<<                >>

22 Junio, 2009, 04:40 am
Respuesta #112

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hola mundo.

Como siempre, vengo medio atravesado respecto a la corriente.
Mientras ustedes se han encaramado con la prueba del teorema, yo ando entretenido con otras cosas, como por ejemplo meter las definiciones metamatemáticas en un programa real de computadora.

Incluyo esto acá porque quiero contribuir con algo más que con meras quejas y preguntas.
Les cuento brevemente qué anduve haciendo.

Primero una reflexión sobre Máquinas de Turing, Máquina Virtual Java, memoria RAM y lenguajes de programación, terminando con una sospechosa justificación de por qué elegí el lenguaje Python a fin de cuentas.
Las pongo en un Spoiler porque puede no interesarle a todo el mundo.

Spoiler

Primero que nada, tuve que tomar una decisión acerca de qué lenguaje de programación o qué entorno informático usar para emular lo más exactamente posible la característica de trabajar bajo una Máquina de Turing.
Las Máquinas de Turing en su planteamiento básico resultan algo complicado de manejar, debido a que usan operaciones muy elementales de computación: escribir y borrar bits en una cinta hipotética.
La cinta de la máquina de Turing puede reemplezarse por un disco rígido, una memoria RAM, etc.

Sin embargo hay estudios de teoría de la computación que concluyen que cualquier lenguaje de programación moderno, corriendo en una PC de escritorio actual, emula las características de una Máquina de Turing.
Sin embargo, se debe suponer la situación ideal de que la memoria RAM disponible (la famosa ''cinta'') es ampliable tanto como se quiera, o sea, se mantiene finita pero ilimitada, y puede crecer tanto como lo deseemos.
Esa situación sería posible, por ejemplo, si pudiéramos enchufar varios pendrives formando un ''trencito'', y así ampliaríamos la RAM tanto como nos dé la gana.

Pero esa limitación de Hardware no debería preocuparnos tanto como la de Software.
En el pasado hubieron sistemas operativos que no eran capaces de aprovechar toda la RAM disponible.
Hoy día a veces tenemos limitaciones similares.

Pero cualquiera sea el sistema operativo, podemos instalar una Máquina Virtual Java, que es una plataforma especial que permite correr programas Java, claro, pero también permite aprovechar toda la memoria RAM disponible. Si hiciéramos programas inteligentes en Java, se podrían detectar a tiempo las carencias de memoria RAM, y en vez de poner un cartel: ''ERROR: EL SISTEMA SE QUEDÓ SIN  MEMORIA'', se podría poner un cartel más optimista: ''LA MEMORIA RAM ESTÁ POR ACABARSE, POR FAVOR AMPLÍELA PARA PODER SEGUIR CON LA EJECUCION DEL PROGRAMA".

Así que, según yo lo veo, la Máquina Virtual Java es ''LA'' Máquina de Turing.

Ahora bien. Resulta que programar en Java lleva su tiempo. ¿Qué alternativas hay?

Me fijé qué pasaba con el lenguaje de programación Python.
Este es un lenguaje interpretado, de manera que trabaja bajo un entorno de comandos.
Python trabaja con listas y cadenas de caracteres de manera bastante natural, de manera que el programador no debe preocuparse en general de las limitaciones de la memoria RAM.
No he investigado sobre este tema, pero da toda la sensación de que uno podría programar inteligentemente en Python para detectar también carencias de memoria, y poner un cartelito que pida más RAM cuando haga falta.
Existen versiones de Python para cualquier plataforma, así que tendríamos, de nuevo, una correcta Máquina de Turing, si es que es verdad que Python es capaz de aprovechar todos los recursos (sobretodo la RAM) que el sistema le brinda.

A pesar de todo esto, no me parecen soluciones demasiado limpias, ni Java ni Python.

Pero al final me volqué por Python porque es sencillísimo programar en ese lenguaje, y así se puede concretar las ideas que uno tiene con mayor rapidez. Uno puede pensar en hacer un esfuerzo mayor más adelante, programando en otro lenguaje, pero en realidad da lo mismo, porque lo que en realidad nos hace falta es una Máquina virtual de Turing, bien diseñada, que dudo que alguien se haya tomado el trabajo de hacer.

Otro punto en contra de Python es que uno no puede hacer una verificación de tipos de datos, de manera que una cadena de caracteres podría entrar como un número o una lista o cualquier objeto posible, con los peligros que eso acarrea.

Aún así, me quedé con Python, porque me permitió terminar en una tarde una lista de funciones para verificar los elementos básicos de la metamatemática.

[cerrar]

Las reglas que usé en el programa son las que dio Gustavo, las puse en una clase llamada language y, dada una cadena de caracteres s, las operaciones que pueden hacerse sobre s permiten verificar si:

* s está en el lenguaje L con los signos del mismo,
* s es una constante
* s es una variable
* s es un término sin variables (un átomo)
* s es un término (quizá con variables)
* s es una fórmula

Estas verificaciones son muy fáciles de hacer, siempre y cuando uno no quiera hacer nada más con la cadena s, porque en cuanto uno quiera aplicar axiomas, demostraciones, etc., la cosa se complica un poco más (y aún no he intentado nada con esto último).

No incluyo todavía otro tipo de verificaciones: como por ejemplo si una variable es libre en una fórmula. Pero ya lo voy a hacer en una futura entrega.

Les dejo en el spoiler un volcado de una salida típica del programita que hice (son 5 cadenas distintas, la primera vacía):

Spoiler


ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:  
 está en el lenguaje L? True
 es una constante? False
 es una variable? False
 es un átomo? False
 es un término? False

 es una fórmula? False



ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:  x''''''''''''''
X'''''''''''''' está en el lenguaje L? True
X'''''''''''''' es una constante? False
X'''''''''''''' es una variable? True
X'''''''''''''' es un átomo? False
t
X'''''''''''''' es un término? True
t
t
X'''''''''''''' es una fórmula? False



ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:  Ex'''x=0
EX'''X=0 está en el lenguaje L? True
EX'''X=0 es una constante? False
EX'''X=0 es una variable? False
EX'''X=0 es un átomo? False
EX'''X=0 es un término? False
qX=0
qX=t
qt=t
qf
f
f
EX'''X=0 es una fórmula? True



ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:  (S((x'''+S((x'''+S(x''''')))))+(x.(x'''+S(S(S(0))))))
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) está en el lenguaje L? True
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una constante? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una variable? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es un átomo? False
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))
(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))
(S((t+S((t+t))))+(t.(t+S(S(t)))))
(S((t+S(t)))+(t.(t+S(S(t)))))
(S((t+t))+(t.(t+S(t))))
(S(t)+(t.(t+S(t))))
(t+(t.(t+t)))
(t+(t.t))
(t+t)
t
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es un término? True
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))
(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))
(S((t+S((t+t))))+(t.(t+S(S(t)))))
(S((t+S(t)))+(t.(t+S(S(t)))))
(S((t+t))+(t.(t+S(t))))
(S(t)+(t.(t+S(t))))
(t+(t.(t+t)))
(t+(t.t))
(t+t)
t
t
(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0)))))) es una fórmula? False



ANALISIS METAMATEMATICO DE LA CADENA DE CARACTERES:  Ex'''(-----Ax'(S((x'''+S((x'''+S(x''''')))))+(x.(x'''+S(S(S(0))))))=S(S(0))*-x=S(0))
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) está en el lenguaje L? True
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una constante? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una variable? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es un átomo? False
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es un término? False
q(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0))
q(-----q(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0))
q(-----q(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(t))))))=S(S(t))*-X=S(t))
q(-----q(S((t+S((t+S(t)))))+(t.(t+S(S(S(t))))))=S(S(t))*-t=S(t))
q(-----q(S((t+S((t+t))))+(t.(t+S(S(t)))))=S(t)*-t=t)
q(-----q(S((t+S(t)))+(t.(t+S(S(t)))))=S(t)*-t=t)
q(-----q(S((t+t))+(t.(t+S(t))))=t*-t=t)
q(-----q(S(t)+(t.(t+S(t))))=t*-t=t)
q(-----q(t+(t.(t+t)))=t*-t=t)
q(-----q(t+(t.t))=t*-t=t)
q(-----q(t+t)=t*-t=t)
q(-----qt=t*-t=t)
q(-----qf*-f)
q(-----f*-f)
q(----f*f)
q(---f*f)
q(--f*f)
q(-f*f)
q(f*f)
qf
f
f
EX'''(-----AX'(S((X'''+S((X'''+S(X''''')))))+(X.(X'''+S(S(S(0))))))=S(S(0))*-X=S(0)) es una fórmula? True
 
[cerrar]

Los que quieran experimentar con el programita, o modificarlo, etc., se los dejo adjunto en un archivo.
Está con extensión .txt, pero hay que renombrarlo a .py para que corra en Python.
La versión es Python 3.0.

En este otro Desplegable les dejo a mano las reglas que Gustavo dio en este mismo Thread, las cuales usé en el programa:
Spoiler
Para definir un sistema formal debemos comenzar por definir los símbolos del lenguaje. El lenguaje tendrá:

1. Símbolos lógicos: \( \exists{} \), \( \Rightarrow{} \), \( - \), \( = \).
(El \( - \) es el símbolo de negación. El \( = \) no siempre se incluye entre los símbolos lógicos, pero en este caso sí lo haremos.)

2. Variables: \( x_1 \), \( x_2 \), \( x_3 \),...
(veremos después que estas variables pueden escribirse usando solamente dos símbolos básicos.)

3. Constante: una sola constante, \( 0 \).

4. Símbolos de funciones: \( S \), \( + \), \( \cdot{} \).
(El uso de la palabra "función" es sólo para darle un nombre común a estos símbolos, no es necesario saber qué es una "función".)

5. Signos de puntuación: \( ( \), \( ) \)

Llamamos expresión a cualquier secuencia finita de símbolos.

Un término se define del siguiente modo:

1. Las variables y la constante son términos.
2. Si \( s \) y \( t \) son términos entonces \( (s + t) \), \( (s\cdot{}t) \) y \( S(t) \) son términos.
3. Todo término se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.

(En relación con el comentario anterior sobre el infinito potencial y el infinito actual, nótese que no hablamos del conjunto de todos los términos sino de una construcción paso a paso.)
(A veces, para aliviar la notación, se omiten paréntesis innecesarios y se escribe \( s\cdot{}t \) en lugar de \( (s\cdot{}t) \).)

Una fórmula se define del siguiente modo:

1. Si \( s \) y \( t \) son términos entonces \( s=t \) es una fórmula.
2. Si \( F \) es una fórmula y \( x_i \) es una variable entonces \( \exists{x_i}F \) es una fórmula.
3. Si \( F \) y \( G \) son fórmulas entonces \( -F \) y \( (F\Rightarrow{}G) \) son fórmulas.
4. Toda fórmula se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.

[cerrar]


P.D.: Si no se entiende nada el programa o qué diablos estoy haciendo, a no preocupar, que habrá mejoras en el futuro.
Por hoy me quedé conforme con ver que todo funciona.


22 Junio, 2009, 08:22 pm
Respuesta #113

Gustavo Piñeiro

  • Visitante
La intervención de argentinator es muy oportuna, porque, en el proceso de definir la codificación de Gódel, el paso que sigue es, precisamente, recordar los símbolos del lenguaje formal.

Recordémoslos:

Constante: \( 0 \)
Funciones: \( S \), \( + \), \( \cdot{} \)
Símbolos lógicos: \( \exists{} \), \( \Rightarrow  \), \( - \), \( = \)
Paréntesis: \( ( \), \( ) \)
Símbolo especial para indicar sucesiones de fórmulas: \( \otimes{} \)

Para escribir las variables adoptaremos la siguiente convención (que, de hecho, argentinator, si no entendí mal las cosas, usó en su programa): las variables \( x_1, x_2, x_3,\ldots  \) se escribirán usando los dos únicos símbolos \( v \) y \( {}_| \) de la siguiente manera: \( v_{|}, v_{||}, v_{|||},\ldots \).

En resumen, toda expresión del lenguaje (así como toda sucesión de expresiones) puede escribirse usando un total de 13 símbolos:

\( 0 \), \( S \), \( + \), \( \cdot{} \), \( \exists{} \), \( \Rightarrow  \), \( - \), \( = \), \( ( \), \( ) \), \( \otimes{} \), \( v \), \( {}_| \)

<<                >>

22 Junio, 2009, 09:35 pm
Respuesta #114

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino

Para escribir las variables adoptaremos la siguiente convención (que, de hecho, argentinator, si no entendí mal las cosas, usó en su programa): las variables \( x_1, x_2, x_3,\ldots  \) se escribirán usando los dos únicos símbolos \( v \) y \( {}_| \) de la siguiente manera: \( v_{|}, v_{||}, v_{|||},\ldots \).

Claro, en el programa Python se debe usar la sintaxis estricta de los lenguajes de la metamatemática.
No se permite escribir la versión ''visualmente agradable'' de variables como \( x_0,x_1,x_2,... \), con subíndices, sino que se debe indicar un signo de variable, digamos \( x \), seguido de palotes (una cantidad finita).
La convención que usé en el programa es que las variables \( x_0,x_1,x_2,x_3,... \) se indican por \( x,x',x'',x''',etc. \).
También podría haber usado \( x,x|,x||,x|||,... \), es cuestión de gustos. Eso es algo que se puede cambiar, si alguien me lo exige...

En el programa en Python agregué el símbolo de cuantificación \( \forall{} \), para permitirme más adelante un manejo más cómodo de las fórmulas... aunque no sé si en realidad conviene, porque cuando aparezcan negaciones de cuantificadores voy a tener que transformar unos en otros.

El signo | lo reemplacé en el programa por una prima: '
El signo \( \Rightarrow{} \) lo reemplacé por un *.
Los cuantificadores \( \forall{,\exists{}} \) tuve que escribirlos como letras (las invertidas de las invertidas, que quedan derechas de nuevo): \( A, E \).

El símbolo \( \otimes{} \) no aparece aún el mi programa porque no hice la función que determina si cierta ristra de signos es o no una sucesión de enunciados, pero eso es fácil de programar, una vez que está hecho lo otro. Ese signo voy a tener que reemplazarlo por algún caracter ASCII más a mano, como por ejemplo el arroba: @.

Saludos


23 Junio, 2009, 11:02 pm
Respuesta #115

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Reescribí el programa anterior, ahora está mucho más claro, y está todo documentado internamente.
En el primer intento había usado clases, pero decidí suprimir eso en aras de obtener código más legible.
Estoy asombrado de lo fácil que es programar estas cosas en Python.
De paso también aprovecho para aprender Python.
Bien, les dejo el archivo METAMAT_1_00.TXT como archivo adjunto,
y recuerden que para que corra hay que cambiarle la extensión a .PY

Descubrí un pequeño error en el programa (como siempre pasa, por Ley de Murphy), en la rutina que verifica si cierta expresión es o no es una variable. Acepta como variables a expresiones que comienzan como tales, pero siguen con signos arbitrarios.
De todas formas, eso no es un gran problema, porque no afecta al resto de rutinas del programa, que funcionan bien, y reconocen variables correctamente.
En futuras versiones estará arreglado.

24 Junio, 2009, 11:09 am
Respuesta #116

Gustavo Piñeiro

  • Visitante
Todos sabemos que los números naturales se pueden escribir en binario. No sé si es tan conocido que existe una versión de esta escritura (que es aplicable sólo a enteros positivos, no incluye al 0) en la que los dígitos que se usan no son 0 y 1, sino 1 y 2.

En esta "escritura binaria sin cero" los números del 1 en adelante se escriben así: 1, 2, 11, 12, 21, 22, 111,...

Concatenar dos números escritos en binario sin cero consiste en escribir el segundo número a continuación del primero. Por ejemplo, concatenar 112 con 22 da como resultado 11222.
 
Asignemos ahora los códigos de Gödel. Comencemos con los símbolos del lenguaje:

\( 0 \), \( S \), \( + \), \( \cdot{} \), \( \exists{} \), \( \Rightarrow  \), \( - \), \( = \), \( ( \), \( ) \), \( \otimes{} \), \( v \), \( {}_| \)

Primero asignamos núumeros de Gödel a los símbolos (los números siempre están escritos en binario sin cero). Al primer símbolo le asignamos el número 12, al segundo símbolo le corresponde el 112, al tercero el 1112 y así sucesivamente.

A la concatenación de dos o más símbolos le corresponde la concatenación de los números correspondientes. Así por ejemplo, a la expresión SS0 le corresponde el número 11211212. (Parafraseando a Lewis Carroll, el nombre del número 2 se llama 11211212.)

De este modo, a cada expresión del lenguaje formal (en particular, a cada enunciado, cada fórmula y cada sucesión de fórmulas) le corresponde un número de Gödel o código.

<<                >>

24 Junio, 2009, 09:26 pm
Respuesta #117

Gustavo Piñeiro

  • Visitante
Pasemos ahora a dos definiciones fundamentales, que nos acompañarán a lo largo de toda la demostración.

Definición: Una propiedad (referida a los números naturales) es expresable si existe una fórmula \( P(x) \) (con \( x \) como única variable libre) tal que para todo \( n\in{\mathbb{N}} \) vale que \( n \) cumple la propiedad si y sólo si \( P(n) \) es un enunciado verdadero. (En realidad, en lugar de \( P(n) \) habría que escribir \( P(x/\overline{n}) \), donde \( \overline{n} \) es el numeral correspondiente a \( n \).)

Por ejemplo, la propiedad de "Ser un número par" (o "x es un número par") puede expresarse mediante la fórmula \( \exists{y}(x = 2\cdot{y}) \), que, estrictamente hablando, debería escribirse así: \( \exists{v_{||}}(v_| = SS0\cdot{v_{||}) \).

Otros ejemplos: es fácil ver que "Ser un número primo", "Ser un cuadrado perfecto", "Ser un número triangular" son, por ejemplo, propiedades expresables.

Definición: Una relación binaria (referida a pares de números naturales) es expresable si existe una fórmula \( P(x,y) \) (con \( x \) e \( y \) como únicas variable libres) tal que para todo par \( (n,m)\in{\mathbb{N}^2} \) vale que \( n \) está relacionado con \( m \) si y sólo si \( P(n,m) \) es un enunciado verdadero. (Con la misma aclaración de antes acerca de la escritura.)

Por ejemplo, es fácil ver que "x es un divisor de y", "x e y son coprimos" son relaciones expresables.

De la misma manera la definición puede extenderse a relaciones ternarias, etc.

25 Junio, 2009, 01:38 pm
Respuesta #118

Gustavo Piñeiro

  • Visitante
Recapitulemos un poco: el lenguaje formal nos permite, en principio, escribir afirmaciones referidas a números naturales, como por ejemplo "1 + 1 = 2". Sin embargo, queremos usar ese mismo lenguaje para hacer afirmaciones acerca de otras afirmaciones, como por ejemplo "'1 + 1 = 2' es demostrable".

Hemos definido entonces una codificación de Gödel, que a cada secuencia finita de símbolos (en particular a cada enunciado) le asigna un número natural. Al enunciado "S0 + S0 = SS0" (que es la traducción al lenguaje formal de "1 + 1 = 2") le corresponde un número natural calculable de manera efectiva y al que, para abreviar, llamaremos c.

Decir entonces que "'1 + 1 = 2' es demostrable" equivale a decir que "c es el código de un enunciado demostrable".

Para completar nuestro propósito inicial de ver que "'1 + 1 = 2' es demostrable" es traducible al lenguaje formal debemos ver que la propiedad de "Ser el código de un enunciado demostrable" es expresable.

Esto puede hacerse de (al menos) dos maneras diferentes: se puede probar como consecuencia inmediata de un teorema muy general (así se hace en "Gödel para todos") o se puede de modo más constructivo (más parecido a como lo hizo Gödel). Por diversos motivos, he decidido inclinarme aquí por el modo constructivo, que es más largo, pero más explícito y más apegado a la demostración original de Gödel.

En los sucesivos comentarios iré desarrollando esta parte de la demostración.

26 Junio, 2009, 01:32 pm
Respuesta #119

Gustavo Piñeiro

  • Visitante
Recordemos que hemos escrito a los números naturales en un sistema binario sin cero (1, 2, 11, 12, 21, 22, 111, 112,...). Al asignar los códigos de Gödel hemos procedido así: al primer símbolo del lenguaje le asignamos el número 12, al segundo el 112, al tercero el 1112, etc. A la concatenación de dos símbolos le corresponde la concatenación de sus respectivos códigos (la concatenación de dos números consiste en escribir el segundo a continuación del primero). Vamos a ver ahora que la operación de concatenación de números es expresable.

Veremos con el tiempo que, en realidad, toda la demostración del teorema de Gödel se apoya en el único hecho de que la operación de concatenación de números es expresable, ya que (como se verá también) es éste el hecho que permite expresar en el lenguaje aritmético todas las operaciones sintácticas de ese mismo lenguaje (gracias a la concatenación el lenguaje es capaz de "hablar" de su propia sintaxis).

Proposición: La operación de concatenación de números escritos en "binario sin cero" es expresable.

Demostración:


Hay que demostrar que la relación ternaria "z es la concatenación de x e y" es expresable. No es difícil ver que si \( L(y) \) es la cantidad de cifras del número \( y \) escrito en binario sin cero, entonces la concatenación de x e y se calcula como \( x\cdot{2^{L(y)}}+y \).

¿Cómo expresamos \( 2^{L(y)} \) en el lenguaje formal? Aquí vemos una de las limitaciones de este lenguaje: toda fórmula debe estar escrita con una cantidad finita y fija de símbolos. No se puede escribir "\( 2\cdot{}2\cdot{}\ldots \cdot{2} \) \( L(y) \) veces", la traducción de \( 2^{L(y)} \) debe ser más sutil.

Se puede probar que \( 2^{L(y)}-1 \) es el mayor de los números de la forma "potencia de 2, menos 1" que es menor o igual que \( y \). Por otra parte, "Ser potencia de 2" es expresable, porque equivale a "Su único divisor primo es 2".

Por lo tanto "z es la concatenación de x e y" es expresable, porque equivale a "Existe un número u tal que...

...u es una potencia de 2, menos 1.
...u es el mayor número número de esa forma que es menor o igual que y.
...z = x.(u + 1) + y."

Observación:

La importancia de la operación de concatenación de números radica en que es isomorfa a la operación de concatenación de símbolos del lenguaje. De hecho, podemos dar esta definición: una operación aritmética cualquiera es una concatenación si es isomorfa a la concatenación de símbolos de un lenguaje.

Se puede hacer esta objeión: la demostración que estamos haciendo descansa fuertemente en la escritura de los números. Esta objeción puede evitarse eligiendo una concatenación diferente, ya que existen concatenaciones que no dependen de la escritura de los números, sino que se definen a partir de propiedades intrínsecas (como, por ejemplo, la factorización en primos). La concatenación en binario sin cero tiene la ventaja técnica de que es la que permite demostrar de manera más sencilla que hay una concatenación expresable.