Andrea Snaidero
La tesi che ho scritto tratta di logica matematica e della teoria dei modelli. Quella che segue è una breve descrizione del mio lavoro.
Siamo interessati ai numeri naturali e alle formule aritmetica del prim'ordine, ovvero agli enunciati matematici scritti nel linguaggio dell'aritmetica. Tale linguaggio, oltre che ai consueti simboli logici (variaibli, uguale, connettivi e quantificatori), comprende un simbolo per il prodotto, uno per la somma, uno per la funzione successore e uno per la relazione di minore uguale. Inoltre, lavorando con un linguaggio al prim'ordine, le variabili possono rappresentare esclusivamente numeri naturali, ad esempio non possono rappresentare insiemi o funzioni. Possiamo interpretare una formula aritmetica in una qualunque struttura algebrica purché quest'ultima sia dotata di operazioni e di relazioni che ci permettano, stabilendo una convenzione, di interpetare i simboli del linguaggio; in questo caso si parla di struttura aritmetica, o semplicemente struttura. Precisamente, per essere una struttura aritmetica, una struttura algebrica deve essere dotata di un'operazione binaria per rappresentare la somma, un'altra per rappresentare il prodotto, un'operazione unaria per rappresentare la funzione successore e una relazione per rappresentare il minore uguale. Un insieme di formule si chiama teoria, e una struttura che soddisfa una teoria si dice modello di quella teoria; la teoria completa dei numeri naturali è l'insieme di tutte le formule che sono vere nei numeri naturali. Col termine nonstandard ci riferiamo alle strutture che non sono isomorfe ai numeri naturali.
Si può dimostrare che esistono molti modelli nonstandard della teoria completa dei numeri naturali, tuttavia la dimostrazione di questo fatto non è costruttiva, e non riusciamo a descrivere esplicitamente tali modelli. Siamo interessati a dare una descrizione esplicita di modelli nonstandard, in particolare vorremo poter enumerare tutti gli elementi di un dato modello e dare degli algoritmi per calcolare somma e prodotto di questi elementi; se un modello ammette una tale descrizione lo chiamiamo ricorsivo. Un semplice risultato negativo afferma che non esistono modelli ricorsivi nonstandard della teoria completa dei numeri naturali: la teoria completa dei numeri naturali è troppo espressiva. Ci chiediamo dunque se è possibile restringere l'insieme degli assiomi che imponiamo che vengano soddisfatti, e trovare in questo modo un modello nonstandard computabile. Una teoria più piccola, cioè un sottoinsieme della teoria completa dei numeri naturali, la chiamiamo frammento dell'aritmetica. Chiaramente esiste un'intera gerarchia di frammenti dell'aritmetica ordinati dalla relazione d'ordine data dall'inclusione. Per frammenti particolarmente piccoli possiamo trovare facilmente modelli ricorsivi nonstandard, mentre per frammenti molto grandi possiamo dimostrare che non esistono. Nella tesi esploriamo la regione di confine fra i frammenti che ammettono modelli ricorsivi nonstandard e quelli che non l'ammettono e riportiano la dimostrazioni dei risultati principali su questo argomento.
Puoi scaricare il documento completo qui:
Scarica la Tesi
Se sei interessato a una presentazione più concisa puoi consultare le slide che ho usato nella discussione:
Scarica le slide