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

У математичко? логици, Геделове теореме о непотпуности су две теореме о ограниче?има формалног система , ко?е ?е доказао Курт Гедел , 1931 . године. ^[1]

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

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

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

Прва теорема о непотпуности [ уреди | уреди извор ]

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

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

Референце [ уреди | уреди извор ]

^ Godel, Kurt (1931). ?Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I”. Monatshefte fur Mathematik und Physik . 38-38: 173?198. S2CID 197663120 . doi : 10.1007/BF01700692 .
^ Mori?,Lalovic, Filip,Ilija (2014). ?Klasiˇcni dokazi Gedelove teoreme o nepotpunosti” (PDF) .

Литература [ уреди | уреди извор ]

?, 1931, "Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme, I", in Solomon Feferman , ed., 1986. Kurt Godel 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 Godel 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 Godel'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 . Godel'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. Godel's paper begins on page 5, preceded by one page of commentary.
Jean van Heijenoort editor, 1967, 3rd edition 1967. From Frege to Godel: 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 Godel approved the translation, which in many places was accommodated to his wishes." (p. 595). Godel'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 Godel's corrections of errata and Godel'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 Godel 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 Godel'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 . Недоста?е или ?е празан параметар |title= ( помо? ) .
Jean van Heijenoort , 1963, "Godel's Theorem" in Edwards, Paul, ed., Encyclopedia of Philosophy, v. 3 . Macmillan, pp. 348?57.
Geoffrey Hellman (1981). ?How to Godel a Frege-Russell: Godel's Incompleteness Theorems and Logicism”. Nous . 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 Godel's paper. Archived from the original . Sept. 16, 2004.
Kikuchi, Makoto; Tanaka, Kazuyuki (1994). ?On Formalization of Model-Theoretic Proofs of Godel's Theorems”. Notre Dame Journal of Formal Logic . 35 (3 mr=1326122). doi : 10.1305/ndjfl/1040511346 .
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, " Godel'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 Godel 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 Godel'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 Godel, 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 Godel: 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 Franzen , 2005. Godel's Theorem: An Incomplete Guide to its Use and Abuse . A.K. Peters. ISBN 1-56881-238-8 MR 2146326
Douglas Hofstadter , 1979. Godel, Escher, Bach: An Eternal Golden Braid . Vintage Books. ISBN 0-465-02685-0 . 1999 reprint: ISBN 0-465-02656-7 . MR 530196
?, 2007. I Am a Strange Loop . Basic Books. ISBN 978-0-465-03078-1 . MR 2360307
Stanley Jaki , OSB, 2005. The drama of the quantities . Real View Books.
Per Lindstrom , 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). Godel's Proof , revised ed. ISBN 0-8147-5816-9 . MR 1871678
Rudy Rucker , 1995 (1982). Infinity and the Mind: The Science and Philosophy of the Infinite . Princeton University Press. MR 658492
Peter Smith, 2007. An Introduction to Godel's Theorems. Архивирано на са?ту Wayback Machine (23. октобар 2005) Cambridge University Press. MR 2384958
N. Shankar, 1994. Metamathematics, Machines and Godel'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. MR 1318913
Smullyan, Raymond M. (19. 9. 2013). The Godelian Puzzle Book: Puzzles, Paradoxes and Proofs . Courier Corporation. ISBN 9780486497051 .
Hao Wang , 1997. A Logical Journey: From Godel to Philosophy . MIT Press. ISBN 0-262-23189-1 MR 1433803
Francesco Berto, 2009, "The Godel Paradox and Wittgenstein's Reasons" Philosophia Mathematica (III) 17.
Dawson, John W., Jr. (1996). Logical dilemmas: The life and work of Kurt Godel . Taylor & Francis. ISBN 978-1-56881-025-6 .
Dawson, John W., Jr. (1997). Logical dilemmas: The life and work of Kurt Godel . Wellesley, Massachusetts: A. K. Peters . ISBN 978-1-56881-256-4 . OCLC 36104240 .
Rebecca Goldstein , 2005, Incompleteness: the Proof and Paradox of Kurt Godel , 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 Godel'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 Godel's Theorem in Max Kolbel, 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 Godel: 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 Godel Phenomena in Mathematics: A Modern View ", in Kurt Godel and the Foundations of Mathematics: Horizons of Truth , Cambridge University Press.
Hao Wang , 1996, A Logical Journey: From Godel 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 Godel" entry by Juliette Kennedy in the Stanford Encyclopedia of Philosophy , July 5, 2011.
"Godel's Incompleteness Theorems" entry by Panu Raatikainen in the Stanford Encyclopedia of Philosophy , November 11, 2013.
Paraconsistent Logic § Arithmetic and Godel's Theorem entry in the Stanford Encyclopedia of Philosophy .
MacTutor biographies:
- Kurt Godel. Архивирано на са?ту Wayback Machine (13. октобар 2005)
- Gerhard Gentzen. Архивирано на са?ту Wayback Machine (19. октобар 2012)
What is Mathematics:Godel's Theorem and Around by Karlis Podnieks . An online free book.
World's shortest explanation of Godel's theorem using a printing machine as an example.
October 2011 RadioLab episode about/including Godel's Incompleteness theorem
Hazewinkel Michiel, ур. (2001). ?Godel incompleteness theorem”. Encyclopaedia of Mathematics . Springer. ISBN 978-1556080104 .
How Godel’s Proof Works by Natalie Wolchover , Quanta Magazine , July 14, 2020.

[1] Godel, Kurt (1931). ?Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I”. Monatshefte fur Mathematik und Physik . 38-38: 173?198. S2CID 197663120 . doi : 10.1007/BF01700692 .

[2] Mori?,Lalovic, Filip,Ilija (2014). ?Klasiˇcni dokazi Gedelove teoreme o nepotpunosti” (PDF) .

[1]

[2]

Нормативна контрола
Државне	Француска BnF подаци Немачка Израел С?еди?ене Државе Летони?а Чешка
Остале	Енциклопеди?а Британика