PROGRAMMA DEFINITIVO 

LOGICA MATEMATICA 1 (AA 2018-19)

Paolo Lipparini


 Sistemi assiomatici. Sistemi formali. Formule ben formate. Notazione 
"polacca". Dimostrazioni e teoremi all'interno di un sistema formale. 
 Logica proposizionale. Connettivi, tavole di verita', tautologie. Teorema 
di adeguatezza. Teorema di completezza (senza dimostrazione). Teorema di 
deduzione.

 Calcolo dei predicati: termini, formule atomiche, formule ben formate; 
enunciati. Modelli (o interpretazioni); soddisfacilbilita'. Assiomi logici 
e regole di inferenza. Teorema di completezza (senza dimostrazione). 
Teorema di compattezza. Esistenza di modelli non standard.

 Insiemi. Nozione intuitiva. Assiomi: estensionalita', coppia, potenza, 
infinito, unione, separazione. Assioma di comprensione e paradosso di 
Russell. Assioma di scelta e alcune forme equivalenti.
 Buoni ordini. Prodotto lessicografico. Esempi di iterazioni trasfinite. 
Confrontabilita' di buoni ordini. Ordinali. Paradosso di Burali-Forti.  
 Cenni al problema della "program termination". Uso di una "funzione 
rango" (decrescente ad ogni passo del programma) verso un insieme bene 
ordinato per dimostrare che un programma termina dopo un numero finito di 
passi.

 Paradosso del mentitore. Paradosso di Berry. Aritmetica di Peano. 
Godeliani. Teorema di Tarski. Funzioni ricorsive. Macchine di Turing. Tesi 
di Church (o di Church Turing). Teoremi di incompletezza di Godel.
 Cenni (facoltativi) a problemi indecidibili. Il problema della parola per 
gruppi e semigruppi. Morfismi fra semigruppi e congruenze. Reticoli come 
insiemi parzialmente ordinati e come strutture algebriche. 


Il programma consiste del seguente materiale:

 Shoenfield,   https://www.mat.uniroma2.it/~lipparin/stud/AA1516/sh.pdf

 Elliott Mendelson, Introduzione alla logica matematica, pagine 10-15, 
23-33, 37, 42-46, 50, 60-75, 128-129, 146, 149-150, 167, 175-177, 277-280 
(I numeri di pagina si riferiscono all'edizione italiana reperibile in 
biblioteca).

 Le note sul teorema di completezza distribuite a lezione + le altre note 
scaricabili a https://www.mat.uniroma2.it/~lipparin/stud/AA1819/thins.pdf
(da completare)

 Le note di G. Pareschi, 
 http://www.mat.uniroma2.it/~gealbis/EALreticoli.pdf
 fino a Proposizione 2.2 inclusa.

 Per maggiori dettagli vedi 
 https://www.mat.uniroma2.it/~lipparin/stud/AA1819/progcomm.txt