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.

Rudolf Carnap var en av dem, för vilka Gödel hade presenterat sitt resultat redan fyra veckor före konferensen i Königsberg. Denne hade dock inte förstått vad Gödels upptäckt innebar. Föreställningen att kriterierna för semantisk sanning kunde skiljas från kriterierna för bevisbarhet var för honom, ur positivistiskt perspektiv, otänkbar och därmed kunde han inte tillgodogöra sig teoremets innehåll. Att det i ett konsistent system kunde konstrueras en sats, som i systemet kunde bevisas vara såväl sann som obevisbar var det som Gödel gjort möjligt med hjälp av uppfinningen, Gödelnumrering.

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.

Det bevis, som var tänkt att utgöra kärnan i Hilberts program, skulle således aldrig finnas att få. 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.

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).