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 proposizionaleModifica

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 conseguenzeModifica

  • 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 sintatticaModifica

Enunciato:

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

DimostrazioneModifica

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  , allora si può dedurre la stessa contraddizione anche da un suo sottoinsieme finito.

Compattezza semanticaModifica

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

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

DimostrazioneModifica

Sia   un insieme di enunciati del primo ordine e   l'insieme dei suoi sottoinsiemi finiti. Per ogni   sia   un modello di  . Definisco:

 

Dati  , si hanno   per ogni i, perciò  .   ha la proprietà dell'intersezione finita e quindi posso considerare un ultrafiltro   che lo contiene.

Per concludere si dimostra che l'ultraprodotto   è un modello di  .

Sia   un enunciato,   e si può considerare  . Per ogni  , equivalentemente  , si ha che   e perciò:

 

da cui si conclude   e   per il teorema di Łoś.

Collegamenti esterniModifica

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