Геделова теорема о потпуности

Геделова теорема о потпуности је теорема математичке логике коју је доказао Курт Гедел у својој докторској дисертацији 1929. и касније у раду објављеном 1930. У свом најпознатијем облику, она тврди да је у предикатском рачуну првог реда свака логички ваљана формула доказива. Ово је једна од најважнијих теорема математичке логике, јер показује да класичан предикатски рачун „садржи“ све законе логике који се могу исказати предикатским формулама.

У формулацији Геделове теореме о потпуности, реч доказива је синтактичке природе: она означава да постоји формално извођење формуле у теорији у питању, у овом случају у предикатском рачуну првог реда. Такво извођење–доказ је коначан списак корака у којем се сваки корак или позива на аксиому теорије или се добија из претходних корака применом основних правила закључивања. Када је такво извођење дато, исправност сваког од корака се може проверити алгоритамски (на пример, помоћу рачунара, или ручно). Појам ваљане формуле, пак, је семантички: формула је ваљана ако је тачна у сваком моделу језика формуле (односно свака таква интерпретација је и један њен модел).

Геделова теорема о потпуности показује да су аксиоме и правила закључивања предикатског рачуна првог реда „потпуни“ у смислу да никакве додатне аксиоме или правила закључивања нису потребни како би се извеле све логички ваљане формуле. Комплементарно својство је исправност (семантичка конзистентност или непротивуречност). Теорема о исправности тврди да је предикатски рачун првог реда семантички исправан, односно да се у њему могу извести једино логички ваљана тврђења. Понекад се теорема о исправности третира као део једног, свеобухватног исказа о потпуности, попут формулације самог Гедела из 1929., која у основи гласи:

Постоји рачун предикатске логике првог реда такав да за сваки скуп формула Γ и сваку формулу φ важи: φ следи из Γ ако и само ако се φ може извести из Γ у овом рачуну.

Теорема о потпуности установљава темељну везу између семантике (теорије модела, која изучава шта је тачно у различитим интерпретацијама) и синтаксе (теорије доказа, која изучава шта се може доказати у појединачним формалним системима). Ако $\vDash$ означава семантичку последицу и $\vdash$ изведивост у рачуну, горња Геделова теорема гласи

$\Gamma \vDash \varphi \,\Leftrightarrow \,\Gamma \vdash \varphi$.

Овде, смер здесна налево одговара исправности, а слева надесно потпуности рачуна. Слабији исказ Геделове теореме о потпуности цитиран на почетку чланка, одговара случају када је Γ празан скуп формула (заправо се може доказати да су „слабији“ и „јачи“ исказ еквивалентни). Ова теорема, међутим, не укида нити маргинализује разлику између ова два приступа. У ствари, други резултат који је прославио Гедела, његова теорема о непотпуности, показује да постоје суштинска ограничења у погледу тога шта се у математици може постићи формалним доказима: конкретно, да се унутар довољно богатих теорија не може свака доказати сваки ваљан исказ. (Пажња: име Геделове теореме о непотпуности се односи на друго значење речи „потпун“. Види чланак Теорија модела.)

Геделова теорема о потпуности успоставља теоријску основу аутоматских доказивача, дакле изради и провери доказа помоћу рачунарских програма. Првобитно је чинила и први корак у оквиру Хилбертовог програма (израда потпуног и непротивуречног рачуна за целу математику), све док програм није дотучен управо Геделовом теоремом о непотпуности.

Идеја доказа

Изворни Геделов доказ се данас углавном више не користи. Уместо њега, обично се употребљава следећа „Основна теорема логике првог реда“, коју је формулисао Хенкин 1949.:

Сваки конзистентан скуп формула има модел.

Овде се конзистентност односи на синтаксни појам: кажемо да је скуп формула Γ конзистентан (непротивуречан), ако се из њега у датом рачуну не може извести контрадикција, односно не постоји формула φ таква да је $\Gamma \vdash \varphi$ и $\Gamma \vdash \lnot \varphi$.

Теорема о потпуности се може једноставно доказати претпостављајући ову теорему. И заиста, претпоставимо да је $\Gamma \vDash \varphi$, али није $\Gamma \vdash \varphi$. Рачун има својство да се конзистентном скупу формула може придружити негација формуле која се из њега не може извести при чему је и новодобијени (бројнији) скуп формула и даље конзистентан. У нашем случају, $\Gamma \cup \{\lnot \varphi \}$ је такође конзистентан скуп формула и према Хенкиновој теореми има модел. У таквом моделу је, међутим, φ нетачна, супротно претпоставци да је у питању ваљана формула.

Уопштења и везе са другим тврђењима

Важи и следећи општији облик Геделове теореме о потпуности:

У свакој теорији првог реда T, за дату реченицу S у језику ове теорије постоји извођење S из T ако и само ако је S задовољена у сваком моделу теорије T.

Теорема о потпуности је средишње својство логике првог реда и не вреди у другим логикама. Логика другог реда, на пример, нема своју теорему о потпуности. Такође, потпуност је својство појединачног рачуна P (ознака $\vdash$ за изведивост заправо означава $\vdash _{P}$) и доказ се изводи за конкретан појединачан рачун. Гедел је своју теорему доказао у Хилбертовом рачуну. Такође потпун је, на пример, Генценов рачун секвената, облика природне дедукције.

Геделова теорема о потпуности је екививалентна леми о ултрафилтрима, слабом облику аксиоме избора, у смислу да се еквиваленција може доказати у Зермело-Френкел теорији скупова без аксиоме избора (ZF).

Изворни докази

• Курт Гедел, „О потпуности логичког рачуна“ (Kurt Gödel, "Über die Vollständigkeit des Logikkalküls"), докторска дисертација, Универзитет у Бечу, 1929. Ова дисертација садржи изворни доказ теореме о потпуности.
• Курт Гедел, „Потпуност аксиома логичког функцијског рачуна“ (Kurt Gödel, "Die Vollständigkeit der Axiome des logischen Funktionen-kalküls"), Monatshefte für Mathematik und Physik 37 (1930), 349-360. Овај чланак садржи исти материјал као дисертација, али у прерађеном и скраћеном облику. Докази и објашњења су краћи и изостављен је дугачак увод.