Istituzioni di Logica Matematica

I semestre, a.a. 2006-2007, Dipartimento di Matematica, Pisa Codice esame AA103, 45 ore, 7 crediti. Anno di corso: non specificato

Prof. Alessandro Berarducci. Esercitatore: Mauro Di Nasso

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 κ-categoriche. Isomorfismi parziali. Teorie complete e incomplete. Studio di alcune specifiche teorie assiomatiche. Cenno alla logica del secondo ordine. Cenno all’intuizionismo. Teoria della calcolabilità. Modelli di calcolo. Funzioni calcolabili. Insiemi ricorsivi e ricorsivamente enumerabili. Teorema di Post. Esistenza di una funzione universale. Teorema smn. Indecidibilità 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 indecidibilitlà del calcolo dei predicati. Teorema di Tarski sulla indefinibilità della verità. Teorie decidibili e indecidibili. Decidibilità e indecidibilità 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

È 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.

MODALITÀ DI VERIFICA DELL’APPRENDIMENTO Esame finale scritto e orale.