6
Nessuna.
MAT/01 Logica Matematica.
Prova orale.
Il corso intende fornire alcuni strumenti propri della logica matematica, in particolare metodi model-teoretici, per un’analisi di strutture al primo ordine. Prevede, inoltre, un’introduzione alle nozioni fondamentali di teoria della computabilità al fine di illustrare i teoremi di incompletezza di Gödel.
Deduzione naturale per il calcolo proposizionale, validità e completezza. Teorema di compattezza con applicazione alla teoria dei grafi. Linguaggi e strutture al primo ordine. Soddisfacibilità e teorema di coincidenza. Formule vere in una struttura, formule soddisfacibili, formule logicamente valide e formule logicamente equivalenti. Conseguenza logica. Omomorfismi, monomorfismi e isomorfismi tra strutture. Insiemi definibili in una struttura. Isomorfismi e insiemi definibili. Confronto tra strutture: strutture elementarmente equivalenti e strutture isomorfe. Sottostruttura elementare. Test di Tarski-Vaught ed applicazione alle strutture ordinate dei razionali e dei reali. Deduzione naturale per il calcolo dei predicati: teorema di completezza. Teorema di compattezza ed alcune applicazioni: i teoremi di Loweinheim-Skolem, modelli non standard dei naturali e dei reali, non assiomatizzabilità di alcune classi di strutture. Teorie k-categoriche ed esempi: ordini densi lineari privi di massimo e di minimo, gruppi abeliani divisibili e privi di torsione. Teorema di Vaught per la completezza di una teoria k-categorica. Teorie decidibili.
Computabilità: funzioni primitive ricorsive, funzione di Ackermann e funzioni parziali ricorsive. Tesi di Church. Macchine di Turing e tesi di Turing. Insiemi ricorsivi e insiemi ricorsivamente enumerabili. Macchina di Turing universale. Problema della fermata ed altri problemi non decidibili. Aritmetica di Peano e cenni sui teoremi di incompletezzza di Gödel.
Al termine dell’insegnamento, lo studente deve dimostrare di
Padronanza delle conoscenze, chiarezza nell’esposizione, rigore nell’uso del linguaggio, disinvoltura nell’uso delle nozioni acquisite.
