PROGRAMMA DI: ISTITUZIONI DI LOGICA MATEMATICA
Codice esame AA103
Docente: Alessandro Berarducci
Esercitatore: Mauro di Nasso
Anno accademico: 2006-2007
Corso di Laurea: Matematica  -  Semestre: secondo   -  Anno di corso: non specificato 
45 ore, 7 crediti

CONTENUTI DELL'INSEGNAMENTO
Teorie formali e loro  modelli. Calcolo proposizionale. Calcolo dei predicati. Sistemi dimostrativi. Teorema di completezza di Gödel. Teorema di compattezza. Teoremi di Lowenheim-Skolem.  Teorie kappa-categoriche. Isomorfismi parziali.  Teorie complete e incomplete.  Studio di alcune specifiche teorie assiomatiche.  Cenno alla logica del secondo ordine. Cenno all'intuizionismo.
Teoria della calcolabilita'. Modelli di calcolo. Funzioni calcolabili. Insiemi ricorsivi e ricorsivamente enumerabili. Teorema di Post. Esistenza di una funzione universale. Teorema smn. Indecidibilita' del problema della fermata.  Altri problemi indecidibili. Gerarchia aritmetica.
Teoremi di incompletezza. Primo e secondo teorema di incompletezza di Gödel.. Teorema di Rosser. Teorema di Church sulla indecidibilitla' del calcolo dei predicati.  Teorema di Tarski sulla indefinibilita' della verita'.
Teorie decidibili e indecidibili. Decidibilita' e indecidibilita' di alcune specifiche teorie del primo ordine.

TESTI DI RIFERIMENTO
Dispense del docente. http://www.dm.unipi.it/~ berardu/
Barwise, Handbook of Mathematical Logic. 
Bell  & Machover, A course in mathematical logic. 
Mendelson, Logica Matematica.
Shoenfield, Logica Matematica.

PREREQUISITI. 
E' consigliabile che lo studente abbia una buona conoscenza delle nozioni fondamentali della teoria degli insiemi. Tali conoscenze possono ad esempio essere acquisite
nel corso di Elementi di Logica Matematica. 
        
METODI DIDATTICI
Lezioni ed esercitazioni integrate, di cui almeno 15 ore di esercitazioni. 

MODALITA' DI VERIFICA DELL'APPRENDIMENTO
Esame finale scritto e orale.