> Mat.'s ufuldstændighed > Gödels bevis (1) Udskriv denne side
     
Matematikkens ufuldstændighed
         
Se også:
Index og søg
Udskriv siden
         

Gödels bevis (1)

Gödels ufuldstændighedsteoremer
Gödels selvrefererende udsagn
Hofstadters diagram
Kilder

 

Sidens topGödels ufuldstændighedsteoremer

I 1930-31 fremsatte og beviste Kurt Gödel to teoremer som begge underminerede tiltroen til matematiske formelle systemers fuldkommenhed:

  1. I ethvert konsistent formelt system som er stærkt nok til at danne grundlag for teorien om tallene findes sætninger som hverken kan bevises eller modbevises.
    Variant: ... findes sætninger som ikke kan bevises, men som alligevel er sande.
  2. Konsistensen (modsigelsesfriheden) i et formelt system som er stærkt nok til at danne grundlag for teorien om tallene, kan ikke bevises indenfor det formelle system.

Gödels bevis for disse to "ufuldstændighedsteoremer" satte et punktum for bestræbelserne (bl.a. formuleret af Hilbert og Russell) på:

  • dels at bevise at konsistente formelle systemer er fuldstændige, dvs. at de kan nå ud til alle sandheder i form af sætninger (velformulerede strenge) som kan formuleres indenfor systemet,
  • dels at føre bevis for det formelle systems konsistens indenfor systemet.

I den logiske ramme for Gödels bevis som vi kommer til nu,

antager vi at det formelle system F er konsistent.

Dette indebærer ikke, at vi nødvendigvis tror på at denne konsistens kan bevises indenfor F, men blot at vi har gode grunde til at tro på F's konsistens, f.eks. fordi der kan laves pålidelige modeller for F. Troen på konsistensen af TTT hviler f.eks. på at tallene (specielt de hele positive tal) er en brugbar model for TTT.

I et konsistent formelt system må vi gå ud fra at

hvis der kan gives bevis for en sætning, altså at denne sætning er et teorem i systemet, så må denne sætning også være sand.

Det er jo hele ideen med det formelle system: at nå frem til sandheder ved at bevise at sætninger er teoremer i systemet.

Det er her afgørende at det formelle system er konsistent, for i et inkonsistent formelt system kan man nå frem til "hvad som helst", altså også usandheder. Se f.eks. FysikForHvemSomHelst 2005: "Hvad er et paradoks (1)"?

Derimod kan vi ikke uden videre antage at et sandt udsagn kan bevises.

Det er blot et ønske vi har om formelle systemers "evner", nemlig at de er stærke nok til at de ved udledninger eller beviser kan "nå ud til" alle sandheder i form af sætninger (velformulerede strenge) som kan formuleres indenfor systemet. Hilbert og Russell håbede netop at kunne bevise dette.

Sidens topGödels selvrefererende udsagn

Den ydre logiske ramme som Gödels bevis hviler på, er beslægtet med paradokser baseret på selvrefererende udsagn. Givet et formelt system F som antages at være konsistent (modsigelsefrit).
Gödel opstiller udsagnet:

G: Udsagnet G kan ikke bevises indenfor F

Udsagnet G er ikke i sig selv et paradoks, men det er selvrefererende, hvilket under alle omstændigheder får det til at virke lidt "underligt". Sml. med en variation ud fra løgner paradokset i form af udsagnet "Denne sætning er sand".
Den negerede udgave af G er:

non G: Udsagn G kan bevises indenfor F

Selv om G ikke i sig selv er et paradoks, tager tingene nu en forbløffende vending.
Lad os undersøge om G kan bevises.

  • Vi antager at G kan bevises indenfor F.
  • Så må non G være sand, for det er jo netop hvad non G siger.
  • Men når negationen til G er sand, må G selv være falsk.
  • På den anden side: Når G kan bevises i et konsistent formelt system F, så må G være sand.
  • Men G kan ikke både være falsk og sand, så vi er kommet til en modstrid.
  • Derfor må vores antagelse, at G kan bevises i F, være forkert.
  • Altså kan G ikke bevises indenfor F.

 

  • Vi ved nu at G ikke kan bevises indenfor F.
  • Men det er jo netop hvad G siger.
  • Altså må G være sand.

 

  • Vi ved nu at G både er ubeviselig i F og sand.
  • F er altså ufuldstændig, idet F ikke kan nå ud til alle sandheder.

Dette er den ene af formuleringerne af Gödels første ufuldstændighedsteorem.

 

Vi kan også formulere det således:

  • Det formelle system F er enten inkonsistent eller ufuldstændigt.

 

Vi kan gå videre:

  • Da vi nu ved at G er sand, så må non G være falsk.
  • Da beviser i et konsistent formelt system altid fører til sande udsagn, kan non G heller ikke bevises i F.
  • G kan altså hverken bevises eller modbevises i F.

Dette er den anden af formuleringerne af Gödels første ufuldstændighedsteorem.

 

Og mere endnu:

  • Det er muligt indenfor det formelle system F at bevise at:
    "Hvis F er konsistent så er G sand".

    (Denne kendsgerning er ikke indlysende og følger ikke af det foregående.)
  • Lad os nu antage at også konsistensen af F kan bevises indenfor F.
  • Men hvis konsistensen af F er bevist, og det også er bevist at "Hvis F er konsistent så er G sand", så har vi her et samlet bevis indenfor F for G.
  • Men dette strider jo mod at vi i Gödels bevis for første fuldstændighedsteorem som resultat fandt at G ikke kan bevises indenfor F.
  • Altså må vores antagelse være forkert: Konsistensen af F kan ikke bevises.

Dette er Gödels andet ufuldstændighedsteorem.

 

Sidens topHofstadters diagram

Diagram fra Douglas R. Hofstadter: "Gödel, Escher, Bach - an Eternal Golden Braid", chap. 3.

Sidens topKilder

Douglas R. Hofstadter: "Gödel, Escher, Bach - an Eternal Golden Braid", Basic Books, Inc., Publishers, New York, 1979. Semi-populær fremstilling, meget underholdende, men også ret krævende.

Ernest Nagel & James R. Newman: "Gödels Proof", New York University Press, 1974. Populær fremstilling, kortfattet og klar.

Rebecca Goldstein: "Incompleteness - The Proof and Paradox of Kurt Gödel", Atlas Books, W.W.Norton & Co., 2006. Populær fremstilling, kommer også ind på filosofiske aspekter.

Roger Penrose: "The Emperor's New Mind - concerning computers, minds, and the laws of Physics", Penguin Books, 1989. Semi-populær fremstilling, behandler paralleller til Gödel's teoremer i form af Turing's stoppeproblem (halting problem), uberegnelighed.

Elliott Mendelson: "Introduction to Mathematical Logic", D. Van Nostrand Co. Inc., 1964. Universitetslærebog af den rene matematiske type - skrappe sager.

Wikipedia, http://en.wikipedia.org, har mange gode - og svære - artikler om f.eks. "Gödels incompleteness theorems", "Axiomatic set theory".

Se flere henvisninger: Supplement: Beviser

Sidens topSe videre: Gödels bevis (2)

Opdateret 3-11-2011 , TM

 
Sidens top