La aritmetización de la sintaxis

Capítulo 15

INTRODUCCIón

• El objetivo será establecer una relación entre las expresiones de una teoría formal y un código numérico.

• En particular, vamos a intentar asociar las expresiones del lenguaje de la aritmética LA con números. Luego lo haremos para secuencias de expresiones.

• Veremos, entonces, que existe un correlato entre ciertas propiedades sintácticas y ciertas propiedades numéricas.

• ¿Podremos decir que ciertas propiedades sintácticas “son” propiedades numéricas? Disctutir.

• Existe más de una forma de asociar expresiones sintácticas con números.

• Sin embargo, vamos a presentar la idea original de Gödel.

• Ésta es la clave para “hacer hablar” a la matemática de sí misma.

• Pero antes, vamos a contar algunos resultados matemáticos involucrados en la idea original de Gödel.

TEOREMA FUNDAMENTAL DE LA ARITMÉTICA

• Todo número natural mayor que 1 se puede representar de forma única (salvo por el orden de los factores) como el producto de números primos. Llamaremos a dicha representación: factorización de un número.

• 6936 = 2 . 2 . 2 . 3 . 17 . 17 = 23 . 31 . 172

• 1200 = 2 . 2 . 2 . 2 . 3 . 5 . 5 = 24 . 31 . 52

• Este teorema requiere dos demostraciones clásicas: existencia y unicidad.

¿qué es un número primo?

•Se dice que un número natural p es primo si y sólo si tiene exactamente dos divisores: 1 y p (uno y sí mismo)

•¿El número 1 es primo?

•¿Cuántos primos pares hay?

•¿Cuántos números primos hay? ¿Por qué?

•La propiedad de ser primo es verificable en una serie finita de pasos mecánicos. (11.8 R3. Prime(n) es p.r)

• Algoritmo:

• Dado un número natural n

• Si n = 1:

• Responder: n no es primo

• Terminar

• Si no:

• Para cada número primo pi ≤ √n:

• Realizar la división entera de n por pi

• Si el resto de dividir n por pi es igual a 0:

• Responder: n no es primo

• Terminar

• Si no:

• Continuar

• Responder: n es primo

• Terminar

•A partir del algoritmo anterior, podemos construir otro algoritmo que genere la lista de todos los números primos. (11.8 R4. π(n) es p. r.)

•La factorización de un número se puede obtener en una serie finita de pasos mecánicos.

• Algoritmo:

• Dado un número natural n ≥ 2

• Para cada número primo pi ≤ √n:

• c = 0

• Mientras n sea divisible por pi:

• n = n div pi

• c = c + 1

• Si c > 0:

• Responder: pic.

• Continuar

• Si no:

• Continuar

• Responder: 1

• Terminar

• Sea el lenguaje de la aritmética LA con los símbolos lógicos usuales (conectivas, cuantificadores, identidad, paréntesis), los símbolos de cero y sucesor y las funciones suma y multiplicación.

• Vamos a codificar a los símbolos anteriores con números impares.

• Además, en el lenguaje de la aritmética, tenemos una cantidad inagotable de variables.

• A estas últimas las vamos a numerar con números pares.

• Entonces, obtenemos el siguiente esquema de codificación:

Numeración de Gödel

Símbolo s

¬ ∧ ∨ → ↔ ∀ ∃ = ( ) 0 S + x x y z …

Código c

1 3 5 7 911

13

15

17

19

21

23

25

27

2 4 6 …

ESQUEMA DE CODIFICACIÓN

Sea la expresión e una secuencia de k+1 símbolos de LA s0, s1, s2,… sk.

El número de Gödel (g. n.) de la expresión e se calcula multiplicando los primeros k+1 números primos πi, cada uno elevado a la

potencia ci, donde ci es el código del símbolo si (con i desde 0 hasta k).

•S tiene g. n. 223 = 8388608

•SS0 tiene g. n. 223 . 323 . 521 = (no llega la calculadora)

•∃y(S0+y)=SS0 tiene g. n. 213 . 34 . 517 . 723 . 1121 . 1325 . 174 . 1919 . 2315 . 2923 . 3123 . 3721 = (un número muy grande)

Símbolo s

¬ ∧ ∨ → ↔ ∀ ∃ = ( ) 0 S + x x y z …

Código c

1 3 5 7 911

13

15

17

19

21

23

25

27

2 4 6 …

•Otra forma de verlo:

•Dada una expresión del lenguaje, considerar la cadena de símbolos involucrada.

•Utilizar los números primos para codificar la posición de cada símbolo dentro de la cadena.

•Elevar cada número primo a la potencia correspondiente según el esquema de codificación.

•Multiplicar.

•En forma análoga, se pueden asociar expresiones de distintos lenguajes formales con números modificando el esquema de codificación.

•Tenemos un procedimiento mecánico para ver si un número es primo o no.

•Tenemos un procedimiento mecánico para factorizar números.

•Tenemos un procedimiento mecánico para codificar expresiones de un lenguaje formal.

•A partir de nuestro esquema de codificación anterior, tenemos dos algoritmos:

•Uno para transformar una expresión en un número.

•Otro para transformar un número en una expresión.

• Dada una secuencia de expresiones de un lenguaje:

• e0, e1, e2,… en

• Codificarlas con su número de Gödel correspondiente:

• g0, g1, g2,… gn

• Y luego volver a utilizar los números primos:

• 2g0 . 3g1 . 5g2 … πgn

• ¿Podemos codificar secuencias de secuencias?

CODIFICANDO SECUENCIAS de

expresiones

Propiedades sintácticas como propiedades numéricas.

• Ahora vamos a intentar definir algunas propiedades sintácticas como propiedades numéricas.

• Term(n) es verdadero sii la expresión de código n es un término de LA.

• Atom(n) es verdadera sii la expresión de código n es una fórmula atómica de LA.

• Wff(n) es verdadera sii la expresión de código n es una fórmula bien formada de LA.

• Sent(n) es verdadera sii la expresión de código n es una sentencia de LA.

• Prf(m, n) es verdadera sii m es el código de la demostración de la sentencia de código n.

• ¿Las funciones anteriores son verificables en un número finito de pasos mecánicos? ¿Cómo?

• Comencemos con Term(n).

• Recordemos del capítulo 4.3:

• Los símbolos no lógicos de LA son {S, 0, +, ×}

• 0 es una constante.

• S es una función de ariadad 1.

• + y × son funciones de aridad 2.

• +(a, b)

• ×(a, b)

• Luego, por comodidad, nos permitimos escribir cosas como (a+b) o (a×b).

• Luego, la definición recursiva:

• 0 es un término

• Las variables son términos

• Si φ y ψ son términos, entonces +(φ, ψ) y ×(φ, ψ) son términos.

• Nada más es un término.

• Term(n):

• Decodificar n y obtener e = s0s1s2…sk, dónde cada

si es un símbolo de LA y la longitud de e es k+1

• Si k = 0 y s0 es 0 o s0 es una variable (x, y, z…):

• Responder: true

• Terminar

• Si no:

• Si s0 es S:

• Sea e’ = s1s2…sk

• Responder: Term(⎡e’ )⎤

• Terminar

• Si s0 es + o s0 es ×:

• Sea e’’ = s2s3…sk-1

• Para símbolo s de e’’:

• Si sj es ,:

• Sea a = s2s3…sj-1 y sea b = sj+1sj+2…sk-1

• Responder: Term(⎡a )⎤ ∧ Term(⎡b )⎤

• Terminar

• Si no:

• Continuar

• Responder: false

• Terminar

• El único símbolo de predicado de LA es la identidad, por lo cual las fórmulas atómicas son todas de la forma (φ = ψ). Suponemos que siempre aparecen los paréntesis.

• Atom(n):

• Decodificar n y obtener e = s0s1s2…sk, dónde cada si es un símbolo de LA y la longitud de e es k+1

• Sea e’ = s1s2s3…sk-1

• Para cada simbolo s de e’:

• Si sj es =:

• Sea a = s1s2…sj-1 y sea b = sj+1sj+2…sk-1

• Responder: Term(⎡a )⎤ ∧ Term(⎡b )⎤

• Terminar

• Si no:

• Continuar

• Responder: false

• Terminar

• Las fórmulas bien formadas de LA se construyen a partir de las fórmulas atómicas y la aplicación de conectivas lógicas y cuantificadores. De nuevo, suponemos todos los paréntesis.

• Wff(n):

• Decodificar n y obtener e = s0s1s2…sk, dónde cada si es un

símbolo de LA y la longitud de e es k+1

• Si s0 es o s∀ 0 es o s∃ 0 es ¬:

• Sea e’ = s1s2…sk

• Para cada simbolo s de e’:

• Si sj no es una variable:

• Responder: Wff(⎡e’ )⎤

• Terminar

• Si no:

• Continuar

• Si no:

• Si Atom(e):

• Responder: true

• Terminar

• Si no:

• Recorrer los símbolos de e contando los paréntesis para deducir cuál es la conectiva

principal: → ↔∧ ∨

• Sacar los paréntesis exteriores.

• Separar la expresión en dos partes a partir de

la conectiva principal.

• Responder: Wff(a) ∧ Wff(b)

• Terminar

•Hasta ahora, con las fórmulas bien formadas, permitimos variables libres.

•Las sentencias son fórmulas bien formadas cerradas, es decir, sin variables libres.

•Free(n) es verdadera sii la expresión de código n no tiene variables libres: el algoritmo deberá recorrer los símbolos de la expresión, contar las variables y los paréntesis.

•Sent(n):

•Responder: ¬Free(n) ∧ Wff(n)

•Terminar

• Falta la más importante:

• Prf(m, n) es verdadera sii m es el código de la demostración de la sentencia de código n.

• Una demostración es una secuencia finita de sentencias donde cada una de ellas es:

• Una instancia de un esquema de axioma.

• El resultado de la aplicación del modus ponens en sentencias anteriores.

• El resultado de la instanciación de un cuantificador universal.

• Ya mostramos antes cómo codificar secuencias de expresiones.

•Axiom(n): es verdadera sii n es el código de una sentencia que es una instancia de un esquema de axioma.

•Axiom(n) es computable porque los axiomas son recursivos.

•MP(m, n): es verdadera sii la sentencia de código n se puede obtener a partir de aplicar modus ponens a por lo menos dos sentencias de la secuencia de sentencias de código m.

•Univ(m, n): es verdadera sii la sentencia de código n se puede obtener a partir de instanciar un cuantificador universal de alguna sentencia de la secuencia de sentencias de código m.

• MP(m, n):

• Decodificar m y obtener los códigos de las sentencias de la

secuencia g0,g1,g2...gk

• Decodificar n y obtener t

• Para cada gi:

• Decodificar gi y obtener ei

• Para cada gj:

• Decodificar gj y obtener ej

• Si se puede aplicar modus ponens en ei y ej de manera tal de

obtener t:

• Responder: true

• Terminar

• Si no:

• Continuar

• Responder: false

• Terminar

• Univ(m, n):

• Decodificar m y obtener los códigos de las sentencias de la

secuencia g0,g1,g2...gk

• Decodificar n y obtener t

• Para cada gi:

• Decodificar gi y obtener ei

• Si a partir de ei se puede obtener t por instanciación de un cuantificador universal:

• Responder: true

• Terminar

• Si no:

• Continuar

• Responder: false

• Terminar

• Prf(m, n):

• Decodificar m los códigos de las sentencias de la

demostración d = g0,g1,g2...gk

• Para cada gi de d:

• Si ¬(Axiom(gi) ∨ MP(∏(πi-1gi-1), gi) ∨ Univ(∏(πi-1

gi-1), gi)):

• Responder: false

• Terminar

• Si gk = n:

• Responder: true

• Terminar

• Si no:

• Responder: false

• Terminar

• Teorema: Term(n), Atom(n), Wff(n), Sent(n) y Prf(m, n) son funciones primitivas recursivas.

• Demostramos que son computables sólo utilizando ciclos.

• La demostración rigurosa es bastante más compleja.

Hasta ahora

UN POCO DE Notación

• Si φ es una expresión del lenguaje formal L, entonces ⎡φ⎤ es el número de Gödel (g. n.) de la expresión φ.

• Dentro de una fórmula ⎡φ⎤ va a ser igual a escribir el numeral correspondiente a ⎡φ⎤. Por ejemplo:

• Para la expresión S, ⎡S⎤= 223 = 8388608.

• Ahora bien, si escribimos ⎡S⎤dentro de una fórmula, ⎡S⎤es equivalente a escribir su numeral: SSSSS…0, con 8388608 apariciones de S.

Diagonalización

• La diagonalización de φ es ∃y(y=⎡φ⎤∧ φ)

• Teorema: existe una función primitiva recursiva diag(n) que devuelve el número de Gödel de la diagonalización de la fórmula bien formada de código n.