Esercizio di logica... per me sempre più complicato...

[*missdreamer*]

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!!!

[fields]

Se conosci i teoremi che riguardano la decidibilità dei linguaggi che contengono solo predicati unari, l'esercizio è immediato... Li conosci?

[*missdreamer*]

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.

[fields]

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?

[*missdreamer*]

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.

[fields]

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.

[*missdreamer*]

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.

[*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?

[fields]

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?

[bub]

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.