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

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

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.

Teorema di completezza

Il teorema di completezza afferma che, per ogni insieme $\Gamma$ di formule ben formate (fbf) e per ogni fbf $\alpha$, $\alpha$ è una conseguenza logica di $\Gamma$ se e solo se $\alpha$ è dimostrabile da $\Gamma$, in simboli $\Gamma \vDash \alpha \iff \Gamma \vdash \alpha$.

Dimostrazione

Basterà provare $\Gamma \vDash \alpha \implies \Gamma \vdash \alpha$, in quanto l'implicazione opposta è data dal teorema di correttezza. Per assurdo, si assuma $\Gamma \not \vdash \alpha$. Allora $\Gamma \cup \{\neg \alpha \}$ è coerente. Inoltre, esiste una qualche valutazione di verità $\nu$ tale che $\nu (\Gamma \cup \{\neg \alpha \})=1$. In altre parole, si ha $\nu (\Gamma )=1$ e $\nu (\alpha )=0$, ovvero $\Gamma \not \vDash \alpha$.

Voci correlate

• Logica proposizionale
• Teoria del primo ordine
• Decidibilità
• Teoremi di incompletezza di Gödel
• Coerenza (logica matematica)
• Teorema di completezza
• Correttezza (logica matematica)

Collegamenti esterni

• (EN) completeness, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.