Logica: esercizio su teoria dei modelli.
Esercizio.
Il linguaggio L è quello dei grafi (un simbolo di relazione 2-ario r) più infinite costanti {ci : i in N}. Sia T la teoria che contiene Trg più gli assiomi r(ci,cj) per ogni i diverso da j (con Trg la teoria dei grafi aleatori ovvero costituita da i seguenti assiomi: 1) non r(x,x) per ogni x; 2) r(x,y)-->r(y,x) per ogni x e y; 3)esistono x y z tali che x diverso da y diverso da z diverso da x; 4) presi comunque x1,...,xn,y1,..,yn tali che xi diverso da yj per ogni i,j=1....n allora esiste z tale che r(xi,z) per ogni i e non r (yi,z) per ogni i). La teoria T è completa? è N-categorica? Che cardinalità hanno i modelli N-saturi di T?
Svolgimento.
Anzitutto la teoria dei grafi aleatori è N categorica. Avendo questa un linguaggio numerabile (infatti è lo stesso della teoria dei grafi) risulta completa per il teorema di Vaught. Ho pensato di dimostrare la completezza di T dimostrandone 1) la consistenza (coerenza), 2) il fatto che presi comunque due modelli siano elementarmente equivalenti. Credo che la consistenza si possa affrontare col teorema di compattezza abbastanza facilmente. Ho invece dei problemi sul punto 2).
Chiedo cortesemente un aiuto. Grazie anticipatamente.
Il linguaggio L è quello dei grafi (un simbolo di relazione 2-ario r) più infinite costanti {ci : i in N}. Sia T la teoria che contiene Trg più gli assiomi r(ci,cj) per ogni i diverso da j (con Trg la teoria dei grafi aleatori ovvero costituita da i seguenti assiomi: 1) non r(x,x) per ogni x; 2) r(x,y)-->r(y,x) per ogni x e y; 3)esistono x y z tali che x diverso da y diverso da z diverso da x; 4) presi comunque x1,...,xn,y1,..,yn tali che xi diverso da yj per ogni i,j=1....n allora esiste z tale che r(xi,z) per ogni i e non r (yi,z) per ogni i). La teoria T è completa? è N-categorica? Che cardinalità hanno i modelli N-saturi di T?
Svolgimento.
Anzitutto la teoria dei grafi aleatori è N categorica. Avendo questa un linguaggio numerabile (infatti è lo stesso della teoria dei grafi) risulta completa per il teorema di Vaught. Ho pensato di dimostrare la completezza di T dimostrandone 1) la consistenza (coerenza), 2) il fatto che presi comunque due modelli siano elementarmente equivalenti. Credo che la consistenza si possa affrontare col teorema di compattezza abbastanza facilmente. Ho invece dei problemi sul punto 2).
Chiedo cortesemente un aiuto. Grazie anticipatamente.
Risposte
Ti consiglio di leggere il regolamento e il relativo topic su come si scrivono le formule matematiche utilizzando i codici, per rendere il tutto più comprensibile.
Direi che non ti serve scomodare il teorema di compattezza per la consistenza. Esistono modelli di grafi aleatori costruibili abbastanza facilmente. Il secondo punto, invece, dovrebbe discendere automaticamente dal fatto che i grafi aleatori sono [tex]\omega[/tex]-omogenei e [tex]\omega[/tex]-universali. Scusa se non scendo nei dettagli, ma è già tardi... Se poi hai ancora dei problemi rispondi e cercherò di essere più preciso.
Anzitutto grazie mille per avermi risposto. Per quanto riguarda quanto hai scritto purtroppo ho da chiederti qualche delucidazione:
1)La teoria dei grafi aleatori è chiaramente consistente. Io però ho bisogno di dimostrare la consistenza di T (linguaggio e assiomi diversi). Avevo pensato di usare compattezza per restringermi al caso di un numero finito d'assiomi. In particolare al caso in cui gli assomi siano quelli di Trg più un numero finito di quelli r(ci,cj) (gli altri casi sono banali): questa sottoteoria è chiaramente coerente perchè dato un grafo aleatorio posso trovarne sempre un grafo completo con un numero finito di vertici (lo stesso dei cj degli assiomi) all'interno: interpretando le cj in tali vertici avrei cosi che tale grafo è modello della sottoteoria. Per compattezza avrei che T è coerente.(spero di non esser stato troppo contorto nella spiegazione)
2)La completezza di T invece mi sfugge: tu hai accennato al fatto che i grafi aleatori sono N-omogenei e N-universali..Avresti voglia di spiegarmi come potrei usare questi fatti per la teoria T? Grazie anticipatamente.
1)La teoria dei grafi aleatori è chiaramente consistente. Io però ho bisogno di dimostrare la consistenza di T (linguaggio e assiomi diversi). Avevo pensato di usare compattezza per restringermi al caso di un numero finito d'assiomi. In particolare al caso in cui gli assomi siano quelli di Trg più un numero finito di quelli r(ci,cj) (gli altri casi sono banali): questa sottoteoria è chiaramente coerente perchè dato un grafo aleatorio posso trovarne sempre un grafo completo con un numero finito di vertici (lo stesso dei cj degli assiomi) all'interno: interpretando le cj in tali vertici avrei cosi che tale grafo è modello della sottoteoria. Per compattezza avrei che T è coerente.(spero di non esser stato troppo contorto nella spiegazione)
2)La completezza di T invece mi sfugge: tu hai accennato al fatto che i grafi aleatori sono N-omogenei e N-universali..Avresti voglia di spiegarmi come potrei usare questi fatti per la teoria T? Grazie anticipatamente.
Sorry, it's my fault...
Ieri sera non ho capito nemmeno cosa leggevo... Mi ero fissato sulla teoria dei grafi aleatori, non avevo letto gli assiomi che aggiungevi.
Allora ripartiamo da capo. Per la consistenza: consideriamo il grafo [tex]M[/tex] con supporto l'insieme dei numeri naturali [tex]\mathbb N[/tex] e con le relazioni [tex]r(n,m)[/tex] per ogni [tex]n \ne m[/tex]. Sia [tex]N[/tex] un grafo aleatorio. Per l'[tex]\omega[/tex]-universalità di [tex]N[/tex], possiamo immergerci dentro il grafo precedente. Interpretando la costante [tex]c_i[/tex] con l'immagine di [tex]i[/tex] in [tex]N[/tex], otteniamo un modello che soddisfa tutti gli assiomi. Quindi la teoria è consistente.
Per mostrare che due modelli sono elementarmente equivalenti, invece, non saprei. Osservo però che potremmo limitarci a mostrare che due modelli numerabili sono sempre elementarmente equivalenti, grazie al teorema di Lowenheim - Skolem all'ingiù...
Ieri sera non ho capito nemmeno cosa leggevo... Mi ero fissato sulla teoria dei grafi aleatori, non avevo letto gli assiomi che aggiungevi.
Allora ripartiamo da capo. Per la consistenza: consideriamo il grafo [tex]M[/tex] con supporto l'insieme dei numeri naturali [tex]\mathbb N[/tex] e con le relazioni [tex]r(n,m)[/tex] per ogni [tex]n \ne m[/tex]. Sia [tex]N[/tex] un grafo aleatorio. Per l'[tex]\omega[/tex]-universalità di [tex]N[/tex], possiamo immergerci dentro il grafo precedente. Interpretando la costante [tex]c_i[/tex] con l'immagine di [tex]i[/tex] in [tex]N[/tex], otteniamo un modello che soddisfa tutti gli assiomi. Quindi la teoria è consistente.
Per mostrare che due modelli sono elementarmente equivalenti, invece, non saprei. Osservo però che potremmo limitarci a mostrare che due modelli numerabili sono sempre elementarmente equivalenti, grazie al teorema di Lowenheim - Skolem all'ingiù...
Ma a tuo parere...La teoria T è N categorica?avremmo così da Vaught la completezza ...Ho preso due modelli M,N numerabili di T, questi a loro volta lo sono per Trg omettendo le interpretazioni delle costanti, per tanto isomorfi grazie alla N categoricità di Trg...Per avere che sono isomorfe come strutture nel linguaggio originale L avrei però bisogno che le costanti venissero fissate..Allora ho pensato: parto dall'immersione parziale finita tra M' e N' (M,N ridotte al linguaggio di Trg) che fissa m costanti; sarebbe bello poter estendere questa ad un' immersione totale in cui tutte le costanti vengono fissate (dalla teoria si sa che esiste un'immersione totale che estende quella parziale). Se riuscissimo nell'intento, salvo miei errori di comprensione, col metodo andirivieni saremmo in grado di estender l'immersione parziale finita ad un isomorfismo. Questo sarebbe ancora isomorfismo tra strutture nel linguaggio ridotto ma ora con il vantaggio che le costanti vengono fissate..Cosa dici?Grazie ancora per la gentilezza e la rapidità con cui hai risposto precedentemente.
[OT]Per caso studi a Torino?[/OT]
L'off topic è motivato dal fatto che mi sono appena ricordato che questo era il testo dell'ultimo compito facoltativo che ci era stato assegnato nel corso di logica della triennale e che non avevo mai provato a svolgere!
Allora baro un po' e ti dico che la consegna dell'esercizio era:
L'off topic è motivato dal fatto che mi sono appena ricordato che questo era il testo dell'ultimo compito facoltativo che ci era stato assegnato nel corso di logica della triennale e che non avevo mai provato a svolgere!
Allora baro un po' e ti dico che la consegna dell'esercizio era:
- 1) Dimostrare che [tex]T[/tex] è consistente;
2) Dimostrare che [tex]T[/tex] è completa;
3) Dimostrare che [tex]T[/tex] non è [tex]\omega[/tex]-categorica.
[/list:u:1s8yng14]
Te lo scrivo perché devo uscire adesso... continuerò a pensarci ancora e se troverò la soluzione ti farò sapere. Però te lo dico fin da subito: ho qualche buona idea per dimostrare il punto 3), ma ho il vuoto totale per il punto 2)!
...Forse ho trovato il modo d'affrontare il punto due con l'induzione sulla complessità degli enunciati...La buona idea del punto tre invece? Pensare che mi ero fatto l'idea (errata) che fosse N categorica...Quando puoi fammi sapere, a presto e grazie ancora.
Ok, allora per il punto 3) l'idea è ovviamente di costruire due modelli non isomorfi. Per farlo seguiamo quest'idea guida: dovrebbe essere possibile immergere le costanti una volta in modo che ogni elemento di [tex]M[/tex] sia in relazione con almeno una costante ed una volta in modo che ci sia almeno un elemento che non è in relazione con nessuna costante.
Il secondo modello è facile da ottenersi: basta prendere il grafo che ho già introdotto, supporto [tex]\mathbb N[/tex] e relazioni [tex]r(m,n)[/tex] se [tex]m \ne n[/tex] e aggiungere un elemento [tex]a[/tex] in modo che [tex]a[/tex] sia isolato. Se [tex]N[/tex] è un grafo aleatorio, per l'[tex]\omega[/tex]-universalità possiamo immegergerci dentro quest'altro grafo e quindi ottenere un'interpretazione delle costanti che fa sì che ci sia un elemento che non è in relazione con nessuna costante.
Un po' più complicato è ottenere l'altro modello. Dobbiamo procedere in modo più subdolo, scegliendo le costanti una ad una all'interno del grafo aleatorio [tex]N[/tex]. Fissiamo un'enumerazione di [tex]N[/tex], [tex]N =[/tex]; vogliamo costruire le costanti per induzione, in modo che
Il secondo modello è facile da ottenersi: basta prendere il grafo che ho già introdotto, supporto [tex]\mathbb N[/tex] e relazioni [tex]r(m,n)[/tex] se [tex]m \ne n[/tex] e aggiungere un elemento [tex]a[/tex] in modo che [tex]a[/tex] sia isolato. Se [tex]N[/tex] è un grafo aleatorio, per l'[tex]\omega[/tex]-universalità possiamo immegergerci dentro quest'altro grafo e quindi ottenere un'interpretazione delle costanti che fa sì che ci sia un elemento che non è in relazione con nessuna costante.
Un po' più complicato è ottenere l'altro modello. Dobbiamo procedere in modo più subdolo, scegliendo le costanti una ad una all'interno del grafo aleatorio [tex]N[/tex]. Fissiamo un'enumerazione di [tex]N[/tex], [tex]N =
- 1) per ogni [tex]k[/tex] sia verificata [tex]r(n_k,c_k)[/tex];
2) per ogni [tex]k[/tex] e per ogni coppia [tex]1 \le i < j \le k[/tex] sia verificata [tex]r(c_i,c_j)[/tex].[/list:u:3txdfab3]
Scegliamo [tex]c_1[/tex] in modo che si abbia la relazione [tex]r(c_1, n_1)[/tex]. In questo modo le condizioni 1) e 2) sono banalmente verificate. Supponiamo di aver definito [tex]c_1, \ldots, c_{k-1}[/tex] e costruiamo [tex]c_k[/tex]. Siccome siamo all'interno di un grafo aleatorio possiamo scegliere un elemento [tex]z[/tex] che sia in relazione con tutti gli elementi [tex]\{c_1, \ldots, c_{k-1},n_k\}[/tex]. Prendiamo allora [tex]c_k = z[/tex].
In questo modo otteniamo induttivamente un insieme di costanti che soddisfa la proprietà: "per ogni elemento [tex]a \in N[/tex] esiste un indice [tex]i[/tex] tale che [tex]r(a,c_i^N)[/tex]".
I due modelli così costruiti non possono allora di certo essere isomorfi!
Se ti riesce di risolvere il punto 2), prova a postare la soluzione, sono curioso anch'io adesso.
Grazie mille sei davvero disponibile: ora mi leggo bene quanto hai scritto...Se mi convince quanto ho trovato del punto due, te lo scrivo (il prima possibile, difficilmente però di stasera visto che a breve devo uscire): ad ogni modo credo d'averne intuito la strada. A presto grazie ancora!
Ok esercizio risolto in tutti i suoi punti: sono di fretta ora...A breve ti faccio avere completezza e l'ultimo punto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo