Epistemowikia
Revista «Hiperenciclopédica» de Divulgación del Saber
Segunda Época, Año IX
Vol. 8, Núm. 1: de enero a marzo de 2014
Epistemowikia es parte de
Logotipo de CALA Virtual
CALAALA | Communitas | Evolvere
Editio | Epistemowikia | Exercitatio | Fictor | Flor
Epistemowikia no se hace responsable ni se identifica necesariamente con el contenido ni las opiniones expresadas por sus colaboradores.
La Universidad de Extremadura no se hace en ningún caso responsable de los contenidos publicados en Epistemowikia.
La Asociación Conocimiento Comunal (CONOMUN) no se hace en ningún caso responsable de los contenidos publicados por terceros.

Inicio | La revista | Índex | Hemeroteca | Búsquedas | Quiénes somos | Contacto | Publica

Indecidibilidad e incompletitud

De Epistemowikia

A principios del siglo XX David Hilbert planteó un problema, un reto, que era probar que la aritmética era consistente, es decir, debe ser imposible construir dos declaraciones, que por un lado hayan sido deducidas de forma correcta a partir de los axiomas y que por otro lado se contradigan. Pero esto no era lo único, también le inquietaba la completitud de la aritmética, o lo que es lo mismo, que se pudiese demostrar como verdaderas todas las declaraciones que fuesen ciertas. Según Manuel Sacristán <<un cálculo es completo cuando se pueden demostrar en él como teoremas todos los enunciados formalmente verdaderos construibles con sus símbolos>>. Entonces Hilbert se preocupó de buscar una forma para reducir las expresiones matemáticas a símbolos con un significado claro y preciso y lograr que el problema se pudiera abordar de mejor forma. Por ello escribió un libro junto con Wilhelm Ackermann llamado Grundzüge der theoretischen Logik ("Fundamentos de la Lógica Teórica"). En el libro se planteaba si mediante el uso de reglas que permitan manipular expresiones que incluyan cuantificadores y conectivas lógicas, adjuntados a los axiomas de una teoría matemática, se podría deducir todas las proposiciones que fueran ciertas en cada estructura que cumpliera los axiomas. Dicho de otro modo, lo que se planteaba es si para todas las interpretaciones válidas de los símbolos se podría demostrar todo cuanto fuera verdadero.

Gödel encontró una respuesta para una de las cuestiones que Hilbert había propuesto y en su tesis doctoral, "La completitud de los axiomas del cálculo funcional de primer orden" demostró el teorema de completitud, es decir, que era posible demostrar todo enunciado verdadero en el sistema de la lógica de predicados de primer orden. Sin embargo, no demostraba que a partir de los axiomas aceptados en la teoría de números se pudiera demostrar todo enunciado verdadero referente a los números naturales. Además existe un pequeño conflicto: Según el teorema de completitud se pueden demostrar todos los enunciados que se siguen de los axiomas, pero si uno de esos enunciados es cierto para los números naturales y no lo es para otro sistema de entidades que también satisfaga los axiomas, entonces ese enunciado no se puede demostrar. Los matemáticos del momento estaban tranquilos porque confiaban en que no existieran entidades que se disfrazaran de números para diferir de ellos en aspectos esenciales. Por esto el teorema que poco después expondría Gödel produciría una gran sorpresa y revolución.


En 1930 Gödel probó que existían proposiciones en la aritmética que no se podían demostrar que eran ciertas pero tampoco que eran falsas. Esas proposiciones eran indecidibles. Este hecho tiró abajo la idea perseguida por todos los matemáticos de poder demostrar cualquier proposición como cierta o falsa a través de las reglas de inferencia.


Poco después, como consecuencia de la indecidibilidad, Gödel publicó su segundo teorema, el de la incompletitud, que dice que la lógica de predicados de orden superior, la que incluye la aritmética, no puede ser a la vez completa y consistente. Entonces debe existir algún enunciado referente a los números naturales que no se pueda demostrar pero que sea verdadero, es decir, hay entidades que siguen a los axiomas de la teoría de números pero que dajan de comportarse como tales en otros aspectos.


Gödel no pensaba que sus teoremas de incompletitud demostrasen que el método axiomático fuera inadecuado. Él lo que creía es que esos teoremas demostraban que la deducción de teoremas no puede mecanizarse y que para la investigación matemática era necesaria la intuición.


Entonces, con este teorema vemos que tenemos un sistema formal, que es lo bastante complejo como para describir la teoría de números, pero que no puede ser completo, es decir, no tenemos un sistema de axiomas que nos permita formular esa teoría de números de forma que la proposiciones resultantes se puedan demostrar. Pero dicha teoría de números es una parte fundamental de las matemáticas, así que éstas no se pueden formular como un sistema axiomático completo y se podrán tener verdades matemáticas que no se puedan demostrar.


Según Nagel y Newman, <<las principales conclusiones a las que llegó Gödel fueron dos. Demostró: 1) que es imposible presentar una prueba metamatemática de la consistencia de un sistema lo bastante comprensivo como para contener toda la aritmética, a menos que se empleen reglas de deducción que difieran esencialmente de las reglas de transformación utilizadas para derivar teoremas dentro del sistema, y 2) que la potencia del método axiomático es fundamentalmente limitada.

Los pasos principales de la argumentación de Gödel fueron:

I. Mostró cómo construir una fórmula G que represente la declaración metamatemática ‘La fórmula G no es demostrable’.
II. Mostró que G es demostrable si, y solo si, es demostrable su negación formal. En cualquier caso, si una fórmula y su negación son ambas formalmente demostrables, el correspondiente cálculo es inconsistente. Es decir que, si el cálculo es consistente, entonces ni G ni la negación de G son formalmente derivables de los axiomas de la aritmética. O sea, que si la aritmética es consistente, entonces G es una fórmula formalmente indecidible.
III. Mostró también que, aunque G no sea formalmente demostrable, es sin embargo una fórmula verdadera.
IV. Mostró así mismo que, dado que G es al mismo tiempo verdadera y formalmente indecidible, los axiomas de la aritmética adolecen de incompletud. Es decir, que no es posible deducir todas las verdades aritméticas de los axiomas.
V. Describió la manera de construir una fórmula aritmética A que represente la proposición metamatemática ‘La aritmética es consistente’, y mostró que la fórmula ‘A si y solo si G’ es formalmente demostrable. Tras lo cual probó que la fórmula A no es demostrable. De donde se desprende que la consistencia de la aritmética no puede ser establecida por un argumento representable en el cálculo aritmético formal. >>


Los conceptos y los métodos que aparecen con la incompletitud tienen un papel muy importante en la teoría de recursión, lo cual afecta a toda la informática moderna. Generalizando las ideas de Gödel se ha llegado a deducir distintos resultados relacionados con los límites de los procedimientos computacionales. Uno de ellos es la irresolubilidad del "problema de la detención", que consiste en decidir si se detendrá o se quedará dando vueltas en un bucle infinito un ordenador arbitrario con un programa y unos datos arbitrarios. Otro resultado es la demostración de que no hay ningún programa que no altere el S.O. de un ordenador y pueda detectar todos los programas que sí lo alteren (virus).


Fuentes

http://paginaspersonales.deusto.es/abaitua/konzeptu/nlp/godel.htm

http://boards5.melodysoft.com/app?ID=canalingenio&msg=162

http://www.wikilearning.com/incompletitud-wkccp-20769-3.htm

http://www.wikilearning.com/indecidibilidad-wkccp-20769-4.htm

Fuente de la imagen: http://www.cibernous.com/autores/kgodel/teoria/biografia.html


Bibliografía

- BELLÈ, D. & PARLAMENTO, F.. Undecidability in Weak Membership Theories. En Ursini, Aldo & Paolo Agliano (eds.) Logic and Algebra. Marcel Dekker. New York. 1996.

- BHATTACHARYA, P. B. , JAIN, S. K. & NAGPAUL S. R. Basic Abstract Algebra. Cambridge University Press. Cambridge. (2nd ed.) 1994

-BÜCHI, J. R.. Turing Machines and the Entscheidungsproblem. Math. Annalen 148 ,pp. 201-213. 1962

- BOOLOS, G. JEFFREY, R. Computability and Logic. Cambridge University Press. Cambridge. 1974

- CHANG, C.C., KEISLER, H. J. Model theory. North-Holland. Amsterdam. 1974

- CHURCH, A. . A note on the Entscheidungsproblem. Journal of Symbolic Logic. Vol. 1, pp. 40-41; A correction, ibid., pp. 101-102. 1936 (reimpreso en M. Davis. The Undecidable)

- CHURCH, A. & QUINE, W. V. Some Theorems on definability and decidability. Journal of Symbolic Logic. Vol. 17, n. 3. 1952

- COLLINS, G.E. & HALPERN, J. D. On the interpretability of arithmetic in set theory. Notre Dame Journal of Formal Logic, Vol. 11, pp. 477-483. 1970

- CUTLAND, N. Computability. Cambridge University Press. Cambridge. 1980

- DAVIS, M. Computability and Unsolvability. McGraw- Hill . New York. 1958 (2ºed. Dover 1982)

- DAVIS, M (ed.) The Undecidable. Basic papers on undecidable propositions, unsolvable problems and computable functions. Raven Press. New York. 1965 (Correcciones a la traducción en Bauer-Mengelberg, Stefan Journal of Symbolic Logic vol 31, pp. 484-494.1966 )

- DAVIS, M. Unsolvable problems. En J. Barwise (ed). Handbook of mathematical logic. North-Holland. Amsterdam. 1977.

- EBBINGHAUS, H.-D., FLUM, J & THOMAS, W.. Mathematical Logic. Springer- Verlag. New York. 1984.

- EPSTEIN, R. L. & CARNIELLI, W. A. Computability. Computable Functions, Logic and the Foundations of Mathematics. Wadsworth & Brooks. Pacific Grove. 1989.

- ERSHOV, YU. L., LAVROV I. A., TAIMANOV A. D., TAISTSLIN M. A. Elementary Theories. Russian Mathematical Surveys , vol 20, pp. 35-105. 1965

- ERSHOV, YU. L. Definability and computability. Consultants Bureau. New York. 1996

- FEFERMAN , S. Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae. Vol. 49, 35-92. 1960

- FEFERMAN , S. Deciding the Undecidable: Wrestling with Hilbert’s Problems. En In the light of logic. Oxford University Press. New York. 1998

- GÖDEL, K. Über formal unentsheidbare Sätze der Principia Mathematica und verwandter Systeme. I. Monatshefte für Mathematik und Physik, vol 38, pp. 173-198. 1931 (Traducción inglesa en Davis, The Undecidable, Raven Press. New York pp 39-74)

- GRZEGORCZYK, A. Undecidability of Some Topological Theories. Fundamenta Mathematicae. Vol 38, pp. 137-151. 1951

- HRBACEK, K & JECH, T. Introduction to Set Theory. M. Dekker. New York.(2ªed.) 1984

- HUBER DYSON, V. On the decision problem for theories of finite models. Israel Journal of Mathematics. 1, pp 55-70. 1964

- HUBER DYSON, V. On the decision problem for extensions of a decidable theory.Fundameta Mathematicae, 64, pp 7-70. 1979

- JANICZAK, A. Undecidability of Some Simple Formalized Theories Fundamenta Mathematicae. Vol. 40, pp. 131-139. 1953

- KLEENE, S. C. A symmetric form of Gödel’s theorem. Indagationes mathematicae. Vol. 12. pp 244-246. 1950

- KLEENE, S. C. Introduction to Metamathematics. North Holland. Amsterdam. 1952

- KREISEL, G. Models, Translations and Interpretations. En Mathematical Interpretation of Formal Systems L. E. J. Brouwer, E. W. Beth & A. Heyting (eds.) North-Holland. Amsterdam. 1955

- KULIKOV N. A. Definability of graphs by congruence lattices. Algebra i Logica. Vol. 24. 1, pp 13-25. 1985

- MAL’CEV A. I. Effective inseparability of the set of identically true from the set of finitely refutable formulas of certain elementary theories. Amer. Math. Soc. Trans. 2, 45, pp. 1005-1008. 1965. (Soviet Math. 2 1961)

- MAL’CEV A. I. On a correspondence between rings and groups. Amer. Math. Soc. Trans. 2, 45. 1965

- MAL’CEV, A. I. The metamathematics of algebraic systems (Collected papers:1936-1967) North-Holand. Amsterdam. 1971

- MAL’CEV, A. I. Undecidability of the elementary theory of finite groups. Soviet Math. 2, pp 714-717. 1961

- MARCJA , A., PREST, M & TOFFALORI, C. On the Undecidability of some classes of abelian-by-finite groups. Annals of Pure and Applied Logic 62, pp. 167-173. 1993

- MEL’NICHUK I. L. Unsolvability of problems of equality and divisibility in certain varieties of semigroups. Algebra i Logica Vol. 23, 4, pp 430-438. 1984

- MENDELSON, E. Introduction to Mathematical Logic. Chapman & Hall, Englewood Cliffs, New Jersey. (fourth ed.)1997

- MINSKY, M. L. Computation : Finite and Infinite Machines. Prentice-Hall. London. 1967

- MONK, J. D. Mathematical Logic. Springer-Verlag. New York. 1976

- MONTAGNA F & MANCINI, A. A Minimal Predicative Set Theory. Notre Dame Journal of Formal Logic. Vol. 35, 2, pp 186-203. 1994

- MOSCHOVAKIS Y. N. Notes on Set Theory. Springer-Verlag. New York. 1994

- MYHILL, J. Creative Sets. Zeitschr. f. math. Logik und Grundlagen d. Math. Bd I S. pp. 97-108. 1955

- MUZALEWSKI, M. Restricted Problems in Some Classes of Algebraic Systems. Zeitschr. f. math. Logik und Grundlagen d. Math. Bd. 24, S, pp. 279-287, 1978

- ODIFREDDI, P. Classical Recursion Theory. North-Holland. Amsterdam. 1989.

- PAL’CHUNOV, D.E. Undecidability of theories of Boolean algebras with selectedideals . Algebra i logica. Vol. 25, n. 3, pp. 326-346. 1986.

- PRIDA, J. F. Una caracterización topológica de las clases D-elementales. En J. Echeverría, J. de Lorenzo, L. Peña (eds.) Calculemos... Matemáticas y libertad Trotta.Valladolid. 1996

- PRIDA, J. F. A Nonstandard Approach to Arithmetic. Rev. R. Acad. Cienc. Exact. Fís. Nat. Vol. 93, n. 2. pp. 227-229. 1999

- RABIN, M. O. On recursively enumerable and arithmetic models of set theory. Journal of Symbolic Logic. Vol. 23, n. 4. 1958

- RABIN, M. O. A simple method for undecidability proofs and some applications. Logic, Methodology and Philosophy of Science (Proc. 1964 Internat. l Congr.) North-Holland. Amsterdam. pp. 58-68. 1965

- ROBINSON, J.. Definability and Decision Problems in Arithmetic. Journal of Symbolic Logic. Vol. 14, n. 2. 1949

- ROBINSON, D. J. S. A Course in the Theory of Groups. Spinger-Verlag. New York. 1993

- ROGERS, H.. Certain Logical Reduction and Decision Problems. Annals of Mathematics. Vol. 64, n. 2. 1956

- ROGERS, H. Theory of Recursive Functions and Effective Computability. McGraw-Hill. New York. 1967

- ROSSER, J. B. Extensions of some theorems of Gödel and Church. Journal of Symbolic Logic. Vol. 1, pp. 87-91. 1936 (También en Davis, The Undecidable, pp. 231-235)

- SHOENFIELD, J. Mathematical Logic. Addison-Wesley. Reading. 1967

- SKOLEM, TH. Selected Works in Logic. Universitetsforlaget. Oslo. 1970

- SMORYNSKI, C.. Review of [Ershov 1965] Journal of Symbolic Logic. Vol. 39, n.3. 1974.

- SMULLYAN R. M. Theory of Formal Systems. Princeton University Press. Princeton 1961

- SMULLYAN R. M. Diagonalization and Self-Reference. Clarendon Press. Oxford. 1994

- SPREEN, D. Effective inseparability in a topological setting. Annals of pure and Applied Logic. Vol. 80, pp. 257-275. 1996

- SUPPES, P. Axiomatic Set Theory. Dover. New York 1972

- TARSKI A, MOSTOWSKI A., ROBINSON R. M. Undecidable theories. North- Holland. Amsterdam. 1953

- TOFFALORI, C.. An undecidability theorem for lattices over group rings. Annals of Pure and Applied Logic. Vol. 88, pp. 241-262. 1997

- TURING, A. M. On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, ser 2 , vol. 42, pp 230-265, 1936-37; Correction, ibid. vol 43, pp. 544-546, 1937. (Reimpreso en Davis, The Undecidable, pp. 115-153)

- URSINI, A. & AGLIANO, P. (eds.) Logic and Algebra. (Lecture Notes in Pure and Applied Mathematics, 180) Marcel Dekker. New York. 1996.

- VAUGHT R. On a theorem of Cobham concerning undecidable theories. Proc. Logic, methodology and Philosophy of Science 1960. Intern. Congress. Stanford University Press. Stanford. 1962

- WILLARD, R. Hereditary Undecidability of Some Theories of Finite Structures. Journal of Symbolic Logic. Vol. 59, n. 4. 1994


Licencia









Esta obra se publica multilicenciadamente con las siguientes licencias. Por tanto, usted es libre de reproducir, distribuir, comunicar públicamente, interpretar y transformar, por cualquier medio, con o sin ánimo de lucro, la presente obra, en cualquier momento o lugar, licenciando o multilicenciando, según sea el caso, la obra original o la obra derivada, con una de las siguientes licencias o con un subconjunto de ellas:





Herramientas personales