Diario Lezioni 2021-2022

Diario delle Lezioni a.a. 2021-2022 : Lunedì e Mercoledì ore 16-19 aula M4 (Blocco Aule) e Venerdì ore 12-14, aula 009 (Palazzina C)

LINK allo streaming sincrono delle lezioni (NO registrazione)

Introduzione al Corso

1. lunedì 20/9: presentazione e avvio del corso; Discussione generale su dimostrazioni e refutazioni logiche. Esempi di dimostrazioni, ed in particolare di dimostrazioni matematiche.  Discussione sui risultati detti “negativi”: impossibilità di quadrare il cerchio, non risolubilità per radicali delle equazioni di grado superiore al quinto, problema dei tre corpi.

2. Mercoledì 22/9: Formalizzazione della dimostrazione del teorema di Euclide sull’infinità dei numeri primi. Discussione conseguente. Cenni sulle teorie assiomatiche con qualche esempio: geometria euclidea, teoria ingenua degli insiemi, aritmetica di Peano. Cenni sugli enunciati dei teoremi di incompletezza di Gödel.

3. Venerdì, 24/9: un esempio di "risultato negativo" al di fuori  delle dimostrazioni puramente matematiche (nell'Informatica Teorica): il problema dell'arresto delle Macchine di Turing. Discussione. Riferimenti: Slides sulle MdT .  I concetti di Proposizione del Primo Ordine, Formula Logica del Primo Ordine (chiusa) e Proposizioni Puramente Logiche. Gli enunciati dei Teoremi di Corretta e Completezza per la Logica del Primo Ordine. Riferimenti: Capitolo 1 (Introduzione) del libro Logica. Vol. 1 Dimostrazioni e modelli al primo ordine, Springer, 2014.

MODULO A (Maieli)

4. Lunedì 27/9: Nozioni preliminari: ordini parziali ed ordini totali, relazioni ben fondate, buoni ordini. Esempi. Definizione di albero e prime proprietà degli alberi. Una semplice costruzione sugli alberi (prolungamento di alberi finiti) . Riferimenti: Capitolo 2, pagg. 36 - 41 del libro Logica. Vol. 1.

5. Mercoledì 29/9: Definizioni induttive di un insieme. Dimostrazioni per induzione. Induzione sull’ordine lessicografico. Dimostrazione che l'ordine lessicogafico è un buon ordine. Assioma di scelta e sua applicazione per dimostrare il lemma di König. Dimostrazione del Lemma di König numerabile senza Assioma di Scelta.  Capitolo 2, pagg. 41 - 48 del libro Logica. Vol. 1.

6. Venerdì 1/10: Esercitazione sul principio di induzione: l’induzione sui multinsiemi finiti di numeri naturali ed il taglio delle teste dell’Idra  (scarica i file EserciziLogicaCap2.pdf).

7. Lunedì 4/10: Linguaggio del primo ordine: alfabeto. Due formulazioni diverse di un alfabeto del primo ordine. Definizione induttiva di termine su di un linguaggio del primo ordine. Definizione induttiva di formula su di un linguaggio del primo ordine. Occorrenze libere e vincolate di variabili in una formula. Sostituzione di un termine in una formula: il "problema della cattura di una variabile". Riferimenti: Capitolo 3, pagg. 49 - 61 del libro Logica. Vol. 1

8. Mercoledì 6/10: Sottoformule. Grado di una formula. Sequenti. Osservazioni sulla cardinalità del linguaggio. Strutture per un linguaggio del primo ordine. Termini e formule a parametri (chiusi) in una struttura. Valutazione di termini e formule in una struttura. Modelli e Contromodelli per formule chiuse del primo ordine. Riferimenti: Capitolo 3, pagg. 62 - 69 del libro Logica. Vol. 1

9. Venerdì 8/10: Esercitazione: sulla nozione di soddisfacibilità, da parte di una struttura, di una formula chiusa del primo ordine Prima discussione sull’assiomatizzazione al primo ordine della nozione di insieme finito e della nozione di insieme infinito. Esercizi sulla soddisfacibilità al primo ordine, varie presentazioni assiomatiche della teoria dei gruppi. Scarica il testo degli EserciziLogicaCap3-1.pdf

10. Lunedì 11/10: Presentazione del calcolo dei sequenti LK di Gentzen per la logica del primo ordine: lista delle regole, commenti e discussione. Formulazioni moltiplicativa e additiva delle regole del calcolo dei sequenti Definizione di derivabilità di una formula (e di un sequente) e di derivabilità di una formula (e di un sequente) da un insieme di formule. Esempi. Riferimenti: Capitolo 3, pagg. 70 - 73 del libro Logica. Vol. 1

11. Mercoledì 13/10:Teorema di correttezza per la logica del primo ordine (Vedi Errata-Corrige Volume 1). La nozione di reversibilità di una regola logica.  Elenco delle regole reversibili del calcolo dei sequenti. Dimostrazione della reversibilità delle regole. Definizione di Analisi di un sequente da un insieme di formule come generalizzazione della nozione di derivazione di un sequente da un insieme di formule. Esempi. Dimostrazione dei punti 4 e 5 della Proposizione 7 di pag. 79 del Libro di Logica. Riferimenti: Capitolo 3, pagg. 73 -  80 del libro Logica. Vol. 1

12. Venerdì 15/10: Esercitazione:  scrivere nel calcolo dei sequenti la derivazione che stabilisce che il Vero è elemento neutro della Congiunzione ed il Falso è elemnto neutro della Disgiunzione.  Il teorema dell’ubriaco e la necessità della regola di contrazione per la nozione di derivabilità nel calcolo dei predicati del primo ordine. Esercizi sulla nozione di derivabilità in LK in assenza  di quantificatori (calcolo preposizionale) ed in presenza di quantificatori. (Esercizi 3.8.1, 3.9.1 e 3.10 del file EserciziLogicaCap3-2.pdf).

13. Lunedì 18/10: Ordine Ciclico. Costruzione dell’Analisi Canonica Senza Tagli di una formula del primo ordine. Proprietà dell'A.C.S.T di una formula del primo ordine. Esempi e discussione. Riferimenti: Capitolo 3, pagg. 80 -  88 del libro Logica. Vol. 1.

14. Mercoledì 20/10: Costruzione dell’Analisi Canonica Con Tagli di una formula chiusa A da una Teoria T del primo ordine. Proprietà dell'A.C.C.T. Esempi e discussione. Prime Proprietà dei rami scorretti dell'Analisi Canonica con e senza tagli (Lemma 1 e Lemma 2 di pag. 94). Riferimenti: Capitolo 3, pagg. 88 - 97 del libro Logica. Vol. 1.

15. Venerdì 22/10: Esercitazione: sulla nozione di derivabilità in LK in presenza di quantificatori (Esercizio 3.11) + analisi canonica con e senza tagli (Riferimenti: EserciziLogicaCap3-2.pdf. Dimostrare che se T è una teoria finita del primo ordine e Gamma un sequente di formule del primo ordine (non necessariamente chiuse) allora Gamma è derivabile da T se e solo se  "not(T), Gamma" è derivabile logicamente (dove "not(T)" è il sequente delle formule negate che occorrono in T). Suggreimento: procedere per induzione sull'altezza delle dimostrazioni.

16. Lunedì 25/10:  Teorema fondamentale dell’analisi canonica: lemmi e dimostrazione completa. Prime conseguenze del teorema: teorema di completezza, teorema di eliminabilità del taglio. Corollario della non-contraddittorietà di LK. Ulteriori conseguenze del teorema fondamentale dell’analisi canonica: teorema di compattezza, teorema di Löwenheim-Skolem. Osservazioni conclusive sul teorema fondamentale dell’analisi canonica e sulle estensioni delle sue conseguenze al caso dei linguaggi più che numerabili (verso la Teoria dei Modelli). Riferimenti: Capitolo 3, pagg. 97 - 108 del libro Logica. Vol. 1.

17. Mercoledì 27/10: La questione dell’eliminazione del taglio di Gentzen. Enunciato del teorema di eliminazione del taglio e suo raffinamento. Strategia generale della dimostrazione. Le trasformazioni elementari definite da Gentzen (i casi-chiave). I casi dell’indebolimento e della contrazione. Le trasformazioni elementari definite da Gentzen: il caso dei quantificatori e le difficoltà ad esso connesse. Riferimenti: Capitolo 4, pagg. 109 - 125 del libro Logica. Vol. 1.

18. Venerdì 29/10: Esercitazione: sulla indipendenza di una formula da un insieme di formule e sulla nozione di derivabilità in LK in presenza di quantificatori (Esercizio 3.9.2 del file EserciziLogicaCap3-2.pdf).

19. Lunedì 1 Novembre: lezione annullata per Festività Ognissanti

20. Mercoledì 3/11: Prima dimostrazione del teorema di eliminazione del taglio applicando la procedura Tglob ottenuta componendo opportunamente tra loro i passi elementari di riduzione e distinguendo i passi logici dai passi strutturali. Lemma di reversibilità. Seconda dimostrazione del teorema di eliminazione del taglio applicando la procedura Trev, ottenuta sfruttando il lemma di reversibilità. Discussione ed esempi. Riferimenti: Capitolo 4, pagg. 125 - 133 del libro Logica. Vol. 1. 

21. Venerdì 5/11: Esercitazione  sulla eliminazione dei tagli senza quantificaori (Esercizio 4.1 del file EserciziLogicaCap4.pdf) ed in presenza di quantificatori (il teorema dell'ubriaco1 ed esempio_1). Esercitazione sulla derivabilità di sequenti del primo ordine in LK in presenza di quantificatori (Esercizio 3.12 del file EserciziLogicaCap3-2.pdf).

Giovedì 11 Novembre 2021, ore 16-19: Primo esonero

MODULO B (Tortora de Falco)

22. 15/11/21: Dimostrazione completa del teorema di compattezza per i linguaggi di cardinalità qualsiasi con la tecnica dei testimoni di Henkin (sfruttando l’assioma di scelta).

23. 17/11/ 21, ore 16-19: correzione esercizi dell'esonero (Maieli - Tortora de Falco)

24. 19/11/21: ore, 12-14. Estensione del teorema di compattezza alle strutture egualitarie. Estensione del teorema di completezza forte alle strutture egualitarie (in presenza degli assiomi dell’uguaglianza). Estensione del teorema di Lowenheim-Skolem per i linguaggi numerabili alle strutture egualitarie.

25. 22/11/20:  ore, 16-19. Qualche conseguenza del teorema di compattezza: limiti espressivi della logica del primo ordine. Esempi ed esercizi.

26. 24/11/21: ore, 16-19. Nozione di isomorfismo tra strutture per un linguaggio del primo ordine. Equivalenza elementare. Nozione di sottostruttura e di sottostruttura elementare. Esempi. Il teorema di Tarski-Vaught.

27. 26/11/21:  ore, 12-14. ll metodo dei diagrammi in teoria dei modelli: presentazione del metodo. Esercizi sulle applicazioni del teorema di compattezza: la connessione non è une proprietà del primo ordine, compattezza ed assioma di scelta nel caso dei linguaggi di cardinalità più che numerabile.

28. 29/11/21:  ore, 16-19. Teorema dell’unione di catene di Tarski. Applicazione del metodo dei diagrammi in teoria dei modelli: i teoremi di preservazione. Dimostrazione del primo teorema di preservazione: una teoria è equivalente ad una teoria universale se e soltanto se è preservata per sottostrutture. Esercizi sul teorema di compattezza: dal teorema di Tychonoff discende il teorema di compattezza per la logica preposizionale.

29. 1/12/21.  ore, 16-19. Applicazione del metodo dei diagrammi in teoria dei modelli. Il teorema di preservazione per le teorie per ogni-esiste: una teoria è equivalente ad una teoria per ogni-esiste se e soltanto se è preservata per unione di catene. Esempi di applicazione dei teoremi di preservazione.

30. Venerdì 3 Dicembre 2021, ore 12-14: (Esercitazione sul Modulo A - Maieli). Commenti alla procedura di eliminazione del taglio per LK: proprietà di weak-normalization, strong normalization e confluenza.

31. 10/12/21 ore, 12-14: Esercizi sulla teoria dei modelli: compattezza, equivalenza elementare.

32. 13/12/21 ore, 16-19: Generalizzazione del teorema di Lowenheim-Skolem discendente per i linguaggi di cardinalità qualsiasi: enunciato e dimostrazione completa (sfruttando l’assioma di scelta). Completezza di una teoria e k-categoricità di una teoria. Teorema del test di Vaught.

33. 15/12/21 ore 16-19: Alef0-categoricità della teoria degli ordini lineari densi e senza estremi (OLDSE) e conseguente completezza di OLDSE. Esercizi sulla teoria dei modelli: equivalenza elementare ed isomorfismo, completezza.