Teorema di compattezza (logica matematica)

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

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

• 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

Enunciato:

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

Dimostrazione

Dato che ogni dimostrazione di una teoria assiomatica fa uso di un numero finito di assiomi, se da un dato insieme di formule si deduce $\varphi \wedge \neg \varphi$, allora si può dedurre la stessa contraddizione anche da un suo sottoinsieme finito. Inoltre, se da un sottoinsieme finito di un insieme di formule si deduce una contraddizione, chiaramente tale contraddizione si deduce anche dall'insieme di formule di partenza. Dunque un insieme di formule non è coerente se e solo se esiste almeno un suo sottoinsieme finito non coerente, che è equivalente a quanto si doveva dimostrare

Compattezza semantica

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

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ś.

Collegamenti esterni

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