PROGRAMMA DETTAGLIATO

LOGICA MATEMATICA (AA 2021-22)

Paolo Lipparini


(6 ott 2021) Presentazione del corso. Cenni informali su Teorema di 
Birkhoff, algebre libere, reticoli, algebre abeliane, trattazione 
algebrica del problema della soddisfacibilita' di vincoli.

(7 ott) Natura e limiti della logica matematica. Approfondimenti si 
possono trovare qui:

https://www.mat.uniroma2.it/~lipparin/stud/AA1516/progcomm1.txt

al giorno 29 settembre.

(8 ott) Definizione di algebra (= struttura algebrica) ed esempi.

(13 ott) Le costanti sono interpretabili come funzioni 0-arie. Distinzione 
fra simboli e loro interpretazione. Sottoalgebre, morfismi.

(14 ott) Esempi classici di strutture quoziente.

(15 ott) Congruenze. Le congruenze sono esattamente i nuclei (nel senso di 
relazione di equivalenza) dei morfismi. Esempi di sottoalgebre. L'insieme 
delle sottoalgebre di un'algebra (aggiungendo eventualmente il vuoto) e' 
un reticolo.

(20 ott) Reticoli completi. Gli insiemi delle sottoalgebre e delle congruenze 
di un'algebra sono reticoli completi. La composizione di due relazioni
binarie compatibili e' ancora compatibile.

(21 ott) Algebre e varieta' a congruenze permutabili. Teorema di Malcev (per
ora senza dimostrazione). Un reticolo di relazioni di equivalenza e' 
modulare. Descrizione del sup di due congruenze e di due relazioni di
equivalenza. 

(22 ott) Il matematico "ideale" secondo Davis e Hersh.

http://www.mat.uniroma2.it/~lipparin/stud/AA1112/dhmatid.pdf

Termini. Caratterizzazione della sottoalgebra generata da un sottoinsieme usando
i termini.

(28 ott) Caratterizzazione algebrica dei reticoli. Semireticoli.
Caratterizzazione dei reticoli distributivi mediante l'omissione di reticoli
(senza dimostrazione).

(29 ott) Caratterizzazione dei reticoli modulari mediante l'omissione
di M_3.
 Sottoalgebra di Frattini di un'algebra e sua caratterizzazione come
intersezione di tutte le sottoalgebre massimali proprie (argomento
facoltativo).

(3 nov) Unione di una catena di sottoalgebre una contenuta nell'altra e'
ancora una sottoalgebra. Sistemi di chiusura e reticolo completo associato.
Sistemi di chiusura algebrici.

(4 nov) Definizione equivalente di sistema di chiusura tramite un 
operatore di chiusura.

(5 nov) Reticoli con 0 e 1; reticoli complementati. Algebre di Boole. 
Loro rappresentazione (senza dimostrazione). Cenni alle algebre di chiusura.

(10 nov) Algebre libere. Esempi di algebre libere in varie classi.

(11 nov) Le identita' valide in una classe K sono quelle valide nell'algebra libera
in K, se esiste. Reticolo distributivo libero su un insieme di 3 elementi.
 La carattereizzazione della sottoalgebra di Frattini non vale necessariamente
per algebre con operazioni infinitarie (facoltativo).

(12 nov) Algebra di Boole libera su un insieme finito. Teorema di esistenza per algebre 
libere in una classe chiusa per prodotti e sottoalgebre.

(17 nov) Teorema di Malcev (caratterizzazione delle varieta' a congruenze permutabili).

(18 nov) Una varieta' e' a congruenze permutabili se e solo se ogni sottoalgebra di
F x F e' a congruenze permutabili, dove F e' l'algebra libera su 2 elementi.

(19 nov) Esempi di varieta' a congruenze permutabili. Teorema di Birkhoff.

(25 nov) Descrizione di tutti i termini di Malcev nella varieta' delle Algebre di Boole.
 Cenni alla Condizione sui Termini (Term Condition, TC). Un gruppo soddisfa a TC se e solo 
se e' abeliano. Lemma di Lampe.

(26 nov) Teorema di Pixley (caratterizzazione delle varieta' aritmetiche). Caratterizzazioni
delle varieta' con un termine-maggioranza. 

(1 dic) Le varieta' con un termine maggioranza sono a congruenze distribuitive.
  Recenti sviluppi sul "problema del continuo" (facoltativo, dettagli in Martin's Maximum++ 
 implies Woodin's axiom (*), David Aspero' and Ralf Schindler, Annals of Mathematics Vol. 
 193, No. 3 (May 2021), pp. 793-835).
 Cenni alla nozione di Eulerio di funzione.
 Cenni al modello cosmologico di Godel (facoltativo, dettagli nel volume delle Opere Complete).

(2 dic) Una varieta' e' a congruenze permutabili se e solo se ogni relazione
riflessiva e compatibile e' una congruenza.
 Un'algebra a congruenze 3-permutabili e' a congruenze modulari.
 Una varieta' con un termine di quasi unanimita' e' a congruenze distributive.

(3 dic) Caratterizzazione delle varieta' a congruenze distributive mediante i 
termini di Jonsson.

(9 dic) Le algebre di implicazione non hanno un termine quasi unanimita'.
 Teorema di Willard su TC: se M_3 e' uno 0-1-sottoreticolo del reticolo delle congruenze di
un'algebra, e due di queste congruenze 3-permutano, allora vale TC (facoltativo).

(10 dic) Le algebre di implicazione soddisfano alla Condizione di Jonsson per n=3.
 La varieta' di Baler soddisfa alla Condizione di Jonsson per n=4 ma non per n=3.
 Cenni ai termini di Jonsson diretti.

(15 dic) Cenni ad applicazioni dell'algebra universale a problemi di complessita' 
(facoltativo; ulteriori dettagli in Dmitriy Zhuk, A Proof of the CSP Dichotomy Conjecture, 
arXiv:1704.01914 e in L. Barto, A. Krokhin, R. Willard, Polymorphisms, and how to use them, 
in The constraint satisfaction problem: complexity and approximability, 1-44, Dagstuhl 
Follow-Ups, 7, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017).
 Termini di Taylor.

(17 dic) Cenni ad alcuni sviluppi recenti in algebra universale.

(22 dic) Cenni ad applicazioni dell'algebra universale. Alcuni riferimenti per chi fosse 
interessato a piu' dettagli:

https://cstheory.stackexchange.com/questions/10916/uses-of-algebraic-structures-in-theoretical-computer-science

http://www.liafa.univ-paris-diderot.fr/~jep/PDF/MPRI/MPRI.pdf
(J. E. Pin, Mathematical Foundations of Automata Theory)

G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott,
Continuous Lattices and Domains.

Cenni alla teoria della dualita' e alla logica algebrica.

Approfondimento: Johnstone, Peter T., Stone Spaces, 1982.

(23 dic) Cenni alle varieta' m-permutabili. Cenni all'esistenza di una condizione di Malcev 
idempotente minimale.
 Reticoli di relazioni di equivalenza permutabili soddisfano all'identita' arguesiana.

(12 gen 2022) Brevi cenni alle origini e alla storia della topologia 
(facoltativo). Dettagli introduttivi a

https://mathshistory.st-andrews.ac.uk/HistTopics/Topology_in_mathematics/