Teorema di compattezza (logica matematica)
Da Wikipedia, l'enciclopedia libera.
Nella logica matematica il Teorema di compattezza è un risultato relativo all'esistenza di mdelli per insiemi infiniti di enunciati nell'ambito della logica proposizionale o di un linguaggio del primo ordine.
Indice |
[modifica] 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.
[modifica] 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.
[modifica] Logica del primo ordine
Nel caso di un linguaggio del primo ordine il teorema di compattezza è 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.
[modifica] Voci correlate
Portale Matematica: accedi alle voci di Wikipedia che parlano di matematica
