LOGICA MATEMATICA (m)

2o MODULO

A. A. 1996-97

Dott. Stefano Baratella

Argomenti effettivamente svolti

Linguaggio per la teoria degli insiemi. Assiomi della teoria degli insiemi di Zermelo-Fraenkel. Paradosso di Russell. Esistenza di classi proprie. Buoni ordini. Rigidita' dei buoni ordini. Tricotomia dei buoni ordini. Assioma di scelta. Ordinali. Ogni insieme bene ordinato e' isomorfo ad un unico ordinale. Somma e prodotto di ordinali. Teorema di recursione transfinita sugli ordinali. Teorema di Cantor-Bernstein. Cardinali. Definizione di cardinalita' di un insieme. Equivalenti dell'assioma di scelta: lemma di Zorn, buon ordinamento, tricotomia, teorema di Tychonoff. Conseguenze dell'assioma di scelta: teorema di Hahn-Banach, teorema dell'ideale massimale, esistenza di insiemi non Lebesgue-misurabili di numeri reali (con dimostrazione). Limiti superiori per la cardinalita' dell'unione di una famiglia di insiemi. Teorema di Cantor. Esistenza di cardinali arbitrariamente grandi (senza uso dell'assioma di scelta). Gerarchia degli Aleph. Esponenziazione di cardinali (senza ipotesi generalizzata del continuo). Cofinalita'. Ordinali regolari . Cardinali debolmente e fortemente inaccessibili. Ogni cardinale successore e' regolare. Lemma di König. Esponenziazione di cardinali sotto ipotesi generalizzata del continuo. Problema dell'estensione della misura di Lebesgue a tutto l'insieme delle parti di [0,1]: legame con l'esistenza di cardinali debolmente inaccessibili sotto la cardinalita' del continuo. Assioma di fondazione e conseguenze. Formulazioni equivalenti dell'assioma di fondazione. Rango di un insieme. Induzione sul rango. Cenni sul problema della consistenza della teoria degli insiemi di Zermelo-Fraenkel. Paradosso di Zermelo. Gerarchia degli insiemi costruibili ed assioma di costruibilita'. Proprieta' della gerarchia dei costruibili. Relativizzazione di una formula ad una classe. I costruibili sono un modello degli assiomi di Zermelo-Fraenkel e dell'assioma di scelta. Consistenza relativa dell'assioma di costruibilita' e dell'assioma di scelta rispetto agli assiomi di Zermelo-Fraenkel.

(Argomenti facoltativi)
Funzioni primitive ricorsive. Funzioni parziali ricorsive. Insiemi ricorsivi e ricorsivamente enumerabili. Tesi di Church. Codifica delle funzioni parziali ricorsive. Problema dell'arresto. Esistenza di insiemi ricorsivamente enumerabili non ricorsivi. Debole rappresentabilita' degli insiemi ricorsivamente enumerabili e forte rappresentabilita' degli insiemi ricorsivi nell'aritmetica formalizzata di Peano (senza dimostrazione). Relazioni diofantee. Enunciato del teorema di Matjasevic e sue conseguenze: soluzione del X problema di Hilbert, una formula per i numeri primi. Codifica cella sintassi (gödelizzazione). Ogni teoria ricorsivamente assiomatizzabile e completa e' decidibile. Ogni teoria ricorsivamente assiomatizzabile e consistente che estende l'aritmetica formalizzata di Peano e' indecidibile. Predicati di dimostrabilita'. L'aritmetica formalizzata di Peano ha predicati di dimostrabilita'. Teorie diagonalizzabili. L'aritmetica formalizzata di Peano e' diagonalizzabile. Conseguenze di diagonalizzabilita' ed esistenza di predicati di dimostrabilita' per una teoria. Primo teorema di incompletezza di Gödel (nella forma: l'aritmetica formalizzata di Peano e' incompleta). Secondo teorema di incompletezza di Gödel (nella forma: l'aritmetica formalizzata di Peano non dimostra la propria cosistenza). Generalizzazioni dei due teoremi di incompletezza. Conseguenze del secondo teorema di incompletezza sul problema della consistenza della teoria degli insiemi e sul programma di Hilbert.

Testi consigliati

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

Date dei prossimi appelli d'esame:

Scritto: 12.9.97 ore 9,00
Orale: 12.9.97 ore 15,00

Scritto: 26.9.97 ore 9,00
Orale: 26.9.97 ore 15,00