teorema de incompletez logica

LA GACETA

521

Una demostraci´n del Teorema de Incompletitud de G¨del
o
o
por
George Boolos

George Boolos (1940–96) fue catedr´tico de Filosof´ del Massachusetts
a
ıa
Institute of Technology. El siguiente art´
ıculo apareci´ publicado con el
o
t´
ıtulo New Proof of the G¨del Incompleteness Theorem en el Notices of
o
the American Mathematical Society, 36 (1989) 388-390).Reproducimos
tambi´n una carta de Boolos al Notices: A letter from George Boolos,
e
Notices of the American Mathematical Society, 36 (1989) 676. La Gaceta agradece a la American Mathematical Society y a Sally Sedgwick
el permiso para la traducci´n y publicaci´n de este material1 .
o
o

George Boolos

De casi todos los teoremas se conocen muchas demostraciones distintas. Adem´s de
a
laprimera demostraci´n rigurosa del Teoo
´
rema Fundamental del Algebra, Gauss dio
otras tres; con posterioridad, diversos autores han encontrado muchas otras. El teorema de Pit´goras, m´s antiguo y m´s sencia
a
a
´
llo que el Teorema Fundamental del Algebra,
tiene cientos de demostraciones. ¿Hay alg´ n
u
gran teorema que s´lo tenga una demostrao
ci´n? En este art´
o
ıculo presentamos unanueva
demostraci´n sencilla del Teorema de Incomo
pletitud de G¨del en la forma siguiente:
o
No existe ning´n algoritmo cuya salida conu
tenga todos los enunciados verdaderos de la
Aritm´tica y ning´n enunciado falso.
e
u
Nuestra demostraci´n es bastante diferente
o
de las usuales y presupone s´lo una cierta fao
miliaridad con la l´gica matem´tica formal.
o
a
Es perfectamentecompleta, excepto por un
detalle t´cnico cuya demostraci´n s´lo esboe
o o
zar´.
e

1
Ambos textos de George Boolos aparecen reproducidos asimismo en el libro reciente de
Reuben Hersch, What is Mathematics, really?, Oxford University Press, Oxford, 1997

522

´
UNA DEMOSTRACION

DEL

¨
TEOREMA DE GODEL

Nuestra demostraci´n se sirve de la paradoja de Berry. Bertrand Russell,
o
envarios de sus art´
ıculos, atribu´ a G. C. Berry, bibliotecario de la Universiıa
dad de Oxford, la paradoja sobre el m´nimo entero que no puede ser definido
ı
con menos de catorce palabras. La paradoja, desde luego, estriba en que se ha
definido el tal entero con trece palabras. Sobre la paradoja de Berry dijo Bertrand Russell en cierta ocasi´n: “Tiene el m´rito de no salirse del ambito de los
oe
´
n´meros finitos”2 . Antes de comenzar, hemos de hablar, siquiera brevemente,
u
sobre algoritmos y sobre “enunciados de la Aritm´tica”, y sobre lo que “vere
dadero”o “falso”significan en el contexto que aqu´ nos concierne. Empecemos
ı
por los “enunciados de la Aritm´tica”.
e
El lenguaje de la Aritm´tica contiene los signos + y × para la adici´n y
e
o
la multiplicaci´n, un nombre 0para el cero, y un signo s para el sucesor (la
o
operaci´n de a˜adir 1). Tambi´n contiene el signo de igualdad =, as´ como los
o
n
e
ı
s´
ımbolos l´gicos ¬ (no), ∧ (y), ∨ (o), → (si . . . entonces . . . ), ←→ ( . . . s´ y s´lo
o
ı o
si . . . ), ∀ (para todo) y ∃ (para alg´n o existe), y los par´ntesis. Las variables
u
e
del lenguaje de la Aritm´tica son las expresiones x, x , x . . .construidos con
e
u
los s´
ımbolos x y : los valores que pueden tomar estas variables son los n´meros
naturales: {0, 1, 2, . . . }. Nos referiremos abreviadamente a estas variables con
las letras y, z, etc.
Con todo esto ya podemos entender suficientemente bien lo que verdadero
y falso significan en el lenguaje de la Aritm´tica; por ejemplo, ∀y∃x, x = sy
e
es un enunciado falso, por que noes cierto que todo n´mero natural x sea
u
el sucesor de alg´n n´mero natural y. (El cero es un contraejemplo: no es el
u
u
sucesor de ning´n n´mero natural.) Por otro lado,
u u
∀x∃y, (x = (y + y) ∨ x = s(y + y))
es un enunciado verdadero: porque para todo n´mero natural x hay un n´mero
u
u
natural y tal que ora x = 2y bien x = 2y + 1. Vemos tambi´n que hay muchas
e
nociones que se...