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

Programma d’esame

Calcolo proposizionale. Formule proposizionali, tautologie, Conseguenza logica, Sistema dimostrativo della deduzione naturale. Calcolo dei predicati. Linguaggi del primo ordine. Termini sostituibili. Semantica di Tarski dei termini e delle formule. Conseguenza logica. Teorie del primo ordine. Teorie coerenti, contraddittorie, complete. Sistema dimostrativo della deduzione naturale. Aspetti non costruttivi delle dimostrazioni per assurdo. Teorema di completezza. Teorie di Hintikka. Teorie di Henkin. Teorie coerenti massimali. Lemma di Lindenbaum. Ogni teoria coerente è contenuta in una teoria coerente massimale di Henkin. Ogni teoria di Henkin coerente massimale è di Hintikka. Ogni teoria di Hintikka ha un modello (modello dei termini). Teorema di completezza. Teorema di compattezza. Teorema di correttezza. Teorie formali dei numeri naturali. Aritmetica di Robinson Q. Aritmetica di Peano PA. Modelli di Q in cui non è vero che ogni numero è pari o dispari. Cenno all’aritmetica di Peano del secondo ordine. Definizione della relazione ¡ nel linguaggio dell’aritmetica. Modelli non standard di PA (numerabili e non). Altre applicazioni del teorema di compattezza (la teoria dei grafi connessi non è elementare, ogni ordine parziale si completa ad un ordine totale, ogni grafo non 3 colorabile ha un sottografo finito non 3 colorabile). Gerarchia aritmetica. Nozione intuitiva di funzione calcolabile e insieme decidibile. Gerarchia aritmetica. Esempi di problemi Π_{1}^{0} dalla matematica classica (Goldbach, Fermat, Riemann, 4 colori, etc.). Idea della dimostrazione che gli insiemi della gerarchia aritmetica sono definibili nel modello stardard ℕ di PA. Esempi: definibilità della funzione esponenziale e della funzione fattoriale in ℕ usando il teorema cinese dei resti. Funzioni primitive ricorsive e ricorsive generali. Funzioni ricorsive primitive. Stabilità degli insiemi primitivi ricorsivi per connettivi proposizionali e quantificatori limitati. Applicazione: l’insieme dei primi è primitivo ricorsivo. Gli insiemi Δ_{0} sono primitivi ricorsivi. Funzioni μ-ricorsive. Calcolabilità intuitiva delle funzioni μ-ricorsive. Programma per macchina a registri che simula il μ. Macchine di Turing. Esistenza di una macchina di Turing universale (senza dim.). Tesi di Church. Insiemi decidibili (ricorsivi). Insiemi semidecidibili. Teorema di Post. Codifica della sintassi. Codifica delle successioni basata sulla scomposizione in primi. Teorema di ricursione sul decorso dei valori. Codifica dei termini. Codifica delle formule. La funzione sostituzione è primitiva ricorsiva. L’insieme delle codifiche degli assiomi di PA è primitivo ricorsivo. Il predicato di dimostrabilità in PA è primitivo ricorsivo (senza dim. dettagliata). L’insieme dei teoremi di PA è ricorsivamente enumerabile. Idem per teorie ricorsivamente assiomatizzabili. Rappresentabilità delle funzioni ricorsive. Insiemi binumerabili in una teoria T. Gli enunciati Δ_{0} veri in ℕ sono dimostrabili nell’aritmetica di Robinson Q. Gli enunciati ∃Σ_{0}^{1} veri in ℕ sono dimostrabili in Q. Le funzioni primitive ricorsive sono binumerabili funzionalmente in Q da formule Σ_{1}^{0} (dove le formule Σ_{1}^{0} si ottengono dalle Δ_{0} per congiunzioni, disgiunzioni, quantificatori limitati universali e quantificatori esistenziali illimitati). Esercizio: le funzioni ricorsive totali sono binumerabili funzionalemente in Q. Esercizio: ogni formula Σ_{1}^{0} equivale in P A ad una formula ∃Δ_{0}. Nel modello standard le formule Σ_{1}^{0} definiscono esattamente gli insiemi semidecidibili. Teoremi di incompletezza. Lemma di diagonalizzazione nell’aritmetica di Robinson. Teorie ω-coerenti. Per teorie ω-coerenti contenenti Q le formule Σ_{1}^{0} dimostrabili coincidono con quelle vere in ℕ. Primo teorema di Gödel: ogni ω-coerente ricorsivamente assiomatizzabile contenente Q è incompleta (ad esempio P A). Secondo teorema di Gödel: P A non dimostra la sua coerenza. (Dimostrazione usando le condizioni di derivabilità.) Ulteriori sviluppi della teoria della calcolabilità. Forma normale di Kleene: il predicato “la funzione calcolabile con indice e converge in t passi ad y” è primitivo ricorsivo (senza dim.). Esempio di funzione totale non calcolabile. Indecidibilità del problema della fermata (gli insiemi K e K_{0} sono ricorsivamente enumerabili ma non ricorsivi). Caratterizzazioni equivalenti degli insiemi ricorsivamente enumerabili: X è il dominio di una funzione ricorsiva parziale, se e solo se è l’immagine di una ricorsiva totale (se non vuoto), se e solo se è l’immagine di una funzione ricorsiva primitiva (Esercizio), se e solo se è della forma ∃-Ricorsivo, se e solo se è della forma ∃-Primitivo-ricorsivo, se e solo se è della forma ∃Δ_{0}. Il complemento di K_{0} non è ricorsivamente enumerabile. L’insieme degli indici delle funzioni ricorsive totali è Π_{2}^{0} ma non ricorsivamente enumerabile. Insiemi ricorsivamente inseparabili. Teorie indecidibili. Esempi di teorie decidibili e indecidibili (teorie per i naturali, gli interi, i razionali, i reali, i complessi). Una teoria completa ricorsivamente assiomatizzata è decidibile. La teoria Q di Robinson è essenzialmente indecidibile (ogni sua estensione coerente è indecidibile). Corollario (Teorema di Rosser) Ogni estensione coerente ricorsivamente assiomatizzata di Q è incompleta. Dimostrazione tramite gli insiemi ricorsivamente inseparabili. Esempio: P A + ¬Con(P A) è incompleta. Teorema di Church: il calcolo dei predicati è indecidibile. Una estensione finita di una teoria decidibile è decidibile. Seconda dimostrazione del teorema di Rosser tramite il lemma di diagonalizzazione. Indecidibilità della teoria dell’anello dei numeri interi (usando il teorema dei quattro quadrati di Lagrange per ridursi a ℕ). Interpretazioni tra teorie (cenni). Indecidibilità della teoria degli anelli commutativi e dei campi usando il metodo delle interpretazioni.

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.