Teorema ketaklengkapan Gödel: Perbedaan antara revisi

'''Teorema ketaklengkapan Gödel''' ({{lang-en|Gödel's incompleteness theorems}}) adalah dua [[teorema]] [[logika matematika]] yang menetapkan batasan (''limitation'') inheren dari semua kecuali [[:en:axiomatic system|sistem aksiomatik]] yang paling trivial yang mampu mengerjakan [[aritmetika]]. Teorema-teorema ini, dibuktikan oleh [[Kurt Gödel]] pada tahun 1931, penting baik dalam logika matematika maupun dalam [[filsafat matematika]]. Kedua hasil ini secara luas, tetapi tidak secara universal, ditafsirkan telah menunjukkan bahwa [[:en:Hilbert's program|program Hilbert]] untuk menghitung himpunan lengkap dan konsisten dari [[:en:axiom|aksioma-aksioma]] bagi semua [[matematika]] adalah tidak mungkin, sehingga memberikan jawaban negatif terhadap [[:en:Hilbert's second problem|soal Hilbert yang kedua]].

<!--

 

In simple terms, a method can be devised so that every formula or statement that can be formulated in the system gets a unique number, called its '''[[Gödel number]]''', in such a way that it is possible to mechanically convert back and forth between formulas and Gödel numbers. The numbers involved might be very long indeed (in terms of number of digits), but this is not a barrier; all that matters is that such numbers can be constructed. A simple example is the way in which English is stored as a sequence of numbers in computers using [[ASCII]] or [[Unicode]]:

 

In principle, proving a statement true or false can be shown to be equivalent to proving that the number matching the statement does or doesn't have a given property. Because the formal system is strong enough to support reasoning about ''numbers in general'', it can support reasoning about ''numbers which represent formulae and statements'' as well. Crucially, because the system can support reasoning about ''properties of numbers'', the results are equivalent to reasoning about ''provability of their equivalent statements''.

 

Now comes the trick: The notion of provability itself can also be encoded by Gödel numbers, in the following way. Since a proof is a list of statements which obey certain rules, the Gödel number of a proof can be defined. Now, for every statement ''p'', one may ask whether a number ''x'' is the Gödel number of its proof. The relation between the Gödel number of ''p'' and ''x'', the potential Gödel number of its proof, is an arithmetical relation between two numbers. Therefore there is a statement form Bew(''y'') that uses this arithmetical relation to state that a Gödel number of a proof of ''y'' exists:

The name '''Bew''' is short for ''beweisbar'', the German word for "provable"; this name was originally used by Gödel to denote the provability formula just described. Note that "Bew(''y'')" is merely an abbreviation that represents a particular, very long, formula in the original language of ''T''; the string "Bew" itself is not claimed to be part of this language.

 

* 1931, ''Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.'' ''Monatshefte für Mathematik und Physik 38'': 173-98.

* 1931, ''Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I.'' and ''On formally undecidable propositions of Principia Mathematica and related systems I'' in [[Solomon Feferman]], ed., 1986. ''Kurt Gödel Collected works, Vol. I''. Oxford University Press: 144-195. The original German with a facing English translation, preceded by a very illuminating introductory note by [[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: 304-23.

 

* [[Ernest Nagel]], James Roy Newman, Douglas Hofstadter, 2002 (1958). ''Gödel's Proof'', revised ed. ISBN 0-8147-5816-9. {{MathSciNet|2002i:03001}}

* [[Rudy Rucker]], 1995 (1982). ''Infinity and the Mind: The Science and Philosophy of the Infinite''. Princeton Univ. Press. {{MathSciNet|84d:03012}}

* 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]], 1991. ''Godel's Incompleteness Theorems''. Oxford Univ. Press.