Teorema di completezza per teorie del 1° ordine
Riporto il teorema dal mio libro, con queste tre formulazioni equivalenti:
1)Teorema di completezza per CP
I teoremi di CP coincidono con le formule logicamente valide.
\( \forall A \in \mathcal{F} \)
\( \vdash A \Leftrightarrow \models A \)
2)Teorema di completezza per una teoria del 1° ordine ( prima forma )
I teoremi di una teoria T coincidono con le formule vere in tutti i modelli di T
\( \forall A \in \mathcal{F} \)
\( \vdash A \Leftrightarrow \mathcal{M} \models A \) \( \forall \mathcal{M} / \mathcal{M} \models T \)
3)Teorema di completezza per una teoria del 1° ordine ( seconda forma )
Una teoria T è coerente se e solo se ammette un modello.
Per dimostrare le rte equivalenze dimostra prima un verso ( e fin qua tutto ok) dalla sintassi alla semantica e quindi le tre diventano:
a)\( \forall A \in \mathcal{F} \)
\( \vdash A \rightarrow \models A \)
b) Se \( \vdash A \) e \(\mathcal{M} \models T \) allora \( \mathcal{M} \models A \)
c)Se esiste un modello \( \mathcal{M} \) per \( T\) allora \( T\) è coerente
Arriviamo ora alla dimostrazione:
Per la dimostrare a) dice semplicemente che le tautologie e gli schemi Ax1 e Ax2 di assiomi risultano logicamente validi (per definizione e fin qui mi trovo) gli schemi Ax3 e Ax4 anche risultano validi (dice che non è difficile verificarlo ma ..non lo fa.. come si fa?).
Le regole di inferenza, Gen e MD, conservano la validità ossia se le premesse sono valide anche la conclusione lo è. (ok ha senso)
Allora facendo induzione sulla lunghezza delle formule tutti i teoremi di CP sono formule logicamente valide.
Ora questo è quello che ho capito io della dimostrazione (a grandi linee)
Dobbiamo dimostrare che i teoremi del CP risultano formule logicamente valide, e per farlo dobbiamo verificarlo che gli assiomi uniti alla tautologie (o meglio non dovrebbero essere le sostituzioni di tautologie?) e alle regole di inferenza (perchè i teoremi sono questi..giusto?)
La frase sottolineata la interpreto così : data una formula A poiché può essere o conseguenza di uno degli assiomi (o meglio degli schemi) oppure si ottiene tramite le formule di inferenza, e quindi ragiono su questo?
(Penso di essermi espressa in maniera molto poco rigorosa nella mia riflessione ma vorrei solo capire se il mio ragionamento è indirizzata verso la giusta direzione)
A presto con gli sviluppi di questa dimostrazione e con i miei nuovi dubbi
ps: Questo è il mio primo post, se ho sbagliato qualcosa ogni consiglio è ben accetto per migliorarlo e renderlo più comprensibile
1)Teorema di completezza per CP
I teoremi di CP coincidono con le formule logicamente valide.
\( \forall A \in \mathcal{F} \)
\( \vdash A \Leftrightarrow \models A \)
2)Teorema di completezza per una teoria del 1° ordine ( prima forma )
I teoremi di una teoria T coincidono con le formule vere in tutti i modelli di T
\( \forall A \in \mathcal{F} \)
\( \vdash A \Leftrightarrow \mathcal{M} \models A \) \( \forall \mathcal{M} / \mathcal{M} \models T \)
3)Teorema di completezza per una teoria del 1° ordine ( seconda forma )
Una teoria T è coerente se e solo se ammette un modello.
Per dimostrare le rte equivalenze dimostra prima un verso ( e fin qua tutto ok) dalla sintassi alla semantica e quindi le tre diventano:
a)\( \forall A \in \mathcal{F} \)
\( \vdash A \rightarrow \models A \)
b) Se \( \vdash A \) e \(\mathcal{M} \models T \) allora \( \mathcal{M} \models A \)
c)Se esiste un modello \( \mathcal{M} \) per \( T\) allora \( T\) è coerente
Arriviamo ora alla dimostrazione:
Per la dimostrare a) dice semplicemente che le tautologie e gli schemi Ax1 e Ax2 di assiomi risultano logicamente validi (per definizione e fin qui mi trovo) gli schemi Ax3 e Ax4 anche risultano validi (dice che non è difficile verificarlo ma ..non lo fa.. come si fa?).
Le regole di inferenza, Gen e MD, conservano la validità ossia se le premesse sono valide anche la conclusione lo è. (ok ha senso)
Allora facendo induzione sulla lunghezza delle formule tutti i teoremi di CP sono formule logicamente valide.
Ora questo è quello che ho capito io della dimostrazione (a grandi linee)
Dobbiamo dimostrare che i teoremi del CP risultano formule logicamente valide, e per farlo dobbiamo verificarlo che gli assiomi uniti alla tautologie (o meglio non dovrebbero essere le sostituzioni di tautologie?) e alle regole di inferenza (perchè i teoremi sono questi..giusto?)
La frase sottolineata la interpreto così : data una formula A poiché può essere o conseguenza di uno degli assiomi (o meglio degli schemi) oppure si ottiene tramite le formule di inferenza, e quindi ragiono su questo?
(Penso di essermi espressa in maniera molto poco rigorosa nella mia riflessione ma vorrei solo capire se il mio ragionamento è indirizzata verso la giusta direzione)
A presto con gli sviluppi di questa dimostrazione e con i miei nuovi dubbi
ps: Questo è il mio primo post, se ho sbagliato qualcosa ogni consiglio è ben accetto per migliorarlo e renderlo più comprensibile
Risposte
Uau nessuna risposta, ho sbagliato io qualcosa nella domanda? Forse non è chiaro cosa chiedo?
Spero che almeno un'anima pia compaia.. devo ancora postare i miei dubbi sull'altro verso dell'implicazione!
Spero che almeno un'anima pia compaia.. devo ancora postare i miei dubbi sull'altro verso dell'implicazione!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo