Gödels ofullständighetssats

Från Rilpedia

(Omdirigerad från Gödels teorem)
Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

Gödels (första) ofullständighetssats säger att :

I varje motsägelsefritt formellt system som är tillräckligt komplext för att kunna beskriva aritmetik för naturliga tal, går det att formulera satser som varken kan bevisas eller motbevisas inom ramen för det formella systemet.

Ett formellt system är här en välpreciserad metod för att härleda matematiska satser rent mekaniskt. Man kräver också att det går att mekaniskt räkna upp alla de satser som det formella systemet kan härleda. Exempelvis utesluter man idéer som att ta samtliga sanna aritmetiska satser som axiom i systemet.

Gödel bevisade också en variant av sin sats, Gödels andra ofullständighetssats, som säger att:

Inget "tillräckligt starkt" motsägelsefritt formellt system kan bevisa sin egen motsägelsefrihet.

Tillräckligt stark i detta sammanhang betyder att systemet är tillräckligt kraftfullt för att det inom systemet ska gå att formulera de aritmetiska operationer som används i beviset av den första satsen.

Gödels satser fick stor betydelse inom matematikfilosofin och de tankar som fanns både bland formalisterna, som strävade efter att axiomatisera hela matematiken och logicisterna som försökte bygga upp matematiken från logik.

Gödels sats har också använts som argument för åsikten att maskiner aldrig kan göras intelligenta och att människan är förmer än en maskin, ett argument som fått kritik för att missbruka Gödels ursprungliga sats och generalisera dem utanför deras givna matematiska sammanhang. Problemet med dessa argument är oftast att de utgår från att människor kan göra saker som det inte finns belägg för att vi kan. Man brukar resonera så här:

  • Eftersom jag som människa kan förstå att den sats som Gödel konstruerar måste vara sann, trots att detta inte kan bevisas i systemet, så måste jag kunna göra saker som systemet inte kan.
  • Mitt medvetande är alltså inte ett motsägelsefritt formellt system.
  • Alltså är jag inte en maskin.

Det finns i huvudsak tre problem med detta, ett för varje rad i argumentet. För det första gäller ens insikt bara motsägelsefria system och det är i allmänhet svårt, även för människor, att kontrollera att ett system är motsägelsefritt. Man kan därför ifrågasätta huruvida man verkligen kan ha den insikt som nämns i den första punkten, i konkreta fall. För det andra motsäger inte ofullständighetssatsen hypotesen att ens medvetande är ett motsägelsefritt formellt system, ty även sådana kan bevisa att andra motsägelsefria system är ofullständiga. Det skulle ändå kunna vara så att det finns en sats som man inte kan bevisa vara sann, men som ett annat formellt system kan bevisa vara sann. För det tredje är det inte säkert att varje maskin med nödvändighet måste ha ett medvetande som är ett motsägelsefritt formellt system. Det skulle för det första kunna vara ett motsägelsefullt system. Det skulle också kunna avvika helt från definitionen av ett formellt system. Man skulle till exempel kunna bygga in slumpmässiga nycker i dess sätt att resonera. Även i de fall där en maskin är programmerad att resonera med hjälp av ett formellt system kan fel i hårdvaran göra att den inte uppför sig som den är avsedd att göra, exempelvis genom att en bit i minnet byter värde. Det skulle kunna leda till att maskinen "upptäcker" faktum som den inte skulle ha sett om den höll sig till sitt program. En sådan maskins "medvetande" skulle inte uppfylla förutsättningarna som gör Gödels bevis giltigt.

Ofullständighetssatsen har jämförts med Heisenbergs obestämbarhetsrelation i kvantfysiken.

Externa länkar och referenser

  • K. Gödel: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I. Monatshefte für Mathematik und Physik, 38 (1931), pp. 173-198. Engelsk version: From Frege to Gödel. Harvard University Press, 1971.
  • Karl Podnieks: Around Goedel's Theorem, http://www.ltn.lv/~podnieks/gt.html
  • D. Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid, 1979, ISBN 0-465-02685-0. (1999 nyutgåva: ISBN 0-465-02656-7). På svenska Gödel, Escher, Bach: Ett Evigt Gyllene Band, (ISBN 91-7608-260-1 [1985], ny upplaga: ISBN 91-7608-331-4 [1992]).
  • En artikel på svenska om "Gödels bevis" finns i band 5 av antologin SIGMA - En matematikens kulturhistoria (eng. red. James R. Newman) (svensk red. Tord Hall, 1959, flera upplagor).
Personliga verktyg