Bevisskiss för Gödels första ofullständighetssats - Proof sketch for Gödel's first incompleteness theorem

Denna artikel ger en skiss av ett bevis på Gödels första ofullständighetssats . Denna teorem gäller alla formella teorier som uppfyller vissa tekniska hypoteser, som diskuteras vid behov under skissen. Vi antar för resten av artikeln att en fast teori som uppfyller dessa hypoteser har valts.

I hela denna artikel hänvisar ordet "nummer" till ett naturligt tal . Nyckelegenskapen som dessa nummer har är att vilket naturligt tal som helst kan erhållas genom att börja med siffran 0 och lägga till 1 ett begränsat antal gånger.

Teorins hypoteser

Gödel sats gäller alla formella teorier som uppfyller vissa egenskaper. Varje formell teori har en signatur som specificerar de icke-logiska symbolerna på teorinspråket. För enkelhets skull antar vi att teorinspråket består av följande samling av 15 (och endast 15) symboler:

En konstant symbol $0$ för noll.
En unionsfunktionssymbol $S$ för efterföljande operation och två binära funktionssymboler + och × för addition och multiplikation.
Tre symboler för logisk sammankoppling, $\land$ , disjunktion, $\lor$ och negation, ¬ .
Två symboler för universella, $\forall$ och existentiella, $\exists$ , kvantifierare .
Två symboler för binära relationer, = och < , för jämlikhet och ordning (mindre än).
Två symboler för vänster, $($ och höger, $)$ parentes för att fastställa kvantifierares företräde.
En enda variabel symbol, $x$ och en särskiljande symbol $*$ som kan användas för att konstruera ytterligare variabler i formen x * , x ** , x *** , ...

Detta är språket för Peano-aritmetik . En välformad formel är en sekvens av dessa symboler som bildas för att ha en väldefinierad avläsning som en matematisk formel. Således är $x = SS 0$ välformad medan $x = \forall +$ inte är välformad. En teori är en uppsättning välformade formler utan fria variabler .

En teori är konsekvent om det inte finns någon formel $F$ så att både $F$ och dess negation är bevisbara. ω-konsistens är en starkare egenskap än konsistens. Antag att $F (x)$ är en formel med en ledig variabel $x$ . För att vara ω-konsistent kan teorin inte bevisa båda $\exists m F (m)$ samtidigt som det bevisar $\neg F (n)$ för varje naturligt tal $n$ .

Teorin antas vara effektiv, vilket innebär att uppsättningen axiom måste vara rekursivt räknas . Detta betyder att det är teoretiskt möjligt att skriva ett slutligt datorprogram som, om det får köras för evigt, skulle mata ut teoriens axiom (nödvändigtvis inklusive varje välformad instans av axiomschemat för induktion ) en i taget inte mata ut något annat. Detta krav är nödvändigt; det finns teorier som är fullständiga , konsekventa och inkluderar elementär aritmetik, men ingen sådan teori kan vara effektiv.

Beskrivningen av beviset

För en förenklad beskrivning av beviset, se Gödel's ofullständiga satser

Skissen här är uppdelad i tre delar. I den första delen tilldelas varje formel i teorin ett nummer, känt som ett Gödel-nummer, på ett sätt som gör att formeln effektivt kan återvinnas från numret. Denna numrering utvidgas till att omfatta ändliga sekvenser av formler. I den andra delen, en specifik formel $PF (x, y)$ är konstruerad sådan att för två nummer $n$ och $m, PF (n, m)$ håller om och endast om $n$ betecknar en sekvens av formler som utgör ett bevis med formeln som $m$ representerar. I bevisets tredje del konstruerar vi en självreferensformel som informellt säger "Jag är inte bevisbar" och bevisar att denna mening varken kan bevisas eller motbevisas inom teorin.

Det är viktigt att alla formler i beviset kan definieras av primitiva rekursiva funktioner , som själva kan definieras i första ordningens Peano-aritmetik .

Gödel-numrering

Det första steget i beviset är att representera (välformade) teorins formler och slutliga listor över dessa formler som naturliga tal. Dessa siffror kallas Gödel-numren för formlerna.

Börja med att tilldela ett naturligt tal till varje symbol för aritmetikspråket, liknande det sätt på vilket ASCII- koden tilldelar ett unikt binärt nummer till varje bokstav och vissa andra tecken. Denna artikel kommer att använda följande uppdrag, mycket lik den som Douglas Hofstadter använde i sin Gödel, Escher, Bach :

siffra	Symbol	Menande
666	0	noll-
123	$S$	efterföljande funktion
111	=	jämställdhetsförhållande
212	<	mindre än relation
112	+	tilläggsoperatör
236	×	multiplikationsoperator
362	(	vänster parentes
323	)	rätt parentes

siffra	Symbol	Menande
262	$x$	ett variabelt namn
163	*	stjärna (används för att göra fler variabler)
333	∃	existentiell kvantifierare
626	∀	universell kvantifierare
161	∧	logiskt och
616	∨	logiskt eller
223	¬	logiskt inte

Gödel-numret för en formel erhålls genom att sammanfoga Gödel-numren för varje symbol som utgör formeln. Gödel-siffrorna för varje symbol är åtskilda av en noll, eftersom inget Gödel-nummer för en symbol enligt design innehåller $0$ . Därför kan vilken formel som helst återställas korrekt från sitt Gödel-nummer. Låt $G (F)$ beteckna Gödel antalet formeln $F$ .

Med tanke på ovanstående Gödel-numrering översätts den mening som hävdar att addition pendlar , $\forall x \forall x * (x + x * = x * + x)$ som antalet:

626 0 262 0 626 0 262 0 163 0 362 0 262 0 112 0 262 0 163 0 111 0 262 0 163 0 112 0 262 0 323

(Mellanrum har infogats på vardera sidan av varje 0 endast för läsbarhet; Gödel-siffror är strikta sammankopplingar av decimaler.) Inte alla naturliga tal representerar en formel. Till exempel numret

111 0 626 0 112 0 262

översätts till " $= \forall + x$ ", vilket inte är välformat.

Eftersom varje naturligt tal kan erhållas genom att tillämpa efterföljande operation $S$ till $0$ ett begränsat antal gånger, har varje naturligt tal sitt eget Gödel-nummer. Till exempel, Gödel antal som motsvarar $4, SSSS 0$ , är:

123 0 123 0 123 0 123 0 666

.

Tilldelningen av Gödel-nummer kan utökas till begränsade listor med formler. För att erhålla Gödel-numret på en lista med formler, skriv Gödel-numren på formlerna i ordning och separera dem med två på varandra följande nollor. Eftersom Gödel-numret i en formel aldrig innehåller två på varandra följande nollor kan varje formel i en lista med formler effektivt återställas från Gödel-numret för listan.

Det är avgörande att den formella aritmetiken kan bevisa ett minimum av fakta. I synnerhet måste den kunna bevisa att varje nummer $m$ har ett Gödel-nummer $G (m)$ . Ett andra faktum som teorin måste bevisa är att med tanke på vilket Gödel-tal som helst $G (F (x))$ med en formel $F (x)$ med en fri variabel $x$ och valfritt antal $m$ , finns det ett Gödel-nummer med formeln $F (m)$ erhålls genom att ersätta alla förekomster av $G (x)$ i $G (F (x))$ med $G (m)$ , och att detta andra Gödel-nummer effektivt kan erhållas från Gödel-talet $G (F (x))$ av $F (x)$ som en funktion av $G (x)$ . För att se att detta faktiskt är möjligt, notera att med tanke på Gödel-talet på $F (x)$ kan man återskapa den ursprungliga formeln $F (x)$ , byta ut $x$ med $m$ och sedan hitta Gödel-talet $G (F (m))$ med den resulterande formeln $F (m)$ . Detta är ett enhetligt förfarande.

Bevisförhållandet

Avdragsregler kan då representeras av binära relationer på Gödel-antalet formellistor. Med andra ord, anta att det finns en avdragsregel $D 1$ , genom vilken man kan förflytta sig från formlerna $S 1, S 2$ till en ny formel $S$ . Då förhållandet $R en$ motsvarande denna avdrags regel säger att $n$ är relaterad till $m$ (med andra ord, $n R 1 m$ innehar) Om $n$ är Gödel antalet listan med formler som innehåller $S 1$ och $S 2$ och $m$ är Gödel antal listan med formler som består av de i listan kodas av $n$ tillsammans med $S$ . Eftersom varje avdragsregel är konkret är det möjligt att effektivt avgöra för alla naturliga tal $n$ och $m$ om de är relaterade av relationen.

Det andra steget i beviset är att använda Gödel-numreringen, beskriven ovan, för att visa att begreppet bevisbarhet kan uttryckas inom teorins formella språk. Antag att teorin har avdragsregler: $D 1, D 2, D 3, ...$ . Låt $R 1, R 2, R 3, ...$ vara deras motsvarande förbindelser, såsom beskrivits ovan.

Varje bevisbart uttalande är antingen ett axiom i sig, eller så kan det härledas från axiomen genom ett begränsat antal tillämpningar av avdragsreglerna. Ett bevis på en formel $S$ är i sig en sträng av matematiska påståenden av speciella relationer (vardera är antingen ett axiom eller relaterad till tidigare uttalanden av avdragsregler), där den sista uttalandet är $S$ . Således kan man definiera Gödel-numret på ett bevis. Dessutom kan man definiera ett uttalande från $Proof (x, y)$ , som för vartannat nummer $x$ och $y$ är bevisbart om och endast om $x$ är Gödel-numret på ett bevis på uttalandet $S$ och $y = G (S)$ .

$Bevis (x, y)$ är i själva verket en aritmetisk relation, precis som " $x + y = 6$ " är, även om det är (mycket) mer komplicerat. Med tanke på en sådan relation $R (x, y)$ , för två specifika siffror $n$ och $m$ , är antingen formeln $R (m, n)$ eller dess negation $\neg R (m, n)$ , men inte båda, bevisbar. Detta beror på att förhållandet mellan dessa två siffror helt enkelt kan "kontrolleras". Formellt kan detta bevisas genom induktion, där alla dessa möjliga relationer (vars antal är oändliga) är konstruerade en efter en. Den detaljerade konstruktionen av formeln $Proof$ använder väsentligen antagandet att teorin är effektiv; det skulle inte vara möjligt att konstruera denna formel utan ett sådant antagande.

Självreferensformel

För varje tal $n$ och varje formel $F (y)$ , där $y$ är en fri variabel, definierar vi $q (n, G (F))$ , en relation mellan två siffror $n$ och $G (F)$ , så att den motsvarar påståendet " $n$ är inte Gödel-numret på ett bevis på $F (G (F))$ ". Här kan $F (G (F))$ förstås som $F$ med sitt eget Gödel-nummer som argument.

Notera att $q$ tar som ett argument $G (F)$ , den Gödel antalet $F$ . För att bevisa antingen $q (n, G (F))$ eller $\neg q (n, G (F))$ är det nödvändigt att utföra talteoretiska operationer på $G (F)$ som speglar följande steg: avkoda numret $G (F)$ i formeln $F$ , ersätt alla förekomster av $y$ i $F$ med siffran $G (F)$ och beräkna sedan Gödel-numret för den resulterande formeln $F (G (F))$ .

Observera att för varje specifikt tal $n$ och formel $F (y) är q (n, G (F))$ en rak (men komplicerad) aritmetisk relation mellan två siffror $n$ och $G (F)$ , som bygger på förhållandet $PF som$ definierats tidigare. Vidare är $q (n, G (F))$ bevisbart om den slutliga listan med formler som kodas av $n$ inte är ett bevis på $F (G (F))$ och $\neg q (n, G (F))$ är bevisbar om slutlig lista över formler kodade av $n$ är ett bevis på $F (G (F))$ . Med tanke på alla siffror $n$ och $G (F)$ är antingen $q (n, G (F))$ eller $\neg q (n, G (F))$ (men inte båda) bevisbar.

Alla bevis på $F (G (F))$ kan kodas av ett Gödel-nummer $n$ , så att $q (n, G (F))$ inte håller. Om $q (n, G (F))$ håller för alla naturliga tal $n$ , finns det inget bevis på $F (G (F))$ . Med andra ord, $\forall y q (y, G (F))$ , en formel om naturliga tal, motsvarar "det finns inget bevis på $F (G (F))$ ".

Vi definierar nu formeln $P (x) = \forall y q (y, x)$ , där $x$ är en fri variabel. Formeln $P i$ sig har ett Gödel-nummer $G (P)$ liksom varje formel.

Denna formel har en fri variabel $x$ . Antag att vi ersätter den med $G (F)$ , Gödel-numret för en formel $F (z)$ , där $z$ är en fri variabel. Då motsvarar $P (G (F)) = \forall y q (y, G (F))$ "det finns inget bevis på $F (G (F))$ ", som vi har sett.

Tänk på formeln $P (G (P)) = \forall y, q (y, G (P))$ . Denna formel beträffande siffran $G (P)$ motsvarar "det finns inget bevis på $P (G (P))$ ". Vi har här den självreferensfunktion som är avgörande för beviset: En formel för den formella teorin som på något sätt relaterar till sin egen bevislighet inom den formella teorin. Mycket informellt säger $P (G (P))$ : "Jag kan inte bevisas".

Vi kommer nu att visa att varken formeln $P (G (P))$ eller dess negation $\neg P (G (P))$ är bevisbar.

Antag att $P (G (P)) = \forall y, q (y, G (P))$ är bevisbar. Låt $n$ vara Gödel-numret på ett bevis på $P (G (P))$ . Som tidigare sett är formeln $\neg q (n, G (P))$ bevisbar. Att bevisa både $\neg q (n, G (P))$ och $\forall y q (y, G (P))$ bryter mot konsistensen i den formella teorin. Vi drar därför slutsatsen att $P (G (P))$ inte är bevisbar.

Tänk på valfritt nummer $n$ . Antag att $\neg q (n, G (P))$ är bevisbar. Då måste $n$ vara Gödel-numret på ett bevis på $P (G (P))$ . Men vi har just bevisat att $P (G (P))$ inte kan bevisas. Eftersom antingen $q (n, G (P))$ eller $\neg q (n, G (P))$ måste kunna bevisas, drar vi slutsatsen att för alla naturliga tal är $n, q (n, G (P))$ bevisbar.

Antag att negationen av $P (G (P))$ , $\neg P (G (P)) = \exists x \neg q (x, G (P))$ är bevisbar. Att bevisa både $\exists x \neg q (x, G (P))$ och $q (n, G (P))$ , för alla naturliga tal $n$ , bryter mot ω-konsistensen av den formella teorin. Således om teorin är ω-konsistent är $\neg P (G (P))$ inte bevisbar.

Vi har skissat ett bevis som visar att:

För alla formella, rekursivt uppräkbara (dvs. effektivt genererade) teorier om Peano Arithmetic ,

om det är konsekvent , finns det en oproverbar formel (på det teorins språk).

om det är ω-konsistent , finns det en formel så att både den och dess negation är obevisbar.

Sanningen i Gödel-meningen

Beviset för Gödel's ofullständighetsteori som just skissats är bevisteoretisk (även kallad syntaktisk ) genom att den visar att om vissa bevis finns (ett bevis på $P (G (P))$ eller dess negation) kan de manipuleras för att producera ett bevis av en motsägelse. Detta vädjar inte om $P (G (P))$ är "sant", bara om det är bevisbart. Sanningen är ett modellteoretiskt eller semantiskt begrepp och motsvarar inte bevisbarhet utom i speciella fall.

Genom att analysera situationen för ovanstående bevis mer detaljerat är det möjligt att få en slutsats om sanningen av $P (G (P))$ i standardmodellen för naturliga tal. Som just sett är $q$ $($ $n$ $,$ $G$ $($ $P$ $))$ bevisbart för varje naturligt tal $n$ , och är således sant i modellen . Därför, inom denna modell, ${\ displaystyle \ mathbb {N}}$ ${\ displaystyle \ mathbb {N}}$

{\ displaystyle P (G (P)) = \ forall y \, q (y, G (P))}

håller. Detta är vad uttalandet " $P (G (P))$ är sant" brukar referera till - meningen är sant i den avsedda modellen. Det är emellertid inte sant i varje modell: Om det vore, skulle det genom Gödels fullständighetssats vara bevisbart, vilket vi just har sett inte är fallet.

Boolos korta bevis

George Boolos (1989) förenklade avsevärt beviset för den första satsen, om man håller med om att satsen motsvarar:

"Det finns ingen algoritm $M$ vars utdata innehåller alla sanna meningar av aritmetik och inga falska."

"Aritmetik" hänvisar till Peano- eller Robinson-aritmetik , men beviset åberopar inga detaljer för någon av dem, tyst antar att dessa system tillåter '<' och '×' att ha sina vanliga betydelser. Boolos bevisar satsen på ungefär två sidor. Hans bevis använder språket för första ordningens logik , men åberopar inga fakta om anslutningsdon eller kvantifierare . Den domän diskurs är naturliga tal . Den Gödel mening bygger på Berry paradox .

Låt $[n]$ förkorta $n på$ varandra följande tillämpningar av efterföljande funktion , med början från $0$ . Boolos hävdar sedan (detaljerna är bara skissade) att det finns ett definierat predikat $Cxz$ som blir sant if en aritmetisk formel som innehåller $z-$ symboler namnet $x$ . Denna provskiss innehåller det enda omnämnandet av Gödel-numrering ; Boolos antar bara att varje formel kan vara så numrerad. Här, en formel $F$ namnen antalet $n$ är iff följande bevisbara:

{\ displaystyle \ forall x (F (x) \ leftrightarrow x = n)}

Boolos definierar sedan de relaterade predikaten:

$Bxy \leftrightarrow \exists z (z < y \land Cxz)$ . (Engelska: $Bxy$ blir sant om $x$ kan definieras i färre än $y-$ symboler):
$Axy \leftrightarrow \neg Bxy \land \forall a (a < x \to Bay)$ . (Engelska: $Axy$ blir sant om $x$ är det minsta antalet som inte kan definieras i färre än $y-$ symboler. Mer besvärligthåller $Axy$ om $x$ inte kan definieras i färre än $y-$ symboler och alla siffror mindre än $x$ kan definieras med färre än $y$ symboler);
$Fx \leftrightarrow \exists y ((y = [10] \times [k]) \land Axy)$ . $k =$ antalet symboler som visas i $Axy$ .

$Fx$ formaliserar Berrys paradox. Balansen mellan beviset, som kräver 12 rader text, visar att meningen $\forall x (Fx \leftrightarrow (x = [n]))$ är sant för något nummer $n$ , men ingen algoritm $M$ identifierar det som sant. Följaktligen överträffar sanningen i aritmetik beviset. QED.

Ovanstående predikat innehåller de enda existentiella kvantifierarna som visas i hela beviset. '<' Och '×' som visas i dessa predikat är de enda definierade aritmetiska begrepp som beviset kräver. Beviset nämner ingenstans rekursiva funktioner eller några fakta från talteorin , och Boolos hävdar att hans bevis avstår från diagonalisering . Mer information om detta bevis finns i Berrys paradox .

Referenser

1931, "Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme, I." Monatshefte für Mathematik und Physik 38 : 173–98.
Engelska översättningar av föregående:
- Jean van Heijenoort , 1967. Från Frege till Gödel: En källbok om matematisk logik . Harvard University Press: 596–616.
- Hirzel, Martin (trans.), 2000, "Om formellt obeslutbara förslag från Principia Mathematica och relaterade system I." .
1951, "Några grundläggande teoremer om matematikens grundval och deras implikationer" i Solomon Feferman , red., 1995. Samlade verk / Kurt Gödel, Vol. III . Oxford University Press: 304–23.
George Boolos , 1998, "A New Proof of the Gödel Inccompleteness Theorem" i Boolos, G., Logic, Logic, and Logic . Harvard Univ. Tryck.

Citat

externa länkar

Ett kortfattat bevis på Gödel's Ofullständighetssats.

Languages

In other projects