[logica] Corollario Teorema di Compattezza
Faccio il secondo anno di università e sto approcciando alla logica matematica proprio in questi giorni.
Dai miei appunti di logica:
Sia $Gamma$ un insieme di FBF (formule ben formate) e $P$ una proposizione. Si scrive $ Gamma |== P $ se per ogni interpretazione tale che tutte le proposizioni di $Gamma$ sono vere anche $P$ è vera, ossia $P$ è vera in tutte le interpretazioni che sono dei modelli per $Gamma$. Il che si dice "$P$ è conseguenza semantica di $Gamma$".
Poi gli appunti recitano, come corollario al Teorema di Compattezza:
"Sia $Gamma$ un insieme di FBF e $P$ una proposizione. Allora
$ Gamma |== P <=> EE Delta sube Gamma|(Delta |== P)$"
Allora:
l'implicazione da destra a sinistra mi sembra chiara: qualora $P$ sia vera sempre quando $Delta$ è vera, quando $Gamma$ è vera necessariamente $Delta$, che è un suo sottoinsieme, sarà vera e $P$ di conseguenza. Intuitivamente, se una cosa è conseguenza di due cose, se ce ne metti una terza la cosa sarà sempre vera.
E' il contrario che mi sfugge. $P$ può essere conseguenza di tutte quante le FBF di $Gamma$ insieme, ma appena ne rendi falsa una non è più vera. Come se per una tesi abbiamo 3 ipotesi necessarie e ne rendiamo falsa una, la tesi non è più vera. Infatti, immaginate un qualsiasi sottoinsieme proprio di $Gamma$ (cioè che non contiene tutti gli elementi di quest'ultimo): il fatto che $ Gamma |== P $ non implica che, rendendo falsa una delle proposizioni non contenute da questo sottoinsieme, $P$ non diventi falsa. L'unica cosa che $ Gamma |== P $ dice è che se le FBF di $Gamma$ sono TUTTE vere, allora $P$ sarà vera. Quindi, per qualsiasi sottoinsieme proprio $Delta$ di $Gamma$, $P$ può essere falsa nonostante $Delta$ sia vera, il che nega $ Delta |== P $. L'unico sottoinsieme che sicuramente rispetta tale proprietà sarebbe $Gamma$ stesso, però mi sembra che il teorema non avrebbe molto senso se così fosse.
Probabilmente avrò sbagliato io a ragionare o nel capire qualche definizione, vi chiedo comunque delucidazioni in merito.
Dai miei appunti di logica:
Sia $Gamma$ un insieme di FBF (formule ben formate) e $P$ una proposizione. Si scrive $ Gamma |== P $ se per ogni interpretazione tale che tutte le proposizioni di $Gamma$ sono vere anche $P$ è vera, ossia $P$ è vera in tutte le interpretazioni che sono dei modelli per $Gamma$. Il che si dice "$P$ è conseguenza semantica di $Gamma$".
Poi gli appunti recitano, come corollario al Teorema di Compattezza:
"Sia $Gamma$ un insieme di FBF e $P$ una proposizione. Allora
$ Gamma |== P <=> EE Delta sube Gamma|(Delta |== P)$"
Allora:
l'implicazione da destra a sinistra mi sembra chiara: qualora $P$ sia vera sempre quando $Delta$ è vera, quando $Gamma$ è vera necessariamente $Delta$, che è un suo sottoinsieme, sarà vera e $P$ di conseguenza. Intuitivamente, se una cosa è conseguenza di due cose, se ce ne metti una terza la cosa sarà sempre vera.
E' il contrario che mi sfugge. $P$ può essere conseguenza di tutte quante le FBF di $Gamma$ insieme, ma appena ne rendi falsa una non è più vera. Come se per una tesi abbiamo 3 ipotesi necessarie e ne rendiamo falsa una, la tesi non è più vera. Infatti, immaginate un qualsiasi sottoinsieme proprio di $Gamma$ (cioè che non contiene tutti gli elementi di quest'ultimo): il fatto che $ Gamma |== P $ non implica che, rendendo falsa una delle proposizioni non contenute da questo sottoinsieme, $P$ non diventi falsa. L'unica cosa che $ Gamma |== P $ dice è che se le FBF di $Gamma$ sono TUTTE vere, allora $P$ sarà vera. Quindi, per qualsiasi sottoinsieme proprio $Delta$ di $Gamma$, $P$ può essere falsa nonostante $Delta$ sia vera, il che nega $ Delta |== P $. L'unico sottoinsieme che sicuramente rispetta tale proprietà sarebbe $Gamma$ stesso, però mi sembra che il teorema non avrebbe molto senso se così fosse.
Probabilmente avrò sbagliato io a ragionare o nel capire qualche definizione, vi chiedo comunque delucidazioni in merito.
Risposte
Se $P$ segue logicamente da $Gamma$ allora è dimostrabile a partire da $Gamma$, ma una dimostrazione utilizza solo un numero finito di assiomi, quindi $P$ segue logicamente da un sottoinsieme finito di enunciati in $Gamma$
"GLNC":
Se $P$ segue logicamente da $Gamma$ allora è dimostrabile a partire da $Gamma$, ma una dimostrazione utilizza solo un numero finito di assiomi, quindi $P$ segue logicamente da un sottoinsieme finito di enunciati in $Gamma$
Stai citando la completezza, non la compattezza
Come hai ben detto la freccia verso sinistra è banale, mentre la freccia verso destra lo è pure se non imponi \(\Delta\) finito; fatta questa precisazione, si mostra che la freccia verso destra è equivalente al teorema di compattezza considerando la contronominale (o antinominale). TFAE
[*:3mijpbkj] per ogni \(\Delta \subseteq \Gamma\) finito si ha \(\Delta \not\models P\) [/*:m:3mijpbkj]
[*:3mijpbkj] per ogni \(\Delta \subseteq \Gamma\) finito \(\Delta \cup \{\neg P\}\) è consistente[/*:m:3mijpbkj]
[*:3mijpbkj] la teoria \(T \cup \{\neg P\}\) è finitamente consistente[/*:m:3mijpbkj]
[*:3mijpbkj] la teoria \(T \cup \{\neg P\}\) è consistente[/*:m:3mijpbkj]
[*:3mijpbkj] \(T \not\models P\)[/*:m:3mijpbkj][/list:u:3mijpbkj]
Ho dimostrato il teorema di compattezza, usando la completezza, in una formulazione che è esattamente quello che doveva dimostrare l'OP, non vedo cosa ti turbi.
Tra l'altro se vuoi che quelle che citi (per dimostrare l'ovvio nel modo più lungo possibile) siano equivalenze (cosa comunque non necessaria per risolvere l'esercizio) stai usando anche te una forma del teorema di completezza
Tra l'altro se vuoi che quelle che citi (per dimostrare l'ovvio nel modo più lungo possibile) siano equivalenze (cosa comunque non necessaria per risolvere l'esercizio) stai usando anche te una forma del teorema di completezza
Premesso che ho capito solo parzialmente le votre risposte (ho appena iniziato!), stavo facendo il seguente ragionamento:
Il teorema di compattezza afferma che:
"Un insieme di FBF è soddisfacibile se e solo se lo è ogni suo sottoinsieme finito"
che, prese le due contronominali e unite, diventa
"Un insieme di FBF è insoddisfacibile se e solo se esiste un sottoinsieme finito insoddisfacibile". (1)
Che io supporrò essere un sottoinsieme PROPRIO in quanto se il sottoinsieme fosse uguale all'insieme stesso, secondo me almeno, non avrebbe molto senso il teorema.
Abbiamo anche il seguente teorema nei miei appunti:
$ Gamma |== Q <=> $[$Gamma uu {negQ}$ è insoddisfacibile] (2)
la cui dimostrazione è facile:
La freccia destra del suddetto Corollario al teorema di compattezza, che riscrivo per comodità:
allora risulta conseguenza di questi due teoremi:
Ora, consideriamo l'insieme $X$ di FBF ${A,B,neg(A^^B)}$ dove A e B sono FBF atomiche, quindi il cui valore di verità non dipende dal valore di verità di altre proposizioni, quindi mai contraddizioni nè tautologie o detto in altro modo soddisfatte si o no "liberamente" a seconda dell'interpretazione. Ovviamente, l'insieme $X$ è insoddisfacibile: se A è vero e B è vero, A e B è vero, non (A e B) è falso. Però consideriamo tutti i sottoinsiemi propri:
1) ${A,B}$: ovviamente soddisfacibile
2) ${A,neg(A^^B)}$, soddisfacibile con A vero e B falso
3) ${B,neg(A^^B)}$, soddisfacibile con B vero e A falso
per cui l'unico sottoinsieme soddisfacibile è lo stesso sottoinsieme, non ce ne è neanche uno PROPRIO e allora il teorema (1) non vale più per sottoinsiemi propri. Quindi tutto il ragionamento fatto finora non vale. Riprendendo la dimostrazione della freccia verso destra, quello nello spoiler,
$ Gamma |== P => $[$Gamma uu {negP}$ è insoddisfacibile] $=> $esiste un sottoinsieme (NON NECESSARIAMENTE PROPRIO) di $Gamma uu {negP}$ insoddisfacibile $=>$ è possibile che il sottoinsieme insoddisfacibile sia unicamente lo stesso $Gamma uu {negP} =>$ è possibile che ogni $Delta uu {negP}$ con $Delta sube Gamma$ sia soddisfacibile $=>$ è possibile che non esista $(Delta sube Gamma)|(Delta |== P)$.
Ditemi dove sto sbagliando a ragionare.
Il teorema di compattezza afferma che:
"Un insieme di FBF è soddisfacibile se e solo se lo è ogni suo sottoinsieme finito"
che, prese le due contronominali e unite, diventa
"Un insieme di FBF è insoddisfacibile se e solo se esiste un sottoinsieme finito insoddisfacibile". (1)
Che io supporrò essere un sottoinsieme PROPRIO in quanto se il sottoinsieme fosse uguale all'insieme stesso, secondo me almeno, non avrebbe molto senso il teorema.
Abbiamo anche il seguente teorema nei miei appunti:
$ Gamma |== Q <=> $[$Gamma uu {negQ}$ è insoddisfacibile] (2)
la cui dimostrazione è facile:
La freccia destra del suddetto Corollario al teorema di compattezza, che riscrivo per comodità:
allora risulta conseguenza di questi due teoremi:
Ora, consideriamo l'insieme $X$ di FBF ${A,B,neg(A^^B)}$ dove A e B sono FBF atomiche, quindi il cui valore di verità non dipende dal valore di verità di altre proposizioni, quindi mai contraddizioni nè tautologie o detto in altro modo soddisfatte si o no "liberamente" a seconda dell'interpretazione. Ovviamente, l'insieme $X$ è insoddisfacibile: se A è vero e B è vero, A e B è vero, non (A e B) è falso. Però consideriamo tutti i sottoinsiemi propri:
1) ${A,B}$: ovviamente soddisfacibile
2) ${A,neg(A^^B)}$, soddisfacibile con A vero e B falso
3) ${B,neg(A^^B)}$, soddisfacibile con B vero e A falso
per cui l'unico sottoinsieme soddisfacibile è lo stesso sottoinsieme, non ce ne è neanche uno PROPRIO e allora il teorema (1) non vale più per sottoinsiemi propri. Quindi tutto il ragionamento fatto finora non vale. Riprendendo la dimostrazione della freccia verso destra, quello nello spoiler,
$ Gamma |== P => $[$Gamma uu {negP}$ è insoddisfacibile] $=> $esiste un sottoinsieme (NON NECESSARIAMENTE PROPRIO) di $Gamma uu {negP}$ insoddisfacibile $=>$ è possibile che il sottoinsieme insoddisfacibile sia unicamente lo stesso $Gamma uu {negP} =>$ è possibile che ogni $Delta uu {negP}$ con $Delta sube Gamma$ sia soddisfacibile $=>$ è possibile che non esista $(Delta sube Gamma)|(Delta |== P)$.
Ditemi dove sto sbagliando a ragionare.
Ho letto velocemente ma secondo me non sbagli da nessuna parte , quel corollario e' formulato in maniera orrenda e l'esercizio è inutile. Come hai ben visto da solo, l'unico caso interessante è quando $Gamma$ è infinito e $Delta$ un suo sottoinsieme finito. Se anche $Gamma$ è finito, può benissimo accadere che tu abbia bisogno di tutto $Gamma$ per trovare l'insoddisfacibilita', per questo nel corollario non c'è inclusione stretta. Il modo migliore per capire il teorema di compattezza, è vederlo nella formulazione che ti ho dato (e dimostrato sfruttando la completezza) nella mia prima risposta, e da cui l'esercizio segue banalmente. Per esercizio potresti dimostrare che è equivalente al teorema di compattezza che hai te.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo