Matematikseminariet: Fullständighet och avgörbarhet

  • Datum: –16.15
  • Plats: Ångströmlaboratoriet 4005
  • Föreläsare: Vera Koponen
  • Arrangör: Matematiska institutionen
  • Kontaktperson: Elin Persson Westin
  • Seminarium

Matematiska resonemang bygger på logiska bevisregler (alternativt logiska axiom) och matematiska axiom. De senare är oftast områdesspecifika, men i princip går det till på samma sätt i alla områden av matematiken. Ett par frågor inställer sig: 

A. Är det så att varje (områdesspecifikt) påstående kan bevisas eller motbevisas från (de områdesspecifika) axiomen? Med andra ord, är axiomen fullständiga? 

B. Finns det någon algoritm som för varje (områdesspecifikt) påstående kan avgöra (dvs korrekt svara ja/nej) om påståendet kan bevisas från (de områdesspecifika) axiomen? Med andra ord, är problematiken (inom området i fråga) algoritmiskt avgörbar? 

Dessa frågeställningar går tillbaka åtminstone till Leibniz (1646-1716). En relaterad fråga är:

C. Givet en samling (områdesspecifika) axiom, är dessa motsägelsefria?

Frågorna fick ny aktualitet i slutet av 1800-talet i samband med arbeten av bl a Cantor, Frege och Russell, och lyftes fram för matematikersamfundet genom Hilberts lista (från 1900 och utvidgad 1902) med 23 (då) olösta problem. De problem som är relaterade till A-C är problem 1 (kontinuumhypotesen), problem 2 (att bevisa aritmetikens motsägelsefrihet) och problem 10 (diofantiska ekvationers avgörbarhet). Alla tre problemen har fått negativa svar i en mening som kan göras precis, genom arbeten av bl a Gödel, Church, Turing, Cohen och Matiyasevich. Mer allmänt så har problemställningarna A-C också fått negativa svar i många andra sammanhang. Detta hindrar oss givetvis inte från att fortsätta att bevisa nya (och intressanta) resultat. Men det säger något om axiomatiska systems begränsningar och om algoritmers/datorers begränsningar. Jag kommer att ge exempel på oavgörbara problem och ofullständiga axiomsystem samt säga något om idéerna bakom resultaten.