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
Numeración de Gödel
•
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:
ESQUEMA DE CODIFICACIÓN
Símbolo
¬ ∧ ∨ →↔ ∀ ∃ = ( ) 0 S + x x y z …
s
1 1 1 1 1 2 2 2 2
Código c 1 3 5 7 9
2 4 6 …
1 3 5 7 9 1 3 5 7
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ímbolo
¬ ∧ ∨ →↔ ∀ ∃ = ( ) 0 S + x x y z …
s
1 1 1 1 1 2 2 2 2
Código c 1 3 5 723 9
2 4 6 …
3 5 7 9 1 3 5 7
• S tiene g. n. 2 = 18388608
• SS0
tiene g. n.
calculadora)
• ∃y(S0+y)=SS0
23
2
.
23
3
.
21
5
= (no llega la
tiene g. n. 213 . 34 . 517 . 723 .
21
25
4
19
15
23
23
21
11 . 13 . 17 . 19 . 23 . 29 . 31 . 37
= (un número muy grande)
• 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.
• 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.
CODIFICANDO
SECUENCIAS de
expresiones
•
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?
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 s0 es ∃ o s0 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:
• Terminar
¬Free(n) ∧ Wff(n)
•
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
•
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
•
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-1gi-1), gi)):
•
Responder: false
•
Terminar
Si gk = n:
•
Responder: true
•
Terminar
Si no:
•
Responder: false
•
Terminar
Hasta ahora
•
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.
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
•
Ahora bien, si escribimos ⎡S⎤dentro de una fórmula, ⎡S⎤es
equivalente a escribir su numeral: SSSSS…0, con 8388608
apariciones de S.
= 8388608.
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.
Descargar

Aritmetización de la Sintaxis