Completezza (logica matematica)
Da Wikipedia, l'enciclopedia libera.
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.
[modifica] Completezza sintattica e semantica
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.
[modifica] Esempi
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.
