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 wikitesto]

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 wikitesto]

  • 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 wikitesto]

Enunciato:

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

Dimostrazione[modifica | modifica wikitesto]

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 semantica[modifica | modifica wikitesto]

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.

Dimostrazione[modifica | modifica wikitesto]

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

Voci correlate[modifica | modifica wikitesto]

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