Gödels ufuldstændighedssætning

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

Gödels ufuldstændighedssætning er en sætning indenfor matematisk logik, som blev bevist af Kurt Gödel, som svar på Hilberts andet problem. Sætningen lyder

Ethvert formelt system, som kan beskrive grundlæggende aritmetik, kan ikke både være konsistent og fuldstændigt.

Det vil sige at der må eksistere påstande, som er sande, men ikke kan bevises (ufuldstændighed) eller påstande, som leder til kontradiktion (inkonsistent). En simplere måde at forklare dette på er ved at sige, at der ikke eksisterer et computerprogram, som kan udregne alle sande påstande for relationer mellem naturlige tal (aritmetik).

Gödel beviste det ved at fremstille en version af løgnerparadokset:

Denne sætning kan modbevises.

Hvis sætningen kan modbevises, må det betyde at sætningen er falsk, ergo betyder det, at "denne sætning kan bevises", hvilket er en kontradiktion til antagelsen. Hvis man antager at sætningen kan bevises, skal den være sand og det kontradikterer antagelsen. Han beskrev dette paradoks i et formelt system via en selvrefererende formel. Han beskrev det formelle system med Gödel-nummerering. Gödel-nummerering er en måde at beskrive systemer med tal.

Gödels ufuldstændighedssætning var en stor overraskelse for matematikere, da man hidtil havde antaget at alle talteoretiske sætninger kunne bevises med Peanos aksiomer.

Matematikeren og filosoffen, George Boolos, har fremstillet et alternativt bevis på sætningen, som var beskrevet på 2 sider.

Sætningen har også konsekvensen at et modsigelsesfrit system, der kan regne med hele tal, ikke kan bevises modsigelsesfrit med sine egne aksiomer. Denne konsekvens kaldes for Gödels anden ufuldstændighedssætning.