Esercizio di logica... per me sempre più complicato...
Ragazzi non vedo l'ora il tormento di questa materia sia finito.....
Il linguaggio L contiene ncontiene solo il predicato P (x). Sia T la teoria di tutte le L-strutture M , così che in M gli insiemi P e M \ P siano infiniti.
(i) Assiomatizzare T in modo ricorsivo
ii) Dimostrare che due modelli numerabili di T sono isomorfi.
iii) Dimostrare la competezza di T
iv) Dimostrare che T è decidibile.
Grazie... ma io non ho ancora capito come vanno fatti questi esercizi!!!
Il linguaggio L contiene ncontiene solo il predicato P (x). Sia T la teoria di tutte le L-strutture M , così che in M gli insiemi P e M \ P siano infiniti.
(i) Assiomatizzare T in modo ricorsivo
ii) Dimostrare che due modelli numerabili di T sono isomorfi.
iii) Dimostrare la competezza di T
iv) Dimostrare che T è decidibile.
Grazie... ma io non ho ancora capito come vanno fatti questi esercizi!!!
Risposte
Se conosci i teoremi che riguardano la decidibilità dei linguaggi che contengono solo predicati unari, l'esercizio è immediato... Li conosci?
Allora quello che io conosco è quanto segue:
Una teoria T è assiomatizzata in modo ricorsivo se l'insieme che contiene i numeri di Goedel di T è ricorsivo.
Ma io non ho capito come si fa ad assiomatizzare in modo ricorsivo... cosa devo davvero fare nel mio caso.
L'altra conoscenza che ho e sicuramente utile per questo esercizio è che se T è assiomatizzata in modo ricorsivo ed è completa allora è decidibile (quindi se dimostro il (i) e (iii) il (iv) segue senza dover fare nulla.
Ma teoremi specifici su linguaggi che contengono solo predicati unari purtroppo non li conosco. Il prof non li ha citati.
Una teoria T è assiomatizzata in modo ricorsivo se l'insieme che contiene i numeri di Goedel di T è ricorsivo.
Ma io non ho capito come si fa ad assiomatizzare in modo ricorsivo... cosa devo davvero fare nel mio caso.
L'altra conoscenza che ho e sicuramente utile per questo esercizio è che se T è assiomatizzata in modo ricorsivo ed è completa allora è decidibile (quindi se dimostro il (i) e (iii) il (iv) segue senza dover fare nulla.
Ma teoremi specifici su linguaggi che contengono solo predicati unari purtroppo non li conosco. Il prof non li ha citati.
Non mi torna la terminologia che usi. Io ho sempre detto, e ho conferma in un libro che ho sottomano, che una teoria T è assiomatizzabile se esiste un insieme A di formule ricorsivo, tale che T è esattamente l'insieme delle formule deducibili da A (i.e., le formule che sono conseguenza logica di A). Inoltre una teoria T è decidibile se l'insieme che contiene i numeri di Godel di T è ricorsivo. Non è che stai confondendo le definizioni?
Un'altra domanda: nel linguaggio L è supposto esserci anche il simbolo di uguaglianza?
Un'altra domanda: nel linguaggio L è supposto esserci anche il simbolo di uguaglianza?
Le definizioni che ho scritto sono proprio quelle che trovo sulle dispense del corso e su il libro sel corso. Ho ricontrollato in questo momento.
No il simbolo di uguaglianza non è contenuto.
No il simbolo di uguaglianza non è contenuto.
Molto strano... Visto che abbiamo qualche problema di interfaccia, ti darò le intuizioni per risolvere i problemi e dovrai pensare tu a tradurle nella tua terminologia.
L' idea è che T è esattamente l'insieme delle formule vere nel modello M il cui universo e' $NN$ e $P=2NN$ , la qual cosa si dimostra attraverso ii). Inoltre si puo' vedere che una formula di T e' vera in M se e solo se e' vera assegnando come valori alle variabili della formula gli elementi 0 e 1. Poiche' dunque si puo' verificare con un numero finito di passi se una formula e' vera in M, ne segue che T e' ricorsivamente assiomatizzabile. La completezza e' ovvia in quanto M rende vera, per ogni formula A, o A o la sua negazione.
L' idea è che T è esattamente l'insieme delle formule vere nel modello M il cui universo e' $NN$ e $P=2NN$ , la qual cosa si dimostra attraverso ii). Inoltre si puo' vedere che una formula di T e' vera in M se e solo se e' vera assegnando come valori alle variabili della formula gli elementi 0 e 1. Poiche' dunque si puo' verificare con un numero finito di passi se una formula e' vera in M, ne segue che T e' ricorsivamente assiomatizzabile. La completezza e' ovvia in quanto M rende vera, per ogni formula A, o A o la sua negazione.
Nel testo dell'esercizio dice di non dimostrare formalmente che T è assiomatizzabile in modo ricorsivo, ma semplicemente di assiomatizzarla in modo ricorsivo, io non riesco a capire che cosa dovrei fare.
Ancora una cosa.... credo di essere riuscita a dimostrare il terzo punto utilizzando il secondo.
Non sia ¬φ una conseguenza di T. Allora T∪{φ} possiede un modello N. Sia N1 un modello di T, allora da (ii) segue che N e N1 sono isomorfi e quindi ne consegue N1 ⊨ φ . Quindi T ⊢ φ.
Giusto?
Non sia ¬φ una conseguenza di T. Allora T∪{φ} possiede un modello N. Sia N1 un modello di T, allora da (ii) segue che N e N1 sono isomorfi e quindi ne consegue N1 ⊨ φ . Quindi T ⊢ φ.
Giusto?
"*missdreamer*":
Ancora una cosa.... credo di essere riuscita a dimostrare il terzo punto utilizzando il secondo.
Non sia ¬φ una conseguenza di T. Allora T∪{φ} possiede un modello N. Sia N1 un modello di T, allora da (ii) segue che N e N1 sono isomorfi e quindi ne consegue N1 ⊨ φ . Quindi T ⊢ φ.
Giusto?
Sì, giusto.
Nel testo dell'esercizio dice di non dimostrare formalmente che T è assiomatizzabile in modo ricorsivo, ma semplicemente di assiomatizzarla in modo ricorsivo, io non riesco a capire che cosa dovrei fare.
Non saprei esattamente cosa intenda il tuo testo. Di solito si dà un algoritmo informale per dimostrare che l'appartenenza a T è determinabile computazionalmente e poi si argomenta che dunque T è ricorsivo per la tesi di Church-Turing.
Una curiosità: qual è il libro del corso che segui?
Se il linguaggio $L$ contiene solo i simboli logici usuali {$AA$, $EE$, $=>$, $<=>$, $e$, $o$, $not$}, un solo predicato unario {$P$}, un insieme numerabile di variabili {$x_1$, $x_2$, $x_3$, ...}, i simboli {$($,$)$,$,$} e nient’altro, data una teoria $T$ di $L$ (una teoria $T$ di $L$ è un qualsiasi insieme non vuoto di $L$-formule tale che se è vero che, $X sube T$, $X$ è finito, $y$ è una $L$-formula e $X |-- y$, allora è vero anche che $y in T$),
se $T$ verifica
1) PER OGNI $L$-struttura $M$ (SE $T$ è soddisfatta da $M$ ALLORA l’interpretazione di $P$ in $M$ ed il sostegno di $M$ meno l’interpretazione di $P$ in $M$ sono entrambi insiemi infiniti)
allora $T$ coincide con l’insieme di tutte le $L$-formule (perché insoddisfacibile) e quindi verifica tutti i punti dell'esercizio. Spero di aver interpretato bene le ipotesi poste dall'esercizio, comunque quello che ho scritto è corretto.
se $T$ verifica
1) PER OGNI $L$-struttura $M$ (SE $T$ è soddisfatta da $M$ ALLORA l’interpretazione di $P$ in $M$ ed il sostegno di $M$ meno l’interpretazione di $P$ in $M$ sono entrambi insiemi infiniti)
allora $T$ coincide con l’insieme di tutte le $L$-formule (perché insoddisfacibile) e quindi verifica tutti i punti dell'esercizio. Spero di aver interpretato bene le ipotesi poste dall'esercizio, comunque quello che ho scritto è corretto.
@bub
Quello che hai scritto e' corretto, ma non si riferisce al problema in questione. T non verifica la tua 1). T viene definito come l'insieme delle formule del linguaggio L vere in ogni L-modello M in cui P e il complemento di P nell'universo di M siano infiniti. Almeno io l'ho capito cosi'.
Quello che hai scritto e' corretto, ma non si riferisce al problema in questione. T non verifica la tua 1). T viene definito come l'insieme delle formule del linguaggio L vere in ogni L-modello M in cui P e il complemento di P nell'universo di M siano infiniti. Almeno io l'ho capito cosi'.
Allora dovrebbe essere questa l’interpretazione corretta (sempre con $L$ linguaggio contenente solo il predicato $P$)
$A$ = {$L$-modelli $M$ | l’interpretazione di $P$ in $M$ è un insieme infinito ed il sostegno di $M$ meno l’interpretazione di $P$ in $M$ è un insieme infinito}
$T$ = {$p in L$ | PER OGNI $M in A$, $M |== p$}.
Adesso se ho capito bene il problema, aggiungo solo che una delle possibili assiomatizzazioni finite di $T$ è la seguente {$EE x_1 P(x_1), EE x_1 not P(x_1)$}. Infatti $T$ deve contenere {$EE x_1 P(x_1)$, $EE x_1 not P(x_1)$} e non è difficile provare che una teoria $T’$ di $L$ (contenente solo in predicato $P$) che abbia le due formule come assiomi deve essere completa (però è un po’ scocciante dimostrarlo usando il sistema che conosco), il che assicura che $T$ non contiene altre formule, visto che $T$ è anche coerente essendo la classe $A$ (è meglio scrivere così) non vuota
Io comunque ero insicuro su come interpretare la frase “Sia T la teoria di tutte le L-strutture M , così che in M gli insiemi P e M \ P siano infiniti”, infatti avevo scritto “Spero di aver interpretato bene le ipotesi poste dall'esercizio”. Fields, che dirti, grazie per il chiarimento: se ho frainteso ancora, beh... è meglio che non intervenga più
, ciao!
$A$ = {$L$-modelli $M$ | l’interpretazione di $P$ in $M$ è un insieme infinito ed il sostegno di $M$ meno l’interpretazione di $P$ in $M$ è un insieme infinito}
$T$ = {$p in L$ | PER OGNI $M in A$, $M |== p$}.
Adesso se ho capito bene il problema, aggiungo solo che una delle possibili assiomatizzazioni finite di $T$ è la seguente {$EE x_1 P(x_1), EE x_1 not P(x_1)$}. Infatti $T$ deve contenere {$EE x_1 P(x_1)$, $EE x_1 not P(x_1)$} e non è difficile provare che una teoria $T’$ di $L$ (contenente solo in predicato $P$) che abbia le due formule come assiomi deve essere completa (però è un po’ scocciante dimostrarlo usando il sistema che conosco), il che assicura che $T$ non contiene altre formule, visto che $T$ è anche coerente essendo la classe $A$ (è meglio scrivere così) non vuota
Io comunque ero insicuro su come interpretare la frase “Sia T la teoria di tutte le L-strutture M , così che in M gli insiemi P e M \ P siano infiniti”, infatti avevo scritto “Spero di aver interpretato bene le ipotesi poste dall'esercizio”. Fields, che dirti, grazie per il chiarimento: se ho frainteso ancora, beh... è meglio che non intervenga più
, ciao!
"bub":
Io comunque ero insicuro su come interpretare la frase “Sia T la teoria di tutte le L-strutture M , così che in M gli insiemi P e M \ P siano infiniti”, infatti avevo scritto “Spero di aver interpretato bene le ipotesi poste dall'esercizio”. Fields, che dirti, grazie per il chiarimento: se ho frainteso ancora, beh... è meglio che non intervenga più
No, no, ora non hai frainteso, anzi ti esorto a intervenire, i tuoi interventi sono molto precisi
fields, ma l'isomorfismo dei modelli lo si deve dimostrare soltanto per quelli che appartengono alla classe $A$, giusto? Perché non mi sembra vero che due modelli numerabili ($L$-strutture) qualsiasi che soddisfano $T$ siano isomorfi.
"bub":
fields, ma l'isomorfismo dei modelli lo si deve dimostrare soltanto per quelli che appartengono alla classe $A$, giusto? Perché non mi sembra vero che due modelli numerabili ($L$-strutture) qualsiasi che soddisfano $T$ siano isomorfi.
Sì, hai ragione, due modelli numerabili qualsiasi di T non sono fra loro isomorfi. Anch'io quindi ho interpretato che si dovesse dimostrare l'isomorfismo dei modelli numerabili della classe A. Certo il testo di questo esercizio è impreciso e inusuale, a cominciare dalle definizione del concetto di assiomatizzabilità riferita da missdreamer, che è abbastanza strana.
Va bene, grazie fields. Anche io conoscevo la tua stessa definizione di ricorsivamente assiomatizzabile... adesso mi è tutto chiaro. Ora devo andare, ciao!
Scusate l'assenza....
non sono più riuscita a collegarmi... grazie per le risposte... ma non ho ancora capito come dimostrare che due modelli sono isomorfi... scusatemi!! Potreste spiegarmelo?
Il testo da cui sono tratte le definizione è Tuschik - Wolter
non sono più riuscita a collegarmi... grazie per le risposte... ma non ho ancora capito come dimostrare che due modelli sono isomorfi... scusatemi!! Potreste spiegarmelo?
Il testo da cui sono tratte le definizione è Tuschik - Wolter
Devi dimostrare che esiste una biettivita' f dall'universo U' di un modello M nell'universo U" di un modello N tale che P'(a) sse P''(f(a)), dove P' e P'' sono le interpretazioni del simbolo P risp. in M e N. Se M e N sono numerabili e con P' e U'\P' infiniti e P'' e U''\P''infiniti, trovare f e' immediato. Esistono infatti biettivita' $g: P'\rightarrow NN$ e $h: NN\rightarrow P''$ e $k:U'\\P'\rightarrow NN$ e $l: NN\rightarrow U''\\P''$. Poni allora $f(x)=h(g(x))$ se $P'(x)$, $f(x)=l(k(x))$ altrimenti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo