Teorema di compattezza (logica matematica)

Da Wikipedia, l'enciclopedia libera.

Nella logica matematica il Teorema di compattezza è un risultato relativo alla coerenza o all'esistenza di modelli per insiemi di enunciati nell'ambito della logica proposizionale o di un linguaggio del primo ordine.

Logica proposizionale[modifica | modifica sorgente]

Nell'ambito della logica proposizionale il teorema afferma che:

Se ogni sottoinsieme finito di un insieme S di formule della logica proposizionale è soddisfacibile allora anche S è soddisfacibile.

Applicazioni e conseguenze[modifica | modifica sorgente]

  • Il teorema di compattezza può essere utilizzato per dimostrare che se il teorema dei quattro colori vale per qualsiasi mappa finita allora deve valere anche per mappe infinite.
  • Il teorema di compattezza è alla base dell'Analisi non standard in cui grazie a questo teorema si riescono ad affiancare l'infinito e l'infinitesimo attuale ai numero reali standard con la conseguenza di poter rifondare tutta l'analisi matematica senza bisogno del complicato concetto di limite.

Compattezza sintattica[modifica | modifica sorgente]

Enunciato:

Un insieme di formule è coerente se e solo se ogni suo sottoinsieme finito è coerente.

Dimostrazione[modifica | modifica sorgente]

Dato che ogni dimostrazione di una teoria assiomatica fa uso di un numero finito di assiomi, se da un dato insieme finito di formule si deduce \varphi \wedge \neg\varphi, allora si può dedurre la stessa contraddizione anche da un suo sottoinsieme finito.

Compattezza semantica[modifica | modifica sorgente]

Nel caso di un linguaggio del primo ordine il teorema di compattezza semantica è il seguente:

Se ogni sottoinsieme finito di un insieme \Phi di formule in un linguaggio del primo ordine ha un modello allora anche \Phi ha un modello.

Dimostrazione[modifica | modifica sorgente]

Sia \Phi un insieme di enunciati del primo ordine e \mathrm{J} l'insieme dei suoi sottoinsiemi finiti. Per ogni \Delta \in \mathrm{J} sia \mathcal{I}_\Delta un modello di \Delta. Definisco:

\tilde{\Delta} = \{\Delta' \in \mathrm{J} : \Delta \subseteq \Delta'\}

Dati \Delta_1,...,\Delta_n \in \mathrm{J}, si hanno \Delta_i \subseteq \Delta_1\cup...\cup\Delta_n per ogni i, perciò \Delta_1\cup...\cup\Delta_n \in \tilde{\Delta}_1\cap...\cap\tilde{\Delta}_n. \{\tilde{\Delta} : \Delta\in\mathrm{J}\} ha la proprietà dell'intersezione finita e quindi posso considerare un ultrafiltro \mathcal{U} che lo contiene.

Per concludere si dimostra che l'ultraprodotto \begin{matrix} \prod_{\Delta \in \mathrm{J}} \mathcal{I}_\Delta / \mathcal{U} \end{matrix} è un modello di \Phi.

Sia \phi \in \Phi un enunciato, \{\phi\} \in \mathrm{J} e si può considerare \{\tilde{\phi}\} \in \mathcal{U}. Per ogni \Delta \supseteq \{\phi\}, equivalentemente \Delta \in \{\tilde{\phi}\}, si ha che \mathcal{I}_\Delta \models \phi e perciò:

\tilde{\{\phi\}} \subseteq \{\Delta \in \mathrm{J} : \mathcal{I}_\Delta \models \phi \}

da cui si conclude \{\Delta \in \mathrm{J} : \mathcal{I}_\Delta \models \phi\} \in \mathcal{U} e \begin{matrix} \prod_{\Delta \in \mathrm{J}} \mathcal{I}_\Delta / \mathcal{U} \end{matrix} \models \phi per il teorema di Łoś.

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica