Completezza (logica matematica)
Nella logica matematica il concetto di completezza esprime il fatto che un insieme di assiomi è sufficiente a dimostrare tutte le verità di una teoria e quindi a decidere della verità o falsità di qualunque enunciato formulabile nel linguaggio della teoria.
Completezza sintattica e semantica modifica
Una prima nozione di completezza riguarda solo l'aspetto sintattico di una teoria (non è quindi collegato con i suoi modelli): una teoria del primo ordine T si dice sintatticamente completa se è possibile in T dimostrare o confutare formalmente qualsiasi enunciato nel linguaggio della teoria, ovvero se per ogni formula ben formata φ è possibile o dimostrare φ o dimostrare ¬φ. Detto in altri termini T è sintatticamente completa se non esiste nessun enunciato indecidibile in T.
Se consideriamo una teoria del primo ordine T ed un suo modello possiamo considerare un'altra nozione di completezza: diremo che T è semanticamente completa se può dimostrare qualunque formula φ che sia vera nel modello.
La completezza sintattica è di per sé una proprietà più forte di quella semantica.
Esempi modifica
L'esempio più banale di teoria sintatticamente incompleta è dato da una teoria priva di assiomi propri e dotata di una costante individuale a ed una relazione unaria R. In tal caso non è possibile dimostrare né R(a) né ¬R(a) usando i soli assiomi logici. Se dotiamo tale teoria dell'unico assioma proprio R(a) otteniamo invece una teoria sintatticamente completa.
Esempi più sofisticati di teorie sintatticamente incomplete (e per le quali la dimostrazione di incompletezza è non banale) sono l'aritmetica di Robinson e l'aritmetica di Peano.
Questi risultati di incompletezza dimostrano tra l'altro anche che in qualsiasi teoria più potente dell'aritmetica di Robinson, e quindi ad esempio in qualsiasi possibile assiomatizzazione della matematica stessa, esistono enunciati indecidibili.
Sebbene in generale si possa immaginare di prendere una teoria incompleta ed aggiungere un certo numero di enunciati indecidibili come assiomi fino a renderla completa, in questi casi questo processo non funziona, perché si possono trovare sempre nuovi enunciati indecidibili.
Voci correlate modifica
Collegamenti esterni modifica
- (EN) completeness, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
