LOGICA MATEMATICA (m)
2o MODULO
A. A. 1997-98
Dott. Stefano Baratella
Oggetto e obiettivi del corso
Il secondo modulo ha come prerequisito (non indispensabile) il primo. Esso ha per oggetto una introduzione ad alcuni importanti filoni della logica matematica. L'obiettivo è quello di presentare differenti aspetti della disciplina che vanno dallo studio di problemi di tipo fondazionale ad applicazioni alla computer science.
Nella prima parte viene introdotta una teoria assiomatica degli insiemi e vengono esaminati vari equivalenti non banali dell'assioma di scelta. Si sviluppano le teorie dei numeri ordinali e dei numeri cardinali, con enfasi sull'aritmetica cardinale. Si studiano poi semplici dimostrazioni di consistenza relativa in teoria degli insiemi.
Nella seconda parte viene presentata la teoria della ricorsività, quale controparte rigorosa della nozione di funzione effettivamente computabile. Infine, si fornisce un cenno sulla dimostrazione dei due teoremi di incompletezza di Gödel e sul loro significato.
Il contenuto del secondo modulo è suscettibile di variazioni a seconda degli interessi dei fruitori del corso.
Ciascun modulo prevede 4 ore di lezione settimanali (tre di teoria ed una di esercitazioni).
Programma
Assiomi della teoria degli insiemi di Zermelo-Fraenkel. Equivalenti dell'assioma di scelta. Insiemi bene ordinati. Numeri ordinali e cardinali. Aritmetica cardinale. Cofinalità. Esponenziazione di cardinali. Insiemi ben fondati. Teorema di collassamento di Mostowski. Alcune semplici dimostrazioni di consistenza relativa.
Teoria della ricorsività. Funzioni ricorsive. Tesi di Church. Insiemi ricorsivi e ricorsivamente enumerabili. Teoremi di incompletezza di Gödel.
Testi consigliati
BELL-MACHOVER, A course in mathematical logic, North Holland
VAN DALEN, Logic and structure, Springer
HODGES, Model Theory, Cambridge University Press
DEVLIN, The joy of sets, Springer
KUNEN, Set theory. An introduction to independence proofs, North Holland
Modalità e svolgimento dell'esame
L'esame finale per ciascun modulo comprende una prova scritta ed una prova orale.
La prova scritta consiste nella risoluzione di esercizi scelti fra quelli proposti periodicamente durante il corso (alcuni fra questi esercizi vengono discussi e risolti durante le ore di esercitazioni).