Gödels sætning, Kurt Gödels første ufuldstændighedssætning, en af de vigtigste og mest overraskende sætninger i matematisk logik.

Den siger, at ethvert modsigelsesfrit formelt system, som er omfattende nok til at kunne udtrykke visse elementære dele af aritmetikken, vil være ufuldstændigt; det vil være muligt at finde udsagn i systemet, som hverken kan bevises eller modbevises, dvs. som er uafgørbare inden for systemet.

Kurt Gödels anden ufuldstændighedssætning siger, at der i et sådant formelt system findes et udsagn, som udtrykker systemets modsigelsesfrihed, og at dette udsagn er et eksempel på en uafgørlig sætning. Det betyder, at det ikke er muligt i et sådant system at vise systemets egen modsigelsesfrihed.

Idéen i Gödels bevis er at konstruere et formelt udsagn, som udtrykker sin egen ubeviselighed. For at opnå dette indførte Gödel et kodesystem, hvor formelle symboler, udtryk og beviser tilordnes kodetal. Disse kodetal kan indrettes på en sådan måde, at ethvert naturligt tal entydigt koder et formelt udtryk, og man kan ved simple talteoretiske egenskaber ved kodetallet afgøre, om tallet koder et udsagn eller et bevis. Ethvert formelt udtryk har i dette system et entydigt bestemt kodetal. Da det formelle system kan tale om talteoretiske relationer, kan det således via kodesystemet tale om sine egne formelle udsagn og beviser.

På grundlag af dette kodesystem, som betegnes en Gödelnummerering, kan udtrykket "x er kodetal for et udsagn, og y er kodetal for et bevis for formlen med kodetal x" udtrykkes som en simpel talteoretisk egenskab. Der findes derfor et formelt udsagn i systemet, Bev(x,y), som formaliserer dette. Det betyder, at for to tal n og m gælder der, at Bev(n,m) kan bevises i systemet, hvis, og kun hvis, n er kodetal for et udsagn og m kodetal for et bevis for dette udsagn.

Det formelle udsagn ¬∃yBev(x,y) udtrykker derfor, at der ikke findes et kodetal y for et bevis for udsagnet med kodetal x, altså at udsagnet med kodetal x ikke kan bevises. ¬∃yBev(x,y) har imidlertid selv et kodetal m. Indsættes m for x i ¬∃Bev(x,y), fås udsagnet ¬∃yBev(m,y), som udtrykker sin egen ubeviselighed.

Gödel viste, at dette udsagn hverken kunne bevises eller modbevises i det formelle system. Strengt taget viste Gödel dette under lidt skærpede betingelser, men disse betingelser blev 1936 svækket af Barkley Rosser.

Læs mere i Den Store Danske

logik

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig