PROGRAMMA COMMENTATO
LOGICA MATEMATICA 1 (AA 2018-19)
Paolo Lipparini
Per la prima parte del programma si fa riferimento al seguente testo:
[M] Elliott Mendelson, Introduzione alla logica matematica.
(qualunque edizione in qualunque lingua. I numeri di pagina si riferiscono
all'edizione italiana reperibile in biblioteca).
Non e' necessario comunque l'acquisto. Se volete potete usare altri testi,
magari fatemeli vedere...
(3 ott)
- Sistemi assiomatici
https://www.mat.uniroma2.it/~lipparin/stud/AA1516/sh.pdf
("sistemi assiomatici" da Shoenfield, Logica matematica; fa parte del programma)
- Cenni ai sistemi formali (talvolta chiamati "teorie formali", o
"formalismi") [M, Capitolo 1, inizio della sezione 4].
(4 ott)
(3 ore)
Logica proposizionale classica. Connettivi, tavole di verita', tautologie.
Notazione "polacca" [M, Esercizio 3 a p. 33]. L'insieme dei connettivi
costituito da "e", "o", "non" e' adeguato a generare tutte le funzioni di
verita'. (facoltativo: sono sufficienti anche solo "non" ed "e";
simmetricamente, anche solo "non" ed "o") [M, Capitolo 1 fino a
Proposizione 1.4 inclusa; esclusi gli esercizi].
(5 ott)
Sistemi formali. Formule ben formate. (facoltativo: natura ricorsiva della
definizione di formula ben formata, ad esempio, nel caso del calcolo delle
proposizioni.) Dimostrazioni e teoremi all'interno di un sistema formale
[M, p. 42-43]. (facoltativo: Cenni al programma di Hilbert.
https://www.mat.uniroma2.it/~lipparin/stud/AA1516/il.pdf )
(10 ott)
Il calcolo delle proposizioni come sistema formale CP. Esempio di
dimostrazione (all'interno di CP). Metodo "numerico" per decidere se una
successione finita di simboli di CP e' una formula ben formata in notazione
polacca [M, Esercizio 3 a p. 33]. Teorema di adeguatezza: ogni teorema di
CP e' una tautologia. Teorema di completezza (senza dimostrazione).
(11 ott)
Forme normali congiuntive e disgiuntive, loro uso per decidere se una
proposizione e' una tautologia. (facoltativo: cenni al problema P=NP,
problemi NP completi e collegamenti con la logica proposizionale.)
(12 ott)
Relazione di conseguenza in un sistema formale. Teorema di deduzione per
il calcolo delle proposizioni.
[La parte di programma svolta finora consiste della sezione citata dal
libro di Shoenfield, piu' le seguenti parti del libro di Mendelson:
Capitolo I, tutto fino alla Proposizione 1.8 inclusa, ma esclusa la
Proposizione 1.6. Inoltre incluse la Proposizione 1.11 con dimostrazione e
la Proposizione 1.13 senza dimostrazione. Inclusi inoltre gli esercizi 3 e
7 a p. 33, gli esercizi 2 e 3 a p. 40-41, esclusi tutti gli altri
esercizi.]
Calcolo dei predicati: introduzione; simboli, termini.
(17 Ott)
(3 ore)
Calcolo dei predicati: formule atomiche, formule ben formate; occorrenze
libere e vincolate di una variabile; enunciati. Soddisfacibilita': modelli
(o interpretazioni); soddisfacilbilita' di una formula in un modello
(relativamente ad una successione che assegna ad ogni variabile un elemento
dell'insieme di base del modello).
(18 ott)
La soddisfacilbilita' di una formula in un modello relativamente ad una
successione dipende solo dall'assegnazione delle variabili libere nella
formula (dimostrazione facoltativa). In particolare, la soddisfacibilita'
di un encunciato non dipende dalla successione.
Assiomi logici e regole di inferenza per il calcolo dei predicati.
Teorie, relazione di conseguenza. Esempi.
Teorie con uguaglianza [note].
(19 ott)
Teorema di completezza e teorema di completezza generalizzato (senza
dimostrazione). Conseguenze: una teoria del primo ordine e' non
contradditoria se e solo se ha un modello. Teorema di compattezza: una
teoria ha un modello se e solo se ogni suo sottoinsieme finito ha un
modello. Applicazione: esistono modelli non standard della teoria T
costituita da tutti gli enunciati validi in (N,+,x,',0, =).[Note
distribuite a lezione]
(24 ott)
Esistenza di un modello non archimedeo della teoria completa dei numeri
reali. Se una teoria ha modelli finiti di cardinalita' arbitrariamente
alta, allora ha un modello infinito. Limitazioni all'espressivita' del
calcolo dei predicati del primo ordine. Un modello finito in un linguaggio
finito e' caratterizzabile a meno di isomorfismi da un enunciato del primo
ordine. Cenni a teoremi e sviluppi ulteriori della teoria dei modelli.
(tutti argomenti facoltativi)
(25 ott)
Esempi di teorie categoriche in qualche cardinalita' (cioe' che hanno solo
un modello in quella cardinalita'; qui consideriamo sempre teorie con
uguaglianza): teoria con la sola uguaglianza; teoria di una relazione di
equivalena con infinite classi tutte infinite; teoria dei campi
algebricamente chiusi.
Teorema di interpolazione di Craig (senza dimostrazione. Scriviamo phi |=
psi se ogni modello che soddisfa ad un enunciato phi soddisfa
all'encunciato psi. Il teorema afferma che se phi |= psi, allora esiste un
enunciato theta che contiene solo i simboli comuni a phi e psi, e tale che
phi |= theta |= psi).
Caratterizzazione delle teorie universali (senza dimostrazione. Una
teoria e' universale se ha come assiomi un insieme di enunciati
universali, ovvero costruiti a partire da una formula senza quantificatori
aggiungendo solo quantificatori universali all'inizio. Il teorema afferma
che una teoria T e' equivalente ad una teoria universale se e solo se la
classe dei modelli di T e' chiusa per sottomodelli).
[La parte di programma svolta finora consiste degli argomenti indicati il
12 ottobre, inoltre: le sezioni 1-3 del Capitolo 2 del libro di Mendelson e
le note fornite a lezione sul teorema di completezza].
Nozione intuitiva di insieme. Formalizzazione della teoria degli insiemi
all'interno del calcolo dei predicati. Assioma di estensionalita'.[Per la
parte relativa alla teoria degli insiemi si possono consultare le note
scaricabili nella pagina web.]
(26 ott)
Assiomi che garantiscono la possibilita' di costruire insiemi: coppia,
potenza, infinito, unione, separazione. Coppie ordinate, prodotto di due
insiemi. Assioma di comprensione e paradosso di Russell. (facoltativo:
cenni alla teoria dei tipi di Russell e alla concezione iterativa di
insieme di von Neumann. Cenni agli assiomi di fondazione e di
rimpiazzamento.)
(7 nov)
Non esiste una funzione suriettiva da X su P(X). Paradosso del massimo
cardinale.
Cenni alla "reverse mathematics" (facoltativo).
Cenni all'evoluzione della logica matematica in Italia (approfondimento:
Piergiorgio Odifreddi su Giuseppe Peano: sostituite la parte finale
dell'indirizzo con /stud/pean.rtf )
Assioma di scelta.
(8 nov)
Forme equivalenti dell'assioma di scelta: (con dimostrazione) un prodotto
di una famiglia di insiemi non vuoti e' non vuoto; una funzione suriettiva
ha un'inversa da un lato. Senza dimostrazione: Principio di Tricotomia;
Principio del Buon Ordinamento. Cenni (facoltativi) a versioni deboli
dell'assioma di scelta e al Problema di Cantor della cardinalita'
dell'insieme dei numeri reali.
Un insieme e' bene ordinato se e solo se non esistono successioni
infinite strettamente decrescenti.
(9 nov) (3 ore)
Cenni al problema della "program termination". Esempi. 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. Esempio in cui non esiste una funione rango verso
N. [Note scaricabili dalla pagina web]
N definito come interseione di tutti gli insiemi induttivi. Assiomi di Peano.
N li soddisfa. Aritmetica di Peano (teoria al primo ordine [M, p. 128-129]).
Prodotto lessicografico. Il prodotto lessicografico di due buoni ordini
e' un buon ordine.
(14 nov)
Esempi di iterazioni trasfinite: iterazione del derivato (sottogruppo dei
commutatori) di un gruppo; iterazione della derivata di Cantor-Bendixson
(e relativo teorema, con cenni alla dimostrazione); iterazione
dell'operazione di potenza di un insieme (gerarchia di von Neumann).
Somma di due buoni ordini disgiunti. Somma e prodotto di ordini non sono
operazioni commutative.
(15 nov) (3 ore)
Segmenti iniziali. Un buon ordine non e' mai isomorfo ad un segmento iniziale
proprio. Teorema: due buoni ordini sono isomorfi oppure uno dei due e'
isomorfo ad un segmento iniziale dell'altro. Le tre possibilita' sono
mutualmente esclusive. Ordinali. Ogni buon ordine e' isomorfo ad un
ordinale (senza dimostrazione). Per ogni insieme di ordinali esiste un
ordinale piu' grande di tutti. Paradosso di Burali-Forti [M, p. 11].
(16 nov)
Ogni insieme non vuoto di buoni ordini (o di ordinali) ha un minimo
(intuitivamente, la classe di tutti gli ordinali e' bene ordinata). Esempi
di ordinali numerabili. Operazione di elevamento a potenza fra ordinali.
Cardinalita' di un insieme come ordinale minimo (assumendo l'assioma della
scelta) quindi esistenza di ordinali non numerabili.
Cenni alla vita e alle opere di Godel. Cenni agli assiomi di grandi
cardinali (facoltativo).
(21 nov)
Paradosso del mentitore. Paradosso di Berry [M, p. 10-12]. Problemi
relativi alla possibilita' di autoriferimento. Cenni al teorema di Tarski
sulla non definibilita' della nozione di soddisfacibilita'. Cenni ai
teoremi di incompletezza di Godel. Godeliano di un simbolo, di
un'espressione, di una sequenza di espressioni del calcolo dei predicati
[M, p. 167].
(22 nov)
Teorema di Tarski [note; una versione semplificata si puo' trovare nel libro di
Jech, Set Theory, 3rd millennium ed., p. 162]
Relazioni esprimibili e funzioni rappresentabili [M, p. 146-147].
(23 nov)
Reticoli come insiemi parzialmente ordinati e come strutture algebriche.
Equivalenza delle due definizioni [vedere, ad esempio, le note di G. Pareschi,
http://www.mat.uniroma2.it/~gealbis/EALreticoli.pdf
fino a Proposizione 2.2 inclusa].
(28 nov)
Funzioni ricorsive primitive. Regola del mu-operatore. Funzioni ricorsive
[M, p. 149-150]. Differenza fra il caso in cui le funzioni si suppongono
totali (definite ovunque) o parziali. Macchine di Turing [M. p. 277-280].
Tesi di Church (o di Church Turing) [M, p. 182].
Dettagli approfonditi su significato e varianti della Tesi di Curch-Turing
si possono trovare in
https://plato.stanford.edu/entries/church-turing
(29 nov)
Ogni funzione ricorsiva e' rappresentabile nell'Aritmetica di Peano (PA,
[M, Proposizione 3.23], cenni facoltativi alla dimostrazione). Omega
consistenza. Primo teorema di incompletezza di Godel [M, Sezione 3.5, fino
a Proposizione 3.31 e commenti seguenti].
(30 nov)
Secondo teorema di incompletezza di Godel. Cenni al dibattito sul
cosiddetto argomento di Lucas. Conseguenze dei teoremi di incompletezza
riguardo la realizzabilita' del Programma di Hilbert.
Per chi fosse interessato, un elenco di osservazioni sui teoremi di
incompletezza di Godel e possibili fraintendimenti si puo' trovare sulla
pagina a cura di Torkel Franzen:
http://www.math.mcgill.ca/rags/JAC/124/godel.html
Una discussione sull'argomento di Lucas con bibliografia si puo' trovare in
P. Pudlak, A note on applicability of the incompleteness theorem to
human mind, Annals of Pure and Applied Logic, 96 (1999), 335-342.
http://www.sciencedirect.com/science/article/pii/S016800729800044X?np=y
(5 dic)
Cenni (facoltativi) a problemi indecidibili: problema di decidere se una
funzione ricorsiva e' totale; problema dell'arresto di una macchina di
Turing; Teorema di Matijasevic; Teorema di Church; problema della parola
per gruppi e semigruppi (chi fosse interessato a maggiori dettagli puo'
consultare il libro di Rotman, An Introduction to the Theory of Groups,
Capitolo 12).
(6 dic)
(tutto facoltativo) Significato aritmetico della non contraddittorieta'
(o contraddittorieta') di teorie (ad esempio la teoria di
Zermelo-Fraenkel). Cenni alla dimostrazione di Gentzen della non
contraddittorieta' dell'Aritmetica di Peano. Ordinali associati ad una
teoria nel senso di teoria della dimostrazione. Cenni alla ricorsivita'
relativa e ai gradi di ricorsivita'.
(7 dic)
Gruppi e semigruppi liberi su un insieme finito di generatori.
Presentazioni. Il problema della parola. Morfismi fra semigruppi e
congruenze [note scaricabili dalla pagina web]. Cenni al caso di strutture
algebriche in generale.
(19 dic)
Gli argomenti svolti in quest'ultima settimana di lezione sono tutti
facoltativi.
Teoria combinatoria dei giochi (puo' essere studiata sul libro di Siegel,
Combinatorial Game Theory [S]).
Giochi finiti a due persone, a somma zero, senza elementi casuali e a
informazione perfetta.
Nim. Teorema di Bouton [S, p. 1-3]. Hackenbush [S, p. 6, 15-16].
(20 dic)
Strutture algebriche; sottostrutture, prodotti, morfismi, congruenze,
quozienti. Nell'insieme totalmente ordinato con 3 elementi con
l'operazione di max esistono due congruenze distinte con una classe in
comune.
(21 dic)
Teorema di Birkhoff (senza dimostrazione). Sottoalgebra di un'algebra
generata da un insieme finito di elementi. Esistenza di algebre libere in
classi chiuse rispetto a prodotti e sottostrutture. Questa parte di
programma si puo' studiare nelle note relative al corso del 2016-17.