PROGRAMMA COMMENTATO
(continua)

LOGICA MATEMATICA (AA 2015-16)

Paolo Lipparini

Ricordo che questi commenti, e i riferimenti ai libri di Mendelson [M] e 
Chang Keisler [CK] fanno parte del programma (esclusi gli esercizi, di 
solito); gli altri riferimenti non fanno parte del programma, a meno che 
non sia esplicitamente indicato altrimenti.


(13 ott)

Il calcolo proposizionale: connettivi, tavole di verita', tautologie [M, 
sezioni 1.1 e 1.2]. Notazione "polacca" [M, 1.2, esercizio 3], piu' dettagli in
 https://en.wikipedia.org/w/index.php?title=Polish_notation&oldid=678489618

La maggior parte del materiale si trova anche in 
[CK, sezione 1.2], anche se presentata in maniera leggermente differente.


(14 ott)

 Forme normali congiuntive [M, esercizio 7 in 1.2 ed esercizi 2 e 3 in 
1.3].
 Insiemi adeguati di connettivi [M, 1.3; facoltativa la Prop. 1.6]. 
Formalizzazione del calcolo proposizionale: simboli, formule ben formate 
[M, 1.4, per ora in parte].


(15 ott)

Dimostrazioni in sistemi formali; teoremi, teorie.  Se una formula e' 
conseguenza di una teoria, e' conseguenza di una sottoteoria finita.
 Assiomi e regola di deduzione per il calcolo delle proposizioni
(ancora [M, 1.4]).


(facoltativo) Cenni alla nozione di indecidibilta'; esempi di problemi 
indecidibili: risolubilita' di equazioni diofantee, il problema della 
parola per gruppi.
 http://www.treccani.it/enciclopedia/teoremi-di-indecidibilita_%28Enciclopedia_della_Scienza_e_della_Tecnica%29/

Approfondimenti:
 M. Davis, Undecidable problems, in Barwise (ed.), Handbook of 
Mathematical logic
 J. Rotman, An introduction to the theory of groups, 1994.


(20 ott)


- Sistemi formali e "verita'" (osservazione).

 Naturalmente (come ripetuto fino allo sfinimento) chi interpreti gli 
assiomi di un sistema formale come corrispondenti ad affermazioni 
"vere", e inoltre assuma che le regole di deduzione siano "valide", 
cioe' facciano passare da affermazioni "vere" ad affermazioni "vere", 
deve necessariamente ammettere che ogni teorema e' "vero".
 Mentre questa idea e' una fra le motivazioni principali per 
l'introduzione dei sistemi formali, bisogna pero' osservare che la 
nozione di "verita'" non entra affatto nella definizione di sistema 
formale.

 (A scanso di equivoci, spesso assoceremo una "semantica" - in un certo 
senso, un'interpretazione - ad un sistema formale. In questo caso avra' 
senso parlare di "verita'", per lo meno, di "verita'" o 
soddisfacibilita' di una formula in un dato modello. Solitamente, 
comunque, la "semantica" non viene considerata parte di un sistema 
formale, anche se, naturalmente, si tratta semplicemente una 
convenzione. Il fattore fondamentale e' che, quasi sempre, la 
"semantica" deve essere trattata usando una metateoria molto piu' ampia, 
quindi la semantica non puo' avere la stessa valenza fondazionale degli 
aspetti "sintattici" dei sitemi formali.)

 In riferimanto al fatto che la nozione di "verita'" non entra nella 
definizione esplicita di sistema formale, citiamo una frase di Hilbert, 
probabilmente scritta all'acme del suo periodo formalista: "Mathematics 
is a game played according to certain simple rules with meaningless 
marks on paper."

 Per chiarire con un esempio che un sistema formale non parla 
necessariamente di "verita'", possiamo osservare che, modificando 
opportunamente l'interpretazione dei simboli del calcolo delle 
proposizioni, tutti gli assiomi e i teoremi diventerebbero 
antitautologie, cioe', negazioni di tautologie, affermazioni sempre 
"false".
 Come altri esempi, notiamo che molti giochi, o anche un programma per 
computer possono essere considerati come sistemi formali. Ad esempio, 
facciamo vedere che gli scacchi possono essere visti come un sistema 
formale.

- Esempio: gli scacchi considerati come sistema formale.

 Consideriamo il seguente insieme di simboli: 0 (intuitivamente indica 
che una casella non e' occupata da nessun pezzo), A, C, T... (una 
lettera per ogni pezzo del bianco), A', C', T'... (una lettera per ogni 
pezzo del nero), i simboli B, N (da interpretare, rispettivamente nel 
senso che la mossa spetta al bianco o al nero).
 Una formula ben formata e' una sequenza di 65 simboli, tale che B o N 
compaiono solo alla 65a posizione, e uno di essi compare in tale 
posizione. Numerando le caselle della scacchiera da 1 a 64, ogni formula 
rappresenta una disposizione dei pezzi della scacchiera, e l'ultima 
lettera ci dice a chi spetta la mossa.
 L'unico assioma e' la descrizione in tal senso della posizione iniziale 
di una partita degli scacchi:
 TP0000P'T'CP0...0P'T'B
 La regola di deduzione e' costituita da quelle coppie di formule che 
rappresentano le possibili mosse consentite nel gioco (cioe', la prima 
componente e' una posizione sulla scacchiera, e la seconda componente e' 
la posizione successiva dopo la mossa di un giocatore).
 Ad esempio, la coppia 
 (T0...B, 0T...N)
 dove i simboli indicati dai puntini non vengono modificati, appartiene 
(generalmente) alla regola. Descrivere esplicitamente quali coppie stanno 
nella regola di deduzione risulta alquanto laborioso, ma in linea di 
principio e' possibile farlo. (Notiamo che la  mossa descritta dalla 
precedente coppia e' ammessa solo qualora il bianco non abbia il re sotto 
scacco.)

 Cosa sono i teoremi in questo sistema formale?

 Cosa sono i teoremi, se modifichiamo l'assioma, o ne aggiungiamo altri?

 NB.: Ad essere precisi, alcune regole degli scacchi non possono essere 
descritte nel modo precedente. Ad esempio, un giocatore non puo' 
arroccare se aveva precedentemente mosso uno dei pezzi coinvolti 
nell'arrocco, riportandolo poi nella posizione originaria. Quindi, dalla 
semplice posizione dei pezzi non si puo' sapere se un arrocco e' 
possibile o meno (questo inconveniente si potrebbe comunque "aggiustare" 
aggiungendo un 66-emo posto in cui si descrivono le possibilita' di arrocco 
dei giocatori).
  Inoltre, secondo le piu' recenti regole per i tornei, se una stessa 
posizione si ripete sulla scacchiera per 5 volte, con le stesse 
possibilita' di mossa, la partita si conclude e viene dichiarata patta 
(indipendentemente dalla volonta' dei giocatori 
http://www.fide.com/fide/handbook.html?id=171&view=article vedi 9.6a). 
Quindi un sistema formale piu' opportuno per gli scacchi e' quello che 
contiene come formule la descrizione dello svolgimento di tutta la 
partita (fino ad un certo momento), nella notazione ormai standard, vedi 
"Algebraic notation" nel documento citato.
 (Quale sarebbe l'assioma, in questo senso?)
 Abbiamo preferito dare l'esempio precedente perche' da' la possibilita' di 
cambiare la posizione iniziale sulla scacchiera, come in certe versioni 
"eterodosse" (vedi Appendix F. Chess960 Rules nel documento citato).
 (Naturalmente, nel sistema formale non c'e' bisogno di indicare la vittoria 
o meno di uno dei due giocatori, visto che questa puo' essere dedotta 
univocamente dalla posizione dei pezzi)


- Esempio di dimostrazione nel Calcolo delle Proposizioni; il teorema di 
deduzione. Teoremi di completezza e adeguatezza (senza dimostrazione). 
[M, 1.4 fino a Proposizione 1.8; inoltre, Proposizione 1.11; inoltre 
Proposizione 1.13 senza dimostrazione]

- Brevissimi cenni alle logiche intuizioniste, a piu' valori, modali 
(facoltativo).

- Cenni alla distinzione fra ricorsivo e ricorsivamente enumerabile. In 
modo leggermente informale, un insieme e' ricorsivo se esiste un 
algoritmo per decidere effettivamente se qualcosa vi appartiene oppure 
no; e' ricorsivamente enumerabile se esiste una procedura effettiva per 
elencare tutti i suoi elementi. L'insieme dei teoremi di un sistema 
formale assiomatizzabile e' ricorsivamente enumerabile. Ma puo' non 
essere ricorsivo (facoltativo). Ad esempio, sotto certe ipotesi, ogni 
teoria T non contraddittoria puo' essere estesa ad una teoria T' 
completa e non contraddittoria. Basta elencare le formule del linguaggio 
e costruire per induzione una teoria T(n) in modo che T(n+1) e' ottenuta 
da T(n) aggiungendo la formula fn se e solo se la negazione di fn non e' 
dimostrabile in T(n). T' e' l'unione di tutte le T(n). Se l'insieme dei 
teoremi di T fosse ricorsivo, la procedura per ottenere T' si potrebbe 
rendere in maniera effettiva, ma questo contraddice il teorema di 
incompletezza di Godel.
 (esiste comunque una dimostrazione tecnica ma piu' diretta che 
l'insieme dei teoremi puo' non essere ricorsivo; i dettagli si trovano, 
ad esempio, sul Mendelson dopo i teoremi di incompletezza di Godel)


(21 ott)

Brevi cenni alla dimostrazione di Gentzen di non contraddittorieta' 
dell'aritmetica. Brevi cenni sulla "Reverse Mathematics" (facoltativi).

Da adesso in poi entriamo nel "Paradiso di Cantor", cioe' supporremo di 
lavorare in una teoria abbastanza ampia in cui si possa tranquillamente 
parlare di tutta la matematica (ad esempio, una teoria opportuna degli 
insiemi, formalizzata, ad esempio, nel calcolo dei predicati. Del 
calcolo dei predicati parleremo in seguito). Per chi fosse scettico, si 
puo' sempre considerare questa teoria come un sistema formale, e tutte 
le dimostrazioni che daremo si possono interpretare in linea di 
principio come dimostrazioni all'interno di questo sistema formale 
(anche se e' discusso il reale significato della precedente espressione 
"in linea di principio").
 Per i teoremi di Godel (almeno secondo l'interpretazione che va per la 
maggiore) non potremo mai dimostrare la non contraddittorieta' di questo 
sistema. Questo sistema e' comunque molto piu' forte di quanto realmente 
necessita; quand'anche risultasse contraddittorio, potremmo sempre 
lavorare in un sistema piu' debole, anche se alcuni dettagli 
risulterebbero molto piu' laboriosi.
 (E, anche se il sistema risultasse contraddittorio, possiamo sempre 
vedere il lato positivo della situazione: dimostrandone la 
contraddittorieta' avremmo trovato la soluzione di un'equazione 
diofantea che ci aspettavamo fosse non risolubile!)
 Approfondimento: F. Brown, L'angelico lombrico (The Angelic Angleworm), 
1943.

 Definizione di modello [CK, parte della Sez. 1.3].


(22 ott)

- Brevissimi cenni alla storia della logica in Italia. Peano. 
 Approfondimento: Piergiorgio Odifreddi su Giuseppe Peano (sostituite la 
parte finale dell'indirizzo con /stud/pean.rtf)
 Ad alcuni anni dalla morte di Peano era burocraticamente impossibile 
tenere un corso di Logica in Italia (sia a filosofia che a matematica, 
Figa' Talamanca, Notiziario dell'Unione Matematica Italiana [riferimento 
da inserire]).
 La rinascita della logica in Italia; il gruppo di ricerca fondato da 
Geymonat. Approfondimenti: Corrado Mangione: Ludovico Geymonat e la 
rinascita della logica italiana, in Storie e protagonisti della 
matematica italiana, Springer-Verlag Italia, 2013.
 http://www.springer.com/mathematics/applications/book/978-88-470-2777-0
 https://it.wikipedia.org/wiki/Piero_Mangani
 Roberto Magari. Vedi: https://it.wikipedia.org/wiki/Roberto_Magari

- Linguaggio, segnatura, interpretazioni [CK, inizio della Sez. 1.3] 
(oppure, ma non sempre con la stessa terminologia [M, sezioni 2.1 e 
2.2]). Omomorfismi fra modelli [CK, fine di 2.1].

- Cenni all'uso del teorema di compattezza per dimostrare l'esistenza di 
modelli non standard della teoria (completa) dei numeri naturali (in 
qualunque linguaggio). L'esempio e' simile a [CK, Corollario 2.1.11]; 
ulteriori dettagli nelle prossime lezioni.


(27 ott)

Ridotti di un modello, espansioni, sottomodelli; termini, formule di un 
linguaggio del primo ordine [CK, 1.3]


(28 ott)

Variabili libere e vincolate. Soddisfacibilita' di una formula 
(relativamente all'assegnazione di valori alle variabili). Nel caso di 
un enunciato (formula senza variabili libere) la soddisfacibilita' e' 
indipendente dall'assegnazione. Cenni all'assiomatizzazione del calcolo 
dei predicati. Corrispondenza esatta fra nozioni sintattiche e 
semantiche (teoremi di completezza, senza dimostrazione). Teorema di 
compattezza (dimostrazione assumendo il Teorema di completezza 
generalizzato). [CK, tutta la sezione 1.3, esclusa la parte da Prop. 
1.3.4 a Prop. 1.3.11, esclusa la Prop 1.3.18 e senza la dimostrazione di 
Prop. 1.3.16]


(29 ott)

Corollari del teorema di compattezza: una teoria che ha modelli finiti 
di cardinalita' arbitrariamente alta ha un modello infinito [CK, 
Corollario 2.1.5]. Una teoria che ha modelli infiniti ha modelli di 
cardinalita' arbitrariamente alta [CK, parte di Cor. 2.1.6]. 
 Espressivita' delle teorie del primo ordine: esiste un enunciato (nel 
linguaggio con solo = ) che equivale all'esistenza di almeno n elementi 
distinti; quindi, nello stesso linguaggio, esiste una *teoria* che ha 
per modelli esattamente i modelli infiniti. Ma non esiste un *enunciato* 
che ha per modelli esattamente i modelli infiniti (se esistesse, si 
consideri la sua negazione e si applichi il primo corollario). Esempio 
di enunciato che ha solo modelli infiniti (esempio: un enunciato che 
descrive gli insiemi linearmente ordinati senza massimo).


(3 nov)

Se T e' una teoria in un linguaggio che contiene il linguaggio della 
teoria dei gruppi e T ha modelli con elementi di periodo (= ordine) 
finito arbitrariamente alto, allora T ha un modello con un elemento di 
periodo infinito (aggiungete una nuova costante g al linguaggio, sia T' 
= T U { g^n diverso da e | n in N}; per l'ipotesi, ogni sottoinsieme 
finito di T' ha un modello; per compattezza, T' ha un modello...).
 In particolare, tutti e soli i gruppi i cui elementi hanno tutti 
periodo finito non possono essere caratterizzati mediante una teoria del 
primo ordine.
 Teorie equivalenti. Modelli elementarmente equivalenti. Teoria di un 
modello.
 Esistono modelli non standard della teoria di N (i naturali, con somma, 
prodotto, successore, eventualmente, anche in una qualunque espansione 
del linguaggio). In particolare, esistono mdelli non standard 
dell'Aritmetica di Peano. [CK, Esempio 1.4.11].
 Completamento (espansione completa) di un modello. Esistono modelli non 
archimedei della teoria di R#.


(4 nov)

Un modello finito in un linguaggio finito e' caratterizzato a meno di 
isomorfismi da un enunciato del primo ordine (facoltativo). Assiomi di Peano; 
Aritmetica di Peano (al primo ordine). Confronto.
 Inizio dello studio di *R, dove *R e' un modello del completamento 
(espansione completa) R# dell'insieme dei numeri reali. *R ha un 
sottomodello isomorfo ad R#, quindi non si perde in generalita', se si 
suppone R sottoinsieme di *R. Si suppone che *R sia un'estensione 
propria di R#. Elementi finiti ed infiniti di *R; infinitesimi. 
[materiale distribuito a lezione]


(5 nov)

- Alcuni assiomi della teoria di Zermelo Fraenkel: estensionalita', 
separazione, coppia, potenza, unione. Concezione iterativa degli insiemi 
(gerarchia cumulativa di Von Neumann), rango di un insieme. Assioma di 
regolarita' (e' intuitivamente vero nell'universo di Von Neumann). [A. 
Andretta, I teoremi di assolutezza in teoria degli insiemi: prima parte, 
BUMI Serie 8, vol. 6-A (2003), Sez. 2 fino a pag. 65, fa parte del 
programma https://eudml.org/doc/262079  ].
 Approfondimenti:
 T. Jech, Set Theory
 M. Foreman, A. Kanamori (a cura di), Handbook of Set Theory
 www.dma.unina.it/~cantor/dispenseANDRETTA.pdf
 campus.unibo.it/74334/1/Insiemi.pdf

- Se un'assiomatizzazione di una teoria degli insiemi ha un modello, 
allora ha un modello M con una carena discendente di elementi tali che 
ogni elemento appartiene al precedente: ... cn+1 in cn in cn-1 ... in c2 
in c1 in c0 (considerare un linguaggio in cui le ci sono aggiunte come 
nuove costanti, e usare il teorema di compattezza).
 Questo puo' apparire paradossale, poiche' l'assioma di regolarita' 
implica che non esiste una tale catena. Il paradosso e' solo apparente, 
la catena discendente non esiste in M, ma puo' essere "vista" solo dall' 
"esterno". Piu' esattamente, per formalizzare un enunciato che afferma 
l'esistenza di tale catena, bisogna parlare di una funzione f da N verso 
un insieme che contiene c0, c1, c2... Questa funzione non esiste in M, 
anche se, col teorema di compattezza se ne dimostra l'esistenza (in un 
ambiente diverso).