Teorema d'incompletesa de Gödel: diferència entre les revisions
Contingut suprimit Contingut afegit
→Referències: Afegeixo secció "Història" |
→Història: Afegeixo dues seccions |
||
Línia 115:
Però aquesta última declaració és equivalent a <math>p</math> mateix (i aquesta equivalència es pot demostrar en el sistema), de forma que <math>p</math> es pot demostrar en el sistema. Aquesta contradicció posa de manifest que el sistema ha de ser inconsistent.
== Limitacions dels teoremes de Gödel ==
Les conclusions dels teoremes de Gödel només estan demostrades per aquelles teories formals que satisfan les hipòtesis necessàries. No tots els sistemes axiomàtics satisfan aquestes hipòtesis, encara que incloguin els nombres naturals com a subconjunt. Per exemple, existeixen axiomatitzacions de la [[geometria euclidiana]], dels [[Cos algebraicament tancat|cossos tancats]] [[Nombre real|reals]], o de l'aritmètica en què la multiplicació no és ''demostrable'' que sigui total; cap d'aquests exemples satisfà les hipòtesis dels teoremes de Gödel. El fet clau és que aquestes axiomatitzacions no són prou expressives per definir el conjunt dels nombres naturals o per desenvolupar les propietats bàsiques dels nombres naturals. Pel que fa al tercer exemple, Dan Willard<ref>{{ref-publicació|cognom=Willard|nom=Dan E.|títol=Self-Verifying Axiom Systems, the Incompleteness Theorem and Related Reflection Principles|publicació=The Journal of Symbolic Logic|data=1 juny 2001|pàgines=536|volum=66|exemplar=2|doi=10.2307/2695030}}</ref> ha estudiat molts sistemes febles de l'aritmètica que no satisfan les hipòtesis del segon teorema d'incompletesa, i que són consistents i capaços de demostrar la seva pròpia consistència.
Els teoremes de Gödel només es poden aplicar a teories generades efectivament (és a dir, enumerables recursivament). Si tots els enunciats vertaders sobre nombres naturals es prenen com a axiomes, llavors aquesta teoria és una extensió consistent i completa de l'aritmètica de Peano per la qual no es pot aplicar cap dels teoremes de Gödel, perquè aquesta teoria no és enumerable recursivament.
El segon teorema d'incompletesa només demostra que la consistència de certes teories no es pot demostrar a partir dels axiomes d'aquestes pròpies teories. No demostra que la consistència no pugui ser demostrada a partir d'un altre conjunt (consistent) d'axiomes. Per exemple, la consistència de l'[[aritmètica de Peano]] es pot demostrar dins la [[teoria de conjunts]] de [[Ernst Zermelo|Zermelo]]-[[Abraham Fraenkel|Fraenkel]] amb l'[[axioma de l'elecció]] (ZFC), o també dins teories de l'aritmètica augmentades amb la [[inducció transfinita]], com en la [[demostració de consistència de Gentzen]].
== Relació amb la computabilitat ==
El teorema d'incompletesa està íntimament lligat a diversos resultats sobre conjunts indecidibles en [[teoria de la computabilitat]].
Stephen Cole Kleene<ref name="kleene1967">{{ref-publicació|cognom=Kleene|nom=S. C.|títol=Recursive predicates and quantifiers|publicació=Transactions of the American Mathematical Society|data=1 gener 1943|pàgines=41–41|volum=53|exemplar=1|doi=10.1090/S0002-9947-1943-0007371-8|issn=1088-6850}}</ref> va presentar una demostració del teorema d'incompletesa de Gödel que emprava alguns resultats bàsics de teoria de la computabilitat. Un d'aquests resultats diu que el [[problema de la parada]] és indecidible: no existeix cap programa d'ordinador que pugui determinar correctament, donat un programa ''P'' com a entrada, si ''P'' s'aturarà quan rebi una determinada entrada. Kleene va demostrar que l'existència d'una teoria de l'aritmètica efectiva i completa, dotada de certes propietats de consistència, faria que el problema de la parada fos decidible, la qual cosa porta a una contradicció. Aquest mètode de demostració també ha estat presentat per Shoenfield,<ref>{{ref-llibre|cognom=Shoenfield|nom=Joseph R.|títol=Mathematical logic|lloc=Natick, Mass.|editorial=ASL, Assoc. for Symbolic Logic [u.a.]|any=2001|isbn=9781568811352|edició=[Nachdr.]}}</ref> Charlesworth<ref>{{ref-publicació|cognom=Charlesworth|nom=Arthur|títol=A Proof of Gödel's Theorem in Terms of Computer Programs|publicació=Mathematics Magazine|data=1 maig 1981|pàgines=109|volum=54|exemplar=3|doi=10.2307/2689794}}</ref> i Hopcroft i Ullman.<ref>{{ref-llibre|cognom=Ullman|nom=John E. Hopcroft; Jeffrey D.|títol=Introduction to automata theory, languages, and computation|lloc=Reading, Mass. [u.a.]|editorial=Addison-Wesley|any=1999|isbn=020102988X|edició=[39. Druck]}}</ref>
Franzén explica com es pot aplicar la solució de Matiyasevich al [[desè Problema de Hilbert]] per tal d'obtenir una demostració del primer teorema de Gödel.<ref>{{ref-llibre|cognom=Franzén|nom=Torkel|títol=Gödel's theorem : an incomplete guide to its use and abuse|lloc=Wellesley, Mass.|editorial=Peters|any=2005|isbn=1568812388|edició=[Nachdr.]}}</ref> Matiyasevich demostrà que no hi ha cap algorisme que, donat un polinomi multivariant <math>p(x_1, x_2,\ldots,x_k)</math> a coeficients enters, determini si existeix una solució entera per l'equació <math>p=0</math>. Com que els polinomis a coeficients enters, i els propis nombres enters, es poden expressar directament en el llenguatge del'aritmètica, si una equació polinòmica entera <math>p=0</math> té solució entera, llavors qualsevol teoria de l'aritmètica ''T'' suficientment forta pot demostrar-ho. És més, si la teoria ''T'' és ω-consistent, llavors mai no podrà demostrar que l'equació té solució si de fet no en té. Així, si ''T'' fos completa i ω-consistent, seria possible determinar de forma algorísmica si una equació polinòmica té alguna solució, només enumerant demostracions de ''T'' fins que es trobés "''p'' té una solució" o bé "''p'' no té cap solució", la qual cosa contradiu el teorema de Matiyasevich. Addicionalment, per a qualsevol teoria consistent ''T'' generada efectivament, és possible generar efectivament un polinomi multivariant ''p'' sobre els enters tal que l'equació <math>p=0</math> no tingui solucions enteres, però no es pot demostrar dins ''T'' la falta de solucions.<ref name="davis2006">[[Martin Davis]] editor, 1965. ''The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable problems and Computable Functions'', Raven Press, New York</ref><ref>James P. Jones, ''[http://www.ams.org/bull/1980-03-02/S0273-0979-1980-14832-6/S0273-0979-1980-14832-6.pdf Undecidable Diophantine Equations]'', Bulletin of the American Mathematical Society v. 3 n. 2, 1980, pp. 859–862.</ref>
Smoryński<ref>{{ref-llibre|cognom=(ed.)|nom=Jon Barwise|títol=Handbook of mathematical logic|pàgines=821–866|lloc=Amsterdam [u.a.]|editorial=North-Holland|any=1989|isbn=9780444863881|edició=5. pr.}}</ref> demostrà com es pot emprar l'existència de conjunts recursivament separables per demostrar el primer teorema d'incompletesa. Sovint aquesta demostració s'amplia per mostrar que els sistemes com l'aritmètica de Peano són essencialment [[Decidibilitat|indecidibles]].<ref name="kleene1967" />
El teorema d'incompletesa de [[Gregory Chaitin|Chaitin]] proporciona un mètode diferent per generar enunciats independents, basat en la [[complexitat de Kolmogórov]]. De la mateixa manera que la demostració de Kleene que hem vist abans, el teorema de Chaitin només aplica per teories que tenen la propietat addicional de què tots els seus axiomes són certs en el model estàndard dels nombres naturals. El teorema d'incompletesa de Gödel es diferencia perquè es pot aplicar a teories consistents en les quals existeixen enunciats que són falsos en el model estàndard; aquestes teories es coneixen amb el nom de ''ω-inconsistents''.
== Història ==
| |||