Compattezza e strutture numerabili
Ciao a tutti!
Sono in difficoltà con questo esercizio di Logica:
Dimostrare che non esiste alcuna formula al prim'ordine che valga esattamente sulle strutture numerabili.
Innanzitutto io ho interpretato quel "vale esattamente" come "vale su tutte e sole" le strutture numerabili. (Vi sembra corretto?) Inoltre mi sembra che convenga usare il Teorema di Compattezza e mostrare che una formula che valga in tutte le strutture numerabili, sia soddisfatta anche da altre strutture.
Ho provato a svolgerlo come per il modello non-standard dell'Aritmetica di Peano, ma non so come superare lo scalino tra la cardinalità numerabile e il continuo!
Ho pensato a un insieme potenza, ma non ho idee.
Qualcuno ha un consiglio? Grazie!
Sono in difficoltà con questo esercizio di Logica:
Dimostrare che non esiste alcuna formula al prim'ordine che valga esattamente sulle strutture numerabili.
Innanzitutto io ho interpretato quel "vale esattamente" come "vale su tutte e sole" le strutture numerabili. (Vi sembra corretto?) Inoltre mi sembra che convenga usare il Teorema di Compattezza e mostrare che una formula che valga in tutte le strutture numerabili, sia soddisfatta anche da altre strutture.
Ho provato a svolgerlo come per il modello non-standard dell'Aritmetica di Peano, ma non so come superare lo scalino tra la cardinalità numerabile e il continuo!
Ho pensato a un insieme potenza, ma non ho idee.
Qualcuno ha un consiglio? Grazie!
Risposte
Credo di aver risolto...
Ho trovato spunto nella dimostrazione del Teorema di Löwenheim–Skolem (upward).
Il metodo è simile a quello dell'Aritmetica non standard: aggiungo una quantità non numerabile di costanti al lunguaggio, e considero le formule del tipo
$c != c'$
con $c$ e $c'$ tra queste costanti.
Ogni sottoinsieme finito di queste formule è soddisfacibile (come struttura basta una qualsiasi numerabile), e lo stesso aggiungendo una formula $\phi$ vera sulle strutture numerabili.
Dunque per il Teorema di Compattezza l'insieme contenente tutte queste formule e $\phi$ è soddisfacibile. Tuttavia un modello che lo soddisfi non può essere numerabile.
$square$
Ho trovato spunto nella dimostrazione del Teorema di Löwenheim–Skolem (upward).
Il metodo è simile a quello dell'Aritmetica non standard: aggiungo una quantità non numerabile di costanti al lunguaggio, e considero le formule del tipo
$c != c'$
con $c$ e $c'$ tra queste costanti.
Ogni sottoinsieme finito di queste formule è soddisfacibile (come struttura basta una qualsiasi numerabile), e lo stesso aggiungendo una formula $\phi$ vera sulle strutture numerabili.
Dunque per il Teorema di Compattezza l'insieme contenente tutte queste formule e $\phi$ è soddisfacibile. Tuttavia un modello che lo soddisfi non può essere numerabile.
$square$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo