Gödels ofullständighetssatser
From Wikipedia, the free encyclopedia
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.[1]
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.[2]