Gedelove teoreme o nepotpunosti

U matematičkoj logici, Gedelove teoreme o nepotpunosti su dve teoreme o ograničenjima formalnog sistema, koje je dokazao Kurt Gedel, 1931. godine.

Ove teoreme pokazuju da ne postoji potpun i konzistentan formalni sistem koji korektno opisuje prirodne brojeve i da nijedan dovoljno strog sistem koji opisuje prirodne brojeve ne može da potvrdi svoju sopstvenu konzistentnost. Pri tome, u matematičkoj logici, neki formalni sistem smatra se konzistentnim ako ne sadrži kontradikcije (za svaku propoziciju φ ne mogu u isto vreme i φ i njoj protivrečna ¬φ biti dokazive), a sistem je potpun ako je dovoljan da se na njemu izgradi odgovarajuća teorija u celini.

Ove teoreme su široko prihvaćene kao dokaz da je nemoguće ostvariti Hilbertov program pronalaženja potpunog i konzistentnog skupa aksioma koji bi važio za celu matematiku. Ili drugim rečima, nemoguće je pronaći neki univerzalni sistem aksioma iz kojeg bi automatski sledio i dokaz o neprotivurečnosti teorije koja bi bila izgrađena na bazi tog sistema. Naprotiv, neprotivrečnost nekog sistema aksioma svodi se na neprotivrečnost nekog drugog sistema aksioma koji se već smatra neprotivrečnim.

Kao primer toga može se navesti odnos između euklidske i neke od varijanti neeuklidskih geometrija, recimo geometrije Lobačevskog. Naime, neprotivrečnost geometrije Lobačevskog, koja je nastala negacijom Euklidovog petog postulata (aksiome paralelnosti), dokazuje se u stvari neprotivrečnošću euklidske geometrije, gde takođe važi i obrnuto. S druge strane, problem nezavisnosti sistema aksioma svodi se na problem neprotivrečnosti. Ili u konkretnom primeru, nezavisnost Euklidovog petog postulata u odnosu na ostale postulate euklidske geometrije dokazuje se neprotivrečnošću geometrije Lobačevskog.

Prva teorema o nepotpunosti

Gedelova prva teorema o nepotpunosti je verovatno najslavniji rezultat u matematičkoj logici. Ona tvrdi da:

Za bilo koju formalnu teoriju koja potvrđuje osnovne aritmetičke istine, može se konstruisati aritmetičko tvrđenje koje je istinito ali nije i dokazivo unutar same te teorije. To znači, da bilo koja teorija koja je sposobna da izrazi elementarnu aritmetiku ne može biti u isto vreme i konzistentna i potpuna.

Literatura

• —, 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 održavanje: Nedostaje uspravna crta (veza)
• 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. Šablon: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. Arhivirano na sajtu 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 održavanje: Format datuma (veza)
• 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. str. 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”. Ur.: Jacquette, Dale. Philosophy of logic. Handbook of the Philosophy of Science. 5. Amsterdam: Elsevier. str. 411—447. ISBN 978-0-444-51541-4. OCLC 162131413. S2CID 291599. arXiv:math/0508572 . doi:10.1016/b978-044451541-4/50014-2. 

Spoljašnje veze

• 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. Arhivirano na sajtu Wayback Machine (13. oktobar 2005)
  • Gerhard Gentzen. Arhivirano na sajtu 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.