PROGRAMMA COMMENTATO LOGICA MATEMATICA 1 (AA 2020-21) Paolo Lipparini (6 ott 2020) Presentazione del corso. Classificazione dei settori matematici (Mathematical Subject Classification). Settori della logica matematica. Sistemi assiomatici (Shoenfield, Logica matematica, p. 11-12). Sistemi formali (Mendelson, p. 42). (8 ott) Natura problematica della nozione di infinitesimo, uso in matematica e relative controversie. Ad esempio, si veda: http://people.dm.unipi.it/dinasso/papers/it1.pdf (la sezione 1 fa parte del programma) Cenni a "Sull'infinito" di Hilbert. Paradosso di Russell e Programma di Hilbert. https://www.mat.uniroma2.it/~lipparin/stud/AA1516/il.pdf Alcuni commenti storici (v. file Materiale.pdf) (9 ott) Il matematico "ideale" secondo Davis e Hersh. https://www.mat.uniroma2.it/~lipparin/stud/AA1112/dhmatid.pdf Commento sulla definizione induttiva di "formula ben formata". Calcolo delle proposizioni (non formalizzato, per ora), connettivi, tavole di verita'. (13 ott) Interpretazione di "implica". Tautologie e loro proprieta'. Notazione polacca. G.C. Rota su Alonzo Church: https://www.mat.uniroma2.it/~lipparin/stud/AA1112/rota.pdf (15 ott) Insiemi adeguati di connettivi. Forma normale disgiuntiva e suo uso per decidere se una formula e' una tautologia. (16 ott) Brevi cenni alla complessita' dei problemi computazionali collegati al calcolo delle proposizioni (non fa parte del programma). Algebre di Boole. Le formule del calcolo delle proposizioni, modulo l'equivalenza logica, formano un'Algebra di Boole (facoltativo). Distinzione fra teoria e metateoria. Un sistema formale per il calcolo delle proposizioni. Esempio di dimostrazione. Teorema di deduzione. (20 ott) Lemma di Lindenbaum e versioni generalizzate. https://www.mat.uniroma2.it/~lipparin/stud/AA2021/Linden.pdf Teorema di adeguatezza per il calcolo delle proposizioni. Teorema di completezza (senza dimostrazione). (22 ott) Calcolo dei predicati come sistema formale: termini, formule atomiche, formule, occorrenze libere e vincolate di una variabile in una formula. (23 ott) Modelli, interpretazioni; soddisfacibilita' di una formula relativamente ad una interpretazione e ad un'assegnazione di valori alle variabili. (27 ott) La soddisfacibilita' di una formula chiusa non dipende dalle assegnazioni. https://www.mat.uniroma2.it/~lipparin/stud/AA2021/VIII.pdf Assiomi e regole di inferenza per il calcolo dei predicati. Teorie. Teorema di completezza ed adeguatezza generalizzato per il calcolo dei predicati (senza dimostrazione). (29 ott) Teorie con uguaglianza. Conseguenze del teorema di completezza: una teoria e' non contradditoria se e solo se ha un modello. Teorema di compattezza. Applicazione: esistenza di un modello non standard per qualunque teoria dell'aritmetica (al primo ordine) vera in N. (30 ott) Esempi di teorie. Ogni modello finito in un linguaggio finito e' caratterizzato a meno di isomorfismi da un enunciato. Aritmetica di Peano. (3 nov) Confronto fra Aritmetica di Peano e Assiomi di Dedekind Peano. Ogni teoria con modelli di cardinalita' finita arbitrariamente alta ha un modello infinito. In particolare, non esiste nessuna teoria i cui modelli sono esattamente i modelli finiti; la teoria dei modelli infiniti non e' finitamente assiomatizzabile. (5 nov) Sia T una teoria in un linguaggio che estende il linguaggio dei gruppi e tale che per ogni n T ha un modello con un elemento di periodo (=ordine) >n. Allora T ha un modello con un elemento di periodo infinito. Ogni teoria dei campi con modelli di caratteristica finita arbitrariamente alta ha un modello di caratteristica 0 (= caratteristica infinita). Teoremi di Lowenheim-Skolem-Tarski (con dimosrazione solo la parte verso l'alto). Debolezza espressiva intrinseca del calcolo dei predicati (e, sotto ipotesi molto generali, di qualunque calcolo per cui valga il teorema di compattezza). (6 nov) Cenni alla teoria dei modelli astratta (facoltativo). Esistenza di un modello non standard dei numeri reali. (10 nov) Cenni all'analisi nonstandard. Caratterizzazione nonstandard della continuita' (v. file Materiali.pdf). Godelizzazione. (12 nov) Cenni su P. Dirac e la funzione delta in analisi non standard. Paradossi semantici. Autoriferimento. Teorema di Tarski. Relazioni numeriche esprimibili. (13 nov) Primo e secondo teorema di incompletezza di Godel e Godel-Rosser. Conseguenze riguardo la realizzabilita' del programma di Hilbert. (17 nov) Funzioni e relazioni ricorsive. Cenni alla tesi di Church. https://www.treccani.it/enciclopedia/tesi-di-church_%28Enciclopedia-della-Matematica%29/ Cenni al cosiddetto "argomento di Lucas". La non contraddittorieta' di una teoria con assiomatizzazione ricorsiva e' comunque una proprieta' aritmetica, cioe' esprimibile nell'aritmetica di Peano. (19 nov) Esempi di argomenti diagonali. (20 nov) Paradosso di Cantor e cenni al paradosso di Burali-Forti. Cenni alla teoria dei tipi di Russell. (24 nov) Teoria assiomatica degli insiemi. Assiomi di estensionalita', della coppia, dell'unione, del'insieme potenza, di separazione. L' "assioma" di comprensione e' contraddittorio. Utilizzo di classi proprie come abbreviazioni di formule; cenni a teorie delle classi e distinzione fra classi e insiemi. (26 nov) Insiemi ereditariamente finiti. Se esiste l'insieme degli insiemi ereditariamente finiti e' un modello degli assiomi introdotti finora. Insiemi induttivi; assioma dell'infinito. (27 nov) Assioma della scelta e alcune forme equivalenti. Nozione di infinito secondo Dedekind. (1 dic) Cenni al modello cosmologico di Godel. Teorema di Cantor sulla cardinalita' di P(x). Principio della partizione. Assioma di rimpiazzamento; V_{\omega+\omega} e' modello di tutti gli assiomi tranne rimpiazzamento (cenni). (3 dic) Esempi di induzioni transfinite (per ora, a livello informale). Gerarchia di von Neumann. Insiemi bene ordinati. (4 dic) Confrontabilita' di buoni ordini. Somme e prodotti. Ordinali e cardinali. (10 dic) Esempi di ordinali numerabili. Ordinali e cardinali limiti e successori. Cardinali regolari, inaccessibili. L'ipotesi generalizzata del continuo, (11 dic) Il "programma di Godel" per suggerire una soluzione al problema del continuo. Modelli interni. La gerarchia degli insiemi costruibili di Godel (senza dimostrazione che si tratta di un modello interno). (15 dic) Giustificazione per l'uso dei modelli interni nelle dimostrazioni di non contraddittorieta' relativa. Confronto fra le gerarchie L alpha e V alpha. Cenni ai teoremi di assolutezza. (17 dic) Cenni al metodo del "forcing". (18 dic) Cenni ai grandi cardinali: inaccessibili, debolmente compatti, misurabili, fortemente compatti, con alcune formulazioni equivalenti (senza dimostrazioni)