Introducción al Teorema de Gödel
Eduardo Alejandro Barrio
UBA - CONICET
www.accionfilosofica.com
2do Cuatrimestre de 2009
Expresabilidad dentro de L
-
Expresar una propiedad numérica: (obtener la
extensión correcta)
-
Una propiedad P es expresada por una fórmula
abierta (x) en un lenguaje aritmético L sss para
todo número n,
Si n tiene P, entonces (n) es verdadera
Si n no tiene la propiedad P,  (n) es
verdadera.
Expresar depende de la riqueza expresiva del lenguaje.
¿Puede expresarse la propiedad ser una fórmula verdadera en
PA dentro del lenguaje PA?
¿Podemos hablar acerca de (talk about) todas las funciones
recursivas en el lenguaje de la aritmética?
Capturabilidad dentro de una T
-
Capturar una propiedad numérica:
Una teoría T captura una propiedad P por una
fórmula abierta (x) en un lenguaje aritmético L
sss para todo número n,
-
-
-
Si n tiene P, entonces hay una demostración
de (n) en T
Si n no tiene la propiedad P, hay una
demostración de (n) en T.
Capturar depende de los axiomas y de las capacidades de
prueba de una teoría.
Expresabilidad  Capturabilidad
-
Expresabilidad no implica capturabilidad:
-
Hay propiedades numéricas que son expresables
que no son capturables.
-
-
La fórmula Prue(x) en T expresa la propiedad de ser
una prueba, pero ninguna fórmula puede capturar esa
propiedad.
Pero, si una teoría T captura una propiedad
numérica, entonces, la expresa.
Decibilidad y completitud respecto de la
negación
-
Resultados:
-
Toda teoría inconsistente es decidible.
-
Cualquier teoría consistente que sea completa respecto de la negación
es decidible.
-
Que una T sea decidible no quiere decir que sea completa respecto de la
negación.
Una cosa es tener un modo mecánico de decidir lo que es un teorema
(decidibilidad) y otra es tener recursos suficientes como para probar o
disprove toda fórmula del lenguaje (ejemplo de teorias p.24)
-
Los teoremas de la aritmética pueden ser enumerados efectivamente.
Lo anterior no quiere decir que la aritmética sea decidible.
Las verdades de la aritmética
-
Objetivo del capítulo 5:
-
mostrar que las verdades aritméticas no pueden ser
enumeradas efectivamente.
Las verdades de la aritmética
-
-
-
Un lenguaje formal L es suficientemente expresivo
ssi
(i) puede expresar toda relación efectivamente
decidible (hay un algoritmo que una compu podría
usar para decidir, en un número finito de pasos, si la
relación se aplica en cualquier caso dado)
(ii) puede expresar cuantificación sobre números.
Las verdades de la aritmética
-
Se necesitan 3 teoremas para mostrar que el conjunto de
verdades aritméticas no es efectivamente numerable:
-
-
-
Teorema 5.1: Si W es un conjunto de números
efectivamente enumerable, hay una función efectivamente
computable que los enumera.
Teorema 5.2: W es el dominio numérico de algún algoritmo
.
Teorema 5.3: hay un conjunto efectivamente enumerable
de números K tal que su complemento (-K) no es
efectivamente enumerable.
Las verdades de la aritmética
-
-
Teorema 5.3: hay un conjunto efectivamente enumerable
de números K tal que su complemento ( K) no es
efectivamente enumerable.
Sea We el dominio numérico del Algorítmo e
K: {e tal que eWe}
Para cualquier e, por definición, e   K ssi e We.
Por lo tanto,  K y Weno pueden ser idénticos.
Por eso,  K no es uno de los conjuntos efectivamente
numerables.
Las verdades de la aritmética
Teorema 5.4: El conjunto de verdades de un lenguaje L suficientemente expresivo no es
efectivamente enumerable.
El T. 5.3 nos dice que hay un conjunto K el cual es efectivamente
enumerable pero su complemento no lo es. Y el T. 5.1 implica que hay una
R decidible tal que n  K sss  x R(x,n)
Ya que R es decidible, R es expresable en un lenguage aritmético
suficientemente expresivo. Entonces sea R(m,n) cuando R(m,n) es
verdadera y  x R(x,n) cuando  x R(x,n) es verdadera (el lenguaje puede
expresar la cuantif. Sobre números naturales).
Tenemos que n  K ssi xR(x,n) es verdadera
Tenemos que n   K ssi  xR(x,n) es verdadera.
Supongamos que el conjunto de verdades aritméticas expresable en L fuese
efectivamente enumarable. Entonces, dada la descripción de R, podríamos
listar efectivamente todas las verdades. (incluso aquellas que hablan de K)
Cuando llegamos a una verdad de tipo “ xR(x,n)”, la encontraríamos en
un lugar de la lista. Y este procedimiento nos permitiría listar todos los
elementos de  K.
Pero, por hipótesis  K no es efectivamente enumarable. Por eso, el
conjunto de verdades no puede ser efectivamente enumerado.
Las verdades de la aritmética
- Teorema 5.5: Hay conjuntos enumerables los cuales
no son efectivamente enumerables.
-
-
-
El T 5.3 nos dice que hay conjuntos de números naturales que
no son efectivamente enumerables, pero todos los conjuntos
de números naturales son enumerables.
Sabemos por T 5.4 que el conjunto de verdades de PA no es
efectivamente enumerable. Pero ese conjunto es numerable.
Teorema 5.6: El conjunto de oraciones verdaderas
de un lenguaje suficientemente expresivo no es
axiomatizable.
-
Supongamos que lo fuera, entonces hay una T tal que sus
teoremas son todas las verdades de PA. Pero sus teoremas
serían efectivamente enumerables. Por eso, el conjunto de
verdades sería efectivamente enumerable.
Las verdades de la aritmética
-Teorema 5.7: Si T es una teoría axiomatizada correcta
(sound), T no puede ser completa respecto de la negación.
-
Supongamos que T es una teoría correcta. Entonces sus
teoremas son todos verdaderos. Entonces la falta de
equivalencia entre verdades de la teoría y teoremas debe
ser a causa de que hay una verdad que no se puede
probar. Sea A esta verdad. Entonces T no prueba A. Y ya
que No A es falsa, T tampoco la puede probar (T es sólida
y sólo prueba teoremas verdaderos) .
Aritméticas suficientemente expresivas
El T 5.7 supone la corrección de la aritmética para mostrar la
incompletitud. Pero este supuesto es innecesario para
probar que la aritmética es incompleta.
Objetivo: Cómo argumentar desde la consistencia a la
incompletitud.
Si se debilita la suposición (de la corrección a la consistencia),
necesitamos considerar T que no sólo expresen sino que
capturen las propiedades aritméticas. (es decir, T que
prueben teoremas acerca de las propiedades aritméticas).
Aritméticas suficientemente expresivas
Queremos que las demostraciones dentro de la teoría sean
capaces de atrapar, caso por caso, cualquier prueba que
se pueda hacer informalmente.
Si P es una propiedad efectivamente decidible de números,
queremos que T sea capaz de capturar P.
Una T de la aritmética es suficientemente fuerte sss captura
todas las propiedades numéricas efectivamente decidibles.
Teorema de Indecidibilidad de PA
Teorema 6.1 Ninguna teoría formal de la aritmética,
consistente, suficientemente fuerte es decidible.
Estrategia de la prueba: la suposición de que T es consistente,
capaz de capturar todas las propiedades numéricas
efectivamente decidibles y decidible conduce a
contradicción.
Consecuencia: El razonamiento matemático no puede
mecanizarse totalmente. Debe dejar de ser decidible una
teoría suficientemente expresiva que sea consistente.
Completitud respecto de la Negación
T.3.2 Cualquier T consistente que sea negación completa es
decidible.
T. 6.1 Ninguna teoría formal de la aritmética, consistente,
suficientemente fuerte es decidible.
Implican que:
Teorema 6.2 Una teoría formal de la aritmética, consistente,
suficientemente fuerte no puede ser completa respecto de
la negación.
Siempre habrá un par de fórmulas A y su negación tal que
ninguna de las dos son teoremas.
Siempre habrá fórmulas verdaderas que la T no puede decidir.
Descargar

Capítulos 5 y 6