Teorema completitudinii lui Gödel
Teorema completitudinii lui Gödel este o teoremă fundamentală a logicii matematice obținută de logicianul Kurt Gödel în 1929 . Stabilește o corespondență între validitatea logică și probabilitatea logică în logica primului ordin .
Se spune că o formulă de ordinul întâi este validă logic dacă este adevărată în fiecare structură a limbajului său. Teorema completitudinii arată că, dacă o formulă este validă, atunci există o dovadă a formulei, care poate fi obținută în număr finit de pași. Prin urmare, deducția este verificabilă manual sau computerizat. Relația dintre adevăr și probabilitate stabilește o legătură strânsă între teoria modelelor și teoria probabilității în logica matematică.
O consecință importantă a teoremei completitudinii este că este posibil să se enumere consecințele logice ale oricărei teorii de ordinul întâi, enumerând toate deducțiile corecte folosind axiomele teoriei.
Teoremele lui Gödel de la completitudinea , referindu -se la un alt sens suplimentar, arată că, în cazul în care o formalizare de putere suficient de aritmetică este consecventă , atunci există o formulă F, dependentă de formalizarea aleasă, pentru care nici adevărul, nici adevărul a negării sale.
Originea problemei
Au fost propuse numeroase sisteme de deducție pentru logica de ordinul întâi, cum ar fi deducția naturală sau sistemul deductiv al lui Hilbert. În comun tuturor acestor sisteme există noțiunea de deducere formală care poate fi, în funcție de caz, o succesiune sau un arbore de formule în care fiecare trecere de la o formulă la alta este justificată de o regulă de deducție definită în același sistem. Ultima dintre aceste formule este considerată concluzia teoremei. Definiția regulilor deductive și definiția deducției formale este astfel încât fiecare dovadă poate fi verificată cu un algoritm și, prin urmare, de către un computer.
Fiecare formulă este exprimată într-un limbaj specific și este definită logic ca fiind valabilă dacă este adevărată în fiecare structură a limbii respective. Pentru a afirma și a demonstra astfel teorema completitudinii, este necesar, de asemenea, să alegeți un sistem de deducere. Acesta din urmă este definit complet dacă orice formulă validă din punct de vedere logic este concluzia unei deduceri formale. Cu alte cuvinte, într-un sistem deductiv complet, fiecare formulă adevărată este demonstrabilă. În acest sens, există multe teoreme de completitudine, una pentru fiecare sistem deductiv complet.
Formulare și consecințe
Teorema completitudinii lui Gödel afirmă că un sistem deductiv pentru logica predicatelor de ordinul întâi este „complet” în sensul că regulile deducției permit să demonstreze toate formulele valabile din punct de vedere logic. Un alt aspect al aceleiași probleme este teorema corectitudinii care afirmă că toate formulele demonstrabile sunt valabile logic. Aceste două teoreme, dacă ambele sunt dovedite, implică faptul că o formulă este logic valabilă dacă și numai dacă este demonstrabilă (adică este concluzia unei deducții formale).
Într-adevăr, se poate dovedi o versiune mai generală a teoremei completitudinii. Această versiune afirmă că, pentru fiecare teorie de ordinul întâi T și pentru fiecare formulă închisă S în același limbaj ca teoria, există o deducere formală a lui S începând de la T dacă și numai dacă S deține în fiecare model de T. Această versiune mai generală este utilizată implicit, de exemplu, atunci când se arată că o afirmație este demonstrabilă din axiomele teoriei grupurilor luând un grup arbitrar și arătând că această afirmație este satisfăcută în acel grup specific
Ramura logicii matematice care studiază proprietățile generale ale modelelor se numește teoria modelelor . Teoria dovezii studiază ceea ce poate fi dovedit formal într-un anumit sistem formal. Teorema completitudinii stabilește o legătură fundamentală între aceste două lumi, deoarece leagă semantica de sintaxă . Cu toate acestea, teorema completitudinii nu trebuie supraestimată prin confundarea celor două concepte de completitudine: celebra teoremă a incompletitudinii de către Gödel însuși, arată că există limitări insurmontabile la ceea ce se poate realiza cu o dovadă matematică. De fapt, numele teoremei incompletitudinii se referă la un alt sens al termenului complet : teorema completitudinii spune că toate formulele care sunt o consecință logică a unei teorii sunt demonstrabile, teorema incompletitudinii spune că unele formule nu sunt dovedibile și nici mai puțin, sunt consecința logică a unei anumite teorii.
O consecință importantă a teoremei completitudinii este faptul că formulele valabile din punct de vedere logic (și, prin urmare, demonstrabile) ale unei teorii sunt doar o cantitate numărabilă . Definiția unei formule logice valabile afectează simultan toate structurile unui anumit limbaj și, prin urmare, nu oferă în mod direct un algoritm pentru verificarea validității unei formule. Mai mult, datorită teoremei incompletitudinii, setul de formule logice valabile nu poate fi decis. Totuși, teorema completitudinii implică faptul că setul de formule care sunt consecințele unei teorii consistente este contabil: algoritmul ar trebui, mai întâi, să numere toate deducțiile formale care pot fi obținute din teorie și să folosească aceasta pentru a număra concluziile oricărui deducere. Natura sintactică a deducțiilor formale care sunt secvențe finite sau arbori face posibilă construirea acestui algoritm.
Relația cu teorema compactității
Teorema completitudinii și teorema compactității sunt două pietre de temelie pentru logica de ordinul întâi. Deși niciuna dintre aceste două teoreme nu este dovedită în detaliu, fiecare poate fi dedusă prin presupunerea celeilalte.
Teorema compactității afirmă că, dacă o formulă φ este o consecință logică a unui set de formule Γ (potențial infinit), atunci este și o consecință a unui subset finit de Γ. Aceasta este o consecință directă a teoremei completitudinii, deoarece doar un număr finit de ipoteze conținute în Γ poate fi utilizat într-o dovadă formală a lui φ, iar teorema corectitudinii asigură faptul că φ este deci o consecință logică a acestui set finit de ipoteze. Această dovadă a teoremei compactității este cea utilizată inițial de Gödel.
Pe de altă parte, în multe sisteme deductive, este posibil să se demonstreze teorema completitudinii pornind de la teorema compactității.
Ineficiența teoremei completitudinii poate fi măsurată în două moduri: în teoria mulțimilor și în matematică inversă. În teoria mulțimilor , lema ultrafiltrului este o versiune slabă a axiomei de alegere care nu este demonstrabilă în ZF, sistemul axiomelor lui Zermelo și Fraenkel . În ZF se arată că teoremele de completitudine și compactitate sunt echivalente și că ambele sunt echivalente cu lema ultrafiltrului. În matematica inversă , sunt luate în considerare doar structurile și teoriile numărabile. În acest context, teoremele de completitudine și compactitate sunt echivalente între ele și ambele sunt echivalente cu sistemul axiomelor WKL 0 , cu echivalența demonstrabilă în RCA 0 . În special, deși fiecare teorie consistentă și numărabilă a primului ordin are un model finit sau numărabil, ca o consecință a teoremei completitudinii și a teoremei Löwenheim-Skolem , se concluzionează că există într-adevăr teorii de ordinul întâi care nu au modele computabile .
Completitudine în alte logici
Completitudinea este o proprietate fundamentală a logicii de prim ordin care nu este valabilă pentru toate logicele. Logica de ordinul doi, de exemplu, nu are o teoremă de completitudine pentru semantica standard (are în schimb completitudine pentru semantica Henkin) și același lucru este valabil pentru toate logica de ordin superior. Prin urmare, este posibil să construim sisteme deductive corecte în logică de ordin superior, dar astfel de sisteme nu vor fi complete. Mai mult, setul de formule logice valabile în logica de ordinul doi nu este recursiv enumerabil.
O teoremă de completitudine poate fi dovedită pentru logica modală folosind semantica Kripke.
Demonstrații
Dovada originală a lui Gödel reduce problema generală la cazul particular al formulelor exprimate într-o formă sintactică dată și apoi se încheie cu un raționament ad hoc .
În textele logice contemporane, teorema completitudinii este mai degrabă dovedită cu dovada lui Henkin care construiește în mod direct un model pentru orice teorie consistentă de ordinul întâi pornind de la termenii limbajului. În 2004, James Margetson a dezvoltat o dovadă complet computerizată utilizând programul Isabelle [1] , iar alte dovezi sunt disponibile.
Elemente conexe
linkuri externe
- ( EN ) Teorema completitudinii lui Gödel , pe Encyclopedia Britannica , Encyclopædia Britannica, Inc.
