Correttezza e completezza

Due domande sul sistema del corso

L’unità sulla deduzione ha fissato il sistema del corso: gli schemi di assioma A1, A2 e A3 di Łukasiewicz e due regole, il modus ponens (MP) e la sostituzione della doppia negazione (SDN), che la lezione sulle quattro tecniche di deduzione ha aggiunto dopo aver dimostrato la doppia negazione. Una deduzione da un insieme $\Gamma$ è una successione finita di formule in cui ciascuna è un assioma, un elemento di $\Gamma$, il risultato del modus ponens applicato a due formule precedenti o il risultato della SDN applicata a una precedente; $\Gamma \vdash \varphi$ significa che esiste una deduzione da $\Gamma$ la cui ultima formula è $\varphi$. L’unità sulla semantica, a sua volta, ha definito nella lezione su conseguenza ed equivalenza semantica la relazione $\Gamma \models \varphi$: ogni assegnazione che soddisfa tutte le formule di $\Gamma$ soddisfa $\varphi$. Entrambe le relazioni si scrivono con lo stesso schema, un insieme a sinistra e una formula a destra; ma la loro natura è opposta. La prima è sintattica ed esistenziale: afferma che esiste un oggetto finito, una deduzione, che si può controllare segno per segno. La seconda è semantica e universale: afferma qualcosa su tutte le assegnazioni, che sono infinite e ciascuna delle quali dà valore a infinite variabili.

Sul sistema si pongono quindi due domande. La prima: deduce soltanto ciò che deve? Il sistema si dice corretto se, per ogni insieme $\Gamma$ e ogni formula $\varphi$, da $\Gamma \vdash \varphi$ segue $\Gamma \models \varphi$: ciò che si deduce da premesse date è vero sotto ogni assegnazione che rende vere le premesse. La seconda: deduce tutto ciò che deve? Il sistema si dice completo se da $\Gamma \models \varphi$ segue $\Gamma \vdash \varphi$. La completezza ammette tre gradi, secondo gli insiemi di premesse che comprende:

• completezza debole: se $\models \varphi$, allora $\vdash \varphi$; ogni tautologia è un teorema;
• completezza per insiemi finiti di premesse: se $\{\gamma_{1}, \ldots, \gamma_{k}\} \models \varphi$, allora $\{\gamma_{1}, \ldots, \gamma_{k}\} \vdash \varphi$;
• completezza forte: se $\Gamma \models \varphi$, allora $\Gamma \vdash \varphi$, per un insieme $\Gamma$ qualsiasi, anche infinito.

Questa lezione dimostra la correttezza e i primi due gradi della completezza. Il terzo si dimostra nella lezione sul teorema di compattezza, e la ragione di questa ripartizione si spiega alla fine della lezione.

Che cosa non dire

In spagnolo la correttezza si chiama talvolta «solvencia», un calco dell’inglese soundness; il termine spagnolo è «corrección», ed è quello che il corso usa in spagnolo. Né va definita come la proprietà del sistema di «inferire un’espressione da un insieme di espressioni», perché questa è la deducibilità stessa e non una proprietà del sistema. Gli errori di contenuto, però, sono altri due.

Il primo consiste nell’affermare che correttezza e completezza «si inferiscono l’una dall’altra». Sono proprietà indipendenti: il sistema di Łukasiewicz senza la regola SDN è corretto (lo mostra la dimostrazione di questa lezione, togliendo un caso) e non è completo (la lezione sui sistemi deduttivi formali ha esibito una tautologia che non deduce); e un sistema che ammettesse tutte le formule come assiomi sarebbe completo senza essere corretto. Il problema risolto 2 studia entrambi gli esempi.

Il secondo errore è più grave, perché presenta un argomento circolare come dimostrazione della completezza. Dice, in sostanza: se $\varphi \nvdash \psi$, allora per il teorema di deduzione $\nvdash (\varphi \rightarrow \psi)$; «per la correttezza» $\not\models (\varphi \rightarrow \psi)$; e per il teorema di deduzione semantico $\varphi \not\models \psi$. Ora, la correttezza afferma che ciò che è deducibile è valido, e la sua contrapposizione che ciò che non è valido non è deducibile:

Il passo dell’argomento va nella direzione opposta, da $\nvdash \chi$ a $\not\models \chi$, e questa è la contrapposizione di $\models \chi \Rightarrow \vdash \chi$, cioè della completezza debole. Se è così, l’argomento presuppone ciò che vuole dimostrare. Ne segue che la completezza non «si inferisce in modo semplice»: è il risultato più profondo del corso, e la sua dimostrazione occupa la maggior parte di questa lezione. Infine, è impreciso riassumere la completezza dicendo che «tutte le espressioni vere hanno una dimostrazione»; ha una dimostrazione ciò che è valido, vero sotto ogni assegnazione, non ciò che è vero sotto qualcuna: la variabile $v_{1}$ è vera sotto molte assegnazioni e non è un teorema.