Anno accademico 2020-2021
ISTITUZIONI DI LOGICA MATEMATICA
Docenti:
Alberto Giulio Marcone
Alberto Giulio Marcone
Totale crediti: 6
Tipologia: Affine/Integrativa
Periodo didattico: Primo Periodo
Lingua insegnamento: ITALIANO
Prerequisiti. Conoscenze di base dei modelli per la logica del prim’ordine e del teorema di completezza e di un modello astratto di computazione (entrambi gli argomenti sono svolti nel corso di Logica Matematica della Laurea triennale)
Metodi didattici. Lezioni frontali con esempi e esercizi.
Modalità di verifica. Esame orale della durata indicativa di 40 minuti in cui allo studente viene richiesta una buona comprensione degli visti a lezione e alcune dimostrazioni di teoremi.
Altre informazioni. In presenza di studenti stranieri il corso verrà offerto in lingua inglese.
OBIETTIVI FORMATIVI
Dare allo studente una solida formazione di base in teoria dei modelli e in teoria della computabilità.
CONTENUTI
Teoria dei Modelli e Teoria della Computabilità.
In dettaglio:
-Teoremi di Löwenheim-Skolem. Ultraprodotti e loro applicazioni. Il teorema di compattezza e le sue applicazioni. Categoricità. Insiemi definibili e teorie o-minimali.
-Insiemi computabilmente enumerabili e loro caratterizzazioni. I teoremi di ricorsione, enumerazione e s-m-n. Relativizzazioni. La gerarchia aritmetica. Il problema di Post e il teorema di Friedberg-Muchnik. Altre applicazioni del metodo finite injury.
-Ulteriori argomenti a seconda del tempo disponibile e degli interessi degli studenti.
TESTI DI RIFERIMENTO
A. Marcja, C. Toffalori, A guide to classical and modern model theory, Kluwer.
R. Soare, Recursively enumerable sets and degrees, Springer.
