Gödels ofullständighetssatser

Gödels ofullständighetsteorem är två fundamentala teorem inom den moderna logiken. De handlar om avgörbarhet och bevisbarhet av utsagor i formella system och lades fram av Kurt Gödel 1931. Teoremen fastlägger, att Hilberts andra problem, om en axiomatisering av aritmetiken kräver ett oändligt antal axiom. Det medför att David Hilberts program, att finna ett fullständigt och konsistent, det vill säga motsägelsefritt, axiomsystem för all matematik är ogenomförbart.

Gödels första ofullständighetsteorem:

I varje konsistent formellt system, tillräckligt för aritmetiken, finns en sann men oavgörbar formel, det vill säga en formel, som inte kan bevisas och vars negation ej heller kan bevisas.

Gödels andra ofullständighetsproblem, är en följdsats till det första teoremet:

Konsistensen hos ett formellt system, tillräckligt för aritmetiken, kan inte bevisas inom systemet.

Gödels första teorem är i grunden villkorligt. Det säger att, om ett formellt system S för aritmetik är konsistent, så är det möjligt att konstruera en sats G, som är sann men obevisbar i detta system. Härav följer, att om S är konsistent, så är G både sann och obevisbar. Trivialt fås då, att om S är konsistent, så är G sann.

Om konsistensen av S nu skulle kunna bevisas i systemet, så skulle G ha bevisats i S och därmed skulle en kontradiktion, G och icke-G, att G är såväl bevisbar som icke bevisbar, kunna härledas. Av reductio ad absurdum-regeln följer då negationen av satsen, att S är konsistent, det vill säga att S inte är, eller kan visas vara, konsistent.

Historia

Det första teoremet presenterades av Gödel den 7 oktober 1930, vid en konferens i Königsberg på temat "De exakta vetenskapernas kunskapsteori" arrangerad av Wienkretsen och Berlinkretsen. Trots att merparten av de mest inflytelserika matematikerna, logikerna och filosoferna var inbjudna, kom Gödels föredrag att röna föga uppmärksamhet. En av de få som reagerade på Gödels framförande var matematikern John von Neumann. Neumann kom att propagera för Gödels andra teorem vid Institute for Advanced Study i Princeton och därmed blev det detta, som först uppmärksammades internationellt. Det teorem, som språkligt är det mest slagkraftiga och tydligast uttrycker, att ett finit formellt bevis för konsistensen av aritmetikens axiom aldrig kan uppnås inom aritmetikens system.

Gödels teorem var revolutionerande och konsekvenserna för Hilbert och formalisterna var obönhörliga. Deduktion i formella system hade visats ha klara begränsningar och följden var, att en fullständig axiomatisering av matematiken aldrig skulle kunna genomföras.

Filosofi och hypoteser

Gödels teorem 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 teorem 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.

Källor

• B. Meltzer (translation) and R. B. Braithwaite (Introduction), 1962. On Formally Undecidable Propositions of Principia Mathematica and Related Systems, Dover Publications, New York 1992.
• Rebecca Goldstein, Ofullständighet. Kurt Gödels bevis och paradox. Bokförlaget Nya Doxa 2005.
• 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 Massachusetts.

Vidare läsning

• 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.
• Torkel Franzén: "Gödel’s Theorem. An Incomplete Guide to Its Use and Abuse", AK Peters, 2005, ISBN 1-56881-238-8.
• Karl Podnieks: Around Goedel's Theorem
• 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).