Геделове теореме о непотпуности

У математичкој логици, Геделове теореме о непотпуности су две теореме о ограничењима формалног система, које је доказао Курт Гедел, 1931. године.

Ове теореме показују да не постоји потпун и конзистентан формални систем који коректно описује природне бројеве и да ниједан довољно строг систем који описује природне бројеве не може да потврди своју сопствену конзистентност. При томе, у математичкој логици, неки формални систем сматра се конзистентним ако не садржи контрадикције (за сваку пропозицију φ не могу у исто време и φ и њој противречна ¬φ бити доказиве), а систем је потпун ако је довољан да се на њему изгради одговарајућа теорија у целини.

Ове теореме су широко прихваћене као доказ да је немогуће остварити Хилбертов програм проналажења потпуног и конзистентног скупа аксиома који би важио за целу математику. Или другим речима, немогуће је пронаћи неки универзални систем аксиома из којег би аутоматски следио и доказ о непротивуречности теорије која би била изграђена на бази тог система. Напротив, непротивречност неког система аксиома своди се на непротивречност неког другог система аксиома који се већ сматра непротивречним.

Као пример тога може се навести однос између еуклидске и неке од варијанти нееуклидских геометрија, рецимо геометрије Лобачевског. Наиме, непротивречност геометрије Лобачевског, која је настала негацијом Еуклидовог петог постулата (аксиоме паралелности), доказује се у ствари непротивречношћу еуклидске геометрије, где такође важи и обрнуто. С друге стране, проблем независности система аксиома своди се на проблем непротивречности. Или у конкретном примеру, независност Еуклидовог петог постулата у односу на остале постулате еуклидске геометрије доказује се непротивречношћу геометрије Лобачевског.

Прва теорема о непотпуности

Геделова прва теорема о непотпуности је вероватно најславнији резултат у математичкој логици. Она тврди да:

За било коју формалну теорију која потврђује основне аритметичке истине, може се конструисати аритметичко тврђење које је истинито али није и доказиво унутар саме те теорије. То значи, да било која теорија која је способна да изрази елементарну аритметику не може бити у исто време и конзистентна и потпуна.

Литература

• —, 1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I", in Solomon Feferman, ed., 1986. Kurt Gödel Collected works, Vol. I. Oxford University Press, pp. 144–195. ISBN 978-0195147209. The original German with a facing English translation, preceded by an introductory note by Stephen Cole Kleene.
• —, 1951, "Some basic theorems on the foundations of mathematics and their implications", in Solomon Feferman, ed., 1995. Kurt Gödel Collected works, Vol. III, Oxford University Press, pp. 304–323. ISBN 978-0195147223.
• B. Meltzer (translation) and R. B. Braithwaite (Introduction), 1962. On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Dover Publications, New York (Dover edition 1992), ISBN 0-486-66980-7 (pbk.) This contains a useful translation of Gödel's German abbreviations on pp. 33–34. As noted above, typography, translation and commentary is suspect. Unfortunately, this translation was reprinted with all its suspect content by

• Stephen Hawking editor, 2005. God Created the Integers: The Mathematical Breakthroughs That Changed History, Running Press, Philadelphia, ISBN 0-7624-1922-9. Gödel's paper appears starting on p. 1097, with Hawking's commentary starting on p. 1089.

• Martin Davis editor, 1965. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions, Raven Press, New York, no ISBN. Gödel's paper begins on page 5, preceded by one page of commentary.
• Jean van Heijenoort editor, 1967, 3rd edition 1967. From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931, Harvard University Press, Cambridge Mass., ISBN 0-674-32449-8 (pbk). van Heijenoort did the translation. He states that "Professor Gödel approved the translation, which in many places was accommodated to his wishes." (p. 595). Gödel's paper begins on p. 595; van Heijenoort's commentary begins on p. 592.
• Martin Davis editor, 1965, ibid. "On Undecidable Propositions of Formal Mathematical Systems." A copy with Gödel's corrections of errata and Gödel's added notes begins on page 41, preceded by two pages of Davis's commentary. Until Davis included this in his volume this lecture existed only as mimeographed notes.
• George Boolos, 1989, "A New Proof of the Gödel Incompleteness Theorem", Notices of the American Mathematical Society, v, 36, pp. 388–390 and p. 676, reprinted in Boolos, 1998, Logic, Logic, and Logic, Harvard University Press. ISBN 0-674-53766-1
• Buldt, Bernd (2014). „The Scope of Gödel's First Incompleteness Theorem”. Logica Universalis. 8 (3–4): 499—552. S2CID 255407764. doi:10.1007/s11787-014-0107-3. 
• Charlesworth, Arthur (1981). „A Proof of Godel's Theorem in Terms of Computer Programs”. Mathematics Magazine. 54 (3): 109—121. JSTOR 2689794. doi:10.2307/2689794. 
• Martin Davis, 2006, "The Incompleteness Theorem", . Notices of the AMS (PDF). 53 (4): 414 https://www.ams.org/notices/200604/fea-davis.pdf.  .
• Jean van Heijenoort, 1963, "Gödel's Theorem" in Edwards, Paul, ed., Encyclopedia of Philosophy, v. 3. Macmillan, pp. 348–57.
• Geoffrey Hellman (1981). „How to Gödel a Frege-Russell: Gödel's Incompleteness Theorems and Logicism”. Noûs. 15 (4): 451—468. JSTOR 2214847. doi:10.2307/2214847. 
• David Hilbert, 1900, "Mathematical Problems." English translation of a lecture delivered before the International Congress of Mathematicians at Paris, containing Hilbert's statement of his Second Problem.
• Martin Hirzel, 2000, "On formally undecidable propositions of Principia Mathematica and related systems I.." An English translation of Gödel's paper. Archived from the original. Sept. 16, 2004.
• Kikuchi, Makoto; Tanaka, Kazuyuki (1994). „On Formalization of Model-Theoretic Proofs of Gödel's Theorems”. Notre Dame Journal of Formal Logic. 35 (3 mr=1326122). doi:10.1305/ndjfl/1040511346. CS1 одржавање: Недостаје усправна црта (веза)
• Kleene, S. C. (1943). „Recursive predicates and quantifiers”. Transactions of the American Mathematical Society. 53 (1): 41—73. doi:10.1090/S0002-9947-1943-0007371-8.  in Martin Davis 1965, The Undecidable (loc. cit.) pp. 255–287.
• Panu Raatikainen, 2015, "Gödel's Incompleteness Theorems", Stanford Encyclopedia of Philosophy. Accessed April 3, 2015.
• Raattkainen, Panu (2005). „On the Philosophical Relevance of Godel's Incompleteness Theorems”. Revue Internationale de Philosophie. 59 (4): 513—534. S2CID 52083793. doi:10.3917/rip.234.0513. .
• John Barkley Rosser, 1936, "Extensions of some theorems of Gödel and Church", reprinted from the Journal of Symbolic Logic, v. 1 (1936) pp. 87–91, in Martin Davis 1965, The Undecidable (loc. cit.) pp. 230–235.
• —, 1939, "An Informal Exposition of proofs of Gödel's Theorem and Church's Theorem", Reprinted from the Journal of Symbolic Logic, v. 4 (1939) pp. 53–60, in Martin Davis 1965, The Undecidable (loc. cit.) pp. 223–230
• C. Smoryński, 1982, "The incompleteness theorems", in Jon Barwise, ed., Handbook of Mathematical Logic, North-Holland, pp. 821–866. ISBN 978-0-444-86388-1
• Willard, Dan E. (2001). „Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles”. The Journal of Symbolic Logic. 66 (2): 536—596. JSTOR 2695030. S2CID 2822314. doi:10.2307/2695030. 
• Zach, Richard (2003). „The Practice of Finitism: Epsilon Calculus and Consistency Proofs in Hilbert's Program” (PDF). Synthese. Springer Science and Business Media LLC. 137 (1): 211—259. ISSN 0039-7857. S2CID 16657040. arXiv:math/0102189 . doi:10.1023/a:1026247421383. 
• Zach, Richard (2005). „Kurt Gödel, paper on the incompleteness theorems (1931)”. Ур.: Grattan-Guinness, Ivor. Landmark Writings in Western Mathematics 1640-1940. Elsevier. стр. 917–925. ISBN 9780444508713. doi:10.1016/b978-044450871-3/50152-2. 
• Francesco Berto. There's Something about Gödel: The Complete Guide to the Incompleteness Theorem John Wiley and Sons. 2010.
• Norbert Domeisen, 1990. Logik der Antinomien. Bern: Peter Lang. 142 S. (1990) ISBN 3-261-04214-1. Шаблон:Zbl.
• Torkel Franzén, 2005. Gödel's Theorem: An Incomplete Guide to its Use and Abuse. A.K. Peters. ISBN 1-56881-238-8 MR2146326
• Douglas Hofstadter, 1979. Gödel, Escher, Bach: An Eternal Golden Braid. Vintage Books. ISBN 0-465-02685-0. 1999 reprint: ISBN 0-465-02656-7. MR530196
•  —, 2007. I Am a Strange Loop. Basic Books. ISBN 978-0-465-03078-1. MR2360307
• Stanley Jaki, OSB, 2005. The drama of the quantities. Real View Books.
• Per Lindström, 1997. Aspects of Incompleteness, Lecture Notes in Logic v. 10.
• J.R. Lucas, FBA, 1970. The Freedom of the Will. Clarendon Press, Oxford, 1970.
• Ernest Nagel, James Roy Newman, Douglas Hofstadter, 2002 (1958). Gödel's Proof, revised ed. ISBN 0-8147-5816-9. MR1871678
• Rudy Rucker, 1995 (1982). Infinity and the Mind: The Science and Philosophy of the Infinite. Princeton University Press. MR658492
• Peter Smith, 2007. An Introduction to Gödel's Theorems. Архивирано на сајту Wayback Machine (23. октобар 2005) Cambridge University Press. MR2384958
• N. Shankar, 1994. Metamathematics, Machines and Gödel's Proof, Volume 38 of Cambridge tracts in theoretical computer science. ISBN 0-521-58533-3
• Raymond Smullyan, 1987. Forever Undecided ISBN 0192801414 - puzzles based on undecidability in formal systems
• —, 1991. Godel's Incompleteness Theorems. Oxford University Press.
• —, 1994. Diagonalization and Self-Reference. Oxford University Press. MR1318913
• Smullyan, Raymond M. (19. 9. 2013). The Godelian Puzzle Book: Puzzles, Paradoxes and Proofs. Courier Corporation. ISBN 9780486497051. CS1 одржавање: Формат датума (веза)
• Hao Wang, 1997. A Logical Journey: From Gödel to Philosophy. MIT Press. ISBN 0-262-23189-1 MR1433803
• Francesco Berto, 2009, "The Gödel Paradox and Wittgenstein's Reasons" Philosophia Mathematica (III) 17.
• Dawson, John W., Jr. (1996). Logical dilemmas: The life and work of Kurt Gödel. Taylor & Francis. ISBN 978-1-56881-025-6. 
• Dawson, John W., Jr. (1997). Logical dilemmas: The life and work of Kurt Gödel. Wellesley, Massachusetts: A. K. Peters. ISBN 978-1-56881-256-4. OCLC 36104240. 
• Rebecca Goldstein, 2005, Incompleteness: the Proof and Paradox of Kurt Gödel, W. W. Norton & Company. ISBN 0-393-05169-2
• Floyd, Juliet; Putnam, Hilary (2000). „A Note on Wittgenstein's "Notorious Paragraph" about the Godel Theorem”. The Journal of Philosophy. JSTOR. 97 (11): 624—632. ISSN 0022-362X. JSTOR 2678455. doi:10.2307/2678455. 
• John Harrison, 2009, "Handbook of Practical Logic and Automated Reasoning", Cambridge University Press, ISBN 0521899575
• David Hilbert and Paul Bernays, Grundlagen der Mathematik, Springer-Verlag.
• John Hopcroft and Jeffrey Ullman 1979, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, ISBN 0-201-02988-X
• Jones, James P. (1980). „Undecidable diophantine equations” (PDF). Bulletin of the American Mathematical Society. 3 (2): 859—862. doi:10.1090/S0273-0979-1980-14832-6. 
• Stephen Cole Kleene, 1967, Mathematical Logic. Reprinted by Dover, (2002) ISBN 0-486-42533-9
• o'Connor, Russell (2005). „Essential Incompleteness of Arithmetic Verified by Coq”. Theorem Proving in Higher Order Logics. Lecture Notes in Computer Science. 3603. стр. 245—260. ISBN 978-3-540-28372-0. S2CID 15610367. arXiv:cs/0505034 . doi:10.1007/11541868_16. 
• Paulson, Lawrence C. (2014). „A Machine-Assisted Proof of Gödel's Incompleteness Theorems for the Theory of Hereditarily Finite Sets”. Review of Symbolic Logic. 7 (3): 484—498. S2CID 13913592. doi:10.1017/S1755020314000112. 
• Graham Priest, 1984, "Logic of Paradox Revisited", Journal of Philosophical Logic, v. 13,` n. 2, pp. 153–179.
• —, 2004, Wittgenstein's Remarks on Gödel's Theorem in Max Kölbel, ed., Wittgenstein's lasting significance, Psychology Press, pp. 207–227.
• —, 2006, In Contradiction: A Study of the Transconsistent, Oxford University Press, ISBN 0-19-926329-9
• Hilary Putnam, 1960, Minds and Machines in Sidney Hook, ed., Dimensions of Mind: A Symposium. New York University Press. Reprinted in Anderson, A. R., ed., 1964. Minds and Machines. Prentice-Hall: 77.
• Wolfgang Rautenberg, 2010, A Concise Introduction to Mathematical Logic, 3rd. ed., Springer, ISBN 978-1-4419-1220-6
• Rodych, Victor (2005). „Misunderstanding Gödel: New Arguments about Wittgenstein and New Remarks by Wittgenstein”. Dialectica. 57 (3): 279—313. doi:10.1111/j.1746-8361.2003.tb00272.x. 
• Shapiro, Stewart (2002). „Incompleteness and Inconsistency”. Mind. 111 (444): 817—832. doi:10.1093/mind/111.444.817. 
• Alan Sokal and Jean Bricmont, 1999, Fashionable Nonsense: Postmodern Intellectuals' Abuse of Science, Picador. ISBN 0-312-20407-8
• Joseph R. Shoenfield (1967), Mathematical Logic. Reprinted by A.K. Peters for the Association for Symbolic Logic, (2001) ISBN 978-1-56881-135-2
• Jeremy Stangroom and Ophelia Benson, Why Truth Matters, Continuum. ISBN 0-8264-9528-1
• George Tourlakis, Lectures in Logic and Set Theory, Volume 1, Mathematical Logic, Cambridge University Press, (2003) ISBN 978-0-521-75373-9
• Avi Wigderson, 2010, "The Gödel Phenomena in Mathematics: A Modern View", in Kurt Gödel and the Foundations of Mathematics: Horizons of Truth, Cambridge University Press.
• Hao Wang, 1996, A Logical Journey: From Gödel to Philosophy, The MIT Press, Cambridge MA, ISBN 0-262-23189-1.
• Zach, Richard (2007). „Hilbert's Program Then and Now”. Ур.: Jacquette, Dale. Philosophy of logic. Handbook of the Philosophy of Science. 5. Amsterdam: Elsevier. стр. 411—447. ISBN 978-0-444-51541-4. OCLC 162131413. S2CID 291599. arXiv:math/0508572 . doi:10.1016/b978-044451541-4/50014-2. 

Спољашње везе

• Godel's Incompleteness Theorems on In Our Time at the BBC. (Incompleteness Theorems listen now)
• "Kurt Gödel" entry by Juliette Kennedy in the Stanford Encyclopedia of Philosophy, July 5, 2011.
• "Gödel's Incompleteness Theorems" entry by Panu Raatikainen in the Stanford Encyclopedia of Philosophy, November 11, 2013.
• Paraconsistent Logic § Arithmetic and Gödel's Theorem entry in the Stanford Encyclopedia of Philosophy.
• MacTutor biographies:
  • Kurt Gödel. Архивирано на сајту Wayback Machine (13. октобар 2005)
  • Gerhard Gentzen. Архивирано на сајту Wayback Machine (19. октобар 2012)
• What is Mathematics:Gödel's Theorem and Around by Karlis Podnieks. An online free book.
• World's shortest explanation of Gödel's theorem using a printing machine as an example.
• October 2011 RadioLab episode about/including Gödel's Incompleteness theorem
• Hazewinkel Michiel, ур. (2001). „Gödel incompleteness theorem”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• How Gödel’s Proof Works by Natalie Wolchover, Quanta Magazine, July 14, 2020.