Teorie completă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 20 august 2020; verificările necesită 2 modificări .

În logica matematică , o teorie se numește completă dacă orice formulă închisă corectă din punct de vedere sintactic sau negația ei este demonstrabilă în această teorie [1] . Dacă există o formulă închisă astfel încât nici negația nu este demonstrabilă în teorie , atunci o astfel de teorie se numește incompletă . Închiderea unei formule înseamnă că nu conține parametri externi, iar corectitudinea sintactică înseamnă că se conformează regulilor limbajului formal al teoriei. Demovabilitatea unei formule este înțeleasă ca existența unei secvențe de enunțuri formale, fiecare dintre ele fie o axiomă a teoriei, fie este obținută conform regulilor formale de derivare din enunțurile anterioare și ultima afirmație din succesiune. coincide cu formula care se dovedește. $\varphi$ $\varphi$ $\varphi$ $T$

Informal vorbind, o teorie este completă dacă orice afirmație bine formulată din ea poate fi dovedită sau infirmată. Astfel, în logica clasică , orice teorie contradictorie este în mod evident completă, deoarece orice formulă din ea este derivată împreună cu negația ei. Din celebra teoremă de incompletitudine a lui Gödel rezultă că orice teorie consistentă de ordinul întâi axiomatizabilă recursiv suficient de puternică este incompletă. În special, aceasta este aritmetica Peano - o teorie care descrie proprietățile obișnuite ale numerelor naturale cu adunare și înmulțire.

Conceptul de completitudine a unei teorii introdus mai sus nu trebuie confundat cu conceptul de completitudine a logicii , ceea ce înseamnă că în orice teorie a acestei logici, toate formulele valide se vor dovedi a fi derivate din axiomele logicii. De exemplu, teorema de completitate a lui Gödel afirmă că logica clasică de ordinul întâi este completă. Aceasta înseamnă că, în orice teorie de ordinul întâi, orice formulă identic adevărată (adică adevărată, indiferent de interpretarea semnăturii și a valorilor variabilelor) va fi derivată.

Exemple de teorii complete

Calculul propozițiilor de ordinul doi .
Sistemul de axiome al lui Tarski pentru geometria euclidiană .
Aritmetica Presburger este o teorie care descrie numerele naturale cu adunare, dar fără înmulțire.
Teoria numerelor raționale cu relație de ordine și adunare.
Teoria câmpurilor cu adevărat închise . În special, teoria numerelor reale cu adunare, înmulțire și relație de ordine ( teorema Seidenberg-Tarski ).
Teoria mulțimilor dense ordonate liniar fără primul și ultimul element.

Exemple de teorii care nu sunt complete

Este clar intuitiv că teoriile cele mai generale, cum ar fi, de exemplu, teoria grupurilor , teoria mulțimilor ordonate liniar , nu trebuie să fie complete: altfel, aceasta ar însemna că aceleași formule închise sunt valabile pentru toate grupurile sau pentru toate multimile ordonate liniar. Este evident că nu este cazul.

Aritmetică formală cu adunarea și înmulțirea numerelor naturale. Un exemplu non-trivial de afirmație scrisă în limbajul acestei teorii și care nu poate fi demonstrată în ea este teorema secvenței lui Goodstein .
Teoria semigrupurilor cu înmulțire care conține axioma asociativității.
Teoria grupurilor cu axiomele asociativității, existența unui element neutru și invers.
O teorie a egalității care conține un singur predicat al egalității și axiomele egalității .

Vezi și

Note

↑ Lyndon R., 1968 , p. 56.

Literatură

Vereshchagin N.K., Shen A. Prelegeri despre logica matematică și teoria algoritmilor. Partea 2: Limbi și calcul Arhivat 30 noiembrie 2016 la Wayback Machine , M.: MCNMO , 2012.
Gilbert D., Akkerman V. Fundamentele logicii teoretice. - M. : URSS, 2010. - 304 p. — ISBN 978-5-484-01144-5 .
Curry, Haskell B. Fundamentele logicii matematice. — M .: Mir, 1969. — 567 p.
Kleene S.K. Introducere în metamatematică. - M . : Editura de Literatură Străină, 1957. - 526 p.
Lyndon R. Note despre logică. - M . : Mir, 1968. - 128 p.