Completitudine (logică matematică)

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În logica matematică, conceptul de completitudine exprimă faptul că un set de axiome este suficient pentru a demonstra toate adevărurile unei teorii și, prin urmare, pentru a decide adevărul sau falsitatea oricărei afirmații care poate fi formulată în limbajul teoriei.

Completitatea sintactică și semantică

O primă noțiune de completitudine se referă doar la aspectul sintactic al unei teorii (nu este deci legată de modelele sale): o teorie de ordinul întâi T se spune că este sintactică completă dacă este posibil în T să demonstreze sau să respingă formal orice afirmație în limbajul teoriei, adică dacă pentru fiecare formulă bine formată φ este posibil fie să se demonstreze φ, fie să se demonstreze ¬φ. Cu alte cuvinte, T este complet sintactic dacă nu există o propoziție indecidabilă în T.

Dacă luăm în considerare o teorie de ordinul întâi T și modelul său , putem lua în considerare o altă noțiune de completitudine: vom spune că T este complet semantic dacă poate dovedi orice formulă φ care este adevărată în model.

Completitudinea sintactică este în sine o proprietate mai puternică decât completitudinea semantică.

Exemple

Exemplul cel mai banal al unei teorii incomplete din punct de vedere sintactic este dat de o teorie fără axiome proprii și dotată cu o constantă individuală a și o relație unară R. În acest caz nu este posibil să se demonstreze nici R (a) și nici ¬ R (a) folosind singur axiomele logice . Dacă dotăm această teorie cu singura axiomă propriu-zisă R (a) obținem în schimb o teorie completă din punct de vedere sintactic.

Exemple mai sofisticate de teorii incomplete din punct de vedere sintactic (și pentru care dovada incompletitudinii este netivială) sunt aritmetica lui Robinson și aritmetica lui Peano .

Aceste rezultate ale incompletitudinii arată, printre altele, că în orice teorie mai puternică a aritmeticii lui Robinson și, prin urmare, de exemplu, în orice posibilă axiomatizare a matematicii în sine, există propoziții indecidabile.

Deși, în general, ne putem imagina luând o teorie incompletă și adăugând o serie de propoziții indecidabile ca axiome până când aceasta este completă, în aceste cazuri acest proces nu funcționează, deoarece se pot găsi întotdeauna noi propoziții indecidabile.

Elemente conexe

Matematica Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică