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ætning 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 mere 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.

Antag at sætning kan modbevises, det må betyde at sætningen er falsk, ergo "denne sætning kan bevises", hvilket er en kontradiktion til antagelsen. Hvis man antager at sætning 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.